Bloomberg Coding: Grid Shortest Path with K Breaks

You are given an m x n grid of 0s (open) and 1s (walls). Starting at (0,0) and moving in four directions, compute the minimum number of steps to reach (m-1,n-1) if you may remove up to k walls along the path. Traversing a 0 costs no wall removals; traversing a 1 consumes one removal. Return the step count or -1 if unreachable.

Approach and flow you should present in an interview:

• Start with a BFS that tracks state as (x, y, remaining_k, steps). Each move increments steps; entering a 1 decrements remaining_k. Use a visited structure keyed by (x,y) that stores the maximum remaining_k seen at that cell to prune worse states.

• Early exits & optimizations: if k >= (m-1)+(n-1) you can return the Manhattan distance immediately. Consider using A* with a Manhattan heuristic or pruning when remaining_k is worse than a previously seen value for the same cell.

• Complexity and trade-offs: the canonical solution has O(m * n * k) time and similar space in the worst case. Explain memory/time trade-offs if you try to compress state or apply heuristics.

Skill signals interviewers look for: correct BFS-with-state implementation, proper visited/pruning to avoid TLE, handling edge cases (single-cell grid, k=0), complexity analysis, and thoughtful optimizations (A*, heuristic pruning).