Bloomberg·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Bloomberg coding round, pretty standard grid problem but the state tracking tripped me up more than I expected.

Questions Asked (1)

Given an m by n grid where 0 is open and 1 is a wall, find the minimum number of steps to travel from the top-left to the bottom-right corner. You can remove at most k walls along the path. Movement is 4-directional. Return -1 if no path exists.

Algorithms & Data Structures

Author's notes

I knew BFS immediately but fumbled on the state representation for a bit.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a shortest path on a state graph where each state is (row, col, walls_removed). Use 0-1 BFS or Dijkstra to find the minimum steps to reach the bottom-right with at most k walls removed, treating open cells as weight 0 and walls as weight 1.

Pro tip: Clarify that 'steps' means the number of moves, not the number of walls removed, and mention that if k is large enough, the problem reduces to standard BFS on open cells only. Also, discuss how to handle large grids by using a deque for 0-1 BFS to achieve O(mn) time.

1. Clarify the problem

Confirm that 'steps' refers to the number of moves (edges) and that removing a wall counts as traversing that cell. Ask if k can be larger than the grid size or if there are constraints on m, n, and k.

2. Define the state and graph

Represent each state as (r, c, w) where w is the number of walls removed so far (0 ≤ w ≤ k). Transitions: moving to an open cell keeps w, moving to a wall increments w by 1.

3. Choose the algorithm

Use 0-1 BFS with a deque: push open-cell transitions to the front and wall transitions to the back. Alternatively, use Dijkstra with a priority queue. Both find the minimum steps.

4. Implement and optimize

Track visited states to avoid cycles. Early exit when reaching (m-1, n-1) with any w ≤ k. For large grids, use a 2D array of size m x n storing the minimum walls removed to reach each cell, and run BFS with a deque.

5. Analyze complexity

Time complexity is O(mn) because each cell is processed at most once per wall count, but with the 2D array optimization it's O(mn). Space complexity is O(mn) for the visited array and deque.

Key Points to Mention

State space includes walls removed, leading to O(mn) states if optimized.
0-1 BFS uses a deque to process 0-weight edges first, ensuring shortest path.
Alternative: Dijkstra with priority queue, but 0-1 BFS is more efficient.
Early termination when reaching the target with any valid wall count.
Edge cases: start or end is a wall (must remove it), k=0, no path exists.
Optimization: use a 2D array to store min walls removed per cell instead of 3D visited.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.