Katkat
Back

Solve Three Coding Problems

SnapchatSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to efficiently manage dynamic, sliding-window data streams and geometric grid traversal using graph search techniques.

Part 1: Rolling Median Stream

Design a class MedianStream that processes a continuous stream of integers and provides the median of the last K elements. If the stream has fewer than K elements, return the median of all current elements.

class MedianStream:
    def __init__(self, k: int):
        pass
    def add_number(self, num: int) -> float:
        pass

Part 2: Dynamic Hazard Grid

You are given an N x N grid where some cells contain hazards that disappear at specific time steps. Starting at (0, 0) at t=0, you can move to an adjacent cell (up, down, left, right) or wait in your current cell for 1 unit of time. Each move takes 1 unit of time. You cannot enter a cell (r, c) at time t if it contains a hazard that is active at time t.

Given start = (0, 0), target = (N-1, N-1), and a list of hazards [(r, c, t_start, t_end)] indicating the hazard is active from t_start to t_end (inclusive), return the minimum time to reach the target. If unreachable, return -1.

Examples

Example 1 (Median): k=3. Stream: 1, 10, 5, 20.

  • Add 1: Median 1.0
  • Add 10: Median 5.5
  • Add 5: Median 5.0
  • Add 20: (10, 5, 20). Median 10.0

Example 2 (Grid): N=3. Hazards: [(0, 1, 0, 2)].

  • At t=0, (0, 1) is blocked. You must wait or move elsewhere.
  • The shortest path might involve waiting until the hazard clears.

Hints

Hint 1

For the median, maintain two balanced heaps (max-heap for the lower half, min-heap for the upper half) and use a sliding window mechanism like a deque or hash map to remove stale elements.

Hint 2

For the grid traversal, treat the state as `(row, col, time)` and use BFS to find the shortest path, noting that you must cap the maximum time to explore to prevent infinite loops.

Hint 3

Since the grid can be visited at different times, use a `visited` set tracking `(row, col, time % period)` if the hazards are periodic, or simply `(row, col, time)` if they are finite.

Follow-up questions

  • How would you optimize the median stream if the range of incoming numbers is restricted to a small interval [0, 1000]?
  • If the grid size N is very large (e.g., 10^5) but hazards are sparse, how would your BFS approach change?
  • How does the time complexity change if 'waiting' is prohibited in the grid traversal?