Java Interview with a Google engineer

Watch someone solve the employee hierarchy problem in an interview with a Google engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Employee Hierarchy

Interview question

Given an array of employee IDs including who they report to, write a function to calculate the score for a given employee. The employee score is equal to the total number of direct and indirect employees that report to that employee, then plus one(self reporting).

Interview Feedback

Feedback about Massive Chameleon (the interviewee)

Advance this person to the next round?

How were their technical skills?

3/4

How was their problem solving ability?

3/4

What about their communication ability?

4/4

Good interview! You were able to solve all the parts of the question that I asked, and you communicated well throughout. There were a couple of places where you could optimize the solution a bit, but nothing major. Whenever you use a data structure, it's good to explain why you're using it. Feel free to reach out with any further questions, and good luck!

Feedback about Electric Avenger (the interviewer)

Would you want to work with this person?

How excited would you be to work with them?

4/4

How good were the questions?

4/4

How helpful was your interviewer in guiding you to the solution(s)?

4/4

The question clear and the interviewer's explanations were very helpful to guide me. I really appreciate the tips in the feedback part too. Overall today's session made me a bit more confident for my interviews. Thank you!

Interview Transcript

Electric Avenger: Hello.

Massive Chameleon: Hi.

Electric Avenger: Hi. How's it going?

Massive Chameleon: Hi, yeah, I'm doing good. How are you?

Electric Avenger: Doing well, thank you. It's now a good time to talk?

Massive Chameleon: Yeah.

Electric Avenger: Okay, great. Do you want to start off then maybe by telling me a bit about yourself, how much experience you have, where you're up to with the interviewing process, that kind of thing?

Massive Chameleon: Sure. So I am done, I am working as a front end developer in Singapore. So my experience is mainly in web front end. And I am, I have about three and a half years experience in front end. And in my job, I deal with the promotional discounts features on an E commerce platform. So this is something that is used mainly in Asia. We also have some in Latin America, but the main market is in Southeast Asia and Taiwan. And currently I am in the process of preparing for on site interview for Google. And my interviews will be in about two weeks time to unhealthy. So I hope I'm hoping to have more practice to get used to the environment under pressure. So thank you for being here.

Electric Avenger: And what level are you interviewing for?

Massive Chameleon: I think it's still L4 the Junior one because I don't have the system design interview.

Electric Avenger: Okay so L4 right. Okay, cool. And did you do a phone interview or just the on site?

Massive Chameleon: Um, it was a phone interview. I had a phone interview for the next round is a virtual on site. So it's still an online interview.

Electric Avenger: Sure, but you did the phone interview already?

Massive Chameleon: Yes, I did one. Yeah.

Electric Avenger: Okay, cool. Okay, so in that case, what we'll do is we'll go ahead with a mock interview, it will be 45 minutes long, just like a real Google interview. And after we finish the interview, then we can discuss feedback and that kind of thing. Okay?

Massive Chameleon: Okay, sure.

Electric Avenger: Okay, cool. So what programming language you want to use?

Massive Chameleon: I will use Java.

Electric Avenger: Java okay, cool. And if it's okay, actually, let's switch it back to a plain text. And the reason that I say that is because the interviewing IO platform, sometimes it might highlight certain errors in your code, that kind of thing. Which won't happen in a Google interview in a Google interview, you're getting that syntax highlighting, but that's it, you won't be able to run your code or debug it or anything like that. So I think it's best if we stick with plain text okay?

Massive Chameleon: Okay, sure.

Electric Avenger: Okay, cool. Sounds good to me, for me, let me note down the time before we begin. So it's around 704, where I am to 749 for the interview, and then we'll discuss feedback afterwards. Okay. Are you ready to begin?

Massive Chameleon: Yep.

Electric Avenger: Okay, cool. So what I'll do is, I will read out the question bit by bit, and I will also copy and paste it, so you can read it for yourself. Okay. Sounds good. So, the employee score for an employee is equal to the total number of direct and indirect employees that report to that employee, then plus one. And the plus one here means that we are adding the employee itself as self reporting. So I'll copy and paste that so far. Give it a read. Let me know if it makes sense. And then I'll continue with the question.

Massive Chameleon: Okay, so, right. Okay. Okay, plus one so that is the employees themselves. Okay. Understand, okay.

Electric Avenger: Does that make sense so far?

Massive Chameleon: Yeah.

Electric Avenger: Okay, cool. So an employee without any other employees reporting to it will have a score of one. And each employee has a unique ID. And given a direct report map, where the key is the ID, then the value will be an array of IDs, who directly report to the key and the map contain all employees. Okay, so we're gonna copy and paste that. And now maybe let's have a look at a map as an example. Okay?

Massive Chameleon: Okay.

Electric Avenger: Okay, cool. So as you can see, in this map here, we have 123. That's an employee. That's the idea of one of the employees and it has two employees, but directly reports. It has 234 and 345. Right. And then if we look at 234 that also has two employees that report to it, 456 and 789. And then if you look at 345, that has no one that reports to it. Same with 456 and 789. Does that make sense?

Massive Chameleon: Okay. Can I kind of assume that no employee will report to themselves?

Electric Avenger: Can you say that again?

Massive Chameleon: Can I assume that no employee will report to themselves? Like, there wouldn't be a case where, for example, 345 and then direct employees themselves to qualify, for example.

Electric Avenger: We'll talk about that kind of thing in a minute. Okay.

Massive Chameleon: Okay. Okay.

Electric Avenger: Sure, so let's just have a look then. So could you tell me, what's the score for 789?

Massive Chameleon: 789? So they don't have any employees directly reporting to them? Okay. But they report to 234.

Electric Avenger: Right.

Massive Chameleon: So, the score is still one, because there's no one under them. So they only have themselves.

Electric Avenger: And what's the score for 123?

Massive Chameleon: For 123, you have to go to the score of 234 plus score of 345. So 234, the score of 456, is one, 789 is also one, so 34 will be three, and then 345 is one. So 123 will be three plus one plus one is five.

Electric Avenger: Okay, great. Awesome. Okay, so now let's think about when the map might be invalid okay? So essentially, let's think about this as being a real company. So we're trying to think about what situations would make it, you know, essentially not make sense. So again, I don't care about kind of your data types or anything like that. I'm thinking more from a business perspective, what data could be put on this map? That wouldn't really make sense, you know, something that would be invalid from a business perspective. Okay.

Massive Chameleon: I would think it would be that an employee that is supposed to report to someone above turns out to be the boss of that employee. So, for example, if we have 234 reporting, to 123, if in the array of 234, we also have 123, that doesn't make sense, because 234 is supposed to be the boss of 234, 123 is supposed to be the boss of 234. So if we have the reverse, also being true, that doesn't makes sense.

Electric Avenger: Okay, sure. Anything else?

Massive Chameleon: I think someone cannot be the boss of themselves.

Electric Avenger: Okay cool.

Massive Chameleon: Other than that? So we can't have a reverse relationship, and we can't have an employee being a boss of themselves. I guess an empty map, is also I mean, it's stranger, it's also possible. So it's like, a totally empty map. There's no employee, or even just one employee who had no direct person reporting to them.

Electric Avenger: Yeah so I guess an empty map just means the company has no employees. And if it has one employee, then that's also fine. So I think those two would be balanced.

Massive Chameleon: Okay, so for the invalid cases, I guess I currently only thinking of those two cases.

Electric Avenger: Okay let's write them down. And the first one you said was, essentially manager can't report to their reports and number two was, no one can really count the loss of themselves, right.

Massive Chameleon: Yeah.

Electric Avenger: Because they can't, we want to use the same terminology, can't report to themselves. Right. Let me let me fix that. Okay, cool. So I'll tell you some other situations. So another one is that a employee can't have more than one manager.

Massive Chameleon: Oh right I see.

Electric Avenger: So for example, let's say I put 456 over here. And the question is, who is the manager of 456? Is it 234, is it 345? We don't know. Right? So an employee only has one manager. Okay.

Massive Chameleon: Okay.

Electric Avenger: And also, the final one is company has only one CEO.

Massive Chameleon: That means only one person with no boss.

Electric Avenger: Exactly. Yeah, exactly. So, and we can actually look at the one, one and two, and we can probably generalise that a little bit more as well. Because, say you have 123 and then have 234. And you have 234 and 456. If I put 123 reporting to 456, that's also a problem, right? So it's not just manager can't report to their report. It's to essentially any of their reports. So if you want to be a bit more generous. I'm gonna say that no loops, if that makes sense.

Massive Chameleon: Okay, okay.

Electric Avenger: Does that make sense?

Massive Chameleon: Yeah. So in the report, the managers cannot report to either direct or indirect reports.

Electric Avenger: Exactly, exactly.

Massive Chameleon: Okay, understand.

Electric Avenger: So, so no, loops can't have more than one manager. And company has only one CEO. Does that all make sense?

Massive Chameleon: Yeah, yeah.

Electric Avenger: Okay, awesome. So now let's go ahead and write some code. Okay. So let's begin by writing a function, okay. And the input to the function will be an employee ID. And what you have to do is you have to calculate the score for that employee. Okay. And let's say that, that a direct report map is going to be a global variable, and you can access that variable anywhere in your code, okay. And lets also assume that the map that you're given is valid. A all of these three rules that we spoke about, you don't need to worry about them. There's no loops, every employee has one manager, and the company only has one CEO. So that's all fine. So assume map is valid. Does that makes sense?

Massive Chameleon: Okay, can I also assume that the employee ID will always exist in the map? Or will there be a case where we don't have the employee at all.

Electric Avenger: You can't assume that no.

Massive Chameleon: Okay, okay, understand. Okay. So if the employee doesn't exist, we can just return zero since we don't really even have an employee in the first place. So looking at these three rules, I think we can essentially represent this map as it it visually is like a tree, because there's only one root. There's no loop and every node has only one parent has a maximum one parent, because except for the root. So if we want to calculate the score for each of the nodes, I think we can go recursively, lets me so for every, for every. Like for every node there for that node, like recursively, the sum of every node every child in that node, and then plus one. So in the case, whereby that node doesn't have any children, then this part will just be zero, and we have one and then we can do this recursively. So for example, if our query is 123, we could we recursively call the call function on 234 and 345. And then when we get to 456, we get one and then 789 also get one and so on and so forth. So, I Yes, I think that's the direction that I could go for.

Electric Avenger: Okay, sounds good.

Massive Chameleon: Okay let me think of any other thing I have to take care of. Okay. Yeah, I think yeah, I think we have the direction. So yeah. That your access each employee in the indirect and direct report only once so so each node only access, they access at most one, so that should be in time complexity is linear O(N), N is the size of the, yeah. I think we can start coding already.

Electric Avenger: Okay.

Massive Chameleon: So read through the score for the employees can be the input Okay, so i'm trying to see the type of the employee ID employee ID will actually be an integer or is it true?

Electric Avenger: That's up to you or whatever you want

Massive Chameleon: I think I think I would prefer it to be string, it can also be integer it's just that if the, if the range of employee id is higher than for example the integer range then that would be just a bit troublesome. So I think... yeah, I think maybe a string would be good

Electric Avenger: Okay, can you just explain again why why you prefer string over integer?

Massive Chameleon: I think that for string it will you'll be able to have a larger range of employee ID, for integer if let's say the range in the problem statement itself can go very very large then then I guess here we are using a maximum it might be an issue but I just feel that if we use string we you can have a larger range of numbers.

Electric Avenger: Okay.

Massive Chameleon: So right this one will be our recursive function so what I need first in the beginning of some score is zero and then we will find recursively the score for each of the report this ID so I will need to get the so is an array of strings of the reporters and everything so. Okay, now it'd be might be that I need to take care of the case where by the people. I think we can that's called net employment. So if the, if the risk is that if the main net doesn't contain our ID we should return zero otherwise, we will find the sum of the form of our direct report and then plus one. So for every person we've got to us we will find the scope for that person. So this is usually the gist of it. So if if the company doesn't, doesn't contain this employees, we return zero because there's no such person otherwise, you will get sum of all the direct reports.

Electric Avenger: Okay, so, so now let's imagine that this function is going to get called many times, right? So if I call it say with 123, and the first time it's going to calculate it, and if I call it again, it will also calculate it every single time. So is there a way that you could maybe improve it, but if I call it multiple times, we get better efficiency?

Massive Chameleon: Oh you mean if I call, get score 123 multiple times outside, is it?

Electric Avenger: Right, so one second, I'm just gonna, I'm gonna mark this as the v1. Okay.

Massive Chameleon: Yeah. Okay.

Electric Avenger: Now lets go down here and do v2. If you want, you can copy and paste some of the v1 if you want to, but essentially, let's make a new version, where it's more efficient, if you call it repeatedly.

Massive Chameleon: Okay, so we have made that score to the same by ID I guess we can store that score number in a global map. So it can be something, it just, it could just be a HashMap actually, so it will keep track of our... So lets just say score map. And we will keep the score of our simply based on the ID says here. Its still the same the company doesn't have that person we will return zero. Otherwise if the score map actually contains this person already, then we can return from our, its like memoization. So, everything else should be the same. So I think, let's say if, if the, if the calculator is large then you might need a long chain for integer otherwise you can just integer.

Electric Avenger: Okay.

Massive Chameleon: Okay so after I, I calculate this, then I have to store this, score of this person inside the map so that we can access directly.

Electric Avenger: Okay awesome. So now let's try v3. Okay. So v3 essentially is that if you look at your v2 it's good in that the first time you call it It calculates it and then every other time you return it from your map right? Let's say we want it to be even better such that the first time you call it it returns in O(1) time okay. So, can you think what you would do in order to make it you know, even the first time that you call it be something like O(1) time and again feel free to copy and paste any of your previous code if you want

Massive Chameleon: Oh right. If you want to do that, I think because we need to calculate recursively the direct report for the first time, so if we want such that gets called always returned constant time I feel that one way is it just to calculate everyone in the beginning that means I need a helper functions. Okay, so If I want to calculate everything in the beginning then I need to, It's something like try to get score from the CEO so that everyone above, everyone below will be calculated. So that means I need to try to find our CEO and then. Okay, so get score here becomes get score of whole tree and then our O(1) operation is basically to get from the map now I'm thinking so the it's like very heavy precomputation kind of yeah. So, now get score is...Okay so I will find the CEO and then I will calculate score from there. And I'll get them that score, will probably be just slightly between score and map. So for, okay I will leave this first and for calculate score, first I need to find who is the roots of this tree. To do that there's a few ways one of the way is to go through it, I think one of the ways to try to find the one who has no direct report, and how do I do that? Let's say every time I have... So for every entry then that that value for that entry we can we can have one incoming edge counts for each of the number inside ID arrays in the one which incoming count is zero is the root of the tree. Okay so I guess I can know that it will be a linear traversal so something like, wait let me think, okay so I need another map basically to store the count. Yeah just to store the count or maybe just to store the employees maybe I need to constantly I just yeah just have have a set of all the reports so the CEO should not appear in this set.

Electric Avenger: Okay.

Massive Chameleon: So maybe we can still...okay so for every employee map key set...We will get this key we will need to add the T you just need to add everyone inside the report array. So, now, I have to go to the T set and if I find someone which is not inside reports then maybe I'll see you soon. If it doesn't contains our key then this is our root and you can break in the case there is no root, I guess that's where the environment is mostly empty then there's you don't have to calculate any score basically it will be everyone is there. So, I guess we can still. If the root ID is not empty then we will try to we, we will calculate score okay. I probably need another helper function just to get the score so maybe I will need to rename this. Okay never mind. We just want to actually do the calculation and import here. Yes, so this is our pre processing step and...wait I need to okay, so score map, I still need the score map as global arrival. So then for the calculate score, it will be doing, it will be the one that is doing the... Ah Okay, so here I will calculate from the root. So the calculate score helper is the one that is doing the heavy lifting.

Electric Avenger: Okay.

Massive Chameleon: Otherwise this one. So by the time a call gets called we should have the score map ready. So, there should be a case where the employee map has id and score map doesn't. So here, I'll just paste that here so... Okay. Okay here is no helper. Here the ID should exist in our ID map and we can also copy this part out here again. Let me just check it, here is not get score anymore, but it is our own function. So this one is the one that would do the recursive and then we put it in our score map. So this one cannot be a void it has to be an integer. This one will be O(N), I mean this one will be constant but this one is O(N) one.

Electric Avenger: Okay.

Massive Chameleon: This is our key processing function.

Electric Avenger: Okay cool. So, if you remember early on, on line 16 17 18. We spoke about three situations when the map is not valid right. So, maybe do you want to pick one of those situations now up to you which one you want to pick and can you write a function that will validate the map to see if that is true or not. So, for example, if your first one is just a map containing loops a lot of you pick the second one you have to verify for every employee do they only have one manager and for the third one you would have to verify does the company only have one CEO So, pick one of these and write a function that is for validation okay?

Massive Chameleon: Okay. I think the third one might be... the second and third one is probably related, because in this case for example, like we can still have the HashMap to keep count of how many incoming edges go through this node. So, if this node has more than one incoming edge for example, like here two people will have one but if its somewhere along the line for example 234. For if it appears here, then we increase the incoming counts. So, any case someone has more than one incoming edge to them then two will be evaluated. And and in the end, we can also try to check how many nodes has zero incoming edge that means they have, if we have more than one not zero incoming edge that means we have more than one CEO so you also get invalidated. So I think the more tricky one is the no loop in order.

Electric Avenger: Okay.

Massive Chameleon: I'll try to do this. In order to do this on... we can try to use, it will be easier to use DFS and BFS because it's more relevant for us first here. So using, okay, so we have to check for all loops. So that means okay, maybe I still need to find the CEO. Yeah, yeah. So so we start, you start switching from our CEO. Then we DFS on that node and we keep track of the nodes that have been visited so far. If any node is visited twice then there's a loop. So let me think. Can I take it that the part of a finding the CEO is taken care of?

Electric Avenger: Okay can you say that again?

Massive Chameleon: Can I just like if we want to find the loop then we will have to get edge from the root of the tree. Can I take it that the root of a tree is given or do I have to find the root of the tree again.

Electric Avenger: So, if you don't know if there are loops. How do you know what the root is?

Massive Chameleon: Oh yeah yeah yeah right. So, in the beginning if the map is not empty and yet there is no CEO then there must be a loop somewhere. Otherwise if there is a CEO then we will have to DFS from that CEO because we don't know yet at that point. Whether there is a loop down along the lines. So in the beginning I still have to check the incoming edges for the nodes and check for the one that has zero incoming edge. If there's no such node and if the maps not empty that means that means we don't have any roots but if there's a root then I have to give edge from there because...I don't know...Even though...I don't know if there's the loop along the bottom.

Electric Avenger: Okay.

Massive Chameleon: Let me think, yep okay so I think, I think Okay, so let me try to do the visit loop part. I think I tried to do the validate node part.

Electric Avenger: Okay sure.

Massive Chameleon: So I think I can borrow some of the code from here. Yeah, we will still try to find a route ID. Will defend against the case whereby the employee map is empty first. Now we try to find the root. So, if we can find the root... if okay so, maybe you just you can go in with anything. Let us use this as our main. So if map is empty then this node but...

Electric Avenger: So, just to clarify, when will your function return true and when will it return false?

Massive Chameleon: So it will return true if there is a loop.

Electric Avenger: Okay.

Massive Chameleon: So if you cannot find any CEO and the map is not empty, then there is a route. Otherwise we are DFS from our route, here let's just say that we also can't be sure whether there's only one CEO. So, there might be more than one CEO. If that's the case we just have to DFS multiple CEO. Yeah That means sure I have to start a list of CEO for... Can we for the sake of this task, can we assume that the condition three and two are all related?

Electric Avenger: We don't know that no.

Massive Chameleon: Okay. Sure. So, I think I have to I actually have to store all the root ID. So ID we insert this key. Then if there's no CEO there must be some group otherwise we will have to use DFS Okay so I'm thinking if DPS can also return a Boolean. We also have the employee ID here and you will need to store. We need to store visited nodes. A set of visited nodes here to mark that yeah, we have visited that node already. So if the visited already contains this employee that means there is a loop. Otherwise we add it to the list in for every report the noticed person. That also lead to a loop then you can return true. If all this condition is uh if none of the direct and indirect employee cast a loop we can return oh so here it is, I have to visit all the CEO. Okay so for all this because the part about which employee only has one manager might not be validated so there might be a time where we have two parents even though it doesn't cause a loop. So we have to refresh the visited set and then um and then... If this root id would cause a loop then we can shortcut here. Yeah basically yeah this part I just it's just pre processing like previously to find all the root IDs. So, the main part is to perform DFS on all the trees inside the forest. It might be, I think the tricky part is like, if someone has more than one manager then if we don't refresh the set then we will run into the like false positive here. I think yeah, maybe a better way to check for no root might be using something like topological sort instead.

Electric Avenger: Sorry could you say that again please?

Massive Chameleon: So, I think the topological sort is basically to find valid order of this of this forest such that the node behind a certain node, for will be the children of the node in front. So, if we have such a valid ordering, in fact, without strict rules, that means, there is no loop inside our grasp for us. If we can't find such an order, then there's no root so, so, there is some loop between that one. It will solve the problem of having having one whole loop or that there is a root and then some loop in-between instead of this part, where I have to find whether there is such a CEO or not. Yeah, so, and yeah so if we use topological sort it will take care of the known CEO and the CEO and look below and take care of both cases.

Electric Avenger: Okay, cool. So, we have around two minutes left of the interview now. Okay. So if this was a normal interview, I would normally leave maybe five minutes at the end, in case you know, the person I'm interviewing has any questions for me that kind of thing. But seeing as this is a mock interview, I think because we only have two minutes. I think it makes sense to go to the feedback now. Okay?

Massive Chameleon: Okay Sure.

Electric Avenger: Okay, cool. So I'll kind of go through my notes. So I began by presenting the question to you, and you asked about if employees can report to themselves. I then asked you about the score for 789 and 123. And you've got that all correct. So that was good. And then asked you about invalid cases. So you mentioned about manager can't report to their reports, and that they can't be a boss or themselves. And then you also spoke about what happens if there's an empty map or a map with one employee, so that was all good. And then I kind of gave you the other ones about having one CEO and not having more than one manager. So then I presented to kind of version one of the question. And you asked about if an employee might not exist? That's a good question to ask. And it's always kind of good to validate your inputs. That was a good question. And you said that you could return zero in that case. And then you also mentioned that the map is a bit like a tree, because it has no loops in it and only has one parents. And you mentioned about recursion. And your comments on line 23, which I thought was nice, which kind of explains how the recursion works. Line 23 was good. And you also proactively spoke about the time complexity and so that it would be O of n. So that was good. So then, you've got through to your implementation, I would say you had a good variable names, good function names. So that was good. I guess one small thing is that on line 30, you initialise the score to zero. But if you want, you can actually just initialise it to one, and that would also work. And you can remove the plus one at the very end. So that's a small improvement you could do. Another thing is on line 28, where you return zero if the map doesn't contain the key. Personally, I would probably throw an exception here, I think if you return zero, say you're calculating the score for 123. Right? And somewhere deep down in the tree, you find an employee who doesn't exist, that means you're going to return the score for 123. But it will kind of be inaccurate, right? So personally, I would say, in this case, it makes more sense to throw an exception because then you know that something has really gone wrong, that the map isn't correct. So that's what I would say as opposed to returning zero, because if it returns zero, you don't know that anything is wrong. Whereas if you throw an exception, and then you know, okay, cool. So then we got to version two, which was about kind of, you know, essentially caching it if we call it more than once, so you made another map that was fine. And then you kind of on line 47 You check the map and on line 55 you add to the map and as you and see actually if you initialise the score, to one, then you can remove the plus one, two places. Now, that's kind of just another small thing. And you spoke about memoization. And then one thing you spoke about is that you may be an integer might be too small. So you mentioned in that case, maybe for use of different data types, that was also fine. One thing that I also thought was interesting was you mentioned about using a string as the data type for employee ID. And I think the reason you gave was that a string can have more values in them integer, which, yes, that's definitely true. But I guess, if you're thinking realistically, you know, an integer can have somewhere between one two and 4 billion values. So it would have to be a very, very large company, if it has more than 2 billion people. So sure, I understand what you're saying that a string has more values and an integer. But realistically, an integer should always be fine for implementing, right? I guess maybe a different argument you can make would be that, if it's an integer, then employee IDs are kind of predictable and easy to guess. Whereas if it's a string, then it could be some some kind of random string, and then it's kind of harder for people to guess IDs, that might be something I don't know. Anyway, so that's, again, that's just kind of a small thing. So then we move up to version three, which was about how do we make it even more efficient. And you mentioned that you could calculate the score for everyone at the beginning. And you said that you were first find. And you said, the way that you would do this is you would get the score of the CEO, and then you'd calculate everyone below them. And then instead of pushing to find the CEO, and you said, maybe you could look at incoming edge counts, and the one who has zero incoming edges will be at the root. And then you decided to do a different approach, which was actually on line 63, you create a hash set of all your reports, and then you add everyone to there. And then when you find an employee who's not in that set, then they must be the CEO. That works fine. Of course, using some, some more storage there. So another approach you could have done actually is, you could have used your existing get score function from version two, and just call it for every employee. That's probably a simpler way of doing it, I would say just iterate through every employee in the map and calculate the score. And if you think about it, you don't need to worry about efficiency there. Because if you call it for someone that you've already called before, then it will just return immediately, right? So say, if you're lucky, and the first employee in the map is the CEO, then you will calculate for everyone then you go, then even though you're still iterating, through the map, it will return immediately for all of them. So personally, I would say it's probably simpler, and also a bit more efficient when it comes to space just to iterate through all the employees calculate the score. And then that's fine. And then actually, you don't need to modify the get score function, you could actually keep the get score function identical as version two. And then when people call it, it will just return it from the map immediately. Does that make sense?

Massive Chameleon: Okay, I understand.

Electric Avenger: One small thing was on line 17, your initialised route ID as empty string? That's fine. Maybe I would have done null, that might have been a bit clearer than on line 70you can just say, if it's not, null, that's another approach. Not really a big deal. So then, what else let me think. If you have a look, calculate score helper in line 84, is very, very similar to what get score used to be right. The only real differences is it never reads from the map, right? It only ever writes into the map on line 95. So again, if you kept it as the original, where it does read from the map, then you know, you could just kind of iterate through all the employees and get the score. So on this point you started talking about validation again, and you spoke about kind of your, which approaches to use, you said that you're going to choose the no loops one, and then using a DFS makes sense for her. And you said that you could start from the CEO. But then we kind of spoke about how do you know who the CEO is if there might be a loop? You're asking, Can you assume that the root is given? I said, again, that might not be possible. So you've thought about it a bit more. And then you kind of began kind of doing your function for validating loop. One small thing is on line 112, you call the function validate loop, which, as you saw, when I asked you the question, it wasn't clear. What does it return? So personally, I would rename the function to maybe be like, hasLoop. And then it's clear, has loop if it returns true, that means it does have a loop of returns false. That means it doesn't have loops. I'll probably rename the front So just to make it a little clearer. So then, right, you're asked if you could assume that the other two conditions are true. And I said no, because if you could assume that, that means you'd have to validate those ones first. And in order to validate those ones, they might depend on having no loops. So some of it's a bit circular. So that's why essentially, you need to validate that there's no loops in isolation of the other two conditions, right? You had this global visitor to set on line 110, but then you re set it online 134, which is fine. And if you think about it, actually, the main chunk of what you do from line 113 to 131, essentially, is finding all the CEOs. But if you think about it, that's not really necessary. Really, what you could do on line 133, instead is just iterate through the entire map for every employee, and do DFS. Right. And then for any employee, if you find a loop, if DFS returns true for any employee, and you know, you have a loop, so actually, you could probably delete all the code from line, I guess, 115 to 131, does that make sense?

Massive Chameleon: Oh, okay.

Electric Avenger: Does that make sense to you?

Massive Chameleon: Let me think, I think, I think my concern is that I do DFS from a non CEO node. And next time, I want to check the CEO node that might contain this node that I have to run DFS again.

Electric Avenger: Sure.

Massive Chameleon: If there is only if there's only I think, if each employee has only one manager, then that should be okay. Because then I don't need to read initialise, this.

Electric Avenger: Or another approach, what that you could do is you could do DFS for every employee. And you could also maybe cache the results, maybe, and then run it for their manager, then you can check, you know, maybe inside your DFS function, maybe you could do a cache perhaps.

Massive Chameleon: Ah yes okay.

Electric Avenger: That's just kind of some feedback on that. Overall, overall, one thing I would say is you use kind of a hash set sometimes in your solution, which is good. And I understand why you're using a hash search, because you know, they have order one lookup time, and they enforce uniqueness. But I think in general, it's probably good. Whenever you use any data structure to state, why are you using it? And then the person interviewing you, then they know explicitly, they've chosen a set because of these reasons. Whereas if you don't state it, it's not 100% clear why you chose that one. So essentially, anytime you structure I was state why you're using it instead of something else. Another good thing is, throughout your solutions, you always use helper functions, which kind of make the code easier to read. So that was nice. And then, yes, towards the end results to the format topological sorts. But yeah, so let's kind of now do a summary. Right? So you said you're interviewing for L4, right?

Massive Chameleon: Yes.

Electric Avenger: So I would say for L4, this was a good interview. You had no trouble at the very beginning here, like calculating the score. And you also did version two, version three, you did them all very easily. Version four again, the validation was all fine. As you saw there were some tweaks maybe to improve upon it. But overall, it was still good. You had good communication the whole time. You're always explaining to me what you were thinking and your approach. That was all good. Yeah, I gave you some feedback, maybe where you might be able to improve, but I think it was a good interview. And you know, if this was a real interview, I would definitely recommend a hire for this.

Massive Chameleon: Okay, thank you so much for your time. I think I learned a lot from this also.

Electric Avenger: Sure so do you have any questions for me?

Massive Chameleon: I think so, for this, I think for this case is I didn't really go through the test cases after I write each version. Do you think that even if they're supposed to have a few versions after what do you think that it would be better if I try to at least go through some of the test cases is in summary.

Electric Avenger: I guess what I would do is I would ask the interviewer, you know, when you finish the essay, because I know, do you want me to test it and If you say yes, then that's good. Whereas in this case, as you can see, there were many, many parts of the question. So I could see that your code was correct. So I didn't ask you to test it in this case. But for another question, it might make more sense. So essentially, what I would do is, when you're interviewing, when you finish writing some code, you can ask the interviewer, do you want me to test it? And then they can say yes or no.

Massive Chameleon: Okay. Okay. Understand.

Electric Avenger: Any other questions?

Massive Chameleon: I think I think I don't have any other questions.

Electric Avenger: Yeah. Okay, cool. And do you need any resources for interviewing? There's a good book that I've used in the past. It's called elements of programming interviews, I'll just write to on line 153. It's a book. You can get it in like, Java, C++, Python, whichever one you want. And yeah, I think it's a really good book. It has a lot of questions in it. And the questions are difficult questions. And if you can do those questions, then then you have no concerns I would say.

Massive Chameleon: Okay, okay. Thank you.

Electric Avenger: If you have time, maybe check it out. If you don't have time. That's also fine.

Massive Chameleon: Okay.

Electric Avenger: Okay, cool. Anything else?

Massive Chameleon: I think that's it for now. Yeah.

Electric Avenger: Okay, great. Well, yeah, well done. Yeah. I thought it was a good interview. And yes, good luck.

Massive Chameleon: Thank you so much, lot.

Electric Avenger: Okay. Thank you. Have a good evening. Bye.

Massive Chameleon: Thank you. Bye.