Amazon OA SDE 2 (2024)

Round 1

Questions: Problem 1: Amazon web service 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 the maximum waiting time denoted by wait[i]. If the ith request is not served within wait[i] seconds, then the request expires and is removed from the queue. The server processes the requests following the first in first out principle. The first 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 max 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 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 max wait time are wait = {2, 2, 3, 1}.

• time = 0 sec, the first request is served. The number of requests in the queue is 4 queue = [1, 2, 3, 4].
• time = 1 sec, request 1 is removed because it is processed. Request 4 is removed because wait[3] == 1 which is done. So the number of requests in the queue is 2 now.
• time = 2 sec, request 2 is processed. So the number of requests in the queue is 1.
• time = 3 sec, request 3 is processed. So the number of requests in the queue is 0.

Output = [4, 2, 1, 0];

Constraints: 1 <= n <= 10^5 1 <= wait[i] <= 10^5

Example: wait = {3, 1, 2, 1}

Candidate's Approach

Candidate's Approach

First, adding elements in a minHeap. Iterating over wait from 0. Check the condition for the current time is less than wait[i]. If yes, reduce the current request count and also remove elements from minHeap if the element is less than or equal to the current time. Also, mark that element visited in the wait array by modifying its value to MIN_VALUE. Then add the request to the answer list. Finally, return the answer.

Code

public class AmazonServerRequest {
    public static void main(String[] args) {
        /*
            wait = {3,1,2,1}
            wait = {2,2,3,1}
            wait = {1,1,2,1}
        */

        int[] wait = {2,2,3,1};
        int[] ans = solve(wait);
        System.out.println(Arrays.toString(ans));
    }

    public static int[] solve(int[] wait) {
        int n = wait.length;
        PriorityQueue<Pair> minHeap = new PriorityQueue<>(Comparator.comparingInt(o -> o.key));
        int k = 0;
        for (int tmp : wait) {
            minHeap.add(new Pair(tmp, k));
            k++;
        }

        int time = 1;
        List<Integer> list = new ArrayList<>();
        list.add(n);
        int request = n;
        for (int i = 0; i < n; i++) {
            if (time < wait[i]) {
                wait[i] = Integer.MIN_VALUE;
                request--;

                while (true) {
                    assert minHeap.peek() != null;
                    if (!(time >= minHeap.peek().key)) break;
                    Pair p = minHeap.poll();
                    request--;
                    wait[p.value] = Integer.MIN_VALUE;
                }

                list.add(request);
                time++;
            } else if (wait[i] != Integer.MIN_VALUE) {
                wait[i] = Integer.MIN_VALUE;
                request--;
                while (!minHeap.isEmpty()) {
                    assert minHeap.peek() != null;
                    if (!(time >= minHeap.peek().key)) break;
                    Pair p = minHeap.poll();
                    if (wait[p.value] != Integer.MIN_VALUE) request--;

                    wait[p.value] = Integer.MIN_VALUE;
                }
                list.add(request);
                time++;
            }
        }

        int[] ans = new int[list.size()];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = list.get(i);
        }

        return ans;
    }

    static class Pair {
        int key, value;
        public Pair(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
}

Suggestions

Suggestions

Suggestions are open for improvements or alternative approaches.

---