Solving My Facebook Phone Interview Question

This video describes and shows how to solve a question I got during a software engineering phone interview with Facebook.It was for a New Grad role and this problem was asked during the second half of the interview.

#keeponcoding #tech #programming #facebook

DISCLAIMER: Links included in this description might be affiliate links. If you purchase a product or service with the links that I provide I may receive a small commission. There is no additional charge to you! Thank you for supporting so I can continue to provide you with free content!

[Garentei]

Simply sort the starting and ending times as independent events and increment the counter on each starting event and decrement the counter on each ending event.

[pradiplamsal]

Man, people must like your frankness and down-to-earth character. Also, this was such an easy to follow, thorough explanation. Keep it up.

[alexdang]

If the question input restrict flight time as 1-24 as whole integer, you can create an array of int[24], then for each flight duration, you plus 1 to the corresponding time slot. (like if it's (4, 6), then slot 4, 5, 6 all plus 1. Then after all flights were done, you go through the array again and find the max. This would avoid sorting.

[dmitrykarpenko]

Is number of hours limited? If yes, you can create an array from 0 to 23 and just loop through the flights and add "changes" (e.g. +1 if starts, - 1 if ends) to the array - and then just loop through it and return a max cumulative sum of the changes. That'd be a "bucket sort"-like O(n) time/space solution.

You could also sort by start and then by end (i.e. check both in the comparator) and add the elements to a queue. Then you'd remove from the start when the flight is over. Same complexity as yours. Handy when you don't have a built-in minheap.

Plese point at any flaws my ideas have:) Thanks!

[CrystalSergeant]

just note that this implementation is very complex. You can just use dict with key (start of flight) and value for end of flight. then you sort dict by key and iterate over sorted keys. Also priority queue can then have just values in there.

[swagatochatterjee]

You could have created two arrays (one for start, other for end) and then used two pointer (take minimum of the start[i] and end[j]; increment count when start is chosen, decrement count when end is chosen) and take maximum of the count.

[vtvtify]

9:36 should be <=, because he said when a flight ends at x and a flight starts at x we only consider start, so baiscally intervals are of the form [a, b), not [a, b]


Usually it's open intervals but at the start of the video his statement implied it's not (therefore based on his definitions in this problem intervals at [9, 9] cant even occur)

[magicsmoke]

This is just like the sweeping line algorthm for finding overlapping segments (computational geometry)

[senthilkumaran]

Number of people alive (maximum) in a year - one of the variants of the question.

[chestly]

Before you solve this is how i would do it:

1) Given an array of these sets(We will pretend they are in some sort of bean) and assuming that the start times are incremental we can calculate the length of each flight
2) We can create a new relative set of flights starting where, for example since 2 is the beginning flight it will be in the 0th position with a start time of 0(and a end time of 4 since its 4 hours long)
3) From here we can increment from 0 to the highest offset + travel time. When a flight starts we add 1 to a counter, when it stops we remove 1.
4) We then keep an absolute counter which is the highest amount of flights at the same time. if the counter is above this then `highestNumFlights = flightCounter` or something along those lines

At the end we return the `highestNumFlights` and that should be it! Excited to keep watching and see your solution!

[colehayden]

dude you seem so laid back and down to earth i love it.

[SenthilKumar-rmtx]

very transparent and easy explanation. Kudos !!! .

[jascu]

not sure this is right, treat all start time as positive 1, end time as negative 1, then having an array of all of them (+1, -1) order by the the hours(simply ascending order of all hours ), finally add up each number in the new array with the 1s (+-), and record the highest number is your result. One issue maybe when multiple plane land and take off at the same time...

[xdeadbeef]

You can also solve the problem using Count Sort, but that'll require nested loops resulting in an O(n^2) time complexity. Interviewers hate O(n^2) solutions

[rakeshbidhar]

This explanation is brilliant. Loved it. Coming from a data engineering background I would Read the input as a spark data frame. Write a simple sql query with where clause current_time between start and end.This will give count of flights for every single time. Then take the max .

[chompnn]

Make a list of Start time and a list of end time sorted, if start time is smaller than end time then up the count and move start index. If start time is larger than end time then move end time index pointer up and check if the current count is greater than the previous max. O(nlogn) time complexity and O(n) space.

[Amritanjali]

We can also solve this by sorting by end time then find the index whose endtime is just hire then the start time in log(n) and take another array and add 1 to that index and subtract 1 from current index
Then I will simply find out cumulative sum and find maximum value for every index

[jaatharsh]

can't thank you enough man, this format is awesome along with informing about the ques walk thru the strategy used to solve.
Keep posting such awesome videos.

[nonyafletcher]

This was good. The video where you did the interview in person was awesome. I like your breakdown strategy and that one specifically demonstrates how legit your skills are. I also appreciate the honesty of struggle vs creating a false image of god-like perfection.

[gwhizGV]

If you prefix sums of deltas you can compute the ans in O(max + #flights) which is linear