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 Take-home Project rounds at Amazon.

What role is this question designed for?

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

Design faster delay-time computation | Amazon Coding Question

Design faster delay-time computation

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

You are given an array of integers representing task priorities. Tasks execute from right to left. For each index i, define its delay time as j - i where j is the largest index > i such that priorities[j] < priorities[i] (i.e., the rightmost strictly smaller element to the right); if no such j exists, the delay time is 0. Return the delay time array for all indices. Example: for [8,2,11,4,9,4,7], the result is [6,0,4,0,2,0,0] (for 8 at index 0, the first smaller when scanning from the far right is 7 at index 6, so delay time is 6). Design an algorithm faster than O(n^ 2); describe your data structures, analyze time and space complexity, and implement the solution. Handle duplicates and large inputs.

Quick Answer: This question evaluates a candidate's ability to design efficient array algorithms and appropriate data structures for nearest-smaller-element queries, assessing performance, correctness with duplicates, and scalability to large inputs.

You are given an array of integers `priorities` representing task priorities. Tasks execute conceptually from right to left. For each index `i`, define its **delay time** as `j - i`, where `j` is the **largest** index `j > i` such that `priorities[j] < priorities[i]` (i.e., the *rightmost* strictly-smaller element to the right of `i`). If no such `j` exists, the delay time is `0`. Return the array of delay times for every index. Example: for `[8, 2, 11, 4, 9, 4, 7]` the answer is `[6, 0, 4, 0, 2, 0, 0]`. For the `8` at index 0, scanning from the far right the first element strictly smaller than 8 is `7` at index 6, so its delay time is `6 - 0 = 6`. Design an algorithm faster than O(n^2). Describe your data structures, analyze time and space complexity, and handle duplicates and large inputs. **Approach (O(n log n)):** Coordinate-compress the values to dense ranks. Build a segment tree indexed by rank that stores, for each rank bucket, the maximum array index inserted so far. Process the array from right to left; before inserting index `i`, query the tree over all ranks strictly less than `rank(priorities[i])` for the maximum stored index — that is the rightmost smaller element to the right. The delay time is `(that index) - i` (or 0 if the query returns nothing). Then insert `(rank(priorities[i]) -> i)` and continue.

Constraints

1 <= n <= 2 * 10^5 (large inputs must be handled; O(n^2) brute force times out)
-10^9 <= priorities[i] <= 10^9
Duplicate values are allowed; equal values do NOT count as 'strictly smaller'
The delay time is based on the LARGEST (rightmost) qualifying index, not the nearest

Examples

Input: ([8, 2, 11, 4, 9, 4, 7],)

Expected Output: [6, 0, 4, 0, 2, 0, 0]

Explanation: For 8 (i=0), rightmost value < 8 to the right is 7 at index 6 -> 6. For 11 (i=2), rightmost smaller is 7 at index 6 -> 4. For 9 (i=4), rightmost smaller is 7 at index 6 -> 2. Others have no smaller element to their right.

Input: ([],)

Expected Output: []

Explanation: Empty input returns an empty result.

Input: ([5],)

Expected Output: [0]

Explanation: Single element has no element to its right, so delay is 0.

Input: ([3, 3, 3],)

Expected Output: [0, 0, 0]

Explanation: Equal values are not strictly smaller, so every delay is 0 (duplicate handling).

Input: ([1, 2, 3, 4, 5],)

Expected Output: [0, 0, 0, 0, 0]

Explanation: Strictly increasing: no element has any smaller value to its right.

Input: ([5, 4, 3, 2, 1],)

Expected Output: [4, 3, 2, 1, 0]

Explanation: Strictly decreasing: for each i the rightmost smaller value is the last index, so delay = (n-1) - i.

Input: ([2, 1, 2, 1, 2],)

Expected Output: [3, 0, 1, 0, 0]

Explanation: For the 2 at index 0 the rightmost smaller is the 1 at index 3 -> 3. For the 2 at index 2 the rightmost smaller is the 1 at index 3 -> 1. The 1s and trailing 2 have none.

Input: ([-1, -5, 0, -3, 2],)

Expected Output: [3, 0, 1, 0, 0]

Explanation: Negatives: for -1 (i=0) the rightmost smaller is -3 at index 3 -> 3. For 0 (i=2) the rightmost smaller is -3 at index 3 -> 1. -5 is the global min, and -3/2 have no smaller value to their right.

Input: ([10, 10, 5, 10, 3],)

Expected Output: [4, 3, 2, 1, 0]

Explanation: Mixed duplicates: every 10 and the 5 have the 3 at index 4 as their rightmost strictly-smaller element; delay = 4 - i for each. The trailing 3 has none.

Hints

Brute force is O(n^2): for each i scan all the way to the end for the rightmost smaller value. To beat it, avoid re-scanning by processing indices right-to-left and reusing a data structure keyed by value.
Coordinate-compress values to dense ranks so you can index a segment tree by rank instead of by raw value (values can be up to 10^9 and negative).
Maintain a segment tree over ranks where each leaf holds the maximum array index inserted so far for that rank. Processing right-to-left guarantees the tree only contains indices greater than the current i.
For index i, query the tree over the range of ranks [0, rank(priorities[i]) - 1] for the maximum stored index. That maximum index is the rightmost strictly-smaller element to the right; subtract i to get the delay (0 if the query is empty).

Quick Overview

This question evaluates a candidate's ability to design efficient array algorithms and appropriate data structures for nearest-smaller-element queries, assessing performance, correctness with duplicates, and scalability to large inputs.