Maximum Population Year (Python)

Python Interview with a FAANG engineer

Watch someone solve the maximum population year problem in an interview with a FAANG engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary
Problem type: Maximum Population Year
Interview question:

  1. Given a list of JSON objects containing years of birth and death for a given person, return the year in which the most people are alive.

Interview Feedback

Feedback about Green Robot (the interviewee)

No negative feedback to give.
Interviewee's communication skills are spot on. He was clear and had a very systematic approach to the problem. His written notes helps interviewer be on track.
Interviewee programming solving skills and critical ability are strong. He has ability to handle challenges thrown at him during the interview.
Interviewee could volunteer with corner cases and time/space complexity.
Interviewee was respectful and polite in his tone.

Feedback about Tea-Smoked Platypus (the interviewer)

The interviewer was very professional and I love the way the interviewer plans out the full interview schedule early during the interview, by checking the background, fundamentals and expectations from me, so as to provide more customized interview experience. During the process the interviewer clearly responded all the clarification questions and provided very helpful comments and feedback at the end. Definitely recommend the interviewer to other folks.

Interview Transcript

Tea-Smoked Platypus: Hello, can you hear me?
Green Robot: Yeah, yes, I can hear you hear you?
Tea-Smoked Platypus: How are you doing today? I can hear you.
Green Robot: Cool. Awesome. Yeah, good. How are you?
Tea-Smoked Platypus: I'm doing good. So have you actually done any of these interviews before on interviewing.io?
Green Robot: Yes, I did. I did a few times.
Tea-Smoked Platypus: Okay, awesome. So let's actually, let me first start off with putting out an agenda on this interview, on what we are going to do. And if you have any other expectation, you can actually put forth that as that.
Green Robot: Sure.
Tea-Smoked Platypus: Just a little bit about myself. I am Seattle based software developer, I have around four years of software development experience. And I yeah, would you like to tell what you're expecting from this interview? What kind of questions would you like to see?
Green Robot: Sure. Yeah. So I'm in the Bay Area in the San Francisco Bay Area. And I've been working in the infrastructure space for like, three, almost three years. I like after I graduate from school. And so I've been working on some network automations and some of the traditional SRE tech stacks. And my language has been Python or Java. But in the work, I used to do a lot of Python and then recently did some Java. But for this interview I'll just do Python? Yeah, that's about it. Oh, it's for the expectation. I just want to practice more so that I can practice my communications and how to like, talk to the interviewer and how to walk through those problems. Yeah, that's about it.
Tea-Smoked Platypus: Okay, that's good. Do you want to do any system design interview question or just a programming question?
Green Robot: I think just programming is good for now. Yeah.
Tea-Smoked Platypus: Okay, sounds good. So what we are going to do is that we are going to put forward a question, and then we are going to work on that for around 40 minutes. And for the rest of the talk, we'll just discuss the feedback. And you know, if we can actually, we'll talk about the problem if you can, but that's the agenda for the interview. Right? So you can you can select your language, and then I'll actually explain you the question.
Green Robot: Sure. Let me select Python3. Cool.
Tea-Smoked Platypus: Okay. All right. So basically, the input that you're given is a list of... it's a structure like this, and you can actually, you know, structure the input as you want. But consider this a JSON, which basically has a name of a person. So, there's like Joe, and for that person, it will have when the person was born, that will have the bot here. Okay, so let's say 1900. And when the person died.
Green Robot: I can actually put a multi line comment for you.
Tea-Smoked Platypus: Okay, thank you. And, and died maybe like in 1930. Okay. So, you have basically an array of this, they are more... Okay, and I can just copy this put it on, maybe born like 1920 and died I mean, like in five years, as a child. Alright, so given this data, what we are interested is to find out what was the year when most number of people were alive?
Green Robot: Okay. Let me write some notes. Find out what was the year when most of the people alive?
Tea-Smoked Platypus: Yeah, most number of people alive, most number of people.
Green Robot: Okay. I see. So I'm assuming that I we are given an array of people profiles, so to speak. And should I assume like those people are? Like the structure of the data is very valid. I mean, like they they will have a birth, and they will have a death. And that's always greater than the birth.
Tea-Smoked Platypus: Yeah, yes. So we can consider that to be valid. But that's actually a very good question. So there might be scenarios where a person hasn't died yet. But let's actually talk later. Let's just focus on the basic case.
Green Robot: Okay, I see. Input data invalid. So if hasn't died yet? Shall we represent that as a null or some some special attribute to?
Tea-Smoked Platypus: Yeah, you can, you can consider it null. Basically, I am giving you the freedom to structure this as you want. So consider it as a part of your test.
Green Robot: Okay. Find out what year the most people are alive. Yeah, I'm thinking, basically, we have an array of people. And so I think so I'm assuming like the order of those people, they do they have any predefined order, or I might have to... I might need to order them by myself.
Tea-Smoked Platypus: So they don't have an order given. Yeah.
Green Robot: Okay, gotcha. I see. Cool, I'm thinking we can, because I want to check basically, check those years, like special year, basically, somebody was born, and also done some special year that somebody was, like, died in some of the year. And then we can know a specific year, based on those events that happened. I can derive like how many people actually still were alive in a specific year. And to do that, I might want to sort this array based on the people's birth year. Okay. If I sort this time this year, the death year could be None.
Tea-Smoked Platypus: Don't think about that scenario yet. Let's just focus on the basic scenario. You are given valid data. Initially, you can even think that but sorted for you. Let's go from there.
Green Robot: Okay, okay. Sure. Yeah, I can maybe like for the special scenario, I can just set up my career like 2021 but death could be 2022. So the person is still alive in a special case, but yeah, sure, let's assume they all have died already. And then they have a birth and death number and they are valid because the deaths are greater than the birth could that be possible that somebody like birth in 1920 and actually death in the same year?
Tea-Smoked Platypus: Yes, that is possible.
Green Robot: That is possible. Okay. Cool. And in that case, I would not say that person was alive? Like, but...
Tea-Smoked Platypus: You can consider basically, you can consider that the birth is on January 1st, and death is at the end of the year, so even if they died somewhere in the middle. We don't have the precision to say when which month they died. So we can just consider they were alive the entire year.
Green Robot: Oh, you mean we consider they were alive the whole year. Okay, take some notes here. Cool. If that's the case, I think, as I just mentioned, I want to basically check some of the events. So what I would do is I want to have some have a priority queue to... I mean heap to contract based on the timeline. And so basically, I will parse those people, profiles into different events, like a birthday events and death events. And then I will scan through people and put those events into my priority queue. And our queue is going to be sorted by the key of the birth year. I mean, that by the year of the birth or death, and then I can. So out of the key value, I can know whether who is this person or and what was the event like a birth event or death event, and then I can keep a track of that. And like a global variable or something, I can track how many people are actually alive per year. And then I can just keep updating this, my max people alive. And eventually I will return but I think it could be a range. So how would I return this, would I return a range of the year or just something specific? One year? Or maybe?
Tea-Smoked Platypus: Now we're looking for? So that's another good point. So there might be multiple of them, which have the highest number of people alive, just written the first one or any one of them is fine.
Green Robot: Okay. Range of year in years. Yeah, I think my approach would be like, scan through the people profiles, and basically log the event and death event with the timeline. And put the events into a priority queue, sort by the year. And basically maintain, I guess I need to have two variables for now, like current people alive max. Three, sorry, three variables. Max alive year, so six. So that if I have something that's actually more than my max, I will update my answer. And eventually the max alive year. Yeah, that's my initial thoughts for now. I think in this approach, like so, for example, each person had like two events, right, birth and death. And so assuming like, we have n people. I think the time complexity should be because I'm maintaining some priority queue. I need to keep pushing into my queue and popping. But I think in the order of log n times like O(log n). It's my queue Is my priority queue is actually it's actually two n. But I will say it's O(n). And then each time I'm pushing popping, and then it's like log n operation, that I have like two n events. So that could be represented as O(n log n). For space, because I'm using the heap. So I'm using the structure to advise is a O(n) to store those events. Plus those constant variable so should be ignored in this case. Yeah, that's for my initial thought for now.
Tea-Smoked Platypus: Okay, that sounds good. Do you want to implement it?
Green Robot: Yeah, sure. Let me implement that. Okay. Yes. Can I borrow your example?
Tea-Smoked Platypus: Yeah, sure.
Green Robot: Yeah. Okay. Yeah. Put a new find next alive. Building some profiles. Notice for now, so I'm getting some... I will say I have an event. And I need to import heapq. So basically, I need to scan through the profile. So for this is like a JSON file. So people maybe people and so the name people dot get name. Should I assume like there is no duplicate names? In this example?
Tea-Smoked Platypus: Yes, you can.
Green Robot: Okay, cool. Yeah. I get the name. And I think I need to have birth year, two years ago, basically, because of the birth year because it's birth, I want to maybe represent that as a one, kind of like one more people. And I would their thing because there's a priority queue. You want to process the like, if sometimes they some people like died at certain year and another people born as the year I want to what order I want. I wanted to have all those born events happen first. So, that to address if if birth and death happened to be the same year I would consider this person as alive. So, how do I maintain that to be the birth year okay maybe this is a min heap, the reverse one. So, here minus one for sorting purpose so the first thing I know I have profiles I just need to check the events so, I want to pick those actual year to call those actual year. Okay, I think I can do a while loop to check peeking and see if they have the right font I have some special case all the people actually were born or born at the same year and they died the same year and some extreme cases. So like why we events and ENTS keep the year equals a year and process that and curr people alive. If current people and check this and because they are the same year, curr people alive same year. It's a little duplicate. Now I'm make sure it's actually out of the while loop from there actually a different year people and in the event. Yeah, I think that's basically the structure of this. Let me write the test cases. In this case profiles. Should I walk through the code first before we run the test?
Tea-Smoked Platypus: No, you can begin on the test, I think your code is pretty good.
Green Robot: Sure. Okay. Find max alive year getting the profiles. Give me something to try. Max people alive equals to line number 47. Profile is not defined. Like I because I have three people. Because I have three people over there. Yeah. Okay, this return the expected result. But this is just like one case. Maybe I can try a few multiple cases.
Tea-Smoked Platypus: So what are the other type of test cases setting and tested that?
Green Robot: Yeah, I want to check like because these are they have overlaps. I want to check some something that doesn't have overlap. Maybe? And so, for simplicity, I just put a single letter for now, but like this, okay. And then I want to test some special case. How do I show this? I need to make sure this special case actually, more than that, so that I can I know my logic actually is correct. Let's say 45 45 2020 2025 and 2020 thing they're identical. They're the same okay. So, I have these are back in 1920 through 1925 that like two people are alive. And then I have like three people they are quite... Why is normal, the other one is like by the same year and the third one oh third one is actually the same. So this test case should test like whether we like if they are alive and die at the same year. We consider this person as alive. And then that should give us three people so the year should be 1945. Yeah.
Tea-Smoked Platypus: The second one, though, maybe actually wasn't alive at 1949. So probably make that as many. Is that okay? Cool?
Green Robot: Cool. Let me try it. If it works out, 1945. Cool. So that gives us an idea of this. The number the person B actually was born in 1945 and also died in 45. We try to process the birth event first.
Tea-Smoked Platypus: So this is actually looking good already. So I have only one one follow up question here is that if we were to have a structure that does not mention death, what are the information that you require to be able to compute the your which has most number of people alive?
Green Robot: You mean, like the we will know the people's death year?
Tea-Smoked Platypus: Yeah, if there are people who are still alive, we won't have that. So have that be like, we can actually, you know, run that as an example. So maybe actually take C and let it let him be alive. And try to adapt your code for that.
Green Robot: Okay, I think I can like this here is not none. In Python, if I do the get, I should get none by default. But I mean, I can actually write it. But because the function itself will return None because I don't know, maybe it doesn't have a death year yet. But should we assume like they should have a birth year right? Each person? Yes, these they have a birth year. Okay, cool. We don't need 100 in here. Yeah, I would just like skip the event for the death for now. Because I know it was that people was born over there. And, and at any year, that person, I mean, when I was checking the events, and any year, it was still after the birth year of the person was still alive. Okay, yes, this will work.

Feedback