cswork / libraryOpen practice workspace

Coding questions · Meta

Solve BST range average and merge intervals

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.

  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.

BST Range Sum and Average

Use BST pruning on level-order values to return the sum and average of values in inclusive range [L,R].

Examples

Example 1

Input: ([10,5,15,3,7,None,18], 7, 15)
Output: {'sum': 32, 'average': 10.666666666666666}

Explanation: Range includes 7,10,15.

Example 2

Input: ([5], 6, 9)
Output: {'sum': 0, 'average': None}

Explanation: No values in range.

Hints

  1. Choose a representation that makes the requested operation direct.
  2. Handle empty inputs and boundary cases first.

Merge Two Sorted Interval Lists

Merge two sorted interval lists into one non-overlapping list, merging touching intervals.

Examples

Example 1

Input: ([[1,3],[8,10]], [[2,6],[15,18]])
Output: [[1, 6], [8, 10], [15, 18]]

Explanation: Cross-list overlap.

Example 2

Input: ([[1,3]], [[3,5]])
Output: [[1, 5]]

Explanation: Touching intervals merge.

Hints

  1. Choose a representation that makes the requested operation direct.
  2. Handle empty inputs and boundary cases first.