Amazon Interview Question
Software Engineer / DevelopersCountry: India
@Ashish:
I think some assumptions are also has to be taken:
For e.g.: There can be multiple entrance of building. Each entrance will have atleast 2 lifts. Moreover, if a single lift would service 20floors than the waiting time would be quite high. Also, there might be some executive floors which requires a good lift service(2-3 three special lifts for their floor to sub floors).
More assumption can also be added.
@Shwetank
Definitely a candidate must ask lot of open ended questions while forming his/her assumptions. This also disables interviewer in contradicting assumptions.
@Superman
Yes indeed skip list is what I have. I was thinking about even-odd or skipping 2, 3 and 5 floors but it seems given large number of floors a person would have to think/walk a lot to figure out the right lift. Hence 20 floor skip.
I would answer smthing like this:
N lifts,
(Roughly)
M lifts that go to all floors.
N/2 - M/2 only for even floors
N/2 - M/2 only for odd floors
And say,
(both will go to ground floor and basement)
Now what N & M should be ? 75 floor building. If its a office building, perhaps, too much of movement.
On avg, smooth would be, one lift to cater to say 3-4 floors.
So, N = 75/3-4 = (rougly) 20
So, for M, required when one wants to go from odd to evn or vice versa. Around 2.
(if distance is large, I'd prefer going to nearest even / odd floor, and then take stairs for one floor. )
SO, estimate is 9 lifts for even floors, 9 lifts for odd floors, and 2 lifts tht go to all floors !!
Divide and conquer ? Have elevators that operate 40 and under and 40 and above. Then you are effectively managing 40 and 35 floors respectively. Similarly, if you have 40 floors, you can have one lift that operates first 20 and last 20. So you can have 1-20, 20-40, 40-60 and 60-80. By any reasonable logic you can manage 20 floors by 1 elevator. Normally there are 4 elevators in most large buildings. So this fits well...
- Ashish Kaila December 02, 2011