Problem description

Part 1: Static boat

You are given a region of Amsterdam city consisting of alternating streets and canals in the format of a matrix, where
“|” means street.
“*” means canal (water)
“=” means a boat (can be only located in canal columns)

For example:

|*|=|*|*|*|=|*|
|=|*|*|*|=|*|*|
|*|*|=|*|*|*|=|
|*|=|*|=|*|=|*|
|*|*|*|*|=|*|*|

You can start at any position in the leftmost column and need to finish at any position in the rightmost column. To do this, you can move to any adjacent (up/down/left/right) cell that is not water (street or boat) every minute. What is the shortest time to complete this journey?

Part 2: Moving boats

Now, boats start cyclically moving one cell/minute in the down direction. This means that our example

|*|=|*|*|*|=|*|
|=|*|*|*|=|*|*|
|*|*|=|*|*|*|=|
|*|=|*|=|*|=|*|
|*|*|*|*|=|*|*|

in one minute would turn into this:

|*|*|*|*|=|*|*|
|*|=|*|*|*|=|*|
|=|*|*|*|=|*|*|
|*|*|=|*|*|*|=|
|*|=|*|=|*|=|*|

The question is the same: What is the shortest time to complete this journey?

Note: you can move every minute, but you can also stay in the same spot and wait.

Possible solutions

For complexity calculations, let’s denote the length of the map as N and the height as M.

BFS

The most intuitive solution is to treat the map like a graph: street and boat squares representing vertices and possible moves representing edges. With all edges having an equal weight (time to pass), this problem is best solved with BFS. Therefore complexity for the first problem part is the following:

Part 1 Time = `O(N * M)`
Part 1 Space = `O(N * M)`

In the second part, we have a more complex situation, where the edges depend on the time passed. However, this is a cycle of M different time states. Therefore, the number of state-positions is (N * M) * M and the number of edges is proportional. Therefore complexity for the second problem part is the following:

Part 2 Time = `O(N * M * M)`
Part 2 Space = `O(N * M * M)`

Dynamic Programming

Let’s utilize the fact that the map has a columnar structure. If we reach street X, it doesn’t make any sense to return to street X-1. And we can’t reach street X+1 from street X-1 without stepping on the street X. If we know the best times to reach each cell of street X, we can calculate the best times to reach the street X+1:

1. Boats can be reached only from adjacent cells of street X
2. Adjacent cells already have the best reach times according to the previous steps of DP
3. The best time to reach each boat can be calculated from Step 1 and Step 2
4. street X+1 can be reached only from boats from Step 3
5. Boat-adjacent cell times can’t be improved by other boat-adjacent times, because otherwise:
   5.1. Let’s assume row A time on street X+1 can be improved from cell B on street X+1
   5.2. Value of row A on street X+1 is exactly 2 minutes more than row A on street X
   5.3. Value of row B on street X+1 is exactly 2 minutes more than row B on street X
   5.4. Therefore row A on street X could be improved from cell B on street X
   5.5. This contradicts the previous DP step
6. Best times for non-boat-adjacent rows of street X+1 can be calculated from closest boat-adjacent cells above and below in O(1) time

Total time complexity for one DP step is O(1) * boats + O(1) * adjacent cells + O(1) * other cells = O(M) Storing DP step state requires M additional space and 2 * M space to calculate the transition. Both can be reused. Therefore final time and space complexities of this algorithm are as follows:

Part 1 Time = `O(N * M)`
Part 1 Space = `O(M)`

Time-wise, it is equivalent to the BFS method, but better space-wise. However application of DP for the second part of the problem is more complex. We need to store the best times for each time state and calculate the transition for each of them. Therefore, the time and space complexities are:

Part 2 Time = `O(N * M * M)`
Part 2 Space = `O(M * M)`

Anlysis

This problem is interesting, but not well suited for standard 1-hour interview rounds, where the candidate has only around 45-50 minutes to solve the problem and write code. Part 1 is too simple (just one BFS) for a high-standard company. And the second part requires more than the remaining time to write and debug a solution, even without follow-up talks about optimisation, complexity, e.t.c.

It may be ok if the candidate is asked to solve the problem without writing code, but you won’t be able to evaluate a lot of problem-solving aspects, such as handling of special cases or code structuring.

Testing LLMs

For the first problem part, all LLMs generated a correct BFS solution; all generation results, as well as prompts, can be found in this repo: King’s Day problem files

GPT o3 and Gemini 2.5 Pro generated BFS-based solutions consistent with the idea described above. However, none of them handled the case of standing still on a boat (you don’t do any movements, but you move together with the boat anyway). Also, Gemini’s code is subjectively much more readable and easier to understand.

Claude 4 suggested a more original idea with 3-dimensional BFS, where time is an explicit third dimension.

1. 3D State Space: Now we track (row, col, time) instead of just (row, col)
2. Time-Dependent Grid: The grid configuration changes every minute as boats move down
3. Additional Action: Players can now stay in place and wait, not just move

It claimed to have the following time/space complexities:

Time: O(N × M × T) where T is the maximum time needed
Space: O(N × M × T) for the visited set

This is worse than both of the previously offered solutions, since T is always bigger or equal to N and tends to be (0.5 * N) * (0.5 * M) + N in the worst case (walking towards a single boat on each street)

However written implementation of this idea has even worse time complexity, as getGridAtTime function has N * M complexity and it is called for each entry in the queue. And in the worst case it will have N * M entries, which brings us to N ^ 2 * M ^ 2 time complexity.

// Calculate grid state at given time
vector<string> getGridAtTime(int time) {
    vector<string> grid = initialGrid;
    
    // Find all boat positions in initial grid
    vector<pair<int, int>> initialBoats;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (initialGrid[r][c] == '=') {
                initialBoats.push_back({r, c});
            }
        }
    }
    
    // Clear boats from grid (replace with water)
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == '=') {
                grid[r][c] = '*';
            }
        }
    }
    
    // Place boats at their new positions after 'time' minutes
    for (auto [r, c] : initialBoats) {
        int newRow = (r + time) % rows;  // Cyclic downward movement
        grid[newRow][c] = '=';
    }
    
    return grid;
}

Consistent with GPT and Gemini models, it did not handle standing on a boat.

Appendix

Photo: Amsterdam canal parade boat party during King’s day © Complete Amsterdam