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 Onsite rounds at Amazon.

What role is this question designed for?

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

Implement a Worker Hours Register | Amazon Coding Question

Implement a Worker Hours Register

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Implement an in-memory `WorkHoursRegister` system for contract workers. The system tracks office entry and exit events, completed work time, promotions, salary over time ranges, and special grant periods that double pay. Support the following operations: 1. Basic worker tracking - `add_worker(id, position, hourly_rate)`: Add a worker with the given position and hourly compensation. Return `false` if `id` already exists; otherwise return `true`. - `register(id, timestamp)`: Toggle the worker's office status. If the worker is outside the office, this starts a new work session at `timestamp`. If the worker is already inside, this ends the current session at `timestamp`. - `get(id)`: Return the worker's total completed work time. If the worker is currently inside the office, the ongoing session does not count yet. 2. Ranking - `top_n_workers(n, position)`: Return the top `n` workers for the given position, formatted as strings like `"worker_id(total_time)"`. - Sort by completed work time in descending order. If two workers have the same time, sort by `id` in lexicographic ascending order. 3. Promotions and salary - `promote(id, new_position, new_hourly_rate)`: Register a promotion request with delayed effect. - If the promotion is requested while the worker is in the office, the current session continues under the old position and old hourly rate. The new position and hourly rate take effect only the next time the worker enters the office. - `calc_salary(id, start, end)`: Compute the worker's pay earned within the time window `[start, end]` by summing, for each completed work session, the duration of overlap with the query window multiplied by the hourly rate that was active during that session. 4. Grant periods - `register_grant(start, end)`: Register a time interval during which qualifying sessions receive double pay. - Upgraded `calc_salary`: If a completed work session is fully contained within any registered grant interval, that entire session is paid at double rate. Partial overlap with a grant interval does not qualify. - `get_grant_bonus(start, end)`: The pair `(start, end)` must exactly match a previously registered grant interval. Return the total extra bonus paid across all workers for that grant interval, where the bonus is the additional one extra multiple of pay for qualifying sessions. Design suitable data structures and implement all operations efficiently.

Quick Answer: This question evaluates data structures and algorithms skills for temporal event tracking, interval arithmetic, stateful session management, ranking, and aggregate payroll computations including grant-based bonuses.

Part 1: Basic Worker Hours Register

Implement a basic in-memory register for contract workers. The system supports adding workers, toggling entry and exit events, and returning total completed work time. A work session starts when an outside worker registers and ends when an inside worker registers again. Ongoing sessions are not included in total completed time.

Constraints

1 <= len(queries) <= 100000
Worker ids and positions are non-empty strings of length at most 30.
0 <= timestamp <= 10^9.
For each worker, register timestamps are strictly increasing.
hourly_rate is an integer, 1 <= hourly_rate <= 10^6, but it is not used in this part.

Examples

Input: ([['add_worker', 'alice', 'dev', 10], ['register', 'alice', 1], ['register', 'alice', 5], ['get', 'alice']],)

Expected Output: [True, True, True, 4]

Explanation: Alice works one completed session from time 1 to 5, so her completed time is 4.

Input: ([['add_worker', 'bob', 'qa', 20], ['add_worker', 'bob', 'qa', 25], ['register', 'bob', 3], ['get', 'bob'], ['register', 'ghost', 4], ['register', 'bob', 10], ['get', 'bob']],)

Expected Output: [True, False, True, 0, False, True, 7]

Explanation: The duplicate add fails. Bob's ongoing session is not counted until he exits at time 10.

Input: ([['get', 'nobody']],)

Expected Output: [None]

Explanation: Unknown workers return None for get.

Input: ([['add_worker', 'a', 'ops', 5], ['register', 'a', 0], ['register', 'a', 2], ['register', 'a', 4], ['register', 'a', 9], ['get', 'a']],)

Expected Output: [True, True, True, True, True, 7]

Explanation: Two completed sessions contribute 2 + 5 = 7.

Hints

Keep one record per worker with inside/outside state, current entry timestamp, and completed total time.
Only add to total time when an exit event is registered; do not count an ongoing session in get.

Part 2: Ranking Workers by Completed Time

Extend the basic worker register with a ranking operation. Workers have a fixed position in this problem. top_n_workers returns the top n workers for a requested position, sorted by completed work time descending and then by id lexicographically ascending. Ongoing sessions do not contribute to the ranking until completed.

Constraints

1 <= len(queries) <= 10000
0 <= n <= number of workers.
Worker ids and positions are non-empty strings of length at most 30.
For each worker, register timestamps are strictly increasing.
Only completed sessions count toward rankings.

Examples

Input: ([['add_worker', 'b', 'dev', 10], ['add_worker', 'a', 'dev', 10], ['add_worker', 'c', 'qa', 10], ['register', 'a', 1], ['register', 'a', 6], ['register', 'b', 2], ['register', 'b', 7], ['top_n_workers', 2, 'dev']],)

Expected Output: [True, True, True, True, True, True, True, ['a(5)', 'b(5)']]

Explanation: Workers a and b both have 5 completed hours, so lexicographic id order breaks the tie.

Input: ([['add_worker', 'a', 'dev', 10], ['add_worker', 'b', 'dev', 10], ['register', 'a', 0], ['top_n_workers', 3, 'dev']],)

Expected Output: [True, True, True, ['a(0)', 'b(0)']]

Explanation: Worker a is inside, but that ongoing session is not completed, so both workers have 0.

Input: ([['add_worker', 'z', 'qa', 10], ['top_n_workers', 5, 'dev']],)

Expected Output: [True, []]

Explanation: No workers have the requested position.

Input: ([['add_worker', 'ann', 'dev', 10], ['add_worker', 'bob', 'dev', 10], ['register', 'ann', 0], ['register', 'ann', 3], ['register', 'bob', 1], ['register', 'bob', 10], ['register', 'ann', 20], ['top_n_workers', 2, 'dev'], ['get', 'ann']],)

Expected Output: [True, True, True, True, True, True, True, ['bob(9)', 'ann(3)'], 3]

Explanation: Ann's second session is ongoing and does not affect either get or top_n_workers.

Hints

Maintain completed time exactly as in the basic register.
For a top query, filter workers by position and sort using the key (-completed_time, id).

Part 3: Promotions and Salary Calculation

Implement a worker register that supports delayed promotions and salary queries. Each completed work session must remember the hourly rate active for that session. A promotion request does not affect an already running session. Instead, the pending promotion is applied the next time the worker enters the office. Salary queries sum pay earned inside a time window using overlap duration multiplied by the session's hourly rate.

Constraints

1 <= len(queries) <= 10000
0 <= timestamp, start, end <= 10^9.
For each worker, register timestamps are strictly increasing.
1 <= hourly_rate, new_hourly_rate <= 10^6.
Total number of completed sessions is at most 10000.

Examples

Input: ([['add_worker', 'a', 'dev', 10], ['register', 'a', 0], ['register', 'a', 10], ['promote', 'a', 'lead', 20], ['calc_salary', 'a', 0, 20], ['register', 'a', 20], ['register', 'a', 25], ['calc_salary', 'a', 0, 30]],)

Expected Output: [True, True, True, True, 100, True, True, 200]

Explanation: The promotion applies only when a enters at time 20. Pay is 10*10 + 5*20 = 200.

Input: ([['add_worker', 'b', 'dev', 10], ['register', 'b', 0], ['promote', 'b', 'senior', 20], ['register', 'b', 5], ['register', 'b', 10], ['register', 'b', 12], ['calc_salary', 'b', 0, 20]],)

Expected Output: [True, True, True, True, True, True, 90]

Explanation: The promotion requested during 0..5 does not affect that session. Pay is 5*10 + 2*20 = 90.

Input: ([['add_worker', 'c', 'qa', 15], ['register', 'c', 10], ['register', 'c', 20], ['calc_salary', 'c', 0, 12], ['calc_salary', 'c', 12, 18], ['calc_salary', 'c', 20, 30]],)

Expected Output: [True, True, True, 30, 90, 0]

Explanation: The salary query uses only the overlap with the completed session [10, 20).

Input: ([['calc_salary', 'missing', 0, 10], ['add_worker', 'x', 'ops', 25], ['register', 'x', 1], ['calc_salary', 'x', 0, 10], ['promote', 'ghost', 'ops2', 30]],)

Expected Output: [None, True, True, 0, False]

Explanation: Unknown salary returns None. An ongoing session is not counted.

Hints

Do not try to recompute historical rates from current worker state; store the rate on each completed session.
Apply a pending promotion only when processing a register operation that starts a new session.

Part 4: Grant Periods and Bonus Pay

Implement a worker register with delayed promotions, salary queries, and special grant intervals. If a completed session is fully contained within any registered grant interval, the qualifying part of salary calculations is paid at double rate. Partial overlap with a grant interval does not qualify. A grant bonus query asks for the total extra pay generated by sessions fully contained in one exact registered grant interval.

Constraints

1 <= len(queries) <= 2000
0 <= timestamp, start, end <= 10^9.
For each worker, register timestamps are strictly increasing.
1 <= hourly_rate, new_hourly_rate <= 10^6.
Total number of completed sessions is at most 2000.
Total number of registered grant intervals is at most 500.

Examples

Input: ([['add_worker', 'a', 'dev', 10], ['register_grant', 0, 10], ['register', 'a', 1], ['register', 'a', 5], ['calc_salary', 'a', 0, 10], ['get_grant_bonus', 0, 10]],)

Expected Output: [True, True, True, True, 80, 40]

Explanation: Session [1, 5) is fully inside grant [0, 10), so salary is 4*10*2 and bonus is the extra 4*10.

Input: ([['add_worker', 'a', 'dev', 10], ['register_grant', 0, 10], ['register', 'a', 5], ['register', 'a', 12], ['calc_salary', 'a', 0, 20], ['get_grant_bonus', 0, 10]],)

Expected Output: [True, True, True, True, 70, 0]

Explanation: The session overlaps the grant but is not fully contained, so it is not doubled.

Input: ([['add_worker', 'b', 'dev', 10], ['register_grant', 10, 20], ['register', 'b', 0], ['register', 'b', 5], ['promote', 'b', 'senior', 30], ['register', 'b', 12], ['register', 'b', 18], ['calc_salary', 'b', 0, 30], ['calc_salary', 'b', 15, 16], ['get_grant_bonus', 10, 20]],)

Expected Output: [True, True, True, True, True, True, True, 410, 60, 180]

Explanation: The first session pays 50. The promoted session [12, 18) is grant-qualified, pays 6*30*2 = 360, and contributes bonus 180.

Input: ([['register_grant', 5, 5], ['register_grant', 0, 10], ['register_grant', 0, 10], ['get_grant_bonus', 1, 10], ['add_worker', 'x', 'ops', 20], ['register', 'x', 2], ['calc_salary', 'x', 0, 10], ['get_grant_bonus', 0, 10]],)

Expected Output: [False, True, False, None, True, True, 0, 0]

Explanation: Invalid and duplicate grants fail. The exact interval [1, 10) was not registered. The ongoing session is ignored.

Hints

Grant qualification is a property of the whole completed session: grant_start <= session_start and session_end <= grant_end.
The bonus for a qualifying session is exactly its base pay, because double pay adds one extra multiple.

Implement a Worker Hours Register

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Part 1: Basic Worker Hours Register

Constraints

1 <= len(queries) <= 100000
Worker ids and positions are non-empty strings of length at most 30.
0 <= timestamp <= 10^9.
For each worker, register timestamps are strictly increasing.
hourly_rate is an integer, 1 <= hourly_rate <= 10^6, but it is not used in this part.

Examples

Input: ([['add_worker', 'alice', 'dev', 10], ['register', 'alice', 1], ['register', 'alice', 5], ['get', 'alice']],)

Expected Output: [True, True, True, 4]

Explanation: Alice works one completed session from time 1 to 5, so her completed time is 4.

Input: ([['add_worker', 'bob', 'qa', 20], ['add_worker', 'bob', 'qa', 25], ['register', 'bob', 3], ['get', 'bob'], ['register', 'ghost', 4], ['register', 'bob', 10], ['get', 'bob']],)

Expected Output: [True, False, True, 0, False, True, 7]

Explanation: The duplicate add fails. Bob's ongoing session is not counted until he exits at time 10.

Input: ([['get', 'nobody']],)

Expected Output: [None]

Explanation: Unknown workers return None for get.

Input: ([['add_worker', 'a', 'ops', 5], ['register', 'a', 0], ['register', 'a', 2], ['register', 'a', 4], ['register', 'a', 9], ['get', 'a']],)

Expected Output: [True, True, True, True, True, 7]

Explanation: Two completed sessions contribute 2 + 5 = 7.

Hints

Keep one record per worker with inside/outside state, current entry timestamp, and completed total time.
Only add to total time when an exit event is registered; do not count an ongoing session in get.

Part 2: Ranking Workers by Completed Time

Constraints

1 <= len(queries) <= 10000
0 <= n <= number of workers.
Worker ids and positions are non-empty strings of length at most 30.
For each worker, register timestamps are strictly increasing.
Only completed sessions count toward rankings.

Examples

Expected Output: [True, True, True, True, True, True, True, ['a(5)', 'b(5)']]

Explanation: Workers a and b both have 5 completed hours, so lexicographic id order breaks the tie.

Input: ([['add_worker', 'a', 'dev', 10], ['add_worker', 'b', 'dev', 10], ['register', 'a', 0], ['top_n_workers', 3, 'dev']],)

Expected Output: [True, True, True, ['a(0)', 'b(0)']]

Explanation: Worker a is inside, but that ongoing session is not completed, so both workers have 0.

Input: ([['add_worker', 'z', 'qa', 10], ['top_n_workers', 5, 'dev']],)

Expected Output: [True, []]

Explanation: No workers have the requested position.

Expected Output: [True, True, True, True, True, True, True, ['bob(9)', 'ann(3)'], 3]

Explanation: Ann's second session is ongoing and does not affect either get or top_n_workers.

Hints

Maintain completed time exactly as in the basic register.
For a top query, filter workers by position and sort using the key (-completed_time, id).

Part 3: Promotions and Salary Calculation

Constraints

1 <= len(queries) <= 10000
0 <= timestamp, start, end <= 10^9.
For each worker, register timestamps are strictly increasing.
1 <= hourly_rate, new_hourly_rate <= 10^6.
Total number of completed sessions is at most 10000.

Examples

Expected Output: [True, True, True, True, 100, True, True, 200]

Explanation: The promotion applies only when a enters at time 20. Pay is 10*10 + 5*20 = 200.

Input: ([['add_worker', 'b', 'dev', 10], ['register', 'b', 0], ['promote', 'b', 'senior', 20], ['register', 'b', 5], ['register', 'b', 10], ['register', 'b', 12], ['calc_salary', 'b', 0, 20]],)

Expected Output: [True, True, True, True, True, True, 90]

Explanation: The promotion requested during 0..5 does not affect that session. Pay is 5*10 + 2*20 = 90.

Input: ([['add_worker', 'c', 'qa', 15], ['register', 'c', 10], ['register', 'c', 20], ['calc_salary', 'c', 0, 12], ['calc_salary', 'c', 12, 18], ['calc_salary', 'c', 20, 30]],)

Expected Output: [True, True, True, 30, 90, 0]

Explanation: The salary query uses only the overlap with the completed session [10, 20).

Input: ([['calc_salary', 'missing', 0, 10], ['add_worker', 'x', 'ops', 25], ['register', 'x', 1], ['calc_salary', 'x', 0, 10], ['promote', 'ghost', 'ops2', 30]],)

Expected Output: [None, True, True, 0, False]

Explanation: Unknown salary returns None. An ongoing session is not counted.

Hints

Do not try to recompute historical rates from current worker state; store the rate on each completed session.
Apply a pending promotion only when processing a register operation that starts a new session.

Part 4: Grant Periods and Bonus Pay

Constraints

1 <= len(queries) <= 2000
0 <= timestamp, start, end <= 10^9.
For each worker, register timestamps are strictly increasing.
1 <= hourly_rate, new_hourly_rate <= 10^6.
Total number of completed sessions is at most 2000.
Total number of registered grant intervals is at most 500.

Examples

Input: ([['add_worker', 'a', 'dev', 10], ['register_grant', 0, 10], ['register', 'a', 1], ['register', 'a', 5], ['calc_salary', 'a', 0, 10], ['get_grant_bonus', 0, 10]],)

Expected Output: [True, True, True, True, 80, 40]

Explanation: Session [1, 5) is fully inside grant [0, 10), so salary is 4*10*2 and bonus is the extra 4*10.

Input: ([['add_worker', 'a', 'dev', 10], ['register_grant', 0, 10], ['register', 'a', 5], ['register', 'a', 12], ['calc_salary', 'a', 0, 20], ['get_grant_bonus', 0, 10]],)

Expected Output: [True, True, True, True, 70, 0]

Explanation: The session overlaps the grant but is not fully contained, so it is not doubled.

Expected Output: [True, True, True, True, True, True, True, 410, 60, 180]

Explanation: The first session pays 50. The promoted session [12, 18) is grant-qualified, pays 6*30*2 = 360, and contributes bonus 180.

Expected Output: [False, True, False, None, True, True, 0, 0]

Explanation: Invalid and duplicate grants fail. The exact interval [1, 10) was not registered. The ongoing session is ignored.

Hints

Grant qualification is a property of the whole completed session: grant_start <= session_start and session_end <= grant_end.
The bonus for a qualifying session is exactly its base pay, because double pay adds one extra multiple.

Quick Overview

Quick Overview