Solve tree traversal and two-pointer problems
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Implement the following independent problems:
1) Vertical columns: Given a binary tree, return lists of node values grouped by vertical columns from leftmost to rightmost. For nodes in the same column and row, preserve left-to-right order of appearance. State time and space complexities. Follow-up: support streaming insertions and queries.
2) Right-side view: Given a binary tree, return the sequence of nodes visible from the right side. Clarify tie-breaking and how to handle missing children. Provide BFS and DFS solutions and their complexities.
3) Two-sum pairs count: Given a sorted integer array and target T, count the number of unique index pairs (i, j), i < j, such that nums[i] + nums[j] == T. Achieve O(n) time and O(
1) extra space; handle duplicates robustly.
4) Zigzag levels: Given a binary tree, output its level-order traversal with alternating left-to-right and right-to-left ordering per level. Discuss trade-offs between deque-based BFS and DFS with level tracking.
Quick Answer: This prompt evaluates proficiency in tree traversal patterns, BFS/DFS reasoning, vertical and right-side view extraction, zigzag level ordering, two-pointer techniques on sorted arrays, duplicate handling, streaming inserts/queries, and rigorous time and space complexity analysis.