I just got invited to perform Google’s FooBar challenge. In this article, I want to share with you how I solved the problems in real-time. The purpose of this article is to educate you—and to have some fun. So, are you ready?

## Level 1: Prime Numbers

The first goal was to find an identifier for a new employee at the “minions” company.

The identifier is selected base on a random number i. How do we come from the random integer `i`

to the identifier of the new minion employee?

- Create a sequence of prime numbers
`'23571113...'`

. - The identifier is the subsequence starting from index
`i`

and ending in index`i+4`

(included). - The value
`i`

is an integer between 0 and 10000.

Here’s the solution I implemented in the video:

def solution(i): # Determine prime sequence primes = getPrimeNumbers() return primes[i:i+5] def getPrimeNumbers(): '''Returns the string of prime numbers up to 10k+5 positions.''' s = '' prime = 2 while len(s) < 10005: # Add new prime to s s += str(prime) # Calculate next prime prime += 1 while not is_prime(prime): prime += 1 return s def is_prime(n): '''Tests if a number is prime. ''' for i in range(2,n): if n % i == 0: return False return True print(solution(0)) # 23571 print(solution(3)) # 71113

## Level 2 Challenge 1: Sequence Sum

Here’s the problem posed by Google:

Numbers Station Coded MessagesWhen you went undercover in Commander Lambda's organization, you set up a coded messaging system with Bunny Headquarters to allow them to send you important mission updates. Now that you're here and promoted to Henchman, you need to make sure you can receive those messages - but since you need to sneak them past Commander Lambda's spies, it won't be easy! Bunny HQ has secretly taken control of two of the galaxy's more obscure numbers stations, and will use them to broadcast lists of numbers. They've given you a numerical key, and their messages will be encrypted within the first sequence of numbers that adds up to that key within any given list of numbers.Given a non-empty list of positive integers l and atarget positive integer t, write a function solution(l,t) which verifies if there is at least one consecutivesequence of positive integers within the list l (i.e.a contiguous sub-list) that can be summed up to thegiven target positive integer t (the key) and returnsthe lexicographically smallest list containing thesmallest start and end indexes where this sequence canbe found, or returns the array [-1, -1] in the casethat there is no such sequence(to throw off Lambda's spies, not all number broadcasts will contain a coded message). For example, given the broadcast list l as [4, 3, 5, 7, 8] and the key t as 12, the function solution(l, t) would return the list [0, 2] because the list l contains the sub-list [4, 3, 5] starting at index 0 and ending at index 2, for which 4 + 3 + 5 = 12, even though there is a shorter sequence that happens later in the list (5 + 7). On the other hand, given the list l as [1, 2, 3, 4] and the key t as 15, the function solution(l, t) would return [-1, -1] because there is no sub-list of list l that can be summed up to the given target value t = 15. To help you identify the coded broadcasts, Bunny HQ has agreed to the following standards: - Each list l will contain at least 1 element but never more than 100. - Each element of l will be between 1 and 100. - t will be a positive integer, not exceeding 250. - The first element of the list l has index 0. - For the list returned by solution(l, t), the start index must be equal or smaller than the end index. Remember, to throw off Lambda's spies, Bunny HQ might include more than one contiguous sublist of a number broadcast that can be summed up to the key. You know that the message will always be hidden in the first sublist that sums up to the key, so solution(l, t) should only return that sublist.LanguagesTo provide a Python solution, edit solution.py To provide a Java solution, edit Solution.javaTest casesYour code should pass the following test cases. Note that it may also be run against hidden test cases not shown here.-- Python cases --Input: solution.solution([1, 2, 3, 4], 15) Output: -1,-1 Input: solution.solution([4, 3, 10, 2, 8], 12) Output: 2,3-- Java cases --Input: Solution.solution({1, 2, 3, 4}, 15) Output: -1,-1 Input: Solution.solution({4, 3, 10, 2, 8}, 12) Output: 2,3 Use verify [file] to test your solution and see how it does. When you are finished editing your code, use submit [file] to submit your answer. If your solution passes the test cases, it will be removed from your home folder.

Here’s the first code that I tried:

def solution(l, t): start = 0 while start < len(l): for stop in range(start, len(l)): s = sum(l[start:stop+1]) if s == t: return [start, stop] elif s > t: break start += 1 return [-1, -1]

The code solves the problem but it takes quadratic runtime so I though—can we do better? Yes, we can! There’s a linear runtime solution:

def solution(l, t): start = stop = 0 while start <= stop and stop < len(l): s = sum(l[start:stop+1]) if s == t: return [start, stop] elif s < t: stop += 1 else: start += 1 stop = max(start, stop) return [-1, -1]

Both solutions work—but the latter is much faster. Here’s the output and the test cases:

print(solution([250,0,0], 250)) print(solution([1,2,3,4], 15)) print(solution([4, 3, 10, 2, 8], 12)) print(solution([4, 3, 5, 7, 8], 12)) print(solution([260], 260)) ''' [0, 0] [-1, -1] [2, 3] [0, 2] [0, 0] '''

After submitting the solution in my browser shell, Google tells me that there is one more challenge to go to reach the next level:

## Level 2 Challenge 2: Digits and Remainder Classes

Here’s the problem posed by Google:

Please Pass the Coded MessagesYou need to pass a message to the bunny prisoners, but to avoid detection, the code you agreed to use is… obscure, to say the least. The bunnies are given food on standard-issue prison plates that are stamped with the numbers 0-9 for easier sorting, and you need to combine sets of plates to create the numbers in the code. The signal that a number is part of the code is that it is divisible by 3. You can do smaller numbers like 15 and 45 easily, but bigger numbers like 144 and 414 are a little trickier. Write a program to help yourself quickly create large numbers for use in the code, given a limited number of plates to work with. You have L, a list containing some digits (0 to 9). Write a function solution(L) which finds the largest number that can be made from some or all of these digits and is divisible by 3. If it is not possible to make such a number, return 0 as the solution. L will contain anywhere from 1 to 9 digits. The same digit may appear multiple times in the list, but each element in the list may only be used once.LanguagesTo provide a Java solution, edit Solution.java To provide a Python solution, edit solution.pyTest casesYour code should pass the following test cases. Note that it may also be run against hidden test cases not shown here.-- Java cases --Input: Solution.solution({3, 1, 4, 1}) Output: 4311 Input: Solution.solution({3, 1, 4, 1, 5, 9}) Output: 94311-- Python cases --Input: solution.solution([3, 1, 4, 1]) Output: 4311 Input: solution.solution([3, 1, 4, 1, 5, 9]) Output: 94311

I first went on developing a naive solution (no premature optimization)!

def solution(l): x = find_largest_bucket(l) return find_max_number(x) def find_largest_bucket(l): ''' Are the digits in the list divisible?''' if sum(int(digit) for digit in l)%3 == 0: return l ''' Find all smaller buckets recursively ''' buckets = [] for digit in l: if digit not in {0, 3, 6, 9}: tmp = l[:] tmp.remove(digit) buckets.append(find_largest_bucket(tmp)) largest_bucket = max(buckets, key=find_max_number) return largest_bucket def find_max_number(l): '''Returns maximal number that can be generated from list.''' sorted_list = sorted(l)[::-1] number = ''.join(str(x) for x in sorted_list) return int(number) print(solution([3, 1, 4, 1])) print(solution([1 for i in range(1000000)]))

While this code solves the problem, it’s not optimal. It can be painfully slow for large lists because of the many levels of recursion. So I went back and developed a new version based on remainder classes:

Here’s the code of the new idea:

def solution(l): # Don't modify existing list object bucket = l[:] # Remainder Class: state = sum(bucket)%3 while state > 0 and bucket: # Transition between remainder classes by removing numbers if state == 1: to_remove = set(bucket) & {1, 4, 7} if not to_remove: to_remove = set(bucket) & {2, 5, 8} elif state == 2: to_remove = set(bucket) & {2, 5, 8} if not to_remove: to_remove = set(bucket) & {1, 4, 7} # Remove min and move to new remainder class bucket.remove(min(to_remove)) state = sum(bucket) % 3 # Calculate maximal number from bucket sorted_list = sorted(bucket)[::-1] number = ''.join(str(x) for x in sorted_list) return int(number) if number else 0 print(solution([3, 1, 4, 1])) print(solution([3, 1, 4, 1, 5, 9])) print(solution([])) print(solution([9, 9, 9, 9]))

The output is correct. After submitting the solution, Google tells me that I managed to pass the level successfully! Hurray!

I even get to refer a friend…

Awesome! Commander Lambda was so impressed by your efforts that she's made you her personal assistant. You'll be helping her directly with her work, which means you'll have access to all of her files-including the ones on the LAMBCHOP doomsday device. This is the chance you've been waiting for. Can you use your new access to finally topple Commander Lambda's evil empire?

## Level 3 Challenge 1:

Here’s the next challenge:

foobar:~/prepare-the-bunnies-escape xcent.py$ cat readme.txt Prepare the Bunnies' Escape =========================== You're awfully close to destroying the LAMBCHOP doomsday device and freeing Commander Lambda's bunny prisoners, but once they're free of the prison blocks, the bunnies are going to need to escape Lambda's space station via the escape pods as quickly as possible. Unfortunately, the halls of the space station are a maze of corridors and dead ends that will be a deathtrap for the escaping bunnies. Fortunately, Commander Lambda has put you in charge of a remodeling project that will give you the opportunity to make things a little easier for the bunnies. Unfortunately (again), you can't just remove all obstacles between the bunnies and the escape pods - at most you can remove one wall per escape pod path, both to maintain structural integrity of the station and to avoid arousing Commander Lambda's suspicions. You have maps of parts of the space station, each starting at a prison exit and ending at the door to an escape pod. The map is represented as a matrix of 0s and 1s, where 0s are passable space and 1s are impassable walls. The door out of the prison is at the top left (0,0) and the door into an escape pod is at the bottom right (w-1,h-1). Write a function solution(map) that generates the length of the shortest path from the prison door to the escape pod, where you are allowed to remove one wall as part of your remodeling plans. The path length is the total number of nodes you pass through, counting both the entrance and exit nodes. The starting and ending positions are always passable (0). The map will always be solvable, though you may or may not need to remove a wall. The height and width of the map can be from 2 to 20. Moves can only be made in cardinal directions; no diagonal moves are allowed. Languages ========= To provide a Python solution, edit solution.py To provide a Java solution, edit Solution.java Test cases ========== Your code should pass the following test cases. Note that it may also be run against hidden test cases not shown here. -- Python cases -- Input: solution.solution([[0, 1, 1, 0], [0, 0, 0, 1], [1, 1, 0, 0], [1, 1, 1, 0]]) Output: 7 Input: solution.solution([[0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 0], [0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1], [0, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0]]) Output: 11 -- Java cases -- Input: Solution.solution({{0, 1, 1, 0}, {0, 0, 0, 1}, {1, 1, 0, 0}, {1, 1, 1, 0}}) Output: 7 Input: Solution.solution({{0, 0, 0, 0, 0, 0}, {1, 1, 1, 1, 1, 0}, {0, 0, 0, 0, 0, 0}, {0, 1, 1, 1, 1, 1}, {0, 1, 1, 1, 1, 1}, {0, 0, 0, 0, 0, 0}}) Output: 11 Use verify [file] to test your solution and see how it does. When you are finished editing your code, use submit [file] to submit your answer. If your solution passes the test cases, it will be removed from your home folder.

And my solution:

def solution(m): # Calculate map stats w, h = len(m[0]), len(m) # width and height # The current minimal solution s_min = 401 # Iterate over all possible inputs (by replacing 1s with 0s). for m_0 in all_maps(m): # Find the minimal path length s_min = min(min_path(m_0, w, h), s_min) # Optimization: Minimal solution? if s_min == w + h - 1: return s_min return s_min def min_path(m, w, h): '''Takes a map m and returns the minimal path from the start to the end node. Also pass width and height. ''' # Initialize dictionary of path lengths # integer: {(i,j), ...} (Set of nodes (i,j) with this integer path length) d = {1: {(0,0)}} # Expand "fringe" successively path_length = 2 while path_length < 401 and d[path_length-1]: # Fill fringe fringe = set() for x in d[path_length-1]: # Expand node x (all neighbors) and exclude already visited expand_x = {y for y in neighbors(x,m) if not any(y in visited for visited in d.values())} fringe = fringe | expand_x # Have we found min path of exit node? if (h-1, w-1) in fringe: return path_length # Store new fring of minimal-path nodes d[path_length] = fringe # Find nodes with next-higher path_length path_length += 1 return 401 # Infinite path length def neighbors(x, m): '''Returns a set of nodes (as tuples) that are neighbors of node x in m.''' i, j = x w, h = len(m[0]), len(m) candidates = {(i-1,j), (i+1,j), (i,j-1), (i,j+1)} neighbors = set() for y in candidates: i, j = y if i>=0 and i<h and j>=0 and j<w and m[i][j] == 0: neighbors.add(y) return neighbors def all_maps(m): '''Returns an iterator for memory efficiency over all maps that arise by replacing a '1' with a '0' value.''' # Unchanged map is a valid solution yield m for i in range(len(m)): for j in range(len(m[i])): if m[i][j]: # Copy the map copy = [[col for col in row] for row in m] # Replace 1 by 0 and yield new map copy[i][j] = 0 yield copy print(solution([[0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0]])) ''' print(solution([[0, 1, 1, 0], [0, 0, 0, 1], [1, 1, 0, 0], [1, 1, 1, 0]])) # 7 print(solution([[0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 0], [0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1], [0, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0]])) # 11 '''