Google Foobar: Level 2

I finally had time to start Level 2 of the Google Foobar Challenge. This level contains 2 challenges. 

The instructions for challenge 2A ("Lovely Lucky LAMBs") are as follows:

At first glance this seems like this is going to require coding in a bunch of rules — but once you extrapolate the patterns from the hints and test cases they give you, the actual code is a breeze to implement. 

The calculations for determining the max and min # of henchmen are going to have separate formulas, so you might want to break this out into two functions — at least initially, to make it a little easier to work with and test the min/max cases. So a template for the solution might look a little like this: 

def min_henchmen(total_lambs): 

   return count


def max_henchmen(total_lambs):

   return count


def solution(total_lambs):

   return max_henchmen(total_lambs) - min_henchmen(total_lambs)

Let’s address the logic for the ‘stingy’ cases first. When we’re stingy with the LAMB payouts, we’re giving the least amount of lambs to the most amount of henchmen — all the while keeping them all happy and content. As the included test cases states: if you were as stingy as possible with 10 LAMBs, you could pay 4 henchmen with 1, 1, 2, and then 3 LAMBs. This satisfies the requirements because:

- The first most junior henchman receives exactly 1 lamb - (1 lamb like above)

- The 2nd most junior henchman gets at least as many LAMBs as the most junior henchman (1 lamb)

- A henchman will revolt if the share of their next two subordinates combined is > their share (Well, we gave out 2 here which is at least 1+1, so we’re good)

Following this logic then, if we wanted to be as stingy with 12 lambs, we could compensate 5 henchmen: 1, 1, 2, 3,  and then 5 LAMBs.

And so on. Seeing a pattern here? The max # of henchmen that we can give lambs out to can be determined by the Fibonacci sequence. We can handout LAMBs to more henchmen until the sum of all the LAMBs are less than or equal to total_lambs.

Now we just need to work out our min_henchmen() function. The point this time is to be as generous as possible with our LAMB payouts. This means they’ll be fewer henchmen receiving LAMBs, and we’ll have to fulfill all the requirements just like before. 

So again let’s consider our first case. If we have 10 LAMBs in total, fulfill all the requirements to keep the henchmen happy, and be as generous as possible, we’d be able to pay just 3 henchmen: 1, 2, and 4 LAMBs, respectively. In this scenario, we wouldn’t be able to pay a fourth henchman with only 3 remaining lambs without causing a revolt. In order to pay 4 henchman, we would need at least 15 lambs. So the payouts would go like this: 1, 2, 4, 8, etc (respectively). In a nutshell, calculating the minimum amount of henchman (while maximizing the # of LAMBs each henchman receives) is be found by a basic geometrics series.

And then our solution function is easy - we simply return the difference by whatever was returned from the max_henchmen() function - min_henchmen().

This is my complete implementation in python:

I didn’t test the code extensively, but it passed all the test cases. 

On to the second challenge of level 2!

Google's Secret Foobar Challenge

The other day while googling around I came across this message: 

“Curious developers are known to seek interesting problems. Solve one from Google?” Sure, why not?  Upon accepting the challenge I was logged into foobar and presented with a greeting that told me I had managed to infiltrate “Commander Lambda’s” sinister organization.

I did some quick searching around to find other people who had encountered this, and what their experiences were with it. Turns out this has been around for quite some time —but can be quite elusive. Getting into foobar can be tricky, and there’s no guarantee you will. Luck is a major contributor to stumbling upon this, and it’s highly dependent on searching for the right programming related keyword(s). When you’re lucky enough to search for the right topic though, the page will slant a little and the banner with the foobar invite will appear at the top of Google like the one I got.

There are five levels in total. Each level contains a number of challenges. The amount of challenges increases per level along with complexity. There’s some randomness to the content prepared for each foobar invite: your level 1 might not be the same as someone else’s level 1, your level 2 may or may not be the same as someone else’s level 2 content, etc. Each challenge goes like this: you are presented with a puzzle, and you have to code up a solution that will solve that puzzle. Once you start a level, a timer starts counting down and you have until the timer ends to complete and submit a solution. You navigate through the foobar console using basic *nix like commands — if you have any experience with any of these the interface will be pretty intuitive for you. You have the choice of submitting a java or python solution for each challenge.

It seems that in its earlier days foobar was utilized as a secret hiring tool for Google to spot talented coders. It seems that it is no longer actively utilized for that purpose, however. Still, it's a fun exercise to try, and even if you don't end up getting a prize out of it, the challenges can help to sharpen your algorithmic thinking skills and get prepare you for any future coding tests and challenges you might face. 

As I get around to it, I'll post my code and walkthroughs for each level of the challenge.

Level 1: Prison Labor Dodgers

This was the first challenge I encountered and the premise of it was pretty simple:

Two lists are given to you, named ‘x’ and ‘y’, that might look like this:

x: [13, 5, 6, 2, 5], y: [5, 2, 5, 13]

Or this: x: [14, 27, 1, 4, 2, 50, 3, 1], y:[2, 4, -4, 3, 1, 1, 14, 27, 50]

In any case, the goal is to identify the unique id, or basically the number that is present in one of those lists but not the other. In the case of the two lists above, the solutions (unique IDs) would be 6, and -4, respectively.

One thing to keep in mind is that there won’t be any inherit ordering or sorting of the numbers in each list, so you can’t count on this in your solution if you intend on taking any shortcuts.

This is what I came up with for a quick & dirty solution:

def solution(x, y):

    first = x

    second = y

    if len(x) > len(y):

        second = x

        first = y

    exists = {}

    for ID in first:

        exists[ID] = True

    for ID in second:

        if ID not in exists.keys():

            return ID

First I make sure the lists are ordered and processed accordingly based on their size (larger list gets scanned first to ensure we look at all possible values). We then iterate through the second list, and check whether that number exists in our dictionary; if not then that’s our unique ID and we return that. 

I decided to roll my own implementation rather than use any of python’s features (you could, for instance, convert both lists to sets and then compute the symmetric difference of them). There are many ways you could go about this. Make sure to verify your code solution for each challenge prior to submitting it! This will indicate whether there are any test cases your code hasn’t passed — so you can go back and try to find what part isn’t working. If you wait to submit a solution only to find out it fails a couple cases, you will fail that challenge. I’ve only done 1 challenge so far and passed all the test cases… so I don’t even know yet what happens if you fail a level.

Another note: Google has test cases prepared in the background - but you don’t actually know what these are, so your solution actually has to work. Expect that google has thought of the various edge cases that could occur from your code, because they typically have, and have built those in to the tests.