Uber·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Uber SWE coding round, one problem the whole session. Grid-based chain collection thing with magnetic plates. Harder than it looked at first glance.

Questions Asked (1)

You have n plates on a 2D grid, each with coordinates (x, y) and a magnetic power d. Picking up a plate instantly collects all other plates within d units along the same row or column (chain reaction applies recursively). You can pick one plate per second. Write a function getMinTime(n, d, x, y) that returns the minimum number of seconds to collect all plates. n can be up to 1e5, coordinates and d up to 1e9.

Algorithms & Data StructuresSystem Design

Author's notes

I stared at the example for a solid minute before I even started talking.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a graph where each plate is a node, and picking a plate creates directed edges to all plates it can collect (same row/column within distance d). The minimum seconds to collect all plates equals the size of a minimum path cover in this directed graph, which by Dilworth's theorem equals the size of a maximum matching in a bipartite graph. Since the graph can be dense (O(n^2) edges), use a sweep-line with balanced BSTs to efficiently find reachable plates and build a sparse graph, then compute maximum bipartite matching using Hopcroft-Karp.

Pro tip: Don't jump straight to coding; first clarify that chain reactions mean transitive closure, and that the answer is the minimum number of starting plates. Mention that you'd handle large coordinates and n with coordinate compression and efficient data structures.

1. Clarify problem and model as graph

Confirm that picking a plate triggers a chain reaction, so the set of plates collected from one pick is the transitive closure. Model each plate as a node, with directed edges to plates it can directly collect.

2. Reduce to minimum path cover

The minimum number of picks to cover all plates equals the minimum path cover in the directed graph. By Dilworth's theorem, this equals the size of a maximum matching in a bipartite graph constructed from the original graph.

3. Efficiently build the bipartite graph

Since the graph can be dense, avoid O(n^2) edges. Use sweep-line with balanced BSTs (e.g., sorted sets) to find for each plate the nearest plates in each direction along rows and columns within distance d, and add only those edges.

4. Compute maximum matching

Run Hopcroft-Karp on the sparse bipartite graph to find the maximum matching size. The answer is n minus the matching size.

5. Analyze complexity and edge cases

Discuss time complexity: O(n log n) for graph construction and O(E sqrt(V)) for matching, where E is O(n). Handle edge cases like duplicate coordinates, large d, and n=1.

Key Points to Mention

Chain reaction implies transitive closure; picking one plate may collect many indirectly.
Minimum path cover in DAG equals n - maximum matching (Dilworth's theorem).
Graph can be dense; use sweep-line with balanced BSTs to find reachable plates efficiently.
Hopcroft-Karp algorithm for maximum bipartite matching in O(E sqrt(V)).
Coordinate compression and handling large coordinate values up to 1e9.
Time and space complexity analysis, and potential optimizations for n=1e5.

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