Question

Amazon | USA | OA | SDE1 | Coding Questions and Solutions | 2022 | Set-84

Answer 1

I had OA today, I got 3 questions to solve. I solved other two but couldn't solve this.
Pls share the solution.

 

Problem Statement
There is a door at Amazon Office which can be used only by one person at a time i. e either a person can enter from the door or exit but no two people can do it simultaneously. If two person going in the opposite direction arrived at the door at the same time then these 3 cases should be considered:-

 

If the door was not used before or it was not used in the previous second then the person who wants to exit goes first.
If the door has been used in the previous second for entering, then the person who wants to enter goes first.
If the door has been used in the previous second for exiting, then the person who wants to exist goes first.
If two people arrive at the same time and going in the same direction then the person whose name in the given list comes first will go first.

 

Note:- To cross the door, it will take exactly one second for each person.
Input
The first line of input contains a single integer N containing the number of people The second line of input contains N space- separated integers depicting the arrival time of the ith person. The last line of input containing N space- separated integers which are either 0 or 1. 0 indicates that the person wants to enter and 1 indicates he wants to exit.

 

Constraints:-
1 <= N <= 50000
0 <= Arrival[i] <= Arrival [i+1] <= 1000000000

 

Output
Print N space- separated integers denoting the time at which the ith person will cross the door.

 

Example
Sample Input:-
4
0 0 1 5
0 1 1 0

 

Sample Output:-
2 0 1 5

 

Explanation:-
At t = 0:- the first and the second person wants to enter and exit. As per case 1 2nd person will goes first.
At t=1:- the first and the 3rd person wants to enter and exit. As per case 3 the 3rd person goes first.
At t= 2:- only 1st is the only person standing so he goes.
At t = 3 and 4 no one wants to cross
At t = 5 the 4th person is the only one who wants to cross.

 

Sample Input:-
5
0 1 1 3 3
0 1 0 0 1

 

Sample Output:-
0 2 1 4 3

Answer 2

Not sure what happened to the last time this was posted, but here's the Java solution I shared to that one:

 

    public static String getDoorOrder(int N, int[] A, int[] D) {
        // N = number of people, A = arrival time, D = direction
        byte doorState = 1;
        int nCounter = 0;
        int second = 0;
        Queue<Integer> enter = new LinkedList<>();
        Queue<Integer> exit = new LinkedList<>();
        boolean waitingToEnter = false;
        boolean waitingToExit = false;
        
        while (nCounter < N || (waitingToEnter || waitingToExit)) {
            while (nCounter < N && A[nCounter] == second) {
                if (D[nCounter] == 0) {
                    enter.add(nCounter);
                } else {
                    exit.add(nCounter);
                }
                nCounter++;
            }
            
            waitingToEnter = !enter.isEmpty();
            waitingToExit = !exit.isEmpty();
            
            if (waitingToEnter && waitingToExit) {
                if (doorState == 1) {
                    A[exit.poll()] = second;
                } else {
                    A[enter.poll()] = second;
                }
            } 
            else if (waitingToEnter) {
                A[enter.poll()] = second;
                doorState &= 0;
            }
            else if (waitingToExit) {
                A[exit.poll()] = second;
                doorState |= 1;
            }
            else {
                // Nothing happened this second but we're not done processing
                // people at the door.  Reset the door back to Exit status and 
                // save iterations by jumping ahead in time to A[nCurrent] - 1
                // (minus 1 so that second++ doesn't skip us ahead erroneously).
                doorState |= 1;
                if (nCounter < N) {
                    second = A[nCounter] - 1;
                }
            }
            
            second++;
        }

        StringBuilder resultBuffer = new StringBuilder();
        for (int i = 0; i < N; i++) {
            if (i > 0) {
                resultBuffer.append(" ");
            }
            resultBuffer.append(A[i]);
        }
        
        return resultBuffer.toString();
    }