Google Foobar Challenge

You, • dev
Back

While searching the web for various pieces of information, my Chrome browser suddenly transformed into a game. I was thrown into a terminal with a bash prompt. Upon running the "ls" command, I received more information, which made it clear that I was to participate in a game designed to help space bunnies escape from the evil Commander Lambda's space station. Levels 1 and 2 were quite straightforward, but Level 3 requiered some more thought. I will briefly cover my solutions to each level below.

Foobar challenge

After finishing the first level, I looked into what the Foobar challenge was really about. It was started as a way to find people to hire. It's not clear if it's still used for that today, but getting an invite to join still felt pretty special. This secret way of looking for skilled people made it all feel more exciting and exclusive. The challenges got harder as I went on, which showed that they were designed to really test people, in case they are still using it to find candidates. I got more and more interested and kept going, not just to maybe get noticed but also because I enjoyed the challenge.

The rules of the game were straightforward: you could tackle the problems using either Java or Python, and external packages were off-limits. Additionally, as I was opting for Python, I had to conform to using version 2.7.

Once I felt confident in my solution, the next step was to verify the code against hidden tests. If the code passed this preliminary check, it could then be submitted for a real evaluation. A successful pass at this stage meant I could request a new challenge, moving forward in this intriguing game of logic and skill.

Let's walk through the first challenge, which was a simple warm-up exercise. The problem statement was as follows:

Level 1 - Solar Doomsday

==============

Who would've guessed? Doomsday devices take a LOT of power. Commander Lambda wants to supplement the LAMBCHOP's quantum antimatter reactor core with solar arrays, and you've been tasked with setting up the solar panels.

Due to the nature of the space station's outer paneling, all of its solar panels must be squares. Fortunately, you have one very large and flat area of solar material, a pair of industrial-strength scissors, and enough MegaCorp Solar Tape(TM) to piece together any excess panel material into more squares. For example, if you had a total area of 12 square yards of solar material, you would be able to make one 3x3 square panel (with a total area of 9). That would leave 3 square yards, so you can turn those into three 1x1 square solar panels.

Write a function solution(area) that takes as its input a single unit of measure representing the total area of solar panels you have (between 1 and 1000000 inclusive) and returns a list of the areas of the largest squares you could make out of those panels, starting with the largest squares first. So, following the example above, solution(12) would return [9, 1, 1, 1].

My Solution

So the first thing I did was to write a function that would return the largest square that could be cut from a given area while the remaining area was still positive. This is the function I came up with:

def solution(area):

    squares = []
    while area > 0:
        # Find the largest square possible.
        largest_side = int(area**0.5)

        # Calculate the area of this largest square
        largest_square = largest_side**2

        squares.append(largest_square)
        area -= largest_square

    return squares

Notice that I don't use any protection against negative numbers. This is because the problem statement specifies that the input will always be a positive integer.

I could also have written a recursive function, but I opted for a while loop instead. I find that while loops are easier to read and understand.

Level 2 - Don't Get Volunteered!

Power Hungry

============

Commander Lambda's space station is HUGE. And huge space stations take a LOT of power. Huge space stations with doomsday devices take even more power. To help meet the station's power needs, Commander Lambda has installed solar panels on the station's outer surface. But the station sits in the middle of a quasar quantum flux field, which wreaks havoc on the solar panels. You and your team of henchmen have been assigned to repair the solar panels, but you'd rather not take down all of the panels at once if you can help it, since they do help power the space station and all!

My Solution

def solution(xs):
    # Separate the numbers into different categories
    positives = [x for x in xs if x > 0]
    negatives = [x for x in xs if x < 0]
    zeros = [x for x in xs if x == 0]

    # Calculate the product of all positive numbers
    product_positive = 1
    for p in positives:
        product_positive *= p

    negatives.sort()

    # Calculate the product of negative numbers (exclude the smallest if count is odd)
    product_negative = 1
    for n in negatives[:len(negatives) - len(negatives) % 2]:
        product_negative *= n

    # Special cases: if there's only one negative and no positives, consider zeros
    if len(negatives) == 1 and not positives:
        if zeros:
            return "0"
        return str(negatives[0])

    # If all are zeros and/or positives, return product of positives
    if not negatives:
        if not positives:
            return "0"  # all are zeros
        return str(product_positive)  # all are positives

    # If we reached here, we have both positives and negatives
    return str(product_positive * product_negative)

The key here is to separate the numbers into different categories. Then, I calculated the product of all positive numbers. Next, I sorted the negative numbers and calculated the product of all negative numbers, excluding the smallest if the count is odd. Finally, I handled the special cases.

Level 3 - Ion Flux Relabeling

===================

Oh no! Commander Lambda's latest experiment to improve the efficiency of the LAMBCHOP doomsday device has backfired spectacularly. The Commander had been improving the structure of the ion flux converter tree, but something went terribly wrong and the flux chains exploded. Some of the ion flux converters survived the explosion intact, but others had their position labels blasted off. Commander Lambda is having her henchmen rebuild the ion flux converter tree by hand, but you think you can do it much more quickly -- quickly enough, perhaps, to earn a promotion!

Flux chains require perfect binary trees, so Lambda's design arranged the ion flux converters to form one. To label them, Lambda performed a post-order traversal of the tree of converters and labeled each converter with the order of that converter in the traversal, starting at 1. For example, a tree of 7 converters would look like the following:

---7---

--3-6--

1-2-4-5

Write a function solution(h, q) - where h is the height of the perfect tree of converters and q is a list of positive integers representing different flux converters - which returns a list of integers p where each element in p is the label of the converter that sits on top of the respective converter in q, or -1 if there is no such converter. For example, solution(3, [1, 4, 7]) would return the converters above the converters at indexes 1, 4, and 7 in a perfect binary tree of height 3, which is [3, 6, -1].

The domain of the integer h is 1 < = h < = 30, where h = 1 represents a perfect binary tree containing only the root, h = 2 represents a perfect binary tree with the root and two leaf nodes, h = 3 represents a perfect binary tree with the root, two internal nodes and four leaf nodes (like the example above), and so forth. The lists q and p contain at least one but no more than 10000 distinct integers, all of which will be between 1 and 2^h-1, inclusive.

My Solution

def find_parent(h, num):
    # Total nodes in the tree of height h is 2^h - 1
    total_nodes = 2 ** h - 1
    
    # Current node starts with the root node which is also the maximum node.
    current_node = total_nodes

    # We'll keep track of the current height as we might move up and down the tree.
    current_height = h

    # If we're looking for the root, it has no parent, return -1
    if num == total_nodes:
        return -1

    while current_height > 0:
        # Each subtree has 2^(current_height-1) - 1 nodes
        subtree_nodes = 2 ** (current_height - 1) - 1

        # The maximum node number in the left subtree will be the current node number
        # minus the number of nodes in the right subtree (which is equal to subtree_nodes)
        # minus 1 for the current node itself.
        max_left_tree_node = current_node - subtree_nodes - 1

        # Check if the current node is the direct parent of the target node
        if num == current_node - 1 or num == max_left_tree_node:
            return current_node

        # If the number we're looking for is less than the maximum node in the left subtree,
        # it's somewhere in the left subtree. We'll move to the left subtree and continue.
        elif num < max_left_tree_node:
            current_node = max_left_tree_node
        # Otherwise, it's in the right subtree. We'll move to the right subtree and continue.
        # The maximum node in the right subtree is the current node - 1.
        else:
            current_node -= 1

        # Whether we moved left or right, we're now looking at a subtree, so we decrease the height.
        current_height -= 1

    # If we've gone through the whole tree and didn't return, something is wrong. The number wasn't in the tree.
    return -1  # This should never happen for a valid input.


def solution(h, q):
    # Initialize an empty list to hold the results.
    parents = []
    
    # For each converter in the list, find its parent using the find_parent function and add it to the results list.
    for converter in q:
        parent = find_parent(h, converter)
        parents.append(parent)
    
    # Return the list of parents as the final result.
    return parents

This problem requieres a bit of math. The first thing I did was to write a function that would find the parent of a given node in a perfect binary tree. I used the following logic:

Once I had this function in place, the rest was easy. I just had to call the function for each converter in the list and add the result to the final list.

Thanks for reading!

There were 2 more challenges for level 3, but I will not cover them here as they are quite complex and I don't want to spoil the fun for anyone who might want to try them.

Once I completed level 3 and submitted my solution, i was asked to provide some information about myself. I was also given the option to share my profile with recruiters. I'm not sure if this is still used to find candidates, but it was a fun experience nonetheless.

I hope you enjoyed this post.

© Magnus Friberg.RSS