Lesson learned:
- As with anything in Software Engineering, if we could resist the laziness, go with a boring solution first then progressively optimize it later, this would be done much sooner.
Table of Contents:
- About Foobar
- My Foobar experience
- Bringing a gun to a guard fight
- Disorderly Escape
- PAQ (Potential Asked Questions)
- Final words
Visit it here: https://foobar.withgoogle.com/
See also: Things you should know about Google Foobar Invitation.
I think different people might get different sets of challenges. It also depends on when you do it. That said, take my opinions and experience below with a grain of salt.
There are 5 levels, each has different numbers of problem to solve:
- Level 1: 1 problem, super easy.
- Level 2: 2 problems, easy.
- Level 3: 3 problems, still easy. In fact, these 3 problems took me the least of time. By the time you finish this, Foobar will ask for your resume and contact information (as if Google doesn't already know them).
- Level 4: 2 problems, Medium to Hard. 4.1 is a graph one. 4.2 is Geometric Calculus. We will talk about it later.
- Level 5: 1 problem. It's not Hard. Calling it's Hard is an offense to it!.
Foobar gives us a very generous time limit for each problem. For Level 1, if I remember correctly, we have 7 days. I thought that it was a joke, or perhaps Google also looks for very young but smart kids, so they give us enough time to learn the language. By the time I hit level 5, I did't like that joke anymore.
You can watch the videos of me solving the first 7 problems (1.1 to 4.1) within 4 hours since entering Foobar. The first few minutes of each video should show you full problem statements (and I guess that'll be the only interesting bits for you). However, if you're comfortable with Medium level in Leetcode, just ignore them.
Now, let's talk about the 2 most interesting problems.
- Problem statements and ideas can be found here.
- My solution
- Total time wasted here: 11h over 2 days.
This one is not so hard, requires a bit of Geometric Calculus knowledge, which is something I'm capable of. But I spend more than 10h thinking and solving an entirely other problem by mistake: The Laser gun and mirrored room. That puzzle is about how many bodyguards do we, as the Commander, need to block all beams? Foobar problem is about how many vectors can we shoot the Commander when our beam can travel a limited distance? Damn!
I recorded the first 1.5 hours on this one, but then threw it away since I know I'll need more time than that, and you don't like to watch me struggling more than 30m anyway.
This is my favorite problem. If not because of it, I wouldn't bother to write about this journey.
- Here's the code with detailed reasoning. But I suggest that you should read the problem statement and think about it for a while before reading the code.
- Total time wasted here: 20 days (too many hours to keep track).
Let me try to phrase it in a simpler term instead of reuse the wordy statement from Foobar.
Given a matrix of W * H size. Each cell can take a value from 1 to S
inclusively. 2 matrices are said to be in an equivalence class if we can
apply any number of the following transformations to turn one into the other:
- Swap any 2 columns
- Swap any 2 rows
Example of equivalence matrices with W=3, H=2, S=2:
100 010 001 100
010 100 100 001 ...
How many equivalence classes can be constructed knowing W, H, and S?
Skip this section if you aren't interesting in the wrong approaches.
This section is structured to be read like a straight path from start to end. However, in reality, it is not this well-organized, I went back and forth between ideas various times. My feelings moved between hopeless and excited like a pendulum. I believe anyone who has solved any non-trivial problem has a similar experience.
With the observation that if H=1, we can change the problem statement to: How
many ways to put W objects to S group, which have a trivial solution using
Star and Bar counting method. Since the role of W and H can
change, if there's a Dynamic Programming solution that needs a 2D memo matrix,
we already have the first row and first column. I also hadn't seen any DP
problem so far. This must be it!
I spend 3 days tapping my head against the wall on this approach.
Day 4, no more hope for DP, I tried a new approach. What if this is a Graph problem? We could consider each cell as a node directly connected to all other cells in the same column and the same row. Our transformations preserve the paths between nodes. Perhaps it's a Topological Sorting problem. If we could generate all the matrices and sort them somehow, then it is solved.
This approach led me to depression.
I can't count how many times I looked at the statement and even the welcome message for a hint, any hint.
In the Foobar statement, they use the term "matrix configuration". There is one immutability that we can use:
- The number of cells with state
i(for1<=i<=S) within each row and each column won't change. Let's call it row/column configuration. - The set of row/column configurations won't change.
So, we could calculate the 2 sets of configurations for rows and columns for each matrix, then use it to compare them. The time complexity for this solution would be terrible, but at least it's a valid solution. It should pass some test cases and generate more test cases for my other solutions!
That brute force solution can't even get through the case W=5, H=5, S=5 on my
machine.
My 2nd last resort is, obviously, to find other people's solutions for ideas. Some searching led me to this question on Math/StackExchange. I stop reading at the keyword Burnside lemma in the accepted answer. That's all the hint I need.
Reading the wiki article on Burnside lemma for the first time makes me wanna jump. "It's a Group Theory problem, a fucking Group Theory problem". That's it. That's why all other kinds of Math I tried to apply didn't work.
Read that article several more times make me wanna cry. "What language is it? WTF".
For the record, I'm used to be a Math competitive student, used to read Advanced Calculus for fun during high school (sadly, I didn't make it to the final round of the Vietnam Mathematics Olympiad, otherwise, I would be a Mathematician now instead of a Software Engineer).
I'm not a stranger to Math. But the language there is alien to me.
I spent the next 2 weeks reading a couple of books, slides and watching videos (see "Help resources" section below).
I think I understood the concepts, the lemma, and some other theorems. I could solve some exercises, verify many other examples of Burnside's lemma applications. But, for some reason, I still can't crack the matrix problem.
I read the answer on Math/Exchange, again and again, ignore all the code, just
try to decipher the math, still can't digest the logic. "Why would we need
lcm and gcd? What OEIS sequences have anything to do with this? Oh,
Maple, hello old friend, but I'm sorry that I don't want to look at you right
now!"
The Python code there, however, was helpful to show that my Brute Force solution was wrong. "Damn, I couldn't even write a proper brute force."
Since I'm almost run out of time (and mental energy) on this one, I decided to give it one last shot. The best way to think in logic is to write down our thought and verify one by one. I did it with pen and paper before, but I guess it failed because I was too lazy to write down all the calculations. This is my last chance. If it also fails, then, fine!
This time, I need to do it differently, carefully, every single word must be beautifully typed. This time, I need the strongest, heaviest weapon in my programming toolbox: Literate programming.
Thanks to Knuth, I succeed this time. All the logic was cleared. All the questions were answered. All the local test cases passed. The moment my solution passed Foobar tests, I can't help but shout to the void on Twitter.
Among many things I had read/watch, these are the most useful:
- An introduction to group theory - Tony Gaglione: a good read, clear enough to grasp the concepts of Group Theory while short enough to finish it in several days (138 pages). Pinter's A Book of Abstract Algebra is another good one but it's much longer (400 pages) and doesn't have free PDF available.
- Essence of Group Theory - videos on Youtube: those videos offer another approach to Group Theory, which help me to strengthen my understanding.
- Python solution by Kody Puebla. I only use it to generate test cases.
There's one question stuck in my mind.
Is there any Closed-form expression (CFE) for the answer?.
I tried to search for them, even discover a paper for the CFE of
Number Partition function p(n) (related to function numbersSumToN in my
solution) from a Math Exchange question in 2011 (the wiki article
Partition (number theory) isn't up-to-date regarding this). But I
have no luck in finding the CFE for this problem.
Math is beautiful and sometimes can be surprising. Consider how Pi hiding in prime regularities and what E has anything to do with Counting Derangement, I believe such expression exists!
I think I'll put it out of my head for a while, revisit it in the future, with a fresher mind and hopefully with more Math knowledge.
To the people at Google who use it for level 5, thank you, I can't wait for the next time I need Group Theory in my life!
How to get the invitation?
Just Google it 😂.
OK, so there's some trick to get invited. But why did you do that?
I need a new game to play after finish work. And I'm already feeling bored with Leetcode after solving 800+ problems there. Boredom brings the memory back, and I was doing some random search that time. So I recalled about Foobar and decide: "Why not?"
Don't you have work to do? How could you spend so much time on this?
Don't worry, I still make sure my day work is done, only doing this part-time at night and weekend. Honestly, I don't have many hobbies and already deactivate my Facebook account, so I have spare time to burn.
Did you Google the solutions?
I search for 4.2 after submitting the solution, to see if there's any smarter solution. For level 5, we've talked about it in the previous sections.
Did you get an email from Google after Level 3?
Nope.
It's so easy (right now) to game the system for an invitation, and the solutions for almost all problems can be found on the Internet. So, I think there are already too many resumes submitted via Foobar, make Foobar less useful for Google as a hiring tool. It's fortunate that they still keep the system around, so we can play for fun.
I don't expect the email or interview, just feel cool to accomplish something I couldn't have done 6 years ago.
Despite calling it’s “wasted time”, I enjoy this adventure, thanks to anyone keeping Foobar maintained. I hope that this repo could become popular so that the Foobar team needs to use new problems, so we can have another journey.