Google Foobar’d Me!

Lately I’ve been reviewing my data structures, algorithms, and mathematics fundamentals. Last day I had been searching for a refresher on natural logarithms, when my search bar suddenly distorted into “Up for a challenge?”:

This was odd to me, so I first checked that I wasn’t typosquatted. The URL was correct. I figured Google was offering me a game to play. I’ve played other Google Doodles, they’re fun. Sure, why not, I’ll take a quick break to play.

I was presented with a UN*X style terminal interface. I typed in ls and found start_here.txt. Ok, let’s try cat start_here.txt. The content was “Type request to request a challenge”. This is a strange game, I thought. I was certainly intrigued though, so ok, I typed in request.

At this point I started to clue into what was going on. A new folder had been created, and in it was a coding problem:

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 she's tasked you 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 answer(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, answer(12) would return [9, 1, 1, 1].

Languages
=========

To provide a Python solution, edit solution.py
To provide a Java solution, edit solution.java

Test cases
==========

Inputs:
    (int) area = 12
Output:
    (int list) [9, 1, 1, 1]

Inputs:
    (int) area = 15324
Output:
    (int list) [15129, 169, 25, 1]

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.

I opened a new tab and started to use Google to explore what this Foobar game was all about. Oh dear. Turns out I had been really out of touch. This was a “secret” recruitment tool. Except it wasn’t so secret, it had been around for several years and seemed quite well known in the developer community. Some results told me that Google no longer recruit with it, it really is just a game now. Others say they still use it. But it didn’t really matter to me either way. I was currently in the process of training and testing my coding skills. This was a perfect way to test how far I’d come, and I like challenges. OK Google, challenge accepted!

I’d like to mention now that I wasn’t sure if I should be sharing this, since it was supposedly a secret challenge. But I found the following while searching for an answer to that question:

• Nowhere in the Foobar challenge did Google suggest that they wanted things to be kept secret. In fact it was the opposite, Google had posted documents saying they highly value ‘Googleyness’, a set of values that includes high transparency and a willingness to share and teach
• I found that several other people had also concluded that it was ok to post their own solutions and experiences

Seems that Google would not only be ok with sharing, they would actually encourage it. That’s wonderful, then let’s keep going!

So the question also came with a text file listing the constraints:

• Code could be provided in Java 8 or in Python 2.7.13
• Automated tests would be run against your solution, and execution time itself was a tested limit
• What exactly was being tested was left a mystery. You could only tell if your code was passing or failing these hidden test cases
• There was a not-allowed list that included some standard libraries and any third party libraries
• No spawning threads or processes and no trying to change the execution environment
• No more than 32k characters

There was also a time limit that would start when a challenge was requested. I’d already triggered that at this point, but fortunately I had no other plans, and it was a generous 24 hour limit.

I’ve worked in Java before, and had been meaning to work more with Python. I really like when I can make a single task achieve multiple goals. So I decided to choose Python.

This first question was mercifully straight forward. I’m sure Google realized that, just as I had, many would end up kicking off their first question before realizing what they were dealing with. So there was plenty of time to get Python 2.7.13 setup and to get comfortable with its syntax. This is what I came up with:

# Author: Derek Moran, Level 1 Minion @ Commander Lambda Space Station
# Date: 11-NOV-2022

import math

def solution(area):
    # Your code here
    return getLargestSquareAreasListDescending(area)

# Takes as its input a single unit of measure representing the total area
# Provided area must be between 1 and 1000000 inclusive
# Returns a list of the areas of the largest squares you could make out of those panels, starting with the largest squares first
# ex: getLargestSquareAreasListDescending(12) would return [9, 1, 1, 1]
def getLargestSquareAreasListDescending(area):
    if not type(area) is int:
        raise TypeError("Provided area must be an integer")

    if area < 0 or area > 1000000:
        raise TypeError("Provided area must be between 1 and 1000000 inclusive")

    areaList = []
    remainingArea = area

    while remainingArea > 0:
        maxUnitArea = int(math.floor(math.sqrt(remainingArea)) ** 2)
        remainingArea -= maxUnitArea
        areaList.append(maxUnitArea)

    return areaList

I’m a little disappointed that I threw a TypeError in a case where it wasn’t actually the type in question. I got the lower bound wrong too. I didn’t notice that until after submitting. But mostly I’m just thrilled that Google thought I’d be a good candidate to take their challenge in the first place. It was a confidence booster.

If a reader of this happens to be from Google, then thank you for the invitation. I’ll try not to disappoint you. For anyone who is taking or has taken the challenge already, then I hope it will be intriguing to compare your results with mine. For anyone else, I hope these postings will help you know what to expect when you are invited to the challenge yourself.