Amazon Interview Question SDE-2s
Country: India
Interview Type: In-Person
1) Take the current elevators position in an array from top to bottom (sorted order)
2) Find the floor and ceil for the user position using binary search. Take the minimum distance from user position to floor and ceil and return the appropriate index
int FindClosestElevatorUsingBinarySearch(int elevatorsPositionInOrder[],int startArray,int endArray,int key){
if(startArray > endArray){
return INT_MIN;
}
int middleIndex = (startArray + endArray)/2;
if(elevatorsPositionInOrder[middleIndex] == key){
return middleIndex;
}
if(middleIndex-1 < startArray){
if(elevatorsPositionInOrder[middleIndex] < key){
return middleIndex;
}
}
if(middleIndex+1 > endArray){
if(elevatorsPositionInOrder[middleIndex] > key){
return middleIndex;
}
}
if(elevatorsPositionInOrder[middleIndex-1] < key && elevatorsPositionInOrder[middleIndex+1] < key){
return abs(key - elevatorsPositionInOrder[middleIndex-1]) > abs(key-elevatorsPositionInOrder[middleIndex+1])?middleIndex+1:middleIndex-1;
}
if(elevatorsPositionInOrder[middleIndex] > key){
return FindClosestElevatorUsingBinarySearch(elevatorsPositionInOrder,startArray,middleIndex-1,key);
}else{
return FindClosestElevatorUsingBinarySearch(elevatorsPositionInOrder,middleIndex+1,endArray,key);
}
}
int MElevatorsNFloors(int elevatorsPositionInOrder[],int noOfElevators,int userRequest){
if(elevatorsPositionInOrder == NULL || noOfElevators == 0){
return INT_MIN;
}
return FindClosestElevatorUsingBinarySearch(elevatorsPositionInOrder,0,noOfElevators-1,userRequest);
}
The Following Code implements the above approach(avidok),in a simpler fashion plus shows the nearest elevator either ways,(up or down)
#include<stdio.h>
int abs(int x,int y)
{
return (x>y)? (x-y) : (y-x);
}
int findNearest(int queryFloor,int elevatorPos[],int start,int end)
{
int middle,pos;
do
{
middle=(end+start)/2;
if(queryFloor==elevatorPos[middle])
{
return middle;
}
else
{
if(elevatorPos[middle]<queryFloor)
{
pos=middle;
if(middle!=(M-1))
pos=(abs(queryFloor,elevatorPos[middle])<abs(queryFloor,elevatorPos[middle+1])) ? middle : middle+1;
start=middle+1;
}
else
{
pos=start;
if(start!=(M-1))
pos=(abs(queryFloor,elevatorPos[start])<abs(queryFloor,elevatorPos[start+1])) ? start : start+1;
end=middle-1;
}
}
}while(start<=end);
return pos;
}
int findMinTime(int queryFloor,int elevatorPos[],int M)
{
int pos=findNearest(queryFloor,elevatorPos,0,M-1);
return abs(queryFloor,elevatorPos[pos]);
}
int main()
{
int queryFloor=5;
int N=100;
int elevatorPos[]={1,7,44,63,81,91};
int M=6;
printf("%d seconds taken \n",findMinTime(queryFloor,elevatorPos,M));
return 0;
}
Meaning of the question --> aim should be to be able to select the closest lift to the user from the list of m lifts.
Maintaining the order of lifts -->
This will just take O(m) in the worst case. At the very beginning we have the ordered list.
Let this be in the form of a dict with keys 1-->m. value of each key will give you the name of the lift in that position and the floor position of that lift.
Whenever a lift moves from position i --> do binary search on values from i-->m (if lift was going up) or 1 --> i otherwise. Binary search(compare floor number of lift in position i/2+m/2) and so on. Stop when floor number matches or when we find the right position. Shift the order of the rest of the lifts. Here m is considered asymptotically negligible. So O(m) is practically O(1). Even otherwise, this can be done after completing the user request. So we have all the time.
Now when a user from floor i presses the lift button to go down/up -- >
let us discuss the 'up' case. --> if lowest lift is above floor i we found our lift already. similarly if highest lift is below floor i we found out lift and in O(1) in both cases. Now if its not the above 2 cases --> Do binary search on the ordered list of lifts. This can be done in O(log(m)) which cannot be asymptotically greater than O(log(n)) because in that case we can have a simple mechanism by which we can make sure we always have a dedicated lift available for a floor. (clue --> check up what asymptotically greater means.. eg O(n) asymptotically lesser than O(nlog(n))
The problem with the Obvious algos to this problem is the Worst Case O(N) time .
This maybe reduced by the following approach :
1) input N(#of floors) , input M(#of elevators) , input the User Request (q)
2)Assume The Building comprising Chunkc/blocks comprising N/M floors each .
3)create a bool array of size N/M all elems initialized to 0 .
4)Input the M positions for the elevators , one by one and 'true' the corresponding block/chunk in the above array , e.g if elevator at 56 ,where N=100 , M=5 , then block no. (56x5)/100 is set to 1, showing that this block contains an elevator .
5) Now reduce the operations onto just the block number containing the floor q .
6) if that block number not 'lit',find the nearest elevator containing block in O(log (M/N)) time .
7)if its value is 1 , then find the positions of elevator in that block No. by applying Binary Search on Array containing the M Positions of escalator with key as lowerbound of the Block Number (e.g 80 to 99 ) .
8) Now apply the Binary search approach onto finding the nearest Elevator of the Shortlisted / Pruned Elevator positions .
... I will try come up with a code on it shortly , comment for improvements and flaws .
The time should be log(N) to base M. It will be better to contruct a circular array of lifts which moves in a given direction all the time with half going up and other half going down and each lift at log(N) floors apart from other. This design is flawed because the amount of energy wasted in such a arrangement will be huge as all lifts will be on constant move.
Question not clear
- Pras August 17, 2013