Amazon Interview Question for Senior Software Development Engineers


Team: AWS
Country: United States
Interview Type: Phone Interview




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

Here was my solution from the interview:

// Day runs from minute 0 to minute 1440 (exclusive)
// Input: example 9:30 => 570
// arr [570, 675, 990]
// dept [705, 690, 1005]
// Assume data is valid - i.e. length, no neg, etc.

int[] arr = { 570, 675, 990 };
int[] dept = { 705, 690, 1005 };

// Create a frequency map for the day
Map<Integer, Integer> freqMap = new HashMap<>();
for (int n = 0; n < arr.length; n++) {
    int a = arr[n];
    int d = dept[n];
    for (int i = a; i < d; i++) {
        int count = freqMap.containsKey(i) ? freqMap.get(i) : 0;
        freqMap.put(i, count + 1);
    }
}

// Calculate the max value
int maxVal = 0;
for (Integer n : freqMap.values()) {
    if (n > maxVal) {
        maxVal = n;
    }
}

System.out.println("Gates needed: " +maxVal);

Time complexity O(n) since the map is bounded by constant 1440 min per day
assuming HashMap has time O(1) with a decent hash algorithm.

- funktional September 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

/*
solution idea (inspired by merge sort)

1) make sure both, arrival and departure times are sorted. Arrival 
times are already, departure time aren't.
Then think of the arrivals and departures as of 
queues and look at their first elements. The smaller one wins, if equal, 
the departure wins.
if the winner is departure, a gate is freed (assume, it can go below 0)
if the winner is arrival, a gate is used
sort departure time ascending()

2) assume the arrival and departure time can be converted into some
form that allows easy comparsion of > (string representation as given
won't do it). Leave this "parsing step out" but do something like 
houre*60+minute.

time complexity: O(n*lg(n)) assuming #departures and #arrivals are equal
*/

#include <vector>
#include <algorithm>

int GetGates(std::vector<int>& arrivals, std::vector<int>& departures)
{
	std::sort(departures.begin(), departures.end());
	int n=arrivals.size();
	if(n != departures.size()) throw "#arrivals should equal #departures";
	if(arrivals[n-1] >= departures[n-1]) throw "last departure must be after last arrival";

	int a=0, d=0, mg=0, cg=0; // mg: max # gates, cg: current # gates
	
	while(a<n) 
	{
		if(arrivals[a] < departures[d]) 
		{ 
			cg++; 
			a++;
		}
		else 
		{
			cg=std::max(cg-1,0);
			d++;
		}
		mg=std::max(cg,mg);			
	}
	return mg;
}

- Chris September 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def airportGates2(arr, dep):
    dep = sorted(dep)
    currentPlanes = 0
    currentDeparturePosition = 0
    maxArrival = 1
    
    for i in xrange(len(arr)):
        arrTime = arr[i]
        maxArrival = max(maxArrival, currentPlanes)
        currentPlanes += 1
        
        for j in xrange(currentDeparturePosition, len(dep)):
            if dep[j] < arrTime:
                currentDeparturePosition = j
                currentPlanes -= 1
            else:
                break
        
    return maxArrival

- Oladipo September 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Map<Integer, Integer> freqMap = new HashMap();
for (int a=0;a<dep.length-1;a++){
freqMap.put(arr[a],freqMap.get(arr[a])!=null?freqMap.get(arr[a])+1:1);
freqMap.put(dep[a],freqMap.get(dep[a])!=null?freqMap.get(dep[a])+1:1);
}

for (Integer n : freqMap.values()) {
if (n > count) {
count = n;
}
}
return count;

- Jay September 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Here's my solution in C#. Runtime complexity will be O(n).

        public static void FindMaxGates()
        {
            // Convert time to seconds
            int[] arr = { 570, 675, 990 };
            int[] dept = { 705, 690, 1005 };

            // You need atleast one gate
            int gateCount = 1;

            // If Next arrival is less than previous departure, Add gate
            for (int i = 0; i < arr.Length; i++)
            {
                if (i + 1 >= arr.Length)
                {
                    break;
                }

                if (arr[i + 1] < dept[i])
                {
                    gateCount++;
                }
            }

            Console.WriteLine("Gates Needed: {0}", gateCount);
        }

- Jay September 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Convert time to seconds
  int arr[ ] = { 570, 675, 990 };
  int dep[ ] = { 705, 690, 1005 };

  int  i,MinGates=1;

for( i=0; i<sizeof(arr)-1; i++)
    if(dep[i]>=arr[i+1] ) MinGates++;

Printf(" No. of Gates required is %d",MinGates);

- chaitu470 September 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

arrivals = ["9:30", "11:15", "16:30"]
departures = ["11:45", "11:30", "16:45"]

def timeTrans(time):
# translate the H:M time into minute integer
    timesplit = time.split(":")
    hour = int(timesplit[0])
    minute = int(timesplit[1])
    
    return (hour*60) + minute - 1
    
def gatesNeeded(arr, dep):
# iterate through the arrival times and
# check for open gates, open new one if none
    gates = {0:0}
    gate_count = 1
    for i in range(len(arr)):
        arrival_time = timeTrans(arr[i])
        departure_time = timeTrans(dep[i])
        empty_gate = False
        
        for g in gates:
        # check for gates whose planes have already departed
        # at time of arrival for plane i
            if arrival_time >= gates[g]:
            # if an empty gate is found, update it with
            # new departure time
                empty_gate = True
                gates[g] = departure_time
            else:
                pass
            
        if not empty_gate:
        # if no gate is found, open a new gate
        # and update its departure time
            gate_count += 1
            gates[gate_count-1] = departure_time
            
    # return the total number of gates open
    return gate_count


print gatesNeeded(arrivals, departures)

O(n) time complexity.

- Nate September 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Above solutions are not O(n). The optimal runtime is O(n logn). Here min heap is used to store the departure times.

public static int find(int[] arr, int[] dep) {

        Heap heap = new MinHeap(arr.length);

        int gates = 1;

        heap.add(dep[0]);

        for (int i = 1; i < dep.length; i++) {

            if (arr[i] < heap.peek()) {
                gates++;
            } else {
                heap.extractTop();
            }

            heap.add(dep[i]);
        }

        return gates;
    }

- jaks September 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you explain your comment as to why the above are not O(n) and why the optimal runtime is O(n log n)?

- funktional September 21, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
using namespace std;
int main()
{
        int n,i;
        int *arr,*dep;
        cout<<"enter the number of flights";
        cin>>n;
        arr=new (nothrow) int[n];
        if(arr == NULL)
        {
                cout<<"memory for arr couldn't be allocated";
        }

        dep=new (nothrow) int[n];
        if(dep == NULL)
        {
                cout<<"memory for dep couldn't be allocated";
        }
        if(dep!=NULL && arr!=NULL)
        {       cout<<"please enter proper arr and dep time for all the flights";
                for(i=0;i<n;i++)
                {
                        cin>>arr[i];
                        cin>>dep[i];
                }
                int gate=1, psudogate=1;
                for(i=0;i<n;i++)
                {
                        for(int j=0;j<i;j++)
                        {
                                if(arr[i]<dep[j])
                                        psudogate++;
                                else
                                        psudogate--;
                        }
                        if(psudogate>gate)
                                gate++;
                }
        cout<<endl<<"number of gates require ="<<gate;

        }

delete [] arr;
delete [] dep;
return 0;

- gauravonspeed September 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution -- it is easy to understand:

#include <array>
#include <map>
#include <iostream>

using namespace std;
int main()
{
	array<int,4> arr={570,675,990,690};
	array<int,4> dep={705,690,1005,1005};

	map<int,int> seq;

	pair<map<int,int>::iterator, bool> ret;
	for (auto it: arr) {
		ret = seq.insert(pair<int, int>(it, 1));
		if (ret.second == false) seq[it]++;
	}
	for (auto it: dep) {
		ret = seq.insert(pair<int, int>(it, -1));
		if (ret.second == false) seq[it]--;
	}

	int gates=0;
	int temp=0;

	for (auto& kv: seq){
	    cout << kv.first << " => " << kv.second << endl;

	    temp += kv.second;
		if (temp > gates) gates = temp;
	}
	cout << "We need gates: " << gates << endl;

}

/* output:
570 => 1
675 => 1
690 => 0
705 => -1
990 => 1
1005 => -2
We need gates: 2
*/

- echang September 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Put arrival-departure pairs into a Node. Sort it by arrival.
For each node in list...Check if it intersects next nodes. Break upon first non-intersection.
Maintain count of intersections for that node. If the count > best, mark best as count.
Best is the answer.


Although it's O(N^2), because our break is very tight, average running time will be close to O(N). Since sorting is O(N log N) solution will be on average O(N log N)

- Anonymous September 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

using System;

namespace NumberOfGates
{
    class Program
    {
        static void Main(string[] args)
        {
            int numberofGates = 0;
            int maxNumberGates = 0;

            int[] Arrivals =  { 570, 660, 975 };
            int[] Departures = { 705, 690, 1075 };

            int arrivalIndex = 0;
            int departureIndex = 0;

            //Sort the Departures Array
            Array.Sort(Departures);

            for (var i = Arrivals[arrivalIndex]; i < Departures[Departures.Length - 1]; ++i)
            {
                if (arrivalIndex < Arrivals.Length && i == Arrivals[arrivalIndex])
                {
                    arrivalIndex++;
                    ++numberofGates;
                    if (numberofGates > maxNumberGates)
                    {
                        maxNumberGates = numberofGates;
                    }
                }

                if (i == Departures[departureIndex])
                {
                    departureIndex++;
                    --numberofGates;
                }
            }

            Console.WriteLine("Max Number of Gates required: {0}", maxNumberGates);
            Console.Read();
        }
    }
}

- Mukesh October 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

using System;

namespace NumberOfGates
{
class Program
{
static void Main(string[] args)
{
int numberofGates = 0;
int maxNumberGates = 0;

int[] Arrivals = { 570, 660, 975 };
int[] Departures = { 705, 690, 1075 };

int arrivalIndex = 0;
int departureIndex = 0;

//Sort the Departures Array
Array.Sort(Departures);

for (var i = Arrivals[arrivalIndex]; i < Departures[Departures.Length - 1]; ++i)
{
if (arrivalIndex < Arrivals.Length && i == Arrivals[arrivalIndex])
{
arrivalIndex++;
++numberofGates;
if (numberofGates > maxNumberGates)
{
maxNumberGates = numberofGates;
}
}

if (i == Departures[departureIndex])
{
departureIndex++;
--numberofGates;
}
}

Console.WriteLine("Max Number of Gates required: {0}", maxNumberGates);
Console.Read();
}
}
}

- Mukesh October 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

using System;

namespace NumberOfGates
{
class Program
{
static void Main(string[] args)
{
int numberofGates = 0;
int maxNumberGates = 0;

int[] Arrivals = { 570, 660, 975 };
int[] Departures = { 705, 690, 1075 };

int arrivalIndex = 0;
int departureIndex = 0;

//Sort the Departures Array
Array.Sort(Departures);

for (var i = Arrivals[arrivalIndex]; i < Departures[Departures.Length - 1]; ++i)
{
if (arrivalIndex < Arrivals.Length && i == Arrivals[arrivalIndex])
{
arrivalIndex++;
++numberofGates;
if (numberofGates > maxNumberGates)
{
maxNumberGates = numberofGates;
}
}

if (i == Departures[departureIndex])
{
departureIndex++;
--numberofGates;
}
}

Console.WriteLine("Max Number of Gates required: {0}", maxNumberGates);
Console.Read();
}
}
}

- msdogra October 12, 2016 | Flag Reply


Add a Comment
Name:

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

Books

is a comprehensive book on 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