Timeline
Day 1: I applied.
Day 2: I got a rejection email saying my background/skillset was not a close enough match for what they need. The same email also offered an optional take-home: if I passed it, I would go straight into the interview process and skip the first coding round. I filled out a Typeform (name and email), and within a day MarioHR sent me the assessment link.
Format
The platform is MarioHR. You log in with GitHub, and the whole session is screen-recorded.
It is timed. They officially say to set aside 1-2 hours, that it is very hard, and that they "don't expect you to finish". They mainly look at your problem-solving approach and coding ability.
Any language is fine, and you can look up docs and libraries. AI is not allowed.
The problem is in repo form. You put your code in the solution/ directory, and there is a test_cases.md included.
The problem
(I think this is RowGame from TopCoder, roughly.)
There is a row of N cells, each with an integer value, which can be negative. A piece starts at cell 1. The first move goes right, and after that the direction alternates on every move. Each move can go 0 or more cells. After each move, the score increases by the sum of the values of all cells from the start to the end of that move (both ends included). The score can never drop below 0 at any point. Find the maximum score you can get using at most k moves.
Constraints: N <= 50, cell values within +/-400 million, k <= 400 million.
Approach
DFS with a cache: if you put the score in the key, the number of states explodes; if you leave the score out of the key, the result is wrong. The right way is to treat the score as the DP value: dp[moves][position] = the highest score when you get there. A higher score can only let you make more moves (a high score dominates a low one), so keeping only the highest score per state is enough.
The direction is fully determined by the parity of the move count, so you don't need it in the state. At the start there is only one valid state.
With k up to 400 million, O(k*N^2) will never finish. In the later phase the moves turn into bouncing back and forth over some interval to farm score, and the whole DP array gets a fixed increment every two moves. Once you detect that the increment has stabilized, you compute the earliest point at which something will change (a move becomes valid or invalid, the best source gets overtaken, a new cell becomes reachable), jump straight to that point, and then keep simulating.
Watch out for overflow: the max score can reach around 8e18, which just barely fits in int64.
Result
I failed the take-home. My DP was only off by an initialization bug, but I ran out of time. You need to think through the DP state and the initial state first, before you start writing.
Discussion
Loading comments…