Implement a balance tracker and interval merger
Company: Rippling
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
This screening contained two coding exercises.
**Part 1: Driver balance tracker**
You are building an in-memory ledger for a delivery platform. Each update changes the balance of a single driver.
Implement a data structure that supports:
- `apply_update(driver_id, delta)`: add `delta` to the driver's current balance
- `get_driver_balance(driver_id)`: return the current balance for one driver, or `0` if the driver has no record
- `get_total_balance()`: return the sum of balances across all drivers
The follow-up requirement is that `get_total_balance()` may be called very frequently, even inside loops, so a solution that recomputes the total from scratch on every call may be too slow. Discuss or implement an approach that keeps these operations efficient. Another follow-up asks how to support many queries of the form: "What is the cumulative total after the first `k` updates in a sequence of balance changes?"
**Part 2: Merge time ranges**
Given a list of closed intervals `[[start1, end1], [start2, end2], ...]`, merge all overlapping intervals and return the resulting list sorted by start time.
Example:
- Input: `[[1,3],[2,6],[8,10],[15,18]]`
- Output: `[[1,6],[8,10],[15,18]]`
Quick Answer: This question evaluates data-structure design and algorithmic problem-solving skills, focusing on incremental aggregation for an in-memory ledger, historical prefix-sum style queries, and merging of overlapping intervals, and it falls under the Coding & Algorithms domain.
Part 1: Delivery Driver Balance Tracker
You are building a system that tracks the balance of each delivery driver. Each operation is processed in order, and the system must answer balance queries quickly.
Implement a function that processes a list of operations:
- ('ADD', driver_id, amount): add amount to that driver's balance. The amount may be negative.
- ('BALANCE', driver_id): return the current balance of that driver.
- ('TOTAL',): return the sum of all drivers' balances.
Return the answers to all query operations in the order they appear.
A naive solution would recompute the total by summing every driver's balance on each TOTAL query, but that is too slow when TOTAL is called frequently. Design an efficient tracker.
Constraints
- 0 <= len(operations) <= 200000
- driver_id consists of printable characters and has length between 1 and 50
- -10^9 <= amount <= 10^9
- The running balances and total fit in a signed 64-bit integer
Examples
Input: [('ADD', 'd1', 10), ('ADD', 'd2', 5), ('BALANCE', 'd1'), ('TOTAL',), ('ADD', 'd1', -3), ('TOTAL',)]
Expected Output: [10, 15, 12]
Explanation: After the updates, d1 has 10, then total is 15, then d1 becomes 7 and total becomes 12.
Input: [('BALANCE', 'ghost'), ('TOTAL',)]
Expected Output: [0, 0]
Explanation: An unseen driver has balance 0, and the total is also 0.
Hints
- If TOTAL is called often, do not sum all balances each time. Keep a cached running total and update it whenever an ADD happens.
- A missing driver has balance 0, so BALANCE for an unseen driver should return 0.
Part 2: Merge Intervals
Given a list of closed intervals, merge all overlapping intervals and return the result as a list of non-overlapping intervals sorted by start time.
Two intervals overlap if the next interval starts before or exactly when the previous one ends. For example, [1, 4] and [4, 5] should be merged into [1, 5].
Constraints
- 0 <= len(intervals) <= 200000
- -10^9 <= start <= end <= 10^9
Examples
Input: [[1, 3], [2, 6], [8, 10], [15, 18]]
Expected Output: [[1, 6], [8, 10], [15, 18]]
Explanation: The first two intervals overlap and merge into [1, 6].
Input: [[1, 4], [4, 5]]
Expected Output: [[1, 5]]
Explanation: Touching closed intervals are merged.
Hints
- Sorting by interval start makes it possible to merge in one left-to-right pass.
- Compare each interval with the last merged interval. If they overlap, extend the end; otherwise, start a new merged interval.