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

IntermediatePrefer not to say

Jul 2026

Summary

Meta SWE coding round with two problems back to back. Both were algorithmic, one on BSTs and one on interval merging. Nothing behavioral, just code and complexity analysis the whole time.

Questions Asked (2)

Given a binary search tree and an inclusive range [L, R], implement a function that returns both the sum and the average of all node values that fall within that range. You should use the BST property to prune unnecessary traversal. Also handle the edge case where no nodes fall in range, and discuss time and space complexity.

Algorithms & Data Structures

Author's notes

The pruning part is what makes this interesting and also what trips people up.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use the BST property to recursively traverse only nodes that could fall within [L, R]. At each node, if its value is within range, add to sum and count, then recurse left if node.val > L and right if node.val < R. After traversal, compute average as sum/count, handling count=0 by returning (0, 0) or (0, null) as appropriate.

Pro tip: Clarify with the interviewer whether the average should be a float or if integer division is acceptable, and discuss potential overflow if sum is large. Also, mention that pruning ensures O(h + k) time where h is height and k is number of nodes in range, which is optimal.

1. Clarify requirements and edge cases

Confirm the definition of average (float vs integer), how to handle empty range (return 0 for both or null for average), and whether the tree can be empty or have duplicate values.

2. Design the recursive traversal

Write a helper function that takes a node and returns (sum, count) for the subtree. At each node, decide whether to include its value and which subtrees to explore based on BST property.

3. Implement pruning logic

If node.val < L, only recurse right; if node.val > R, only recurse left; if within [L, R], include node and recurse both sides (with further pruning).

4. Compute and return results

After traversal, if count > 0, return (sum, sum/count); else return (0, 0) or (0, null) as agreed. Discuss time and space complexity.

5. Analyze complexity and test

Explain that time is O(h + k) where h is tree height and k is number of nodes in range, and space is O(h) for recursion stack. Walk through a small example to verify.

Key Points to Mention

BST property: left subtree values < node.val < right subtree values
Pruning conditions: skip left if node.val <= L, skip right if node.val >= R
Handling empty result: return sum=0 and average=0 or null, with clear justification
Time complexity: O(h + k) where h is height and k is number of nodes in range, which is optimal
Space complexity: O(h) due to recursion stack, can be O(1) if iterative with parent pointers
Potential integer overflow when summing many large values; consider using long or discussing

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

You have two sorted lists of intervals A and B (sorted by start time). Merge them into a single list of non-overlapping intervals that covers the union of all intervals from both lists. Clarify whether touching intervals like [1,3] and [3,5] should be merged, handle overlaps both within and across lists, and analyze the complexity of your solution.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The touching intervals clarification is a small thing but they do expect you to ask.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the merging rule for touching intervals, then use a two-pointer approach to traverse both sorted lists, merging intervals into a result list while handling overlaps. Analyze time and space complexity, noting O(m+n) time and O(m+n) space for the output.

Pro tip: Explicitly state your assumption about touching intervals (e.g., merge if start <= current_end) and mention that the algorithm can be adapted if the rule differs. This shows attention to detail and adaptability.

1. Clarify requirements

Ask whether touching intervals like [1,3] and [3,5] should be merged. Confirm that the output should be a single list of non-overlapping intervals covering the union.

2. Choose approach

Use a two-pointer technique to iterate through both sorted lists simultaneously, similar to merging two sorted arrays. Maintain a result list and a current interval to merge overlaps.

3. Merge intervals

At each step, pick the interval with the smaller start time from the two lists. If it overlaps or touches the last interval in the result (based on the clarified rule), merge them by updating the end time to the maximum of the two ends. Otherwise, add it to the result.

4. Handle remaining intervals

After one list is exhausted, continue processing the remaining intervals from the other list, merging as needed with the last interval in the result.

5. Analyze complexity

State that the time complexity is O(m+n) where m and n are the lengths of the two lists, since each interval is processed once. Space complexity is O(m+n) for the output list.

Key Points to Mention

Clarify the merging condition for touching intervals (e.g., merge if start <= current_end).
Two-pointer approach leverages the sorted order of both lists.
Merge condition: if next interval's start <= current interval's end (or < if not merging touching), merge by updating end to max of ends.
Time complexity O(m+n) and space complexity O(m+n) for the output.
Edge cases: empty lists, single interval, all intervals overlapping, no overlaps.
The algorithm can be adapted if the merging rule for touching intervals is different.

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