← Uber Interview Insights

Uber·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
May 2026

Summary

Uber SWE interview with a binary tree problem. Nothing too wild but the sorting logic has a few gotchas that can trip you up if you're not careful.

Questions Asked (1)

Q1

Given the root of a binary tree, return its nodes grouped by column from left to right. Within each column, nodes should appear top to bottom by row, and if two nodes share the same row and column, sort them by value.

Algorithms & Data Structures
Author's notes

The column grouping part I got pretty quickly with a BFS and tracking offsets.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a BFS traversal to process nodes level by level, tracking each node's column index. Store nodes in a map keyed by column, and within each column, maintain a list sorted by row and then by value. Finally, extract the columns in sorted order and return the grouped nodes.

Pro tip: Clarify the tie-breaking rule upfront: if two nodes share the same row and column, sort by value. Also, mention that you can use a TreeMap to keep columns sorted, but if columns are sparse, a hash map with sorting at the end may be more efficient.

1. Understand the problem and edge cases

Restate the problem to ensure clarity: group nodes by column, order top-to-bottom by row, and sort by value for ties. Consider edge cases like empty tree, single node, and nodes with same row/column.

2. Choose traversal and data structures

Use BFS (level-order) to naturally process nodes top-to-bottom. Use a hash map (or TreeMap) to map column indices to a list of (row, value) pairs, and a queue for BFS.

3. Traverse and record node positions

During BFS, for each node, record its column and row (level). Add the node's value to the map under its column, storing row and value. For left child, column-1; for right child, column+1.

4. Sort and group nodes

After traversal, for each column, sort the list of (row, value) pairs by row, then by value. Then collect the values in order.

5. Return the result

Extract columns in sorted order (if using hash map, sort keys) and return a list of lists, each containing the node values for that column.

Key Points to Mention

  • BFS traversal ensures nodes are processed top-to-bottom by row.
  • Use a map to group nodes by column, with column indices as keys.
  • For each column, store nodes as (row, value) pairs to handle sorting.
  • Sort within each column by row first, then by value for ties.
  • Consider using TreeMap for automatic column sorting or sort keys at the end.
  • Time complexity: O(N log N) due to sorting, space complexity: O(N).

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