← Zip Interview Insights

Zip·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Ziphq software engineer interview with a grid pathfinding problem. Pretty focused session, just the one coding question but it had enough depth to keep you busy for a while.

Questions Asked (1)

Q1

On an infinite 2D integer grid with a start cell, an end cell, and a set of barrier cells, find and return one shortest path (as a sequence of coordinates) between start and end using only cardinal moves. If no path exists because the end is unreachable, return an appropriate indicator instead of running forever.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

The infinite grid part is what trips you up first.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the grid as an implicit graph and use BFS from the start to find the shortest path, treating barrier cells as blocked. Since the grid is infinite, bound the search to the rectangle defined by start, end, and barriers (expanded by one cell) to guarantee termination and return null if the end is unreachable.

Pro tip: Mention that BFS is optimal for unweighted grids and that bounding the search space is crucial for infinite grids; also discuss how to reconstruct the path using a parent map and handle edge cases like start == end or start/end on barriers.

1. Clarify assumptions and edge cases

Confirm that moves are only up, down, left, right; that barriers are impassable; and handle trivial cases like start equals end or start/end being barriers.

2. Define a bounded search space

Compute the minimal bounding rectangle covering start, end, and all barriers, then expand it by one cell in each direction to allow paths that go slightly outside.

3. Run BFS with parent tracking

Use a queue for BFS from the start, marking visited cells and storing parent pointers; stop when the end is reached or the queue is exhausted.

4. Reconstruct and return the path

If the end was reached, backtrack from end to start using parent pointers to build the coordinate sequence; otherwise return null or an empty list to indicate unreachability.

5. Analyze complexity and trade-offs

Discuss time and space complexity in terms of the bounded area, and mention alternative approaches like A* if heuristics are available.

Key Points to Mention

  • BFS guarantees shortest path in unweighted graphs
  • Bounding the infinite grid using start, end, and barriers
  • Using a parent map or predecessor array for path reconstruction
  • Handling unreachable cases by returning null or empty list
  • Time and space complexity O(N) where N is the number of cells in the bounded region
  • Potential optimization: bidirectional BFS or A* with Manhattan distance heuristic

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