Software Engineer · Full Journey · System Design

Rippling — Software Engineer ✅ Passed

Level: Unknown Level

Round: Full Journey · Type: System Design · Difficulty: 7/10 · Duration: 180 min · Interviewer: Unfriendly

Topics: System Design, Data Structures, Algorithms, Object-Oriented Programming, Heaps, Sorting, Sweep Line Algorithm, Time Complexity, Space Complexity

Location: San Francisco Bay Area

Interview date: 2026-01-20

Summary

Design Delivery Billing System

Round 1: Basic Billing Logic

Question: Implement add_driver, record_delivery, and get_total_cost methods for a food delivery app's in-memory billing service. Performance for get_total_cost must be O(1).

---

Round 2: Payment Processing

Question: Implement pay_up_to (mark deliveries as paid up to a given time) and get_unpaid_amount (return total owed). get_unpaid_amount must be O(1).

---

Round 3: Analytics (Active Drivers)

Question: Find the maximum number of unique drivers working simultaneously in the last 24 hours, considering overlapping deliveries. Use an efficient algorithm for this analytics task.

---

Details

The interview involved designing an in-memory service for a food delivery app to calculate driver payments and display live data. The system needed to handle tens of thousands of drivers, each making hundreds of deliveries per week, with delivery data arriving immediately after each job. Each driver has an hourly rate, and a driver could have multiple concurrent deliveries, with each delivery paying the full amount.

Part 1: Basic Billing Logic

I had to implement three methods:

• add_driver: Save a driver's ID and hourly rate.
• record_delivery: Save a finished delivery (driver exists, end time is in the past).
• get_total_cost: Return the total money owed for all deliveries (O(1) performance).

I used a running total to achieve O(1) complexity for get_total_cost.

Here's the code I implemented:

` from dataclasses import dataclass, field

@dataclass class Driver: driver_id: int hourly_rate: float deliveries: list = field(default_factory=list) # Storing this for later parts

class DeliveryBillingSystem: def init(self): self.drivers: dict[int, Driver] = {} self.total_cost: float = 0.0

def add_driver(self, driver_id: int, usd_hourly_rate: float) -> None:
    self.drivers[driver_id] = Driver(driver_id, usd_hourly_rate)

def record_delivery(self, driver_id: int, start_time: int, end_time: int) -> None:
    driver = self.drivers[driver_id]
    duration_hours = (end_time - start_time) / 3600.0
    payout = driver.hourly_rate * duration_hours

    # Save data for Part 2 and 3
    driver.deliveries.append({
        'start_time': start_time,
        'end_time': end_time,
        'payout': payout,
        'paid': False
    })

    # Add to running total for O(1) access
    self.total_cost += payout

def get_total_cost(self) -> float:
    return self.total_cost

`

Part 2: Payment Processing

I then needed to implement payment processing logic:

• pay_up_to(end_time): Mark deliveries finishing at or before end_time as PAID (do not pay twice, end_time is monotonic).
• get_unpaid_amount(): Return the total money currently owed (O(1)).

I used a min-heap ordered by end_time to find the oldest deliveries first.

` import heapq from dataclasses import dataclass, field from typing import Optional

@dataclass(order=True) class Delivery: end_time: int start_time: int = field(compare=False) driver_id: int = field(compare=False) payout: float = field(compare=False) paid: bool = field(default=False, compare=False)

class DeliveryBillingSystem: def init(self): self.drivers: dict[int, float] = {} # driver_id -> hourly_rate self.total_cost: float = 0.0 self.total_paid: float = 0.0 self.unpaid_heap: list[Delivery] = [] # min-heap based on end_time self.all_deliveries: list[Delivery] = [] # needed for Part 3

def add_driver(self, driver_id: int, usd_hourly_rate: float) -> None:
    self.drivers[driver_id] = usd_hourly_rate

def record_delivery(self, driver_id: int, start_time: int, end_time: int) -> None:
    hourly_rate = self.drivers[driver_id]
    duration_hours = (end_time - start_time) / 3600.0
    payout = hourly_rate * duration_hours

    delivery = Delivery(
        end_time=end_time,
        start_time=start_time,
        driver_id=driver_id,
        payout=payout
    )

    heapq.heappush(self.unpaid_heap, delivery)
    self.all_deliveries.append(delivery)
    self.total_cost += payout

def get_total_cost(self) -> float:
    return self.total_cost

def pay_up_to(self, cutoff_time: int) -> None:
    """Remove deliveries from heap if end_time <= cutoff_time."""
    while self.unpaid_heap and self.unpaid_heap[0].end_time <= cutoff_time:
        delivery = heapq.heappop(self.unpaid_heap)
        if not delivery.paid:
            delivery.paid = True
            self.total_paid += delivery.payout

def get_unpaid_amount(self) -> float:
    return self.total_cost - self.total_paid

`

Part 3: Analytics (Active Drivers)

Finally, I had to find the maximum number of unique drivers working at the exact same time in the last 24 hours. I used a merge & sweep strategy:

1. Filter deliveries to the last 24 hours.
2. Merge overlapping delivery times for each driver.
3. Treat the start and end of these blocks as events on a timeline (sweep line).
4. Sort events by time (process End events before Start events if times are equal).
5. Increment count on "Start", decrement on "End".
6. Track the maximum count seen.

` from collections import defaultdict from typing import List, Tuple

class DeliveryBillingSystem: # ... (Include methods from Part 1 and 2 here) ...

def max_simultaneous_drivers_in_past_24_hours(self, now: int) -> int:
    window_start = now - 86400  # 24 hours ago
    window_end = now

    # Step 1: Group deliveries by driver, ignore those outside the window
    driver_intervals: dict[int, list[tuple[int, int]]] = defaultdict(list)

    for delivery in self.all_deliveries:
        # Skip if no overlap with the window
        if delivery.end_time <= window_start or delivery.start_time >= window_end:
            continue

        # Clip times to fit inside the window
        clipped_start = max(delivery.start_time, window_start)
        clipped_end = min(delivery.end_time, window_end)
        driver_intervals[delivery.driver_id].append((clipped_start, clipped_end))

    # Step 2: Merge overlapping times for each driver
    def merge_intervals(intervals: list[tuple[int, int]]) -> list[tuple[int, int]]:
        if not intervals:
            return []
        intervals.sort()
        merged = [intervals[0]]
        for start, end in intervals[1:]:
            if start <= merged[-1][1]:  # Overlaps or touches previous interval
                merged[-1] = (merged[-1][0], max(merged[-1][1], end))
            else:
                merged.append((start, end))
        return merged

    # Step 3: Create events for the sweep line
    # Event structure: (time, type, driver_id)
    # Type 0 = End, Type 1 = Start (0 comes before 1 when sorting)
    events = []

    for driver_id, intervals in driver_intervals.items():
        merged = merge_intervals(intervals)
        for start, end in merged:
            events.append((start, 1, driver_id))   # Driver starts working
            events.append((end, 0, driver_id))     # Driver stops working

    # Sort by time. If times are equal, process End (0) before Start (1).
    events.sort()

    # Step 4: Run the sweep line
    active_drivers = set()
    max_drivers = 0

    for time, event_type, driver_id in events:
        if event_type == 1:  # Start
            active_drivers.add(driver_id)
            max_drivers = max(max_drivers, len(active_drivers))
        else:  # End
            active_drivers.discard(driver_id)

    return max_drivers

`

During the interview, I was asked about follow-up questions:

• How to add a function to see how much one specific driver is owed?
• Instead of the number of drivers, return the exact time window when the peak happened.
• If the analytics function is called every second, how can we make it faster (use a sliding window or cache)?
• How would you enforce a rule that says a driver cannot have more than 3 active deliveries at once?