PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

This question evaluates skills in designing in-memory data structures and algorithms for temporal event handling, interval arithmetic, stateful toggles, deferred updates (queued promotions), ranking queries, and time-based payroll computation within the Coding & Algorithms domain.

  • hard
  • Instacart
  • Coding & Algorithms
  • Software Engineer

Implement worker time and payroll tracker

Company: Instacart

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Take-home Project

You are building an in-memory worker management module. Each worker has metadata and a history of office attendance intervals. Implement the following operations. ## Data model Each worker has: - `workerId` (string or int, unique) - `title` (string) - `salary` (number): assume this is a pay rate per unit time (e.g., dollars per hour). Pay is accrued **only while the worker is in the office**. Time is given as an integer timestamp (monotonic within a single worker’s timeline). Attendance is tracked by **toggling** in/out: - If the worker is currently **out** of office, a timestamp passed to `registerTime` is the **start** of a new in-office interval. - If the worker is currently **in** the office, a timestamp passed to `registerTime` is the **end** of the current in-office interval. Assume inputs are valid unless otherwise stated, but your design should define behavior clearly for edge cases. ## Operations to implement ### 1) Basic attendance 1. `addWorker(workerId, title, salary)` 2. `registerTime(workerId, timestamp)` - Uses the toggle rule above to start/end an interval. 3. `getTotalInOfficeTime(workerId) -> totalTime` - Returns the worker’s **total accumulated time** in office across all completed intervals. ### 2) Ranking by time in office 4. `topNByInOfficeTime(n) -> list` - Returns the top `n` workers ranked by **total accumulated in-office time**. 5. `topNByInOfficeTimeForTitle(n, title) -> list` - Same as above, but only among workers whose **current title** matches `title`. Define your output format (e.g., list of `(workerId, totalTime)`), and specify tie-breaking. ### 3) Promotions with deferred effect 6. `promote(workerId, newTitle, newSalary)` - A promotion is allowed to be **applied only when the worker is out of the office**. - If the worker is currently **in** the office, the promotion must be queued and will be applied **the next time the worker enters the office** (i.e., at the next start timestamp). - Multiple promotions may be queued for the same worker, but **only the most recent queued promotion matters** (older queued promotions are discarded/overwritten). ### 4) Payroll query 7. `getPay(workerId, startTime, endTime) -> pay` - Returns the worker’s **total pay earned within** the time window `[startTime, endTime)`. - Pay is computed as: for each in-office interval, take its overlap with `[startTime, endTime)` and multiply the overlap duration by the salary rate that was effective during that time. - Promotions change the effective salary (and title) starting at the moment they are applied (per the deferred-effect rule above). ## Notes / constraints to clarify in your design - Whether `registerTime` timestamps are guaranteed non-decreasing per worker. - Whether incomplete intervals (worker currently in office) should be counted by `getTotalInOfficeTime` or `getPay`. - How to handle unknown `workerId`, duplicate `addWorker`, and `startTime >= endTime`. - Expected time complexity targets for each operation (especially `topN*` and `getPay`).

Quick Answer: This question evaluates skills in designing in-memory data structures and algorithms for temporal event handling, interval arithmetic, stateful toggles, deferred updates (queued promotions), ranking queries, and time-based payroll computation within the Coding & Algorithms domain.

Part 1: Basic Attendance Tracker

Implement the basic attendance portion of an in-memory worker tracker. Each worker has a unique workerId, a title, a salary, and attendance state. Calling registerTime toggles the worker between out of office and in office. If the worker is out, the timestamp starts a new interval. If the worker is in, the timestamp closes the current interval. Only completed intervals count toward total in-office time.

Constraints

  • 0 <= len(operations) <= 100000
  • workerId and title are non-empty strings
  • 0 <= salary <= 1000000
  • 0 <= timestamp <= 1000000000
  • registerTime timestamps are non-decreasing for each worker
  • The accumulated total time for any worker fits in a signed 64-bit integer

Examples

Input: ([['addWorker', 'alice', 'Engineer', '50'], ['registerTime', 'alice', '10'], ['registerTime', 'alice', '25'], ['getTotalInOfficeTime', 'alice']],)

Expected Output: [15]

Explanation: Alice has one completed interval [10, 25), so her total is 15.

Input: ([['addWorker', 'bob', 'Analyst', '30'], ['registerTime', 'bob', '0'], ['registerTime', 'bob', '10'], ['registerTime', 'bob', '20'], ['getTotalInOfficeTime', 'bob'], ['registerTime', 'bob', '30'], ['getTotalInOfficeTime', 'bob']],)

Expected Output: [10, 20]

Explanation: After [0, 10), Bob has 10. The open interval starting at 20 is not counted until it closes at 30.

Input: ([['getTotalInOfficeTime', 'ghost'], ['registerTime', 'ghost', '5'], ['addWorker', 'a', 'Dev', '10'], ['addWorker', 'a', 'Lead', '100'], ['registerTime', 'a', '5'], ['getTotalInOfficeTime', 'a']],)

Expected Output: [0, 0]

Explanation: Unknown workers return 0. The duplicate addWorker is ignored. Worker a is currently in office, so the open interval is not counted.

Input: ([['addWorker', 'z', 'Dev', '1'], ['registerTime', 'z', '7'], ['registerTime', 'z', '7'], ['getTotalInOfficeTime', 'z']],)

Expected Output: [0]

Explanation: A zero-length completed interval contributes 0 time.

Input: ([],)

Expected Output: []

Explanation: No operations means no query results.

Hints

  1. Store each worker's current state: whether they are in office, the current start timestamp, and total completed time.
  2. Do not add time when an interval starts. Add timestamp - start only when an interval closes.

Part 2: Ranking Workers by Time in Office

Extend the basic attendance tracker with ranking queries. Workers are ranked by total accumulated in-office time from completed intervals only. A worker currently in office does not receive credit for the open interval until it is closed. Ranking ties are broken by lexicographically smaller workerId.

Constraints

  • 0 <= len(operations) <= 100000
  • workerId and title are non-empty strings
  • 0 <= salary <= 1000000
  • 0 <= timestamp <= 1000000000
  • registerTime timestamps are non-decreasing for each worker
  • Duplicate addWorker commands are ignored
  • registerTime for an unknown worker is ignored

Examples

Input: ([['addWorker', 'a', 'Engineer', '50'], ['registerTime', 'a', '0'], ['registerTime', 'a', '10'], ['addWorker', 'b', 'Engineer', '40'], ['registerTime', 'b', '0'], ['registerTime', 'b', '5'], ['addWorker', 'c', 'Manager', '60'], ['registerTime', 'c', '2'], ['registerTime', 'c', '12'], ['topNByInOfficeTime', '2'], ['topNByInOfficeTimeForTitle', '3', 'Engineer']],)

Expected Output: [['a:10', 'c:10'], ['a:10', 'b:5']]

Explanation: a and c tie at 10, so workerId decides their order. The title-filtered query includes only Engineers.

Input: ([['addWorker', 'b', 'Dev', '1'], ['addWorker', 'a', 'Dev', '1'], ['topNByInOfficeTime', '5']],)

Expected Output: [['a:0', 'b:0']]

Explanation: n is larger than the number of workers. Both have 0 time, so lexicographic workerId order is used.

Input: ([['addWorker', 'x', 'Ops', '10'], ['addWorker', 'y', 'Ops', '10'], ['registerTime', 'x', '10'], ['registerTime', 'y', '1'], ['registerTime', 'y', '4'], ['topNByInOfficeTime', '2']],)

Expected Output: [['y:3', 'x:0']]

Explanation: x is currently in office, but its open interval is not counted.

Input: ([['topNByInOfficeTime', '3'], ['topNByInOfficeTimeForTitle', '2', 'Engineer']],)

Expected Output: [[], []]

Explanation: Ranking with no workers returns an empty list.

Input: ([['addWorker', 'p', 'QA', '10'], ['topNByInOfficeTime', '0'], ['topNByInOfficeTimeForTitle', '-1', 'QA']],)

Expected Output: [[], []]

Explanation: Non-positive n returns an empty ranking.

Hints

  1. The attendance bookkeeping is the same as Part 1: update total time only when an interval closes.
  2. For a straightforward solution, build the candidate list at query time and sort by (-totalTime, workerId).

Part 3: Promotions with Deferred Effect

Implement worker promotions with deferred effect. Each worker has a current effective title and salary. A promotion can be applied immediately only if the worker is out of office. If a promotion is requested while the worker is in office, it is queued and applied the next time the worker enters the office, not when they exit. If multiple promotions are queued for the same worker, only the most recent queued promotion matters.

Constraints

  • 0 <= len(operations) <= 100000
  • workerId and title are non-empty strings
  • 0 <= salary <= 1000000
  • 0 <= timestamp <= 1000000000
  • registerTime timestamps are non-decreasing for each worker
  • Duplicate addWorker commands are ignored
  • registerTime and promote for unknown workers are ignored

Examples

Input: ([['addWorker', 'a', 'Dev', '50'], ['promote', 'a', 'Senior', '80'], ['getWorkerInfo', 'a'], ['registerTime', 'a', '5'], ['getWorkerInfo', 'a']],)

Expected Output: ['Senior:80:out', 'Senior:80:in']

Explanation: Because a is out of office, the promotion applies immediately.

Input: ([['addWorker', 'a', 'Dev', '50'], ['registerTime', 'a', '0'], ['promote', 'a', 'Lead', '70'], ['getWorkerInfo', 'a'], ['registerTime', 'a', '10'], ['getWorkerInfo', 'a'], ['registerTime', 'a', '20'], ['getWorkerInfo', 'a'], ['getTotalInOfficeTime', 'a']],)

Expected Output: ['Dev:50:in', 'Dev:50:out', 'Lead:70:in', '10']

Explanation: The promotion requested while in office is queued. It is not applied on exit at 10, but it is applied when a enters again at 20.

Input: ([['addWorker', 'a', 'D', '1'], ['registerTime', 'a', '0'], ['promote', 'a', 'M', '2'], ['promote', 'a', 'Dir', '3'], ['registerTime', 'a', '5'], ['registerTime', 'a', '8'], ['getWorkerInfo', 'a']],)

Expected Output: ['Dir:3:in']

Explanation: The second queued promotion overwrites the first queued promotion.

Input: ([['addWorker', 'a', 'Dev', '10'], ['registerTime', 'a', '0'], ['promote', 'a', 'Lead', '20'], ['registerTime', 'a', '5'], ['promote', 'a', 'Principal', '30'], ['getWorkerInfo', 'a'], ['registerTime', 'a', '8'], ['getWorkerInfo', 'a']],)

Expected Output: ['Principal:30:out', 'Principal:30:in']

Explanation: After a exits, a new promotion while out of office applies immediately and clears the older pending promotion.

Input: ([],)

Expected Output: []

Explanation: No operations means no query results.

Hints

  1. Keep a pending promotion field per worker. While the worker is in office, promote overwrites this field instead of changing current title and salary.
  2. When registerTime starts a new interval, first apply and clear any pending promotion, then mark the worker as in office.

Part 4: Payroll Query with Effective Salaries

Implement payroll queries for an in-memory worker tracker. Pay is earned only during completed in-office intervals. For each completed interval, use the salary rate that was effective when that interval started. Promotions while out of office apply immediately. Promotions while in office are queued and apply at the next entry timestamp, so they do not affect the current interval. getPay computes pay earned in the half-open window [startTime, endTime).

Constraints

  • 0 <= len(operations) <= 100000
  • workerId and title are non-empty strings
  • 0 <= salary <= 1000000
  • 0 <= timestamp, startTime, endTime <= 1000000000
  • registerTime timestamps are non-decreasing for each worker
  • Duplicate addWorker commands are ignored
  • registerTime and promote for unknown workers are ignored
  • Total pay for any query fits in a signed 64-bit integer

Examples

Input: ([['addWorker', 'a', 'Dev', '10'], ['registerTime', 'a', '0'], ['registerTime', 'a', '10'], ['getPay', 'a', '0', '10'], ['getPay', 'a', '5', '15'], ['getPay', 'a', '10', '20']],)

Expected Output: [100, 50, 0]

Explanation: The completed interval is [0, 10) at rate 10. Only overlaps with the query window are paid.

Input: ([['addWorker', 'a', 'Dev', '10'], ['registerTime', 'a', '0'], ['registerTime', 'a', '5'], ['promote', 'a', 'Senior', '20'], ['registerTime', 'a', '10'], ['registerTime', 'a', '15'], ['getPay', 'a', '0', '20'], ['getPay', 'a', '5', '12']],)

Expected Output: [150, 40]

Explanation: The first interval pays 5*10 = 50. The promotion while out applies immediately, so [10, 15) pays 5*20 = 100.

Input: ([['addWorker', 'a', 'Dev', '10'], ['registerTime', 'a', '0'], ['promote', 'a', 'Senior', '20'], ['registerTime', 'a', '10'], ['getPay', 'a', '0', '20'], ['registerTime', 'a', '20'], ['registerTime', 'a', '25'], ['getPay', 'a', '0', '30'], ['getPay', 'a', '12', '22']],)

Expected Output: [100, 200, 40]

Explanation: The promotion requested during [0, 10) is deferred. It applies when a enters at 20, so [20, 25) uses rate 20.

Input: ([['addWorker', 'x', 'Ops', '5'], ['registerTime', 'x', '10'], ['getPay', 'x', '0', '100'], ['getPay', 'x', '20', '10'], ['getPay', 'ghost', '0', '10']],)

Expected Output: [0, 0, 0]

Explanation: The open interval is incomplete, startTime >= endTime returns 0, and unknown workers return 0.

Input: ([['addWorker', 'a', 'Dev', '10'], ['registerTime', 'a', '0'], ['promote', 'a', 'T2', '20'], ['promote', 'a', 'T3', '30'], ['registerTime', 'a', '10'], ['registerTime', 'a', '15'], ['registerTime', 'a', '16'], ['getPay', 'a', '0', '20']],)

Expected Output: [130]

Explanation: Only the latest queued promotion matters. [0, 10) pays 100 and [15, 16) pays 30.

Hints

  1. Store each completed interval with its start, end, and effective salary rate.
  2. For faster getPay, maintain sorted interval end times and prefix sums of full interval pay, then compute pay before T with binary search.
Last updated: Jun 23, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Find Largest Adjacent Stock Price Change - Instacart (medium)
  • Implement an In-Memory File Storage System - Instacart (medium)
  • Decode an encoded string - Instacart (medium)
  • Evaluate an arithmetic expression - Instacart (medium)
  • Solve Two Sorted-Array Tasks - Instacart (hard)