Solve BST range average and merge intervals
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
1) Given a binary search tree and an inclusive range [L, R], compute both the sum and the average of all node values where L <= val <= R. Use the BST property to prune traversal. Implement sumAndAverageInRange(root, L, R) -> (sum: int, average: float). Specify how to handle the case when no nodes fall in the range, and analyze time/space complexity.
2) Given two lists of intervals A and B, each list sorted by start time in ascending order (intervals are [start, end] with start <= end), merge them into a single list of non-overlapping intervals covering all intervals from A ∪ B. Clarify whether touching intervals (e.g., [1,3] and [3,5]) should be merged, handle potentially overlapping intervals within and across lists, implement mergeTwoSortedIntervalLists(A, B), and analyze complexity.
Quick Answer: This question evaluates understanding of binary search tree properties and range-based traversal pruning for computing aggregates, together with techniques for merging two sorted interval lists into non-overlapping ranges, testing proficiency with tree and interval data structures and aggregate computation in the Coding & Algorithms domain.