Google Interview Question
SDE1sCountry: United States
Interview Type: Phone Interview
Make two different array one for departure time and another for arrival time. Sort them according to time. iterate through both array simultaneously increase pointer of array having smaller time. whenever increase pointer of departure array increase flight in air count decrease otherwise. during traversal max count achieved is answer.
type Flight struct {
Depart int
Arrive int
}
type Event struct {
Time int
Count int
}
func AirborneFlights(flights []*Flight) int {
// O(n)
events := make([]*Event, 0, 2*len(flights))
for _, f := range flights {
events = append(events, &Event{f.Depart, 1})
events = append(events, &Event{f.Arrive, -1})
}
// O(n*log(n)) - may be optimized with bucket sort to O(n) in the best case
sort.Slice(events, func(i, j int) bool {
if events[i].Time == events[j].Time {
// Landings should come first
return events[i].Count < events[j].Count
}
return events[i].Time < events[j].Time
})
// O(n)
tally := 0
max := 0
for i, e := range events {
tally += e.Count
if i == 0 || tally > max {
max = tally
}
}
return max
}
- shakazulu April 16, 2018