← Uptime Crew Interview Insights

Uptime Crew·Software Engineer·Onsite - Coding / Algorithms·Intermediate

Intermediate
Apr 2026

Summary

Coding round at Uptime Crew for a Software Engineer role. One problem, but it had a twist that made the standard solutions not good enough, which I did not see coming until I was already mid-explanation.

Questions Asked (1)

Q1

Given an n x n grid where some cells contain thieves and others are empty, find the path from the top-left to the bottom-right corner that maximizes the minimum Manhattan distance from any thief. As a follow-up variant: if multiple paths tie on that maximum safeness factor, return the shortest one among them.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

I knew the base problem.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Reframe the problem as finding the maximum bottleneck path where the bottleneck is the minimum safeness factor (distance to nearest thief) along the path. Precompute safeness factors using multi-source BFS from all thieves, then use a max-heap (or binary search on the answer) to find the path that maximizes the minimum safeness. For the follow-up, when multiple paths achieve the same maximum safeness, choose the one with the fewest steps, which can be handled by tracking path length in the priority queue or by running BFS on the subgraph of cells with safeness >= optimal value.

Pro tip: Clarify with the interviewer whether the path can move in 4 or 8 directions and whether the grid can contain obstacles; these details affect the BFS and pathfinding implementation. Also, mention that the follow-up variant can be solved by first finding the optimal safeness value, then doing a BFS to find the shortest path among those that maintain that safeness.

1. Understand and clarify the problem

Restate the problem to ensure you understand: maximize the minimum Manhattan distance to any thief along a path from top-left to bottom-right. Ask about movement constraints (4-directional vs 8-directional), grid size limits, and whether cells with thieves are passable.

2. Precompute safeness factors

Use multi-source BFS starting from all thief cells to compute the Manhattan distance to the nearest thief for every cell. This gives the safeness factor for each cell in O(n^2) time.

3. Find the maximum bottleneck path

Use a max-heap (priority queue) to explore paths, always expanding the cell with the highest safeness factor, and keep track of the minimum safeness encountered so far. Alternatively, binary search on the safeness value and check connectivity using BFS/DFS.

4. Handle the follow-up variant

If multiple paths achieve the same maximum safeness, find the shortest one. This can be done by first determining the optimal safeness value, then running BFS on the subgraph of cells with safeness >= that value to find the shortest path from start to end.

5. Analyze complexity and trade-offs

Discuss time and space complexity: O(n^2 log n) for the heap approach or O(n^2 log(maxDist)) for binary search. Mention that the follow-up adds a BFS step, keeping overall complexity the same. Compare approaches and justify your choice.

Key Points to Mention

  • Multi-source BFS to compute distances to nearest thief efficiently.
  • Maximizing the minimum along a path is a bottleneck path problem, solvable with a max-heap or binary search + BFS.
  • The safeness factor is the Manhattan distance to the nearest thief, which can be precomputed.
  • For the follow-up, after finding the optimal safeness, a BFS on the filtered graph yields the shortest path.
  • Time complexity: O(n^2 log n) for heap approach, O(n^2 log(maxDist)) for binary search; space O(n^2).
  • Edge cases: start or end cell is a thief (safeness 0), no path exists, grid size limits.

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