How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Rippling.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Rippling during technical interviews.

Implement a balance tracker and interval merger

Quick Overview

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.

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.

Input: [('ADD', 'a', 7), ('ADD', 'a', 3), ('ADD', 'b', -4), ('BALANCE', 'a'), ('BALANCE', 'b'), ('TOTAL',)]

Expected Output: [10, -4, 6]

Explanation: Driver a ends with 10, driver b ends with -4, and the total is 6.

Input: []

Expected Output: []

Explanation: No operations means no query answers.

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.

Input: []

Expected Output: []

Explanation: No intervals to merge.

Input: [[5, 7]]

Expected Output: [[5, 7]]

Explanation: A single interval remains unchanged.

Input: [[6, 8], [1, 9], [2, 4], [4, 7]]

Expected Output: [[1, 9]]

Explanation: All intervals are contained within or overlap with [1, 9].

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.

Quick Overview