Amazon Interview Question Software Engineer / Developers


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

- sreeram on September 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Righto!

- Anonymous on September 24, 2012 | Flag
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.

- sahaj on September 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorting would not work for negative numbers :(

- rajanikant.malviya on September 26, 2012 | Flag
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;
}

- rajanikant.malviya on September 24, 2012 | Flag Reply
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

- bluesky on September 24, 2012 | Flag Reply
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.

- Epic_coder on September 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is the question is complete??

- narendrabtechcse on September 24, 2012 | Flag Reply
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

- i.mnext on September 24, 2012 | Flag Reply
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

- rajanikant.malviya on September 24, 2012 | Flag Reply
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.

- Steven Schulman on September 24, 2012 | Flag Reply
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;
}

- vinodhian on September 24, 2012 | Flag Reply
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.

- Vignesh on October 05, 2012 | Flag Reply


Add a Comment
Name:

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

Books

is a comprehensive book walking you through getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

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