Amazon | SDE2 | OA

Round 1

Questions: Amazon Web Services (AWS) is a cloud computing platform with multiple servers. One of the servers is assigned to serve customer requests. There are n customer requests placed sequentially in a queue, where the ith request has a maximum waiting time denoted by wait[i]. That is, if the ith request is not served within wait[i] seconds, then the request expires and it is removed from the queue. The server processes the request following the First In First Out (FIFO) principle. The 1st request is processed first, and the nth request is served last. At each second, the first request in the queue is processed. At the next second, the processed request and any expired requests are removed from the queue.

Given the maximum waiting time of each request denoted by the array wait, find the number of requests present in the queue at every second until it is empty.

Note:

• If a request is served at some time instant t, it will be counted for that instant and is removed at the next instant.
• The first request is processed at time = 0. A request expires without being processed when time = wait[i]. It must be processed while time < wait[i].

Example The number of requests is n = 4, and their maximum wait times are wait = [2, 2, 3, 1].

• time = 0 seconds, the 1st request is served. The number of requests in the queue is 4. queue = [1, 2, 3, 4].
• time = 1 second, request 1 is removed because it is processed, request 4 (wait[3] = 1) is removed because time = wait[3] = 1 which exceeds its maximum waiting time. Also, request 2 is served. The number of requests in the queue at time = 1 seconds is 2. queue = [2, 3].
• time = 2 seconds, request 2 is removed because it is processed, request 3 is served. The number of requests in the queue is 1. queue = [3].
• time = 3 seconds, request 3 is removed because it is processed. The number of requests in the queue is 0. queue = [empty].

The answer is [4, 2, 1, 0].

Function Description Complete the function findRequestsInQueue in the editor below.

findRequestsInQueue has the following parameter:

• int wait[n]: the maximum waiting time of each request

Returns int[]: the number of requests in the queue at each instant until the queue becomes empty.

Constraints

• 1 ≤ n ≤ 10^5
• 1 ≤ wait[i] ≤ 10^5

Sample Case 0 Sample Input For Custom Testing

STDIN        Function
-----        ------
4       →    wait[] size n = 4
3       →    wait = [3, 1, 2, 1]
1
2
1

Sample Output

4
1
0

Explanation

• time = 0 seconds, request 1 is served. The number of requests in the queue is 4, queue = [3,1,2,1].
• time = 1 second, request 1 is removed because it is processed, requests 2 and 4 are removed because time exceeds their maximum waiting time, which is wait[1] = wait[3] = 1. Finally request 3 is served. The number of requests in the queue is 1. queue = [3].
• time = 2 seconds, request 3 is removed because it is processed. The number of requests in the queue is 0. queue = [empty].

Sample Case 1 Sample Input For Custom Testing

STDIN        Function
-----        ------
3       →    wait[] size n = 3
4       →    wait = [4, 4, 4]
4
4

Sample Output

3
2
1
0

Explanation

• time = 0 seconds, request 1 is served. queue = [1, 2, 3].
• time = 1 second, request 1 is removed because it is processed, request 2 is served. queue = [2, 3].
• time = 2 seconds, request 2 is removed because it is processed. The number of requests in the queue is 0. queue = [empty].

Working Solution (5/10 test cases passed)

public static List<Integer> processRequests(int[] wait) {
    // Create a queue to store the remaining wait times for each request
    Queue<Integer> queue = new LinkedList<>();

    // Add all requests' wait times to the queue
    for (int w : wait) {
        queue.offer(w);
    }

    int second = 0;
    List<Integer> result = new ArrayList<>();

    // Process the queue until it becomes empty
    while (!queue.isEmpty()) {
        // Print the current number of requests in the queue
        result.add(queue.size());

        // Process the first request (remove it at the next second)
        int firstRequestWaitTime = queue.poll(); // Fetch the first request

        // Decrease the waiting time of the remaining requests by 1
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            int updatedWait = queue.poll() - 1; // Decrease wait time by 1
            
            // If the updated wait time is still valid (i.e., > 0), put it back in the queue
            if (updatedWait > 0) {
                queue.offer(updatedWait);
            }
        }

        second++; // Move to the next second
    }
    result.add(0);
    return result;
}