1. Listen! Ask questions. Look for clues. [02:21] 2. Draw an Example. [03:11] 3. Create (don't code!) a brute force algorithm. [07:16] 4. Focus on the most important parts of the code. [33:01] 5. Using abbreviations while coding will help you write code faster. [41:46] 6. Test your code! [48:16] 7. Walkthrough the logic first, before trying a test case. [48:21]
What's really Hard about interviewing is the constraint of TIME that exists between: Talking about the problem, Illustrating it, etc AND the point when you're supposed to Start Coding it. I've heard many interviewees say they were expected to start coding almost right away, and that If you take too long trying to understand, it's considered a failure. I would certainly like to read your opinions on this. Thanks for uploading this video.
@LivingBlast, LLC Thanks for your response, kind sir. The experiences I keep reading about are coming from the Top Tech companies of course: Google, Facebook, Amazon, Microsoft, etc. And sadly it seems you're at the mercy of the interviewer's mood at the time of the interview... I have read testimonials written by former interviewers themselves who confess on the very fact that they Look Down on candidates that they deem to be "unworthy" within seconds of hearing them speak. This is very HARD because it could be that the interviewer is just tired or just bored, or would prefer to be doing something else, and you pay for it.
@@jlecampana Well... if the interviewer acts like ass, do you really want to work with him later? I understand that future employer may expect certain level of skill, knowledge and intelligence from me and I may not be up to their expectations but their are still ways to communicate that in polite, civilised manner.
The programming part of this is trivial once you know the "trick". The hard part is realizing the "trick" fast enough while being interviewed. If you don't realize this fast enough (or not at all) while being interviwed, god like programming skills will not help. So it's not really about programming, It's about logic.
Create two min heaps one for birth years and one for death years. Initiative running sum to 0 and compare the root of 2 heaps. If root of death heap is smaller decreases the running sum . In other case increment the running sum.
The problem I have with a question like this is that the whole video is 1:06 minutes and she knows the answer! Someone who is interviewing, doesn't know the question, doesn't obviously know the answer, and is nervous during the process, will not even get close to the optimized approach in the 45 minutes each interview last.
I'm no recruiter however I think what they are interested in is not the answer but rather things like: - what's your reaction (stressing or not etc..) - what's your approach to the problem - are you looking for a better solution than what you've done that sort of things...
@@duffmandje to an extent. Yes they are looking for a working solution. Your code doesnt necessarily have to run, they dont care about syntax errors or if you forgot how a method is used, they do care that ultimately the solution works.
@@duffmandje Actually they want a working solution. While it's true that they evaluate your thought process, they are interested in a working solution. It doesn't have to "compile" per se.. thye don't expect you to know methods/arguments by memory and syntax errors do happen in whiteboarding. But they see the entire code as a whole and they want to know you understood the problem and came up with a solution.
But everyone gets 45 minutes, so that's not an issue. If they gave you 5 hours, they would still keep track of how fast you solved it and somebody else will solve this in 30 minutes.
@@quinton_miller solving a problem fast won't make you a good employee.. you can be smart and solve a problem quick and be a slacker at work and don't deliver on time... I've seen very smart people being total slackers and have very poor work ethic
Nice video. I always enjoy coding interviews from time to time. My pseudo code would be to use an array of objects //Create an object/class/struct which has the year as a value and birth or death flag or have a field with birth_death = 1 or -1 //loop through all the objects in this case we have 2n number of inputs to loop through so the running time is O(n) //In this loop we keep track of the data we are interested in I would think that should be : max_people_alive_count, year_start (this would be a birth year when we find the max), //year_end (this would be the death year), we also keep count of the current people alive and by the end of the loop the count should be zero as a sanity check.
I guess this can be solved lot more easier with time complexity O(n log n) and space complexity O(n) , take birth year array and death year array. Sort them separately. Initialize population variable with zero. Have two pointers, ( like we do in merge operation) keep increase / decrease population based on birth array n death array whichever is lower, keep the population, year in an array. Repeat until we finish birth array. Now go through population array linearly and find the max
Look up prefix sum algorithm. It's one of the easiest tricks there is for these interviews and it's almost always obvious when you'll use it: when you need the min/max after dealing with multiple ranges. You could linearly run through each person and keep track of the count of each year, which on paper sounds better than your solution of O(n log n), but with a million people it sucks, obviously.
O(PlogP) is worse solution than O(P+YlogY) for practical reasons because P >>> Y. i.e. the number of years possible is usually very less compared to the size of the given birth/death array for a real world data.
@@hasasi1152 I'm not so sure, a population of 1 million could take over 100 years to be born and die out, yet log 1million is just 20. Sometimes P*Y will be better, sometimes it will not.
Cool solution, definetely easier, but not optimal. Your solution is O(P log P) time and O(1) space, this is generally slower than O(P+Y) time albeit better than O(Y) space, which is her solution. Anyway, good work. Cheers!
If all you want to know is the year and not the value, you can start from the first death year instead of first birth. You know that population does not decrease before the first death.
At 1:03:30 it's said (loosely rewording): "Sometimes people mishear this problem as - find the year where most of the people are alive, which is a different problem." Can anyone explain to me how that can be the case? The year where most people are alive is a year that has the highest population, which is the question being answered all throughout this video, is it not?
I am doubtful that The second approach would work. Consider A)2000->2010, B)2002->2010. If we see if any person is alive during the birth year, person B doesn't count
The guide to crack coding interview lasts 70 minutes yet you are given ~20-30min to solve the problem. Not to mention she gives tips and yet she injects extra code during the coding session that she forgot instead of cleaning it up. Overall it was unorganized and hard to follow even though the overall message was received.
As as interviewer, I'd be concerned that the ambiguity around "find the year" wasn't brought up. Should this be the first year of a max, last year of the max, or should a list of tied max years be returned? It's always best not to start coding from assumptions.
31:29, the runtime complexity mentioned is wrong. It should be O(P+YlogY). You either need to create the array for years and also sort the same for applying the prefix-sum idea or store the yearToCount mapping in a BST implementation (like TreeMap). In addition, a candidate should ask clarification as the original question should be not a single year for the max population. Rather, the question should be either: 1. Which all years, the population is maximum or 2. Output any year where the population is the maximum possible.
Could you be more clear? I can't understand what it is you see her planing to sort. The algorithm she described seems to be 1- iterate all P to retrieve min and max birth year (which is O(P) time and O(1) space); 2- allocate and initialize with value = 0 an array representing the interval from min to max year (which takes O(Y) time and O(Y) space; 3- iterate all P checking birth and death years (array[ birth_year]++ and array[death_year]--) which is O(P); 4- loop year from min to max adding the value in array[year] to total population and registering the max which is O(Y);
delta=[ 0 for x in range(0,max(birth)-min(birth)+1) ] for i in range(0,len(birth)): adddelta(birth[i]-min(birth),1,delta) adddelta(death[i]-min(birth)+1,-1,delta) runningsum=0 maxreturingsum=0 year=0 for d in range(0,len(delta)): runningsum=runningsum+delta[d] if(runningsum >= maxreturingsum): year= min(birth)+1 maxreturingsum=runningsum print(year) print(maxreturingsum)
17:03 how can she O(P^2) is better than O(PY)? she is implicitly assuming there are less people than the year range but in real life, that's not true. most of the time, the year range will be less than 200 while the population can be millions.
it people be weird, why not choose some other wording for the same problem started and finished school, worked in the same place... why did she have to kill them
i would just check if index of birth years is >=birth year and counter, erase result array, store year, if newcounter==oldcoutner, simply store that year on the result array. and then just print/return result array, would this be slower?
Talking while coding is distracting . I would rather write a piece of code, undisturbed by my own voice, and then pause to explain what I did, then continue and alternate in a similar manner pausing where it makes sense to explain.
I know they are imaginary people but give them at least 40-50 years of life, I mean born 1803 and dies 1809, this imaginary person is a child.. Just kidding (:
You can literally just start from the lowest(number) birth year and count how many are alive at that time by using the restrictions of the other people’s birth and death years. If the number is within that range, then ++. Then compare that run through of the year to the next year. Get the higher one. Then repeat up until the highest(number) death year, and print out the highest year. Simple as that.
I think you don't need to make an array from min birth year to max death year in getDeltas function. You can just have an array with the years we encounter(interested years) while looping through people array. That way the use of garbage values are eliminated
What if an input would be a bunch of people that have the same birth date but different death dates. The delta array would have just one element and it is not going to work. We need to take the max death date for creating the delta array.
Why though, the birth date of all the people would be the year of highest population. The deltas array would have one element but I dont see why that may be an issue. The death dates don't change the year of highest population.
Hmm, I disagree. I feel like she is trying to show you how she would think through this in an interview setting. This is the typical workflow. A candidate tries things, makes small realizations, makes mistakes, backtracks, then keeps trying to incrementally improve until the candidate hits an optimal solution. Which I think is what she is trying to say. I found this to be very helpful!
It's possible to have the maximum number of people to be a death year, such as when a catastrophe suddenly wipes out a population when population is at max.
@@dylanhurley1120 yes, the array indices is the order so arr[2000-first_birth_year] gets filled with +1 first and then arr[1750-first_birth_year] . Doesn't matter in which order she fills in the deltas cos running sum is then calculated in order of array indices. Make sense?
Here's two solutions in Python 3.7 (i have no idea if i'm doing tracemalloc right) from datetime import date from dataclasses import dataclass from collections import Counter import tracemalloc from time import perf_counter from typing import Sequence @dataclass class Person: birth: date death: date def alive(people: Sequence, year: int): n = 0 for person in people: if person.birth.year
why wouldn’t you give all the necessary info to the applicant to solve the problem?...in real world you can gather info about the problem easily and there’s an infinite no of questions one can ask you usually design a solution knowing all the constrains
I’ve had interviews where they purposefully don’t give you all the information so that they can see how you communicate to get the info. It is an important part a developers job.
People won’t communicate expectations clearly in any field (you must ask, clarify, ask again, have it mutually agreed upon, and have periodical check ups now and then just in case things change)
She brought it up, and says that for example the interviewer would just output any of those. I suppose another answer would be just output them all, or output the min or max
That's what I would have done also. You could argue though that inserting into a tree is log(y) and retrieving also, so since you're inserting 2p rows, and then iterating through the tree, the runtime complexity is O(2p*log(y) + 2p) = O(p*log(y)) where y is the year range. log Y is going to be a fairly small number (even if we go back to the beginnings of civilizations, we'll only need to consider 5000 years) and the tree solution will use less space and will have much less rows to iterate over to get the actual result, but I would argue that while the tree solution is likely easier to code, the array solution will be faster. With the array approach, you could have many empty values that you iterate through, but even if you iterate through 5000 ints, your array will fit in L1 cache, so skipping over the years with zero deltas will be super fast vs in a tree you'll likely get cache misses by following the pointers around in the tree and I am sure that the compilers will also be able to vectorize the array solution with some nice SIMD instructions.
Thank you for the overview of your algorithm. I took the opportunity to build my own algorithm based on the information you had in your video with some assumptions. The first assumption is the list of people with birth and death years is not sorted by any means and to provide an algorithm that is object oriented and with minimal paths of execution. I wrote it in C++ but it obviously could be done in any language such as what you provided. Here is my solution for what it is worth // ConsoleApplication1.cpp : This file contains the 'main' function. Program execution begins and ends there. // @ @ using namespace std; // Class BirthDeath holds a persons birthyear, deathyear and a routine to determine if a person was alive during a given birthyear class BirthDeath { public: int BirthYear; int DeathYear; int Census; // construct the class with default values BirthDeath() { BirthYear = DeathYear = Census = 0; }; // routine that takes a birthyear and determines if this person was alive at that time bool IsInLifeRange(int nBY) { bool bInMyLifeRange = false; if (nBY >= BirthYear && nBY
In reality in FAANG / MAANG interviews: here is the problem. You have 15 minutes before the end of the interview since we wasted the first 25 talking about your work history and about the company.
I wonder why not many people liked this solution, it is so simple, but I guess it is very expensive since it has to go through all the years again and again for each person to populate the lifeyears list.
1. Listen! Ask questions. Look for clues. [02:21]
2. Draw an Example. [03:11]
3. Create (don't code!) a brute force algorithm. [07:16]
4. Focus on the most important parts of the code. [33:01]
5. Using abbreviations while coding will help you write code faster. [41:46]
6. Test your code! [48:16]
7. Walkthrough the logic first, before trying a test case. [48:21]
What's really Hard about interviewing is the constraint of TIME that exists between: Talking about the problem, Illustrating it, etc AND the point when you're supposed to Start Coding it. I've heard many interviewees say they were expected to start coding almost right away, and that If you take too long trying to understand, it's considered a failure. I would certainly like to read your opinions on this. Thanks for uploading this video.
@LivingBlast, LLC Well said.
@LivingBlast, LLC Thanks for your response, kind sir. The experiences I keep reading about are coming from the Top Tech companies of course: Google, Facebook, Amazon, Microsoft, etc. And sadly it seems you're at the mercy of the interviewer's mood at the time of the interview... I have read testimonials written by former interviewers themselves who confess on the very fact that they Look Down on candidates that they deem to be "unworthy" within seconds of hearing them speak. This is very HARD because it could be that the interviewer is just tired or just bored, or would prefer to be doing something else, and you pay for it.
@@jlecampana Well... if the interviewer acts like ass, do you really want to work with him later? I understand that future employer may expect certain level of skill, knowledge and intelligence from me and I may not be up to their expectations but their are still ways to communicate that in polite, civilised manner.
Hence why you practice.
Not to mention the time for verifying and validating the code throughout a new test case. :/
The programming part of this is trivial once you know the "trick".
The hard part is realizing the "trick" fast enough while being interviewed.
If you don't realize this fast enough (or not at all) while being interviwed, god like programming skills will not help.
So it's not really about programming, It's about logic.
Yea, it has to be almost instant, otherwise easy code or not will take a few minutes to write …
Create two min heaps one for birth years and one for death years. Initiative running sum to 0 and compare the root of 2 heaps. If root of death heap is smaller decreases the running sum . In other case increment the running sum.
The problem I have with a question like this is that the whole video is 1:06 minutes and she knows the answer! Someone who is interviewing, doesn't know the question, doesn't obviously know the answer, and is nervous during the process, will not even get close to the optimized approach in the 45 minutes each interview last.
I'm no recruiter however I think what they are interested in is not the answer but rather things like:
- what's your reaction (stressing or not etc..)
- what's your approach to the problem
- are you looking for a better solution than what you've done
that sort of things...
@@duffmandje to an extent. Yes they are looking for a working solution. Your code doesnt necessarily have to run, they dont care about syntax errors or if you forgot how a method is used, they do care that ultimately the solution works.
@@duffmandje Actually they want a working solution. While it's true that they evaluate your thought process, they are interested in a working solution. It doesn't have to "compile" per se.. thye don't expect you to know methods/arguments by memory and syntax errors do happen in whiteboarding. But they see the entire code as a whole and they want to know you understood the problem and came up with a solution.
But everyone gets 45 minutes, so that's not an issue. If they gave you 5 hours, they would still keep track of how fast you solved it and somebody else will solve this in 30 minutes.
@@quinton_miller solving a problem fast won't make you a good employee.. you can be smart and solve a problem quick and be a slacker at work and don't deliver on time... I've seen very smart people being total slackers and have very poor work ethic
I think a minute of silence would have been appropriate after the first example.
"You have 45 minutes to complete this challenge :^)"
In year 2000 population was 3 people. However, it was the same for the years (1803, 1840, 1894).
Nice video. I always enjoy coding interviews from time to time. My pseudo code would be to use an array of objects
//Create an object/class/struct which has the year as a value and birth or death flag or have a field with birth_death = 1 or -1
//loop through all the objects in this case we have 2n number of inputs to loop through so the running time is O(n)
//In this loop we keep track of the data we are interested in I would think that should be : max_people_alive_count, year_start (this would be a birth year when we find the max),
//year_end (this would be the death year), we also keep count of the current people alive and by the end of the loop the count should be zero as a sanity check.
I guess this can be solved lot more easier with time complexity O(n log n) and space complexity O(n) , take birth year array and death year array. Sort them separately. Initialize population variable with zero. Have two pointers, ( like we do in merge operation) keep increase / decrease population based on birth array n death array whichever is lower, keep the population, year in an array. Repeat until we finish birth array.
Now go through population array linearly and find the max
Look up prefix sum algorithm. It's one of the easiest tricks there is for these interviews and it's almost always obvious when you'll use it: when you need the min/max after dealing with multiple ranges. You could linearly run through each person and keep track of the count of each year, which on paper sounds better than your solution of O(n log n), but with a million people it sucks, obviously.
O(PlogP) is worse solution than O(P+YlogY) for practical reasons because P >>> Y. i.e. the number of years possible is usually very less compared to the size of the given birth/death array for a real world data.
Yeah I don't understand why she didn't use this solution
@@hasasi1152 I'm not so sure, a population of 1 million could take over 100 years to be born and die out, yet log 1million is just 20. Sometimes P*Y will be better, sometimes it will not.
Cool solution, definetely easier, but not optimal. Your solution is O(P log P) time and O(1) space, this is generally slower than O(P+Y) time albeit better than O(Y) space, which is her solution. Anyway, good work. Cheers!
damn she heartless! starts off with a toddler passing...wth
If the company gives me that screeching marker to write with, I will quit the interview.
It has to be part of the test.
Bring your own marker. I have seen worse marker that doesn’t make a mark.
lmao
LMAO!
27:55 so we have one left over person!
It's because she counted two persons born in 1750, when in reality there is only one.
Was surprised she just looked at that like it wasn’t an obvious error and moved on
You are expected to solve 2 questions in 45 minutes for one round of Facebook coding interview, right?
If all you want to know is the year and not the value, you can start from the first death year instead of first birth. You know that population does not decrease before the first death.
As far as i understood wat u want to tell, if v count from first death year then v wud be ignoring all the population count befor first death year.
Isn't this question similar to the question in leetcode where we have to find Minimum number of Meeting rooms?
Thought of the same thing
Meeting Room ll
At 1:03:30 it's said (loosely rewording): "Sometimes people mishear this problem as - find the year where most of the people are alive, which is a different problem." Can anyone explain to me how that can be the case? The year where most people are alive is a year that has the highest population, which is the question being answered all throughout this video, is it not?
I had the same question when I heard that.
I definitely feel much better about being messy during a Whiteboard Coding Interview :)
I am doubtful that The second approach would work. Consider A)2000->2010, B)2002->2010. If we see if any person is alive during the birth year, person B doesn't count
First few minutes: Let's make up a random example by tweaking the numbers as much as possible. LOL
you miscounted the 1750's alive people
Also comforting I don't need to spend time writing loops - the interviewers don't seem interested in that :)
The guide to crack coding interview lasts 70 minutes yet you are given ~20-30min to solve the problem.
Not to mention she gives tips and yet she injects extra code during the coding session that she forgot instead of cleaning it up. Overall it was unorganized and hard to follow even though the overall message was received.
As as interviewer, I'd be concerned that the ambiguity around "find the year" wasn't brought up. Should this be the first year of a max, last year of the max, or should a list of tied max years be returned? It's always best not to start coding from assumptions.
Check the video around 14:15
Actually, that flaw mimics reality. This is why the DOD is so important.The missions are always flawed.
31:29, the runtime complexity mentioned is wrong. It should be O(P+YlogY). You either need to create the array for years and also sort the same for applying the prefix-sum idea or store the yearToCount mapping in a BST implementation (like TreeMap). In addition, a candidate should ask clarification as the original question should be not a single year for the max population. Rather, the question should be either: 1. Which all years, the population is maximum or 2. Output any year where the population is the maximum possible.
Could you be more clear? I can't understand what it is you see her planing to sort. The algorithm she described seems to be
1- iterate all P to retrieve min and max birth year (which is O(P) time and O(1) space);
2- allocate and initialize with value = 0 an array representing the interval from min to max year (which takes O(Y) time and O(Y) space;
3- iterate all P checking birth and death years (array[ birth_year]++ and array[death_year]--) which is O(P);
4- loop year from min to max adding the value in array[year] to total population and registering the max which is O(Y);
Python implementation -
def numberofpersonlive(birth,death):
delta=[ 0 for x in range(0,max(birth)-min(birth)+1) ]
for i in range(0,len(birth)):
adddelta(birth[i]-min(birth),1,delta)
adddelta(death[i]-min(birth)+1,-1,delta)
runningsum=0
maxreturingsum=0
year=0
for d in range(0,len(delta)):
runningsum=runningsum+delta[d]
if(runningsum >= maxreturingsum):
year= min(birth)+1
maxreturingsum=runningsum
print(year)
print(maxreturingsum)
17:03 how can she O(P^2) is better than O(PY)? she is implicitly assuming there are less people than the year range but in real life, that's not true. most of the time, the year range will be less than 200 while the population can be millions.
There is a mistake at 26:03 . You added two people born in 1750 where as there was only 1 born.
it people be weird, why not choose some other wording for the same problem started and finished school, worked in the same place... why did she have to kill them
i would just check if index of birth years is >=birth year and counter, erase result array, store year, if newcounter==oldcoutner, simply store that year on the result array. and then just print/return result array, would this be slower?
why 1750 +2? Shouldn't it be +1?
Why is she adding an index retrieved from the delta array to the firstBirth value at the end of the algorithm?
Talking while coding is distracting . I would rather write a piece of code, undisturbed by my own voice, and then pause to explain what I did, then continue and alternate in a similar manner pausing where it makes sense to explain.
I know they are imaginary people but give them at least 40-50 years of life, I mean born 1803 and dies 1809, this imaginary person is a child.. Just kidding (:
I really don't think you will have that much time to solve this problem.
Exactly
22:05 🤯
You can literally just start from the lowest(number) birth year and count how many are alive at that time by using the restrictions of the other people’s birth and death years. If the number is within that range, then ++. Then compare that run through of the year to the next year. Get the higher one. Then repeat up until the highest(number) death year, and print out the highest year. Simple as that.
While that is a simple solution, it is not efficient, which is what is more important.
I think you don't need to make an array from min birth year to max death year in getDeltas function. You can just have an array with the years we encounter(interested years) while looping through people array. That way the use of garbage values are eliminated
What if an input would be a bunch of people that have the same birth date but different death dates. The delta array would have just one element and it is not going to work. We need to take the max death date for creating the delta array.
Why though, the birth date of all the people would be the year of highest population. The deltas array would have one element but I dont see why that may be an issue. The death dates don't change the year of highest population.
Some example people die at age 6 and 10... maybe longer life examples would be a bit happier.
I find this very confusing. Only a few helpful tips, but I feel like she doesn't stay on track and gets confused on what she is trying to say.
agreed! she even confuses herself and makes mistakes lol. I've read her book as well, makes every simple thing complicated by not staying on the track
Hmm, I disagree. I feel like she is trying to show you how she would think through this in an interview setting. This is the typical workflow. A candidate tries things, makes small realizations, makes mistakes, backtracks, then keeps trying to incrementally improve until the candidate hits an optimal solution. Which I think is what she is trying to say. I found this to be very helpful!
i found the programming part hard not the logic of solving it
It's possible to have the maximum number of people to be a death year, such as when a catastrophe suddenly wipes out a population when population is at max.
Complicated question and Zuckerberg did not even know how to build login system.
arTJs j 🤣🤣
she explains in the most disorganized way, with terrible numbers as examples. Also she made a mistake at 26:04 "1750 2 ppl born!!! clearly a mistake".
Thank you!
Ordering the data takes O(nlog(n)) time, why didn't she mention it??
I was thinking the same, but she actually doesn't explicitly order it , she uses the array indices to order
@@mythri24 The method she is talking about does require the data to be ordered and the starting data isn't necessarily ordered right?
@@dylanhurley1120 yes, the array indices is the order so arr[2000-first_birth_year] gets filled with +1 first and then arr[1750-first_birth_year] . Doesn't matter in which order she fills in the deltas cos running sum is then calculated in order of array indices. Make sense?
Are you talking to a cctv
Here's two solutions in Python 3.7 (i have no idea if i'm doing tracemalloc right)
from datetime import date
from dataclasses import dataclass
from collections import Counter
import tracemalloc
from time import perf_counter
from typing import Sequence
@dataclass
class Person:
birth: date
death: date
def alive(people: Sequence, year: int):
n = 0
for person in people:
if person.birth.year
in O(1) time, I can tell that the year is not (2020 or 2021) :(
only a sucker would solve a problem for free.
why wouldn’t you give all the necessary info to the applicant to solve the problem?...in real world you can gather info about the problem easily and there’s an infinite no of questions one can ask you usually design a solution knowing all the constrains
I find programming jobs in real world don't really give you the resources you need, you are just expected to make the magic happen lol
I’ve had interviews where they purposefully don’t give you all the information so that they can see how you communicate to get the info. It is an important part a developers job.
People won’t communicate expectations clearly in any field (you must ask, clarify, ask again, have it mutually agreed upon, and have periodical check ups now and then just in case things change)
What about if the pic is reached many times in different years?
She brought it up, and says that for example the interviewer would just output any of those. I suppose another answer would be just output them all, or output the min or max
put the years and deltas into a tree and then you don't need to know the min/max. then walk tree.
That's what I would have done also. You could argue though that inserting into a tree is log(y) and retrieving also, so since you're inserting 2p rows, and then iterating through the tree, the runtime complexity is O(2p*log(y) + 2p) = O(p*log(y)) where y is the year range.
log Y is going to be a fairly small number (even if we go back to the beginnings of civilizations, we'll only need to consider 5000 years) and the tree solution will use less space and will have much less rows to iterate over to get the actual result, but I would argue that while the tree solution is likely easier to code, the array solution will be faster.
With the array approach, you could have many empty values that you iterate through, but even if you iterate through 5000 ints, your array will fit in L1 cache, so skipping over the years with zero deltas will be super fast vs in a tree you'll likely get cache misses by following the pointers around in the tree and I am sure that the compilers will also be able to vectorize the array solution with some nice SIMD instructions.
This solution is O(P logP), which is great, but hers is faster (O(P+Y)) with similar space complexity.
45 minutes to solve, I was thinking at the beginning just to solve this in 5 minutes .... isn't it.
5min
1min for coding
4min for going to toilet
Or you can just do a functional approach (using TypeScript):
type Life = { birthYear: number, deathYear: number };
const getMaxPopulatedYear: (lifes: Array) => number = lifes => lifes
.map(({ birthYear, deathYear }) => ([ // Map to "life events"
{ type: 'birth', year: birthYear },
{ type: 'death', year: deathYear }
]))
.reduce((acc, item) => [...acc, ...item], []) // flatMap
.sort((e1, e2) => e1.year > e2.year ? 1 : -1) // sort ascending
.reduce((acc, { type, year }) => { // find max year with max population
if (type === 'birth') {
acc.currentPopulation++;
if (acc.currentPopulation > acc.maxPopulation) {
acc.maxPopulation = acc.currentPopulation;
acc.maxYear = year;
}
} else if (type === 'death') {
acc.currentPopulation--;
}
return acc;
}, { maxYear: 0, maxPopulation: 0, currentPopulation: 0 })
.maxYear; // Return max year
Why the heck you let them die so young! You are dealing with young fellas here... Don't say die then, find something else..
Thank you for the overview of your algorithm. I took the opportunity to build my own algorithm based on the information you had in your video with some assumptions. The first assumption is the list of people with birth and death years is not sorted by any means and to provide an algorithm that is object oriented and with minimal paths of execution. I wrote it in C++ but it obviously could be done in any language such as what you provided.
Here is my solution for what it is worth
// ConsoleApplication1.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
@
@
using namespace std;
// Class BirthDeath holds a persons birthyear, deathyear and a routine to determine if a person was alive during a given birthyear
class BirthDeath
{
public:
int BirthYear;
int DeathYear;
int Census;
// construct the class with default values
BirthDeath()
{
BirthYear = DeathYear = Census = 0;
};
// routine that takes a birthyear and determines if this person was alive at that time
bool IsInLifeRange(int nBY)
{
bool bInMyLifeRange = false;
if (nBY >= BirthYear && nBY
I would not want to work for her, she comes off very snobbish know it all.
In reality in FAANG / MAANG interviews: here is the problem. You have 15 minutes before the end of the interview since we wasted the first 25 talking about your work history and about the company.
I am afraid watching this video made me weaker in code. She doesnt know what the hell she is talking about sometimes.
C++ code (Logic is the same, just a little different approach):
#include
#include
#include
using namespace std;
struct EventYear
{
char symbol;
int year;
};
vector years;
bool compareEventYear(EventYear& eventYear1, EventYear& eventYear2) {
return eventYear1.year < eventYear2.year;
}
int main()
{
int arr[][2] =
{
{
2000, 2010
},
{
1975, 2005
},
{
1975, 2003
},
{
1803, 1809
},
{
1750, 1869
},
{
1840, 1935
},
{
1803, 1921
},
{
1894, 1921
}
};
for (int i = 0; i < ((sizeof(arr) / 2) / sizeof(int)); i++) {
for (int j = 0; j < 2; j++) {
EventYear eventYear;
eventYear.symbol = (j == 0) ? '(' : ')';
eventYear.year = arr[i][j];
years.push_back(eventYear);
}
}
sort(years.begin(), years.end(), compareEventYear);
int maxAlivePeople = 0;
int currentAlivePeople = 0;
int maxAlivePeopleYear = 0;
for (auto& year : years)
{
currentAlivePeople += (year.symbol == '(') ? 1 : -1;
if (maxAlivePeople
function population(r){
let lifeyears = [];
for(let i=0;i
I wonder why not many people liked this solution, it is so simple, but I guess it is very expensive since it has to go through all the years again and again for each person to populate the lifeyears list.
Is it just me or the sound that she makes everytime she is going to start speaking is really annoying ? :/
I wouldn't let someone pass if they actually go through all those phases and not get AT LEAST to 22:22 RIGHT AWAY
Can't you solve it in O(P log P
O(P) using hashmaps
Victor Nascimento would you mind explaining how you'd do that? Im relatively new to coding and you seem to now what you're talking about.
@@VictorNascimentoo How would you solve it in O(P)?
Linda hermosa
didn't take me 10 seconds to solve it. That's too easy