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

Intermediate

Jun 2026

Summary

Coding round at Uptime Crew for a Software Engineer role. One problem, but it was a nastier variant of a known Leetcode problem and the expected solution was stricter than what most people prep for.

Questions Asked (1)

Given an n x n grid where some cells are marked as thief cells, find a path from the top-left to the bottom-right corner that maximizes the minimum Manhattan distance to any thief cell. If multiple paths tie on that safeness score, return the shortest one among them.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I knew the base problem and went straight for binary search plus BFS, which felt clean.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Reframe the problem as a maximin path problem: binary search on the safeness score S, and for each S check if a path exists using only cells with distance ≥ S. Then among paths achieving the maximum S, find the shortest via BFS. This combines binary search, BFS, and careful tie-breaking.

Pro tip: Precompute distances to nearest thief using multi-source BFS to avoid O(n^4) checks, and when binary searching, use the fact that the answer is one of the precomputed distances to reduce search space.

1. Clarify and precompute distances

Confirm grid size, thief positions, and that Manhattan distance is used. Precompute for each cell the distance to the nearest thief using multi-source BFS from all thief cells.

2. Binary search on safeness score

Binary search over possible safeness values (from 0 to max distance). For each candidate S, check if there is a path from start to end using only cells with distance ≥ S.

3. Feasibility check with BFS

For a given S, run BFS from start to end on the subgraph of allowed cells. If reachable, S is feasible; else not.

4. Find shortest path for optimal S

Once the maximum feasible S is found, run BFS again on allowed cells to find the shortest path (minimum number of steps) from start to end.

5. Analyze complexity and edge cases

Discuss time complexity: O(n^2 log D) where D is max distance, and space O(n^2). Handle edge cases like no path, start/end being thieves, or multiple optimal paths.

Key Points to Mention

Multi-source BFS for efficient distance precomputation
Binary search on the answer (maximin optimization)
BFS for path existence and shortest path
Tie-breaking: shortest path among those with max safeness
Time and space complexity analysis
Edge cases: start/end blocked, no path, multiple thieves

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