Uber·Machine Learning Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

Jun 2026

Summary

Uber ML engineer coding round, one question the whole time. Pretty geometry-flavored problem that looks weird at first but clicks once you see the hashmap angle.

Questions Asked (1)

Given a list of 2D integer coordinates representing bus stations, streets run horizontally, vertically, and along both diagonals through these points. For every street passing through at least one station, count how many stations lie on it. Return the stations on the street with the maximum count. If multiple streets tie, return the union of stations across all tied streets.

Algorithms & Data Structures

Author's notes

My first instinct was some kind of geometric sweep and I wasted probably three minutes going down that road before stepping back.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a hash map to group stations by their street lines: horizontal (y), vertical (x), diagonal (x - y), and anti-diagonal (x + y). Track the maximum group size and collect all stations from groups that achieve it, ensuring no duplicates in the final result.

Pro tip: Mention that this is essentially a line detection problem similar to Hough transform, and emphasize that using a single pass with hash maps gives O(n) time, which is optimal since every station must be examined.

1. Identify street representations

For each direction, define a unique key: horizontal (y), vertical (x), diagonal (x - y), anti-diagonal (x + y). Explain that these keys uniquely identify lines in each direction.

2. Group stations by street

Iterate through all stations and add each station to four hash maps (one per direction) using the computed keys. This groups stations that lie on the same street.

3. Find maximum count

After grouping, determine the maximum number of stations on any street by checking the size of each group in all hash maps.

4. Collect and deduplicate

Collect all stations from groups that have the maximum count, using a set to avoid duplicates if a station lies on multiple max-count streets. Return the set as the result.

Key Points to Mention

Time complexity: O(n) with a single pass over the stations, and space complexity O(n) for the hash maps and result set.
Handling ties: if multiple streets have the same maximum count, take the union of their stations, deduplicating stations that appear on multiple tied streets.
Edge cases: empty input, single station, all stations on one line, and multiple lines with the same maximum count.
Choice of hash map keys: using y, x, x-y, x+y ensures unique identification of horizontal, vertical, and both diagonal lines.
Potential optimization: instead of storing all stations in maps, first find max count, then collect stations in a second pass, but the two-pass approach still O(n).
Connection to ML: line detection is fundamental in computer vision (e.g., Hough transform) and feature engineering for geospatial data.

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