← Meta Interview Insights

Meta·Software Engineer·Onsite - Coding / Algorithms·Intermediate

Intermediate
Jun 2026

Summary

Coding round at Meta for a software engineer role. One question, BFS-based tree problem, nothing too wild but definitely requires knowing your traversal patterns cold.

Questions Asked (1)

Q1

Given a binary tree, return its nodes grouped by vertical column, ordered from leftmost to rightmost.

Algorithms & Data Structures
Author's notes

Went with BFS and tracked column indices in a map alongside the node values.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a BFS/DFS traversal while tracking each node's horizontal distance (column index) from the root. Store nodes in a hash map keyed by column index, then sort the keys to output columns from leftmost to rightmost. Within each column, preserve top-to-bottom order (and optionally left-to-right for ties).

Pro tip: Clarify tie-breaking rules upfront (e.g., nodes at the same row and column should be ordered by value or left-to-right) and mention that you can avoid sorting by using a min/max column range if the tree is balanced. This shows attention to edge cases and optimization.

1. Clarify requirements and edge cases

Ask about tie-breaking (same row and column), empty tree, and whether order within a column matters. Confirm output format (list of lists).

2. Choose traversal and track columns

Use BFS (level order) or DFS while passing the column index (root=0, left=col-1, right=col+1). For BFS, process level by level to naturally maintain top-to-bottom order.

3. Store nodes in a map

Use a hash map where keys are column indices and values are lists of node values. Append nodes as you traverse, ensuring within-column order is correct.

4. Sort columns and build result

Sort the column keys in ascending order and collect the lists into the final result. If using a min/max range, iterate from min to max instead of sorting.

5. Analyze complexity and test

State time complexity O(N log N) due to sorting (or O(N) with range), space O(N). Walk through a small example to verify correctness.

Key Points to Mention

  • Horizontal distance concept: root at 0, left child -1, right child +1.
  • BFS vs DFS: BFS naturally preserves top-to-bottom order within columns; DFS may require sorting by depth.
  • Tie-breaking: if two nodes share the same row and column, order by value (or as specified).
  • Data structure: hash map from column index to list of node values.
  • Optimization: track min and max column to avoid sorting keys, achieving O(N) time.
  • Complexity: O(N log N) time with sorting, O(N) space; O(N) time with min/max range.

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