Amazon Interview Question
Senior Software Development EngineersTeam: AWS
Country: United States
Interview Type: Phone Interview
/*
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;
}
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
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;
// 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);
}
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.
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;
}
#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;
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
*/
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)
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();
}
}
}
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();
}
}
}
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();
}
}
}
Here was my solution from the interview:
Time complexity O(n) since the map is bounded by constant 1440 min per day
- funktional September 12, 2016assuming HashMap has time O(1) with a decent hash algorithm.