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

Intermediate

May 2026

Summary

Meta software engineering interview with two coding/algorithm problems back to back. The tree question had some nuance around ordering guarantees that tripped me up a bit, and the interval merging one felt more straightforward but still had follow-up edge cases I wasn't fully prepared for.

Questions Asked (2)

Given the root of a binary tree, group nodes by their vertical column index (root is column 0, left child is c-1, right child is c+1). Within each column, order nodes top to bottom, and left to right when they share the same row and column. Return the columns from leftmost to rightmost. Also: compare BFS vs DFS for this problem, discuss tradeoffs, pick one and justify it, and analyze time and space complexity including edge cases like skewed or very deep trees.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The ordering constraint is what makes this annoying.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem and edge cases, then compare BFS and DFS for vertical order traversal, choose BFS with a queue storing (node, row, col), and explain how to sort nodes within each column. Finally, analyze time and space complexity, including worst-case scenarios like skewed or deep trees.

Pro tip: Mention that using a stable sort or tracking insertion order can handle the left-to-right ordering for same row and column, and that BFS naturally processes nodes top-to-bottom, reducing the need for sorting by row.

1. Clarify and Restate

Confirm the problem details: column indexing, ordering rules (top-to-bottom, left-to-right), and output format. Ask about edge cases like empty tree, single node, or duplicate columns.

2. Compare BFS and DFS

Discuss BFS: level-order traversal ensures top-to-bottom order; DFS: may require sorting by row and column. Tradeoffs: BFS uses O(width) space, DFS uses O(height) space; BFS simpler for ordering.

3. Choose and Justify

Pick BFS because it naturally processes nodes level by level, ensuring top-to-bottom order within columns. For left-to-right, process left child before right child and use a stable sort or track insertion order.

4. Outline Algorithm

Use a queue for BFS, store (node, row, col). Use a hash map mapping column to list of (row, value). After traversal, sort each column's list by row (and insertion order for ties), then output columns in sorted order.

5. Analyze Complexity and Edge Cases

Time: O(N log N) due to sorting, or O(N) if using ordered map and stable insertion. Space: O(N) for storing nodes. Edge cases: skewed tree (O(N) space for BFS), deep tree (recursion depth for DFS), empty tree.

Key Points to Mention

BFS ensures top-to-bottom order naturally; DFS requires sorting by row.
Use a hash map (or TreeMap) to group nodes by column, and sort within columns by row and then by insertion order for left-to-right.
Time complexity: O(N log N) with sorting; can be O(N) with ordered map and careful insertion.
Space complexity: O(N) for storing nodes; BFS queue can be O(N) in worst case (skewed tree), DFS recursion stack O(N) for skewed tree.
Edge cases: empty tree, single node, skewed tree (all left or all right), very deep tree (stack overflow risk with DFS).
Tradeoff: BFS uses more memory for wide trees, DFS uses more memory for deep trees; BFS simpler for ordering.

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

You're given a list of half-open intervals representing meeting times in a day. Merge all overlapping or adjacent intervals and return a sorted, condensed schedule. Describe an O(n log n) solution for unsorted input and a single-pass O(n) approach if the input is pre-sorted. Cover data structures, how you handle zero-length intervals and whether endpoints are inclusive or exclusive, and give complexity for both.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

Felt pretty solid on the sort-then-merge path.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the interval semantics (half-open, zero-length) and then present two solutions: sort-then-merge for O(n log n) and a single-pass merge for pre-sorted input. Walk through the algorithm with a concrete example, emphasizing edge cases and complexity.

Pro tip: Explicitly state that you treat intervals as half-open [start, end) so adjacent intervals like [1,2) and [2,3) merge, and zero-length intervals are preserved as points. This shows attention to detail and avoids ambiguity.

1. Clarify assumptions and edge cases

Confirm that intervals are half-open [start, end), so adjacent intervals merge. Discuss handling of zero-length intervals (e.g., [t,t)) and empty input.

2. Describe the O(n log n) approach for unsorted input

Sort intervals by start time, then iterate and merge overlapping/adjacent intervals into a result list. Explain why sorting is necessary and how merging works.

3. Describe the O(n) single-pass approach for pre-sorted input

If input is already sorted by start, merge in one pass without sorting. Emphasize that this is optimal for sorted data.

4. Analyze complexity and discuss trade-offs

State time and space complexity for both approaches. Mention that O(n log n) is optimal for unsorted input due to the sorting lower bound, and O(n) is optimal for sorted input.

5. Walk through an example and edge cases

Use a small example to illustrate merging, including adjacent intervals and zero-length intervals. Confirm the output is sorted and condensed.

Key Points to Mention

Half-open intervals [start, end) mean adjacent intervals (end == next start) should merge.
Zero-length intervals [t, t) represent a point in time and should be preserved as separate intervals unless they overlap with others.
Sorting by start time is the key step for unsorted input; use a stable sort if needed.
Merging condition: if current interval's start <= last merged interval's end, they overlap or are adjacent; update the end to max(end, current end).
Time complexity: O(n log n) for unsorted (dominated by sorting), O(n) for pre-sorted; space complexity O(n) for output.
Edge cases: empty input, single interval, all intervals overlapping, intervals with same start times.

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