Solve Three Coding Problems
Company: Snapchat
Role: Software Engineer
Category: Coding & Algorithms
Interview Round: Onsite
Quick Answer: This set of problems evaluates competencies in streaming data handling and incremental aggregation, time-dependent grid traversal and reachability under dynamic hazards, and planar path existence with geometric obstacles, touching on data structures, graph algorithms, and computational geometry within the Coding & Algorithms domain.
Streaming Top-K Values
Constraints
- k >= 0
Examples
Input: (3, [5, 1, 9, 3, 10])
Expected Output: [[5], [5, 1], [9, 5, 1], [9, 5, 3], [10, 9, 5]]
Explanation: Maintains top three.
Input: (0, [1, 2])
Expected Output: [[], []]
Explanation: k=0 returns empty lists.
Input: (5, [2, 2, 1])
Expected Output: [[2], [2, 2], [2, 2, 1]]
Explanation: Fewer than k values.
Hints
- Keep a min-heap of the current top k values.
Maximum Safe Delay in a Burning Grid
Constraints
- grid values: 0 empty, 1 fire source, 2 wall
- Arriving at destination at the same time as fire is allowed
Examples
Input: ([[0, 0], [0, 0]],)
Expected Output: 1000000000
Explanation: No fire means arbitrary waiting.
Input: ([[0, 1], [0, 0]],)
Expected Output: -1
Explanation: Escape can be impossible immediately.
Input: ([[0, 0, 0], [2, 2, 0], [1, 0, 0]],)
Expected Output: -1
Explanation: Finite waiting case.
Hints
- Precompute fire arrival times, then binary-search the waiting time with BFS feasibility.
Rectangle Path with Circular Blockers
Constraints
- Circles are closed blockers
Examples
Input: (10, 10, [])
Expected Output: True
Explanation: No blockers.
Input: (10, 10, [(0, 5, 1)])
Expected Output: True
Explanation: Circle touching only left boundary need not block.
Input: (10, 10, [(5, 5, 6)])
Expected Output: False
Explanation: Endpoint-free but boundary-spanning blocker.
Input: (10, 10, [(1, 1, 2)])
Expected Output: False
Explanation: Start inside a circle.
Hints
- Union touching/overlapping circles and rectangle boundaries; certain boundary connections block all paths.