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',)]