How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Meta.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

Solve tree traversal and two-pointer problems

Quick Overview

Solve tree traversal and two-pointer problems evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

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: Solve tree traversal and two-pointer problems evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Vertical Order Traversal of a Binary Tree

Given a binary tree (provided as a level-order array `tree` using `null`/`None` for missing children, LeetCode-style), return the vertical order traversal of its node values. Group node values by their column index, where the root is column 0, a left child is `column - 1`, and a right child is `column + 1`. Return a list of columns ordered from the leftmost column to the rightmost column. Within a single column, order nodes first by their row (depth, smaller depth first); for nodes that share the same row and column, preserve their left-to-right order of appearance during the traversal. State the time and space complexity. Follow-up: how would you support streaming insertions and repeated column queries? Example: `tree = [3,9,20,null,null,15,7]` returns `[[9],[3,15],[20],[7]]`.

Constraints

0 <= number of nodes <= 10^4
Node values fit in a 32-bit signed integer
tree is a valid level-order encoding where every present node lists both child slots (None for missing)

Examples

Input: ([3,9,20,None,None,15,7],)

Expected Output: [[9], [3, 15], [20], [7]]

Explanation: Columns -1..2: [9],[3,15],[20],[7]. Node 3 (col 0,row 0) precedes 15 (col 0,row 2).

Input: ([1,2,3,4,5,6,7],)

Expected Output: [[4], [2], [1, 5, 6], [3], [7]]

Explanation: Column 0 holds root 1 (row0), then 5 and 6 (both row2); 5 appears before 6 in BFS so it comes first.

Input: ([],)

Expected Output: []

Explanation: Empty tree yields no columns.

Input: ([1],)

Expected Output: [[1]]

Explanation: Single node sits in column 0.

Input: ([1,2,3,4,6,5,7],)

Expected Output: [[4], [2], [1, 6, 5], [3], [7]]

Explanation: In column 0, node 6 (left child of 2) is visited before node 5 (right child of 3) in BFS, preserving left-to-right appearance.

Hints

Track a (column, row) coordinate for every node: root is (0,0); a left child is (col-1, row+1), a right child is (col+1, row+1).
Use BFS so that nodes are visited top-to-bottom and left-to-right, giving you a natural tie-break order for same (row, column) nodes.
Bucket nodes by column, then emit columns in increasing column index; within a column sort by (row, appearance order).

Binary Tree Right Side View

Given a binary tree (provided as a level-order array `tree` using `null`/`None` for missing children, LeetCode-style), imagine standing on the right side of the tree. Return the values of the nodes visible from the right side, ordered from top to bottom. A node is visible from the right at a given depth if it is the last (rightmost) node reached at that depth. Missing children simply produce no node at that position. Provide both a BFS solution (take the last node of each level) and a DFS solution (visit right subtree first, record the first node seen at each new depth); both run in O(n) time. Example: `tree = [1,2,3,null,5,null,4]` returns `[1,3,4]`.

Constraints

0 <= number of nodes <= 10^4
Node values fit in a 32-bit signed integer
tree is a valid level-order encoding (None for missing children)

Examples

Input: ([1,2,3,None,5,None,4],)

Expected Output: [1, 3, 4]

Explanation: Depth 0:1, depth 1 rightmost:3, depth 2 rightmost:4 (5 is hidden behind 4).

Input: ([1,None,3],)

Expected Output: [1, 3]

Explanation: Right-leaning: 1 then 3.

Input: ([],)

Expected Output: []

Explanation: Empty tree yields an empty view.

Input: ([1],)

Expected Output: [1]

Explanation: Only the root is visible.

Input: ([1,2,3,4],)

Expected Output: [1, 3, 4]

Explanation: Depth 2 has only node 4 (left child of 2), so it is the rightmost visible node at that depth.

Hints

BFS level by level: the last node you dequeue on each level is the one visible from the right.
DFS alternative: recurse right subtree before left, and record a node the first time you reach a new depth.
Missing children contribute nothing — only push real (non-None) children into the queue.

Count Unique Two-Sum Pairs in a Sorted Array

Given a sorted (ascending) integer array `nums` and an integer `target`, count the number of unique value pairs `(a, b)` with `a + b == target`, where `a` and `b` are taken from two different indices `i < j`. Two pairs are considered the same if they use the same pair of values, so duplicate values must not inflate the count — for example, with many copies of the same value the pair is counted once. Achieve O(n) time and O(1) extra space using the two-pointer technique on the sorted array, and handle duplicates robustly. Return the count. Example: `nums = [1,1,2,2,3,3]`, `target = 4` returns `2` (the value pairs `(1,3)` and `(2,2)`).

Constraints

0 <= len(nums) <= 10^5
nums is sorted in non-decreasing order
-10^9 <= nums[i], target <= 10^9

Examples

Input: ([1, 2, 3, 4, 5], 6)

Expected Output: 2

Explanation: Distinct pairs summing to 6: (1,5) and (2,4).

Input: ([1, 1, 2, 2, 3, 3], 4)

Expected Output: 2

Explanation: (1,3) and (2,2); duplicates do not add extra pairs.

Input: ([2, 2, 2, 2], 4)

Expected Output: 1

Explanation: Only the value pair (2,2), counted once.

Input: ([], 5)

Expected Output: 0

Explanation: No elements, no pairs.

Input: ([5], 5)

Expected Output: 0

Explanation: A pair needs two distinct indices.

Input: ([-3, -1, 0, 1, 2, 3], 0)

Expected Output: 2

Explanation: (-3,3) and (-1,1); there is only one 0 so (0,0) is impossible.

Input: ([1, 2, 3], 100)

Expected Output: 0

Explanation: No pair reaches the target.

Hints

Use two pointers from both ends; if the sum is too small move left in, if too large move right in.
On a match, skip ALL duplicates of the left value and ALL duplicates of the right value so each distinct value pair is counted exactly once.
When the two pointers land on equal values that sum to target (e.g. target/2), that is a single valid pair — count it once and stop.

Binary Tree Zigzag Level Order Traversal

Given a binary tree (provided as a level-order array `tree` using `null`/`None` for missing children, LeetCode-style), return its zigzag level-order traversal: the first level is read left-to-right, the next right-to-left, alternating per level. Return a list of levels, each level being the list of node values in the required direction. Discuss the trade-offs between a deque-based BFS (reverse alternate levels) and a DFS that tracks the level index. Example: `tree = [3,9,20,null,null,15,7]` returns `[[3],[20,9],[15,7]]`.

Constraints

0 <= number of nodes <= 10^4
Node values fit in a 32-bit signed integer
tree is a valid level-order encoding (None for missing children)

Examples

Input: ([3,9,20,None,None,15,7],)

Expected Output: [[3], [20, 9], [15, 7]]

Explanation: Level 0 L-to-R [3]; level 1 R-to-L [20,9]; level 2 L-to-R [15,7].

Input: ([1,2,3,4,5,6,7],)

Expected Output: [[1], [3, 2], [4, 5, 6, 7]]

Explanation: Level 1 reversed to [3,2]; level 2 left-to-right.

Input: ([],)

Expected Output: []

Explanation: Empty tree yields no levels.

Input: ([1],)

Expected Output: [[1]]

Explanation: Single root level.

Input: ([1,2,3,None,4,None,5],)

Expected Output: [[1], [3, 2], [4, 5]]

Explanation: Level 1 reversed to [3,2]; level 2 is [4,5] left-to-right (4 from node 2's right, 5 from node 3's right).

Hints

Do a normal BFS, collecting each level's values into a buffer.
Keep a boolean that flips every level; reverse the buffer on right-to-left levels before appending.
DFS alternative: recurse with a depth index and append to result[depth], inserting at the front when depth is odd — but BFS is usually clearer.

Quick Overview

Solve tree traversal and two-pointer problems

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Vertical Order Traversal of a Binary Tree

Constraints

0 <= number of nodes <= 10^4
Node values fit in a 32-bit signed integer
tree is a valid level-order encoding where every present node lists both child slots (None for missing)

Examples

Input: ([3,9,20,None,None,15,7],)

Expected Output: [[9], [3, 15], [20], [7]]

Explanation: Columns -1..2: [9],[3,15],[20],[7]. Node 3 (col 0,row 0) precedes 15 (col 0,row 2).

Input: ([1,2,3,4,5,6,7],)

Expected Output: [[4], [2], [1, 5, 6], [3], [7]]

Explanation: Column 0 holds root 1 (row0), then 5 and 6 (both row2); 5 appears before 6 in BFS so it comes first.

Input: ([],)

Expected Output: []

Explanation: Empty tree yields no columns.

Input: ([1],)

Expected Output: [[1]]

Explanation: Single node sits in column 0.

Input: ([1,2,3,4,6,5,7],)

Expected Output: [[4], [2], [1, 6, 5], [3], [7]]

Explanation: In column 0, node 6 (left child of 2) is visited before node 5 (right child of 3) in BFS, preserving left-to-right appearance.

Hints

Track a (column, row) coordinate for every node: root is (0,0); a left child is (col-1, row+1), a right child is (col+1, row+1).
Use BFS so that nodes are visited top-to-bottom and left-to-right, giving you a natural tie-break order for same (row, column) nodes.
Bucket nodes by column, then emit columns in increasing column index; within a column sort by (row, appearance order).

Binary Tree Right Side View

Constraints

0 <= number of nodes <= 10^4
Node values fit in a 32-bit signed integer
tree is a valid level-order encoding (None for missing children)

Examples

Input: ([1,2,3,None,5,None,4],)

Expected Output: [1, 3, 4]

Explanation: Depth 0:1, depth 1 rightmost:3, depth 2 rightmost:4 (5 is hidden behind 4).

Input: ([1,None,3],)

Expected Output: [1, 3]

Explanation: Right-leaning: 1 then 3.

Input: ([],)

Expected Output: []

Explanation: Empty tree yields an empty view.

Input: ([1],)

Expected Output: [1]

Explanation: Only the root is visible.

Input: ([1,2,3,4],)

Expected Output: [1, 3, 4]

Explanation: Depth 2 has only node 4 (left child of 2), so it is the rightmost visible node at that depth.

Hints

BFS level by level: the last node you dequeue on each level is the one visible from the right.
DFS alternative: recurse right subtree before left, and record a node the first time you reach a new depth.
Missing children contribute nothing — only push real (non-None) children into the queue.

Count Unique Two-Sum Pairs in a Sorted Array

Constraints

0 <= len(nums) <= 10^5
nums is sorted in non-decreasing order
-10^9 <= nums[i], target <= 10^9

Examples

Input: ([1, 2, 3, 4, 5], 6)

Expected Output: 2

Explanation: Distinct pairs summing to 6: (1,5) and (2,4).

Input: ([1, 1, 2, 2, 3, 3], 4)

Expected Output: 2

Explanation: (1,3) and (2,2); duplicates do not add extra pairs.

Input: ([2, 2, 2, 2], 4)

Expected Output: 1

Explanation: Only the value pair (2,2), counted once.

Input: ([], 5)

Expected Output: 0

Explanation: No elements, no pairs.

Input: ([5], 5)

Expected Output: 0

Explanation: A pair needs two distinct indices.

Input: ([-3, -1, 0, 1, 2, 3], 0)

Expected Output: 2

Explanation: (-3,3) and (-1,1); there is only one 0 so (0,0) is impossible.

Input: ([1, 2, 3], 100)

Expected Output: 0

Explanation: No pair reaches the target.

Hints

Use two pointers from both ends; if the sum is too small move left in, if too large move right in.
On a match, skip ALL duplicates of the left value and ALL duplicates of the right value so each distinct value pair is counted exactly once.
When the two pointers land on equal values that sum to target (e.g. target/2), that is a single valid pair — count it once and stop.

Binary Tree Zigzag Level Order Traversal

Constraints

0 <= number of nodes <= 10^4
Node values fit in a 32-bit signed integer
tree is a valid level-order encoding (None for missing children)

Examples

Input: ([3,9,20,None,None,15,7],)

Expected Output: [[3], [20, 9], [15, 7]]

Explanation: Level 0 L-to-R [3]; level 1 R-to-L [20,9]; level 2 L-to-R [15,7].

Input: ([1,2,3,4,5,6,7],)

Expected Output: [[1], [3, 2], [4, 5, 6, 7]]

Explanation: Level 1 reversed to [3,2]; level 2 left-to-right.

Input: ([],)

Expected Output: []

Explanation: Empty tree yields no levels.

Input: ([1],)

Expected Output: [[1]]

Explanation: Single root level.

Input: ([1,2,3,None,4,None,5],)

Expected Output: [[1], [3, 2], [4, 5]]

Explanation: Level 1 reversed to [3,2]; level 2 is [4,5] left-to-right (4 from node 2's right, 5 from node 3's right).

Hints

Do a normal BFS, collecting each level's values into a buffer.
Keep a boolean that flips every level; reverse the buffer on right-to-left levels before appending.
DFS alternative: recurse with a depth index and append to result[depth], inserting at the front when depth is odd — but BFS is usually clearer.