That’s right, its a new article because this news is just so extremely exciting.
Saturday, December 23rd, 5pm: I had just begun my programming lesson, the final in a trio involving binary lifting. My teacher introduced the problem of the week: the least common ancestor problem. Some programmer instinct in me immediately googled what it was, and within a a few quick keystrokes the answer was before me. But as I started skimming over the excerpt of a Wikipedia article, a strange thing came over the results page: a sudden distortion, and a hidden easter egg was exposed as the page opened:
“Curious developers are known to seek interesting problems. Solve one from Google?”
Incredible as this was, not only did I not immediately press the enticing blue “I want to play” button, but I even had the audacity to RELOAD the page, thinking to view the reveal animation again. I realised my mistake as soon as it did not happen, but worry not as after frantically reloading who knows how many times it happened again. I clicked the button this time. I was led to a unix shell-like interface, and so my rudimentary knowledge of commands turned up “ls”, which lists all files and directories at your current location. Then it dawned on me that I could simply enter “help”, and this resulted in me having a pretty good idea of what I had just discovered.
This was a secret Google page, triggered when the search algorithm detected that I had done enough programming-related searching, that was a recruiting platform. Google, you couldn’t have made this welcome-to-my-secret-society thing ANY cooler.
Apparently, there were 5 levels I had to solve, and each level would yield a challenge with a time limit of 7 days to solve. Upon failing to do so I would lose access to the site and with it my chances of becoming a google engineer.
Well, on the 24th I flipped open my laptop and started the first challenge, brimming with confidence in my C++ abilities. Instead, when I entered the new challenge directory that appeared, I was told I could only use Python and Java. Not only that, I could only use Python 2.7 (not 3.7) and Java 8.
Well jokes on you Google, I learnt some Python and some Java too! Python was my first language and I’ve been using it semi-regularly sometimes and Java is the only option the IB allows, so I had to learn that to teach Seniors in my ECA. So there! I opted for python in this challenge, as I prefer it for non-algorithmic programs as Java’s syntax more closely resembles C++ which I do my competitive programming with. By the way, my rating took a huge hit recently on AtCoder, I was 996 when suddenly I had a bad day and only solved the first problem. It went down like 60 points and then some more on the next contest. It recovered to 928 on my previous contest and I will be in the 4 digits by February I hope.
The first problem was easy enough and I finished it in under 20 minutes, sending me to level 2, which had not 1 but 2 challenges. I solved the first on the night of the 25th.
During that time I was on a sort of road trip around southern Thailand, and as of writing, which is late on the 26th, I have blasted through levels 2 and 3. In all honesty the problems were not really difficult so far, I remember one was literally just 2 nested for loops. The most difficult was a shortest-path-in-maze problem, which is just a direct application of BFS, except you could knock down a wall of your choice to make the shortest path shorter. This took a bit of fiddling about but I spend no more than an hour and a half on it, and I was (and still am) in a groggy state. When I did complete level 3, I submitted some details (including a link to this website) to Google to send to a fellow programmer friend,
I’ll update this soon, when I have finished level 4, and then another one once I (surely) finish 5.
Update Dec 27, 3:20
I have finished challenge 1/2 of level 4. I was given 15 days for this one, but it was still a relatively straightforward problem, and after working on it for again around 1.5 hours with a break in between, I cracked it. This problem was more challenging than level 3c, however I just learnt about various shortest path algorithms and was already quite fluent with graph traversal, so I would again say this wasn’t that difficult and it was mainly just slow implementation on my part. One issue I discovered too late was that in my comments I wrote I used the Bellman-Ford Algorithm, but no, I used the Floyd-Warshall algorithm! Whoops. Going to attempt challenge 2 tonight.
Update Dec 27, 6:30
I have finished Level 4. I quickly identified the second challenge as a flow rate problem, and so basically spend the hour learning and implementing the Ford-Fulkerson algorithm. Level 5 will be completed tomorrow.
Update Jan 9
Well I haven’t updated this in a while, but basically, I was working on some holiday homework on the 28th so I started the challenge on the morning of the 29th. By now I realise that all the solutions are available online and google has stopped using this for hiring(probably), so I’ll post the problem and solution here. Yesterday I requested another challenge thinking nothing would happen but instead I received one, so I solved that and then I solved another today. So there are 3 quite difficult and nice problems that I will present, in order of difficulty.
Expanding Nebula
The easiest was the second ‘Level 5’ problem, a cellular automata problem. Basically you have a HxW grid of cells, and each cell is either filled or empty. Each transition to the next state reduces the number of rows and columns by 1 and the transition is as follows:
Assume the \(j\)th cell in the \(i\)th row is denoted by \((i, j)\). For \(i < H\) and \(j < W\), in the next iteration \((i, j)\) will be filled if exactly one of \((i, j), (i + 1, j), (i, j + 1), (i + 1, j + 1)\) is filled.
Given a state of the nebula, find the number of states that could have come before the transition. The constraints are that \(H < 10\) and \(W \leq 50\).
When I saw this problem, I saw that it had to be some sort of DFSish problem, where we enumerate all possibilities in some way. However seeing as there can be up to 450 cells, this would definitely not be feasible all by itself and I would have to either perform it over a smaller range or be able to rule out nearly all possibilities. I didn’t know how to do the latter so did the former. The key was that the height would always be less than 10, so if we only look at one column of the nebula, the state before would only have a maximum of 20 cells. This is very feasible. We can find all \(2 \times (H + 1)\) nebulae that are the previous states for each column, separating the rows and columns, and then use dynamic programming (very fancy) to find our answer by chaining the previous states together if two columns’ previous states share an identical column. Here is the code:
from collections import defaultdict # defaultdicts have default values for keys that don't yet have a value associated with them
from numpy import rot90, flip
def transition(col1, col2, n):
# Time for some bitwise magic! I was too lazy to convert to 2d array even though
# that is easier to understand so I have instead heavily commented this
# a and b are bits 1-n out of n + 1 in their respective columns
a = col1 & ((1 << n) - 1)
b = col2 & ((1 << n) - 1)
# c and d are bits 2-n+1 out of n + 1 in their respective columns
c = col1 >> 1
d = col2 >> 1
# Let the four cells that contribute to a cell during the transition be a, b, c, and d.
# For the result to be 1, exactly one of a, b, c, and d can be 1, in other words,
# (a, b, c, d) is one of (1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0), (0, 0, 0, 1),
# so one of (a, !b, !c, !d), (!a, b, !c, !d), (!a, !b, c, !d), (!a, !b, !c, d) is equal to (1, 1, 1, 1).
# Bitwise NOT is the ~ for some reason? Why not '!'?
return (a & ~b & ~c & ~d) | (~a & b & ~c & ~d) | (~a & ~b & c & ~d) | (~a & ~b & ~c & d)
def build_map(n, nums):
mapping = defaultdict(set)
nums = set(nums) # Avoid repetition
for i in range(1 << (n + 1)): # Try all combos for the 2 x (n + 1) cloud that resulted in the current column of our cloud
for j in range(1 << (n + 1)):
column = transition(i, j, n)
if column in nums:
mapping[column].add((i, j))
return mapping
def solution(g):
h = len(g)
w = len(g[0])
grid = rot90(g) # Rotate+flip grid to be represented by columns so we can store them as base 10 integers
grid = flip(grid, axis=0)
nums = [sum([int(col)<<i for i, col in enumerate(row)]) for row in grid]
mapping = build_map(h, nums)
dp = [[0 for i in range(1 << (h + 1))] for j in range(w + 1)]
for i in range(1 << (h + 1)):
dp[0][i] = 1
for i in range(1, w + 1):
for col1, col2 in mapping[nums[i - 1]]:
# The number of ways to have the second column be col2 is the sum of all the ways
# to have the first column be col1 (whic is known) and the second column to be col2
dp[i][col2] += dp[i - 1][col1]
return sum(dp[w])Dodge the Lasers
Okay a math problem. Find
\(\sum_{i = 1}^n \lfloor i\sqrt{2} \rfloor\)
(the [] with the top missing is the floor function)
where n can be very, very, very large. Up to one googol in fact. I was completely stuck on this one for quite a while and had to sleep over it, but then I had a flash of inspiration: turn to the Knuths on the shelf. Concrete Mathematics, by Graham, Knuth, and Patashnik, is a trove of knowledge for all things mathematical in computer science. I flipped to Section 3.2 of my downloaded copy (Floor/Ceiling Applications) and found a very interesting result. First of all, the sequence \(\lfloor\sqrt{2}\rfloor, \lfloor 2\sqrt{2} \rfloor, \lfloor 3\sqrt{2} \rfloor, \dots\) appeared, along with the same sequence with \(2 + \sqrt{2}\) instead of \(\sqrt{2}\) as the irrational number. The book goes on to prove that those two sequences partition \(\mathbb{N}_{> 0}\), and also to show that this works for any 2 irrational numbers \(a\) and \(a\) given
\(\frac{1}{a} + \frac{1}{b} = 1.\)
We can use this to create a super fast recursive formula. First, let \(S(x, n) = \sum_{i = 1}^n \lfloor ix \rfloor\), and let \(m = \lfloor a n \rfloor\). Now,
\(S(a, n) + S(b, \lfloor \frac{m}{b} \rfloor) = \frac{m(m + 1)}{2}\)
and \(n + \lfloor \frac{m}{b} \rfloor = m\),
so \(\lfloor \frac{m}{b} \rfloor = m\ – n\)
\(= \lfloor a n \rfloor – n = \lfloor (a\ – 1) n \rfloor\)
and also \(m = n + \lfloor (a\ – 1) n \rfloor\).
Let \(k = \lfloor (a\ – 1) n \rfloor.\)
This means \(S(a, n) = \frac{(n + k)(n + k + 1)}{2} – S(b, k).\)
Using the equation right at the very beginning again, \(= \frac{(n + k)(n + k + 1)}{2} – \)
