Google APAC Test 2017 Round C
Problem link (may require a proxy) · Code
I should have worked through original written-test problems long ago, to get a sense of their difficulty and discrimination, but I kept procrastinating.
I also did the first two rounds, with similarly disappointing results. I solved three problems; with more than an hour left on the fourth, I should normally have figured it out. But I was exhausted and hungry, and with half an hour remaining, I went to bed.
Problem A. Monster Path
Given an $R * C$ grid, a starting point, and $S$ steps, every A cell spawns a monster with probability $P$ and every other cell with probability $Q$. Each cell can spawn at most one monster.
Find the maximum expected number of monsters after $S$ steps.
Use DFS and record the number of visits $x$ to each cell. Each visit adds expected value $(1-P)^x * P$ or $(1-Q)^x * Q$; retain the maximum.
Problem B. Safe Squares
Count all-zero squares in an $R * C$ rectangle.
As in the previous Problem E, use DP to calculate the maximum square side length ending at every bottom-right corner, then sum them.
Problem C. Evaluation
Given dependencies between variables, determine whether each variable is defined, as in C++. A variable assigned from a no-argument function is defined; otherwise it depends on whether its parameters are defined. Function execution order is arbitrary.
This is topological sorting in $O(n^2)$. Mark undefined variables as -1 and reject them immediately; otherwise determine whether a valid topological order exists.
Problem D. Soldiers
Alice and Bob play a game with $n$ soldiers. Each has attack and defence. Every chosen soldier must exceed the attack or defence of every soldier already chosen. The game ends when no soldier can be chosen. Alice moves first and must select more soldiers than Bob. Determine whether this is possible under optimal play.
This comment explains it clearly. Sort soldiers by attack and defence. If one soldier is best in both, Alice wins because Bob has no valid choice. Otherwise, Alice cannot choose the maximum-attack or maximum-defence soldier: Bob would choose the other one and tie the count. Remove such choices and repeat.
This problem taught me a new function:
remove_if(a.begin(), a.end(), cmp). Put the predicate incmp; matching elements are removed, non-matching elements move forward, and the end position is returned.