DRW Intern Software Engineer Interview Experience — A 3-Problem Codility OA With a 5-Part Robot Pathfinding Puzzle

I applied to DRW Singapore for the SWE C++ Internship. The first round was a Codility OA, 150 minutes for 3 problems.

There are n people, each with a distinct ability value in [1, n]. You're given a[i], the ability value of the i-th person. n is guaranteed to be a power of 2, with n <= 200,000.

Then several rounds of a tournament are held. In each round, players are paired off left to right (#1 vs #2, #3 vs #4, ...). In each pair, the one with the higher ability value wins, and the one with the lower ability value is eliminated and leaves. The winners form a new sequence in the same relative left-to-right order they had in the previous round, and then the next round begins. This repeats until only one person is left.

Return an array b[], where b[i] is the total number of matches the i-th person played.

You're given an R x C grid and a starting position. Walls are marked with #, empty cells with ., and the starting position with *. The four characters ^v<> mean move the robot up/down/left/right by one cell. 3 <= R, C <= 50, the outermost ring of the grid is guaranteed to be all walls, all the empty cells are guaranteed to be reachable from each other, and the robot is guaranteed to start on an empty cell.

You don't need to return to the starting position.

There are 5 subtasks after that, each constraining the shape of the empty cells and which cells must be visited, and you output the movement commands. Every subtask requires the final output sequence of commands to be no longer than 100,000. See the examples below.

• Subtask 1: all the empty cells form a rectangle, the robot is guaranteed to be at the very top-left corner of that rectangle, and it must visit only (and all of) the cells along the rectangle's border.
• Subtask 2: all the empty cells form a rectangle, the robot's position is unrestricted, and it must visit every cell.
• Subtask 3: the shape of the empty cells is two rectangles connected by a single cell in the middle, the robot's position is unrestricted, and it must visit every cell.
• Subtask 4: the shape of the empty cells is a path connecting two cells, the robot's position is unrestricted, and it must visit every cell.
• Subtask 5: the shape of the empty cells is unrestricted, the robot's position is unrestricted, and it must visit every cell.

Given an array a[] of length n, pick two numbers from it that share no common digit and whose sum is as large as possible. Find that maximum sum. n <= 200,000.

Example for problem 1:

5 --------- 8
/   \       /   \
5     3     6     8
/ \   / \   / \   / \
5   1 3   2 4   6 8   7    a[]
3   1 2   1 1   2 3   1    b[]

Subtasks 1 and 2:

########
#*.....#
#......#
#......#
#......#
########

Subtask 3:

########
#...#..#
#......#
#...#..#
#.*.#..#
########

Subtask 4:

########
##.*..##
##.##.##
##.##.##
#..##..#
########

Passed the OA, and now I'm getting ready for round one — except it happens to land right in the middle of finals week (picture a crying selfie here).

(Made a small edit — the formatting got a bit messed up.)