Katkat
Back

Implement worker time and payroll tracker

InstacartSoftware Engineer · Online Assessment
HardSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests your ability to manage overlapping time intervals, perform efficient lookups on historical state changes, and calculate cumulative payroll based on dynamic shift rates.

Problem Statement

You are building a payroll engine for a gig-economy platform. You need to implement a class PayrollTracker that manages worker shifts and calculates earnings based on a dynamic hourly rate. Workers can clock in/out multiple times, and their hourly wage may change over time.

Implement the following methods:

  1. update_rate(time_t, hourly_rate): Sets the worker's base hourly rate starting at time_t (inclusive) until a new rate is set.
  2. log_shift(start_time, end_time): Records a completed shift from start_time to end_time (exclusive). Shifts may be recorded out of chronological order.
  3. get_total_pay(): Returns the total earnings for the worker based on all logged shifts and their corresponding rates at the time of the shift.

Constraints

  • time_t is a non-negative integer representing seconds since an epoch.
  • hourly_rate is a positive float.
  • Number of operations: up to 10^5.
  • Shifts may overlap with rate change intervals.

Example

# Timeline:
# 0-10: Rate 10.0
# 10-inf: Rate 20.0

tracker = PayrollTracker()
tracker.update_rate(0, 10.0)
tracker.update_rate(10, 20.0)
tracker.log_shift(5, 15) 
# Shift 5-10: (5 hours * 10.0) = 50.0
# Shift 10-15: (5 hours * 20.0) = 100.0
# Total: 150.0

Hints

Hint 1

Store the rate changes in a sorted structure, such as a balanced BST or a list of tuples, to enable logarithmic time lookups of the rate at any given timestamp.

Hint 2

When calculating pay for a shift, use binary search (e.g., bisect_right in Python) to find all rate intervals that intersect with the [start, end) shift window.

Hint 3

Consider pre-calculating or caching the total pay if the number of `get_total_pay` calls is high, or maintain a running total using a segment tree if updates are frequent.

Follow-up questions

  • How would you modify your implementation to handle 'retroactive' rate changes where a rate is updated for a time in the past?
  • If the system needs to support multiple workers, how would your data structure scale to handle millions of shifts?
  • How would you calculate the payroll if there were 'multiplier' zones (e.g., 1.5x pay on weekends) added to the base hourly rate?