## Amazon Interview Question Software Engineer / Developers

• 0
of 0 votes

There is a bus stand. We have given arrival time of the buses and halt of every bus. timings can overlap. We have to find minimum no of platform on the bus stand, so that no bus has to wait to occupy platform.

Country: India
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
13
of 13 vote

sort the timings (both arrival and departure )

intilaize two variables count and max equal to 0

whenever there is an arrival increment count and and when there is a departure decrement count

and at every step (increment or decrement ) compare it with max and then if count is greater than max update it .....

return max

max is nothing but the maximum no of buses going to be there at any point of time
so there need to max number of platforms

Comment hidden because of low score. Click to expand.
0
of 0 votes

Righto!

Comment hidden because of low score. Click to expand.
0
of 0 votes

Consider this case:
bus1 10 11
bus2 11 12

Shouldn't you take care of this case? To handle this case, for same pair of arrival and departure times, don't increment count.

Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorting would not work for negative numbers :(

Comment hidden because of low score. Click to expand.
3
of 3 vote

find maximum overlap count that is the answer.

Trick is to think of a domain set for time - lets say hour or minute or seconds. Below logic is for domain set "mins"

``````public class BusStandArrivalTimeMinPlatforms {

public static void main(String[] args) {
BusDetail[] busDetails = new BusDetail[5];
busDetails[0]=new BusDetail(){{
arrivalTime=10*60; //10 AM
haltTime=20; //20 mins
}};
busDetails[1]=new BusDetail(){{
arrivalTime=(int) ((10.5)*60); //10:30 AM
haltTime=30; //30 mins
}};
busDetails[2]=new BusDetail(){{
arrivalTime=11*60; //11 AM
haltTime=15; //15 mins
}};
busDetails[3]=new BusDetail(){{
arrivalTime=(int) (10.5*60); //10:30 AM
haltTime=35; //35 mins
}};
busDetails[4]=new BusDetail(){{
arrivalTime=10*60+40; //10:40 AM
haltTime=5; //5 mins
}};
System.out.println("Min platforms: "+getMinPlatfoms(busDetails));
}

public static int getMinPlatfoms(BusDetail[] busDetails) {

int domain=24*60;
int [] slots = new int[domain];

for (BusDetail busDetail : busDetails) {
for(int i=busDetail.arrivalTime; i<busDetail.arrivalTime+busDetail.haltTime;i++){
slots[i]++;
}
}
return findMaxValue(slots);

}

public static int findMaxValue(int... array){
assert(array.length>0);
int max=array[0];
for (int i : array) {
if(max<i){
max=i;
}
}
return max;
}
}

class BusDetail {
public int arrivalTime;
public int haltTime;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````#code in python
bus_timings = [[100, 15],[110, 10], [120, 3], [122, 5], [150, 25], [150, 20], [152, 30]]

platforms = []

for arrival in bus_timings:
found_slot = False
for p in platforms:
last_bus = p[-1]

if(last_bus[0] + last_bus[1] < arrival[0]):
p.append(arrival)
found_slot = True
break

if not found_slot:
new_platform = []
new_platform.append(arrival)
platforms.append(new_platform)

for p in platforms:
print p``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

Calculate the time at which maximum buses are at the platform(O(nlogn) by sorting). The number of buses present at this time is the number of platforms needed.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Is the question is complete??

Comment hidden because of low score. Click to expand.
0
of 0 vote

its a textbook problem, can be mapped directly to the 1st discussed problem of "An activity-Selection problem" of chapter Greedy Algorithms from CLRS-3rd Edition

Comment hidden because of low score. Click to expand.
0
of 0 vote

if we have lesser domain set - say hours (24 slots) we could also use bit manipulation

Comment hidden because of low score. Click to expand.
0
of 0 vote

Presume that every bus arrives back at 10pm and stays until the next morning at 6am. You obviously need one platform for every bus, with the information given. There need to be additional contraints to make the problem work.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Lemme assume that there are 5 bus:

``````/* details[x][0] contains the arrival time and and details[x][1] contains the departure time  of 5 buses where x = 0 to 4 */
/* starts with details[0][1] and ends in details[4][1] */
/* details[ ][ ] array can be populated in minutes as follows :
1.let us assume 24 hours clock.
2. 00:25 is equivalent to 0+25 mins.
3. similarly 10:45 will be 10*60 +45.
4. And 13:15 will be 13*60 + 45.

Note : Here am not considering the buses which arrive and leaves the next day or it stays more than a day. Yet to think a logic for it.``````

``````int MinimumPlatform( int details[5][2] )
{
int i,j,k=0,min =1;
for ( i = 0; i < 5; i ++)
{
k = 0;
for ( j =0; j < i ; j--)
{
if ( details[i][0] < details[j][1];
{
k++;
}
}
if ( k == i +1 )
{
min ++;
}
}

return min;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

We can use a Min Heap to solve this problem

1. Insert first arrived bus into heap (always min- heapify based on its departure time)
2. while inserting next arrived bus into heap (based on its arrival time), check whether any previosly arrived bus(es) can be removed from the heap (by comparing the currentbus.arrivaltime with MinHeaps topelement.depturetime)
3.when ever you insert an element into heap compare it with previous max_heap_size, if it is greater than max_heap_size, update max_heap_size.

max_heap_size is the minimum no: of platforms required in bus stand to hold the buses with out making them wait and with optimial use of platforms.

Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

Learn More

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More