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, that's the year and I can hear that event. Okay popping all the year and 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.
Tea-Smoked Platypus: Alright, so this looks like a very good solution. Another way of thinking about this problem is the range of years that we have. Right here is from 1900 to 1949. That's basically our data set. So is there a possible way to reduce the complexity so that we don't have to store it?
Green Robot: We don't have to store it... So even in store by store in in my events, right? I have a heap too. Yes. Okay.
Tea-Smoked Platypus: It can go any lower.
Green Robot: Okay. Yeah. Thinking so they have a year. If I don't have that sorted, I want to know which year? Most people yeah, I'm thinking because this is a special case. This is like years. So the actual years, like aren't that many, like maybe we have like 2000 years maybe we can maybe have a array of years, each year represent how many people? How many people were actually were were born or dead at that year and each of the year maybe like a tuple. So I can basically scan through my people and take those births and death year as an input and modify my, my tuple. I mean, it's not modified, but is that I can use double or triple this. A list has two elements. So it's like for one and there for example. I can start from here. Hungry or hitting hunger, then resize I can make a bigger say 2100. Okay, so then the first one is 1800 and the second one is 180. Sure. 4 oh, the array size is basically how many possible years I have.
Tea-Smoked Platypus: Okay, so, yeah, considering it's from 1800 to 2100.
Green Robot: Yeah. 2100 Yeah. 2099 Yeah. Okay. Yeah. And so then this like a two element array, in I have a, like a live people alive, or well, I should say birth people. And in certain ways, that people can be all like this each year based on the index, and I just do scans through this constant array to update those birth people and dead people after I have this pre process, that way, I can just scan this array again. And to check because I know what the year each each one and I will try to add the two other people first. So I can get my current alive people and then evaluate that against the my current max people alive attribute. If that's actually more than that, I can update my year and current people alive, as are my immensity for life.
Tea-Smoked Platypus: Okay, so let's actually take an example. So maybe we have only the last shot on the range makes it easier for you to show. So you have to just want to see how your array would be formed and how to return from things.
Green Robot: Okay, so I will like skip some of them. Yeah, I still I probably need to have some time to figure out how to compress this array. There's lots of redundant information. Because I yeah, it's okay.
Tea-Smoked Platypus: You can go with whatever comes to your mind first and then we can optimize.
Green Robot: Okay, sure. So, let's say it's like 1920, I have birth one. And I mean actually is gonna have two death and then after a certain year, I have 1922. And so this is 19 1920 to 25. Okay. Yeah. So then I will scan through this again, I have I still have those variables that people currently. First, they were all zero. And then I have like, two, three is actually more than zero. So I will update this to two, and the year becomes 1920. And then I have I still go through this array and I encounter one death, zero more than one death. So I have one, and this one's unchanged. And then I have this one. I mean, I have one does and they were born on the first I need to check if there are any born additions to my current people alive? So I will, I will try to evaluate against the max people alive. See any possible chance I need to update my year? So the same after that I should have returned the next year. Okay. Yeah. I mean, definitely, this takes a lot of space, especially in some redundant space. But if we were to allow to use some, some sorting, like sorted array or things like that, we can optimize a little bit, but it's like a tradeoff and trading off the space for some, some time. So this can be linear time, linear space, lean startup cost of space, given that the year their top money. Is that sounds correct to what you were what you were thinking about?
Tea-Smoked Platypus: Yes, it is, actually. So both your solutions are fine, I wasn't expecting you to be exactly what I'm thinking code on them books. And you don't have to implement the second one, I think we are at 40 minutes, time. And we can just talk about feedback. So usually interviews are 45 minutes. That's why I don't want to actually push this to one hour. In fact, even shorter, like I think Google interview goes for 35 minutes or so because they talk about your work life and everything for 10 minutes. So this is actually very realistic, this time period. And let's actually get into the feedback now. So let me first go. And let me first start with giving the positive. So I really liked the way you actually asked the questions. There were a bunch of different corner cases that you were able to recognize in the beginning. And that definitely shows your meticulous attitudes towards the problem. And that you also, the solution that you actually gave right away was the most optimized solution that I had in my mind, because I wasn't expecting you to consider that there's a range. So you will basically have to solve. But then I just wanted to for discussion sake, I wanted to see if I can boggle your mind with another approach and how do you react to that? And it seems like it performed really well. And that's when I said the complexity is right. You wanted to give the complexity that's also very good. One thing I liked, also, and probably you should continue doing that is to write down what you're thinking. Your computation is really, I think, wonderful, you don't have to be worried about your communication skills. But the fact that you're also writing it down makes it super clear for the interviewer. So those are the positive, did I miss out on anything of course your problem solving skills and you know command on Python language, it seems good. So those are going to look good as well in your interview. You could I was given some hints but you know, you can expect the interviewer to be a few some hints and it's not considered. You know, it's not considered negative on your feedback. If you are receiving the hint correctly, or at least you're open to them. Oh, that's a very good thing. Cool. And I don't have a lot of negative points to give, I know, you probably want to see what you have to improve also on. But I think there were only a couple of places where I felt that you were too quick to go to an optimized solution, and have actually seen them this, myself and others do have that, you know, we know that solution might be somewhere there. But don't even think about it, don't even think about, you can save the conduct cases and say, I will actually, you know, work on this later. The downside of actually getting stuck in corner cases very early in the beginning, especially with the implementation part is that if you, if it complicates your problem to an extent that you cannot have actually handled in that time period, you saw, you have missed an opportunity to actually solve the problem. But you could have solved the problem if you went step by step. But now, because you actually made things harder for you, there's a possibility that you might not complete it. So just go step by step you make a data set, complicated one by one. And I wanted to, you know, I like hearing those questions. And some maybe some times I was extrapolating to what you were saying, but that's also fine. You did really well, actually, you definitely, if somebody would ask this, you can expect this as a medium level question. Most of the interviews would be of this level, I think even Google interviews of this level, so you did really well. And they would be I don't think I would have any negative feedback in my debrief. So very good job.
Green Robot: Thank you so much for the feedback, I appreciate that. Those are very helpful, especially for the for the corner case, one, sometimes like it's something I can do, or I can just skip, but like I kind of, I don't know, what should I do? But like, I just like naturally point them out. In the corner case. Yeah. But as you mentioned, maybe I should just keep that. And until I finish the implementation first, then maybe we can discuss those corner cases, or how to improve it. Maybe the first working solution first.
Tea-Smoked Platypus: Yep. And also, this, this is probably not a big deal. But you don't have to let down how you're going to implement the thought, like you're talking about prior to everything. That's all fine. But I have seen people actually getting stuck with data structure too much. And not thinking about the algorithm itself. So you can just say, I've got a thought it, I'm going to start this in a way that welcomes before death. And they are sorted by here. And that's all I need to know, at the time when I'm, you know, hearing your first approach. So you did fine in this. So I have no complaints on this interview. But it's another place that people actually get caught up.
Green Robot: Whoa, cool. Thank you so much. Appreciate that.
Tea-Smoked Platypus: Sure, and if you have any feedback you can get now or to me as an interviewer, or maybe how you like the question, or what else would you like me to do as an interview? And then we can wrap up?
Green Robot: Yeah, sure. Yeah, I think that should be about it. Like, I'm just curious, like, do you usually do a real interview in the real life?
Tea-Smoked Platypus: Then I started doing shadow because I just switched my company. It takes a while before I start interviewing.
Green Robot: But I will be taking into it because this is like the peer one. So I try to gauge or try to see if it's a real peer is actually really interviewer potentially. But yeah, thank you for for your time and appreciate that. And you're very professional. And I like the way you and I communicate with your interviewee is really great.
Tea-Smoked Platypus: Thank you very much. All right, have a wonderful time interviewing with companies. I am pretty sure you'll do the same thing. If you find the solution early in the question that basically have the problem done, if you really can make a mental map of how you're going to solve it. If you don't, don't never lose hope I've actually seen some interviews. You know, interviewers did not do well at all. But they did well in other interviews. But I could see that they could have well in the interviewed that I was actually attending as well, but they just lost hope. Oh, I see. I mean, it was hope they, they would have gone through because one bad interview really doesn't actually always make some negative feedback. So always keep your hope up. And don't worry about if you are not giving the solution that the interviewer is asking. It's good to actually, you know, try to judge what they are expecting you to do. But never lose hope for quantity.
Green Robot: Cool. Yeah. I will take a lot of that. Never give up. Never lose hope. Keep try.
Tea-Smoked Platypus: Usually, sometimes we'll like in a couple of minutes, you'll actually get the answer. And that can be at the end. And that will change your entire interview. So who Yeah, I've seen that in my mind as well. That has happened to me.
Green Robot: So sometimes the right answers are not super clear yet. Maybe we can to try to talk about it and walk through it. Sometimes you just came up instantly. So yeah, we never know, buddy. Yep. Cool. All right. Yeah. Thank you so much. I know it's pretty late. We know. I wish you have a wonderful night.
Tea-Smoked Platypus: You too. Good night.
Green Robot: Cool. Thanks. Good night.
Tea-Smoked Platypus: Bye.