Java Interview with an Amazon engineer

Watch someone solve the what are my friends buying problem in an interview with an Amazon engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

What are my friends buying

Interview question

1) An online retailer is releasing a new feature called "What are my friends buying?". The feature lists a set of products that you have not already purchased from the things that your friends have bought, in order of most bought to least bought. To help with this, we have the following 2 APIs. Complete the function that takes in a person and returns the items that the person's friends are buying. 2) Instead of your friends, what about your social circle? A social circle of a person is defined as the person's friends and their friends.

Interview Feedback

Feedback about The Incredible Squirrel (the interviewee)

Advance this person to the next round?

How were their technical skills?

4/4

How was their problem solving ability?

4/4

What about their communication ability?

4/4

Context is an on-site interview for an entry-level software development engineer. You meet the requirements for an entry-level software development engineer. You clarified requirements well and used the interactive text editor well to share them. You coded correctly and can appropriately use and trade-off data structures. You stepped through an example well. You gave a good time and space complexity explanation that is plausible. We moved onto an extension question and ran out of time. We had a good DFS vs BFS discussion. Suggestions for improvement: 1) Be explicit with smaller examples, e.g. (friend 1 has items 1, 2, 3, friend 2 has items 2, 3, 4). Being explicit will also force smaller examples. Smaller examples that still test your code will be faster to walk through thoroughly line-by-line. 2) I think it's OK to be granular with time and space complexities, and then clarify with the interviewer their expectations. Try not to assume certain parts dominate other parts, in this case items you bought vs. items friends bought. 3) You seemed nervous and there were many syntax errors in your code. These syntax errors are fine I don't care, and nerves go away somewhat with practice, but you will always be nervous for interviews and that's OK. 4) You asked about behavioral interview preparation. Basics are covered in the first part of Cracking the Coding Interview, otherwise interviewing.io offers more detailed practice for this. Good luck with your on-sites!

Feedback about Orange Malamute (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

Orange Malamute did an excellent job of conducting this interview. He picked an appropriate question tailored to my needs and offered helpful guidance throughout the process. He offered valuable feedback on the things I did well and pointed out areas that could use improvement. He also provided some great insights on how the interviewing process varies from company/position level and what different interviewers may or may not care about (ie. syntax).

Interview Transcript

The Incredible Squirrel: Um, hi there.

Orange Malamute: Hi can you hear me?

The Incredible Squirrel: Yeah, I can hear you. Can you hear me?

Orange Malamute: I can hear you. I apologise for running a few minutes late.

The Incredible Squirrel: No worries.

Orange Malamute: How are you doing?

The Incredible Squirrel: I'm doing well. How are you doing?

Orange Malamute: Good thank you. So before we start this practice interview, I wanted to ask you a few questions, just to make sure that I ask it gives you the right kind of interview preparation. Is that okay?

The Incredible Squirrel: Yeah, sure. Yeah, that's fine.

Orange Malamute: Is this the first time that you're using interviewing.io?

The Incredible Squirrel: No, I've already had like, three previous sessions yeah.

Orange Malamute: Cool. And what job position and experience level are you interviewing for?

The Incredible Squirrel: So I recently graduated with a degree in computer science, and I'm looking for my first in software engineering position. I currently have interviews lined up for startups and FAANG adjacent companies.

Orange Malamute: Cool. That answers my next question too. Do you, you're interviewing for both startups and FAANG adjacent companies. Is there any preference to which one you'd rather work in?

The Incredible Squirrel: Either I'm really open to anything.

Orange Malamute: Okay, great. And have you had any interviews so far? Or have you yet to have your heavy push interview?

The Incredible Squirrel: I've done online assessments and phone screenings. But I haven't had a real interview yet.

Orange Malamute: Sorry, and you passed some phone screens? So you do have some on sites coming up?

The Incredible Squirrel: Yeah, I do have an on site coming up.

Orange Malamute: Cool. Those are all my questions. Okay. So I can tell you a little bit about myself, anonymously, and then let you know what I can offer you, and then we can take it from there. So I work for a large bank company in Seattle. And at least the company that I work for, actually, it's you're an interesting case, because new graduates are hired in a special intake pipeline internally in my company. All that means is that interviews are very standard, especially at big companies, the way they run them. But for new graduates, you often the experience feels like being a very small cog, like there's like a, what's new grad hiring season is just the volume of people that are interviewed means that sometimes the interviews might be really short at my company, like it may even only be two rounds, something absurd like that, usually, for even entry level positions there's like four or five rounds for new grads because of the volume. Sometimes it's very short. All that means is that usually, with these interviews, there's a lot of leeway for not, you know, you can do badly on a round or two, but with new grad high new grad interview, unfortunately, because of the time constraints, that's not true. Does that make sense?

The Incredible Squirrel: Yeah, that definitely does make sense.

Orange Malamute: You know, that's, that's the downside of a FAANG companies graduate hiring scheme, at least at my company. That's my experience of it. It's a bit unfortunate. At my company, we place an even emphasis on behavioural and technical competencies. But in this preparation, we'll just only be focusing on the technical part. Especially because some start-ups and FAANG adjacent companies only do technical interviews. So it's the best kind of preparation to do really, if you do care about FAANG companies, you should just get preparation specific for that company.

The Incredible Squirrel: Yeah, I currently don't have, I didn't feel I was prepared on applying for FAANG companies. Like it's something I'm definitely interested in. I would definitely like more preparation for that. Maybe like as my second job, not as my first job.

Orange Malamute: Okay, sounds good. Yeah, my company. If you apply during this season, we call it April to November then it's you're in this hyper accelerated pipeline, kind of unlike interviews are always hit or miss but new graduates interviews especially. But if you apply as your second job, then it will be a regular interview for maybe an entry level position or maybe an experience position.

The Incredible Squirrel: Yeah. Okay.

Orange Malamute: So especially since you're done with phone screens, but you're still interviewing for an entry level position. I think I know which question I'd like to give you. So at my company, these technical questions tend to run on the simpler side, and they tend to have lots of extensions. And so like for entry level positions, You know, I'll just tell you upfront with these questions, I don't expect you to reach any extension. So this question might may strike you simple. But I'll, what we can do, depending on how well you do on it is maybe we'll go through the extensions but we'll stay within the time limit. So at my company, the each round is one hour, and the behavioural questions are 20 minutes. And the technical questions 35. So we'll stick to 35 we'll even run over if you need more time. And we'll do all the extensions if you reach the extensions.

The Incredible Squirrel: Perfect. That sounds great to me.

Orange Malamute: And also, I guess I should tell you this, especially for large companies, probably also FAANG adjacent, you'll have rounds of interviews, probably four or five or whatever. And each person is looking for something different in the question that you're answering. And you can try to guess like, you could be or you can just pick up on the cues of the interviewer or even just asked him directly what they're interested in, if you're if you're concerned about it.

The Incredible Squirrel: Okay, yeah, I think that's been one of my I think the thing I realised for my previous interviews is that sometimes I've been too afraid to ask what they're looking for.

Orange Malamute: Yeah, you can ask, they can always say no, but you can always ask. So what I'm going to do is I'm going to paste the description into the code editor. And you can switch to a language and start using it. At my company. We don't we don't let people run the code interactively. But I know especially startup will let you run the code interactively. The choice is yours. If you want to run the code interactively or not. I'd prefer if you didn't.

The Incredible Squirrel: Yeah sure, I'll probably I'll probably do without yeah.

Orange Malamute: Okay. Yeah I pasted the question into the editor.

The Incredible Squirrel: An online retailer is releasing a new feature called "What are my friends buying?". The feature lists a set of products that you have not already purchased from the things that your friends have bought, in order of most bought to least bought. To help with this, we have the following 2 APIs. Complete the function that takes in a person and returns the items that the person's friends are buying. So first, first API returns a list of items purchased by person if purchased multiple items, an item will be in the list multiple times. Okay. And the second is returns a list of friends of a person. Okay. I just need a second to reread the question just to make sure I'm not missing anything. Is there an interface for the person object?

Orange Malamute: That's a good question. You can you can think of the person object as an interface. And you don't also you don't have to use Java. This code happens to be written in Java. But if you want to use any other programming language, you can just assume it's an object.

The Incredible Squirrel: Okay. It's an object purchased multiple times. I'm not sure if I'm understanding the question correctly. But uh, not only would I have to write these two methods, I would also have to I'm just not quite sure I get the question. Cool.

Orange Malamute: So you can these two methods on lines 14 and 19 are given to you so you can assume they exist. And your goal is to create a third new method that can implement the ask in the first paragraph implement that question.

The Incredible Squirrel: Oh, I see. Okay so we're given these two methods and we need to write a third method.

Orange Malamute: Exactly yep.

The Incredible Squirrel: And that's the third method. Okay, so um so we get okay, that clarifies it quite a bit. So we're looking through all of our friends. So the method we have to write will look at all the things our friends thought. And we filter out the items that we have bought, and then we return the items that are left, but we only return one of those items there may there might be duplicates. Is that my, is my understanding valid?

Orange Malamute: Yeah, that sounds right. Maybe if you type it down quickly, just to just to confirm it, that'd be useful.

The Incredible Squirrel: Okay, I'm gonna go down to the switch to Java, I'm gonna copy and paste the question there.

Orange Malamute: Okay.

The Incredible Squirrel: I also happen to code in Java.

Orange Malamute: Okay.

The Incredible Squirrel: Okay um these are given we're expected to write a method that returns a list of items. There should be a get I get new items from friends, person person, um so what we're trying to do is we need to find the friends of this person. A find, create a list of all the items they bought. Friend bought find the list of items this person has bought and then we need to filter out, of the filter out list of items from all friends items. Okay, um, so my first thought Um, can I.

Orange Malamute: The final, just to just to be clear, you need to return the items in a particular order from most likely to least likely.

The Incredible Squirrel: Okay yes and sort results by popularity. Okay so, I think I just need one more second to clarify my ideas. Can I assume that there will always be friends? I ignored checking for nulls.

Orange Malamute: You, we you shouldn't assume there are always friends but you can ignore null handle.

The Incredible Squirrel: Okay, sure. Yeah. Okay, so I think if we, if we create a HashMap for all the items our friend bought if that's the first thing we do, and then we update the frequency, every time we encounter the same item again. We can then later use that to help us sort at the end. Um,

Orange Malamute: And so you're using a HashMap to kind of count how many items?

The Incredible Squirrel: Yeah, um, to keep track of the frequency,

Orange Malamute: And why are you using a HashMap for that use case?

The Incredible Squirrel: Because it has a search, it has a search and insert time of O(1) of a, it has constant time, that way we don't need to, like if we stored into an array, we don't have to look up where the index of the item we're trying to update is. And I was also thinking we could use a hash set as a filter, even before we look for the items our friends bought. And if we have an item in there, we just don't add it to the new HashMap.

Orange Malamute: And why are using the hashset?

The Incredible Squirrel: Same thing it has the benefit of O(1) search and on adding in. So that way, we don't, in this case, we don't need to look. We don't need to look for the index of item we're trying to update.

Orange Malamute: What would an alternative be to using just for that case, a hash that was figuring out if you if you've already bought it?

The Incredible Squirrel: An alternative approach might be if like lists of items were sorted alphabetically, you could use two pointers solution one to keep track of your items and one to keep track of your friends item and then you can get rid of duplicates that way it's incrementing of both pointers up and if they match then yeah. Um but that's I think, that's slower

Orange Malamute: Let's, I agree it will be slower and let's let's keep on going with your proposal.

The Incredible Squirrel: Okay, so I'm just gonna reorder it so I'm gonna find lists of items that we bought first just to use we can filter it before populating the HashMap. Okay so I'll go ahead and code it out in this order. HashSet I'm gonna call it owned I think that's appropriate. Filter or item item dot get. Filter dot add item. So next we're gonna create a HashMap of items of first we're gonna store the list of friends. Friends equals person dot get and then for each friends. So for each friend we're going to look at their items for these items and I realised now that we need our hash map a little bit earlier. I'm going to call these recommended purchases or just recommended. Next I just realised we can call, it might be worth renaming owned filter to like purchased but I'll handle that later now if I'm just gonna rename it to already purchased, I think I think that conveys a lot conveys a better message of what this is. It's already purchase dot contains items, we ignore it. So if we negate that if we if we haven't already purchased it then we're going to update it and we're going to update our recommended. Recommended get or piece. And what this code means is if it is a new item that isn't in recommended. Get or default would return zero and we just add one to it but if we already have two of those items in it, then it'll update it from two to three and we're returning the items as a list so what we can do here is have a list item as well equals new array list. Please I might be mistaken here but I do believe we can put recommended.

Orange Malamute: Let's just assume that you can do that.

The Incredible Squirrel: Yeah. And now all we have to do is sort it. Is it okay if I use arrays dot sort. With my own custom lambda expression.

Orange Malamute: Sure. Yeah, definitely.

The Incredible Squirrel: Okay. So, if you sort result. A minus B. We wanted in terms of we want to in terms of most bought right. So what we can do is amended dot get the minus, ammended dot get. And I think that should work and then we return results. Although I'm actually to be safe, I don't think this will ever happen. But just to prevent overflow, we can use compare. I think that

Orange Malamute: And what does overflow mean in this context?

The Incredible Squirrel: I just okay, you'll never get it. But like let's say a was really big near the integer max range, and B was really small. If you subtracted a from if you if you subtracted of a sorry, so if a was a really if a was a really big positive number and b was a really large negative number, because you're subtracting it that minus would turn into a positive and you could create a value that's greater than the integer range.

Orange Malamute: Okay.

The Incredible Squirrel: I think this is correct. I'm just not sure if I need and I just can't quite count the parentheses the last line on line 68.

Orange Malamute: Oh yeah don't worry about that.

The Incredible Squirrel: Yeah, but I think that should work

Orange Malamute: Can you go through an example question?

The Incredible Squirrel: Yeah, sure. Yeah, let me just create, yeah sure. So let's say we have a let's say that we have two friends friend A, B and we bought items 1, 2, 3, 4, 5. And our friends bought items 10, 9, 8, 7, 6, 5 and they bought and ten is most popular nine is second most popular eight is third most popular etc okay. So here already purchased would contain 1, 2, 3, 4, oh and our friends also bought 4, 3, 2 and 1. Here we will get and this would be equal to A and B recommended is empty here for each friend. If we if we see 1, 2, 3, 4 ignore else we update the recommended. Recommended would then be equal to. Ten with a frequency of 10. Nine with a frequency of 9, etc, etc all the way up until 5 with a frequency of five. Results will just store the key set which would just be 10, 9, 8 all way up to five and not necessarily in that order. And the results should rearrange it to that order. This sort statement. Yeah.

Orange Malamute: So what's the time and space complexity of your answer?

The Incredible Squirrel: Okay would you so i'll define it in terms of total items? Or I'm just thinking about how to define it just because there isn't like an obvious N input, there's isn't like a singular input because we do have items and

Orange Malamute: You're right, you're correct. There's there isn't an obvious input. And so whatever you choose to define, just write it down somewhere and we can discuss it. So we can you can just choose which terms you want to define and then state your time and space complexity in terms in with respect to those terms.

The Incredible Squirrel: Okay, I'll just call it I'll define terms of whole items, or I'll have n equals number of items and we'll assume that the items that we purchased is small, is insignificant relative to the items our friends bought that there are like 1000s of products while we've only bought like 10s or maybe hundreds. So for this, this in terms of time complexity, this would be fairly insignificant so we don't have to count this bit. Sorry, I just need one more second. It's sorry, instead of finding endless number of items means we can just have two variables F number of friends and number of items that they have and we i'll just assume that on it items would be sorry, I think the space time complexity of this would be this would be O(F times items). Assuming we use something like merge sort or quicksort that would then become, O(F*N logF*N)) oh wait no sorry, this would just be our friends won't matter at this point, it would just be O N log N where N is number, i log i where i is number of items.

Orange Malamute: Okay.

The Incredible Squirrel: And i log i is smaller than i. So this can be reduced and ignored in our in our Figo analysis I think the time complexity ultimately will be f times i, number of friends times number of items.

Orange Malamute: i the number of items that you're returning Is that what that is?

The Incredible Squirrel: Oh no, no, I'm not really I'm returning the actual list of items. D you mean it, do you mean for my time complexity analysis or my results analysis or my actual results?

Orange Malamute: Just from the time and space complexity. On line 55, we have N is number of items but I think you mean now is i as number of items.

The Incredible Squirrel: Yeah i is number of times.

Orange Malamute: That's fine. Then F is?

The Incredible Squirrel: Number of friends.

Orange Malamute: Number of friends okay. And so, is it i The number of items per friend? Or is it that or is group?

The Incredible Squirrel: I guess technically this would be like small i items per friends and i is just the total number of and the big i could be the total number of items.

Orange Malamute: Okay. And so yeah, just below line 55 type in what the time and space complexity is.

The Incredible Squirrel: It would be time would be O(F*i + I log I). Space complexity what we're really storing is the max, we're only ever storing i plus our yeah. Our recommended will only ever be as big as i, big i, total number of items and assuming friends is significantly it could also be f if we could have an arbitrarily large number of friends.

Orange Malamute: Cool. Okay. And can you think of any edge cases ignoring null checks but any other any edge cases that you think you need to consider?

The Incredible Squirrel: Sure. Let me just take a second to think about it in a special cases. Sorry, I just need one more. Little bit more time.

Orange Malamute: Okay.

The Incredible Squirrel: But my intuition is telling me that there might be well, I guess if you have zero friends, then you will get recommended zero products. So that's one such problem. If I guess if you're if you'd like recommended the service to a friend and you refer them and recommend them to buy products then you if you bought more items than your friends have done there's a possibility that nothing will be recommended because because what they bought you've already bought. Those are the two special cases I can think of that might occur in real life.

Orange Malamute: So what I like to do is give you an extension to the problem. Okay, what I'll do is I'm gonna place this description on line 34.

The Incredible Squirrel: Instead of your friends, what about your social circle? A social circle of a person is defined as the person's friends and their friends. Oh I see. So my first thought is it's pretty easy to add another loop to get the friends of friends but what we have to ensure is we need to keep track of which people we've already iterated over. Because if you if we extend it to social circles two of my friends are probably friends with each other and we don't need to add and we don't want to be redundant and go through their list twice or like decrease or increase the count of an item we don't want to multi count so I think adding a hash set for us to keep track of like in a similar vein to like breadth first search or depth first search we just keep track of which people we've visited. If we think of this as a connected graph we just want to make sure that we don't go to the same people again would you like me to implement that?

Orange Malamute: Yes please.

The Incredible Squirrel: Okay. So HashSet person reviewed I think that's an appropriate name for the variable these are people we have or like already reviewed HashSet person and clearly after we go over ourselves we should add ourselves to review because friends of our friends or the social circle of our friends will include us by definition so here we call it friend two. Friend, friend dot get. Technically, I'm being inconsistent we can just do it after list. Person friends equals friends dot get friends. And here because we've already gone through our friends already. We're gonna add our friend to it. Actually, we should do a checks for um. I just realised that we probably should get checked for them.

Orange Malamute: Yeah, that makes sense that you add a check there. So we're, this is, this would be the end of 35 minutes. So what I'd like to do is give you feedback now and then we can keep going with this question.

The Incredible Squirrel: Okay. Okay. Sounds good.

Orange Malamute: So, you know, this, this isn't a particularly difficult question. But the main focus of the question was evaluating your data structures and algorithms knowledge, which is also not, not to great depth, but still evaluating that. But at the same time, I was impressed with how you, you made your high level proposal using comments, I'm just going to get lines 51 to 56. That's a really great way of clarifying what your high level proposal is, you know, the fact that I had I told you to write down it wasn't a big deal. But you'll you'll see when once you write it down, it's very easy to refer to it, and also what the interviewer is going to be doing at the end of it, the interview is just copy paste this into some internal tool to as part of the interview debrief, that's helpful, that you can write down your your thought process, it's particularly useful. And then, the reason I asked you very simple questions about, hey, why using a HashMap? Hey, why using a hash set is to make sure you're able to make trade offs between different data structures. So your your proposal to sort the items alphabetically and use two pointers was very novel. But you know, actually, the purpose of my question was very simple. It's just like, you know, hey, you're using a hash that to do you know, you answered correctly to do an efficient lookup, you know, what else could you look up in? And that's literally all I'm asking. It's not, when you get a question like that, you know, often people are just trying to check a box and make sure you can, you can try to make trade offs between data structures. And what else? I think one thing, I mean, I think I like how you did coded correctly. And you explain everything well, I've never had someone had to explain into integer overflow before. And that was a nice touch. And I think your code was correct when you wrote it, and that's fine. So and when I asked you to walk through it with an example, you walk through it correctly, when I asked for the time and space complexity, it's a little bit confusing the way you expressed it, but actually, I think it's, it's correct enough. And so I like that. So overall, I say, I would say you did very well, for this question for an entry level SDE.

The Incredible Squirrel: Thank you.

Orange Malamute: So the feedback I have is, it's not strong. So like, one thing is, I don't know. It's just like, you know how to use Java. But like, there's just a lot of small mistakes you made. And they're not important. So like, an interviewer could care less about syntax. I mean, I don't really care about syntax, but like, just just very small things. I don't know if it's important for you to prepare for this as well. But I'll give you the feedback anyway. So like, you know, line 63 It's like you need to you need to new everything you need to put new, like this

The Incredible Squirrel: Oh yeah I completely forgot new yeah.

Orange Malamute: Not important. I don't really care about that. And also I noticed, you know, line 65, 68 you know, you make it and you put stuff in you know, like it's kind of cool. It's not that important, but you can do. You can make collections from other collections. You can do a new hash set. And you can shove in person dot get purchases. Not it's not important, but it's just something that Java lets you, offers you. I guess something else that's to me it's super minor is the person object is not the one that has a method get purchases. Instead, what you were, what you were given is a method called get purchases i'm pointing on line 28. It's a method call get purchases that you call to get the purchases, but honestly, it's not the point of the question. But, you know, I noticed that I made a note of it. And also, you know, stuff like, line 102 I don't think arrays dot sort works on a list, I think you want to use collections dot sort, but on you know, it's also it's not that important. But it's just, it's just small things like that, that I noticed in an interview, I don't really care about it, you know, so I wouldn't worry about it too much. Also, I noticed in your problem in your method signature on line 50 you used list of items instead of list of item. Also, I didn't really care about that too much.

The Incredible Squirrel: Yeah. I'm sorry, I'm gonna say I'm like, I guess like, a, I guess, like an entity things? I'm a bit like, more nervous. And then a little bit.

Orange Malamute: Yeah, I noticed that you do sound nervous. And the I also noticed that you apologise a lot. You know, I'm not gonna tell you to stop apologising. That's kind of that's very condescending thing to say being in an interview is very nerve wracking. And so all I would say is, it's great, you're doing fine. And don't worry about the syntax errors, and it's not a big deal. For the time and space complexities, my advice is I don't know, it's, I try to try to define it in terms of stuff that's coming in. So like, it's just this use of capital, I, it was a bit confusing for me. But, but, uh, you're right, because the problem is kind of like, how do I define it is like, you know, you have to come up with a term, which is unique items that I did not purchase that my friends purchased. I have to, I need something. But all you need to do is if you're going to use something, then just define it, I think, just like with the high level proposal, simply typing it up with the save a lot of time, you can just on line 107? You know, I think we both understood what F is. That's fine. But you know, this. But you know, capital i is kind of confusing, you can just say, you know, it's a difficult term to define. It's just like number of items, friends, but that you did not, you know, it's a tricky term. Yeah. The point of defining time and space complexity, as you discover, kind of like the directions in which the elastic bands of the problem stretched. So you can say things like, what happens as the number of friends increases to time and space complexity, or what happens to them as the number of items increase or decrease? And so I noticed that you made an assumption, you said, like, I can, I can assume that the number of items my friends bought dominates my own items. And you know, that, you could assume that or you could just throw it in as a term, you could just say, hey, define M as a number of items, I thought. And that way, you can have a fuller expression. And then it's kind of like the elastic band, you can say, oh, but M is dominated. Or you can say, I could counter and say, What if M is not dominated? I see a simple problem, you know, like, whatever. But, you know, like, my advice is, you know, you don't need to make assumptions, you can just assign a term to it. And, and be sure to write it down. So it's clear to everybody what the term means.

The Incredible Squirrel: I see. Yeah, I guess my biggest worry was, up until very recently, I always thought you had to reduce it to like, one variable, ideally. And like, at most, maybe two. But um, from what I'm understanding, it's okay, if the inputs are a bit ambiguous, it's okay to have more.

Orange Malamute: If the inputs are more ambiguous, it's okay to have more. And also, it's, it's a conversation that you can have with the interviewer, if you're worried that they want some reduced form or something simpler, you can ask them, you know, I'm concerned that this, you told me actually, you were concerned about how ambiguous inputs were. And I told you, that's great. You know, let's just write down the terms of what the inputs are. Whereas another interviewer may say, oh, yeah, just try to write the stat. Write it into smaller form. Yeah, that's my feedback. And my advice. Do you have any questions right now?

The Incredible Squirrel: I don't have any more questions right now.

Orange Malamute: So that's the entry level SDE part. And then, you know, the extension question is, hey, let's start doing friends of friends. And I think this is where it went. I mean, your coding, the coding is fine. It's just so what what did i What did what's the extension? The extension is, hey, instead of just your friends what about friends and the friends of friends, right? And so you're doing all the right things. And also, it's really impressive that you spotted that you have to play at line 63, that you're doing the visited set. But really the whole, this whole extension only boils down to one line, it's only in line 75. So it's, you have all this machinery that does the right thing, once it knows what friends to process. But the question is, oh, we're changing what the, what the definition of friends is. So something to consider is when you get an extension to a question, trying to trying to see what is changing about the problem. And maybe you can minimise the amount of code you need to touch. Because that way, like when you walk through it with a test, like example, later on, you've touched so little of it, you can just say all this is the same, all I've done is change lines that we find.

The Incredible Squirrel: I see. I see.

Orange Malamute: And it's and it's not even that it's not complicated. It's more like hey, instead of person dot get or whatever get friends person should be doesn't matter. See, instead of this, it could be get social circle person.

The Incredible Squirrel: I see. And then, and then I can define that method.

Orange Malamute: Yep. Yeah. This might come up for you in the future. If you get extended questions, just consider what part of the question is changing and how much can I reuse and how much how much do I need to write from scratch?

The Incredible Squirrel: I see. Yeah. I guess like, I guess, like a difficult thing for me to realise is when to, I guess the answer is always. I've always struggled to figure out when when's the right time to module to modularize and create a sub function? For for something? Yeah.

Orange Malamute: That's tough. I mean, it depends on your coding style. Like, if sometimes it's easier for some people to work bottom up. So they write a bunch of helper methods, and they kind of glue it all together. But anyway, so maybe for the last few minutes that we have left, what we can do is, so there's this notion of get social circle. I know like your code, is, will probably work fine. Let's just assume you only change this line. Let's implement get social circle for the current definition of the problem, which is, Hey, you want to return your definitions, great. You are included in your social circle. That's great. You want to return your friends, then you want to return for those friends each of their friends.

The Incredible Squirrel: Yes.

Orange Malamute: And in fact, you know, why not? I'll give you the second extension. But like, usually I just kind of, I wait, but you can just do this. I'm typing on line 40. So we're gonna do a social circle of an arbitrary depth.

The Incredible Squirrel: Okay, I see. Ya. So with the first extension, my method was passable with the second extension, it definitely is impossible once I broke it down to some functions. Okay, so I'll go ahead and do you want me to explain it or should I try and see if I can go with it? Because I'm conscious and being conscious of the time that we have left.

Orange Malamute: Um, I think it's a good habit to. The triple that I would do is write a method signature, be extremely crisp about what the input is, what the output is, and exactly like you did on line 54 to 58, write some high level steps, as many as you want maybe one line maybe a few lines, then then you can write the code.

The Incredible Squirrel: Okay this person get social circle.

Orange Malamute: And some interviewers freak out, if you start writing code, they may accuse you of jumping into coding. So just always clarify, I'm just writing the function signature, I just want to clarify understand the inputs and the outputs.

The Incredible Squirrel: Okay, yeah. So my input will be the person you're trying to get social circle of and the output will be a list of all about that will be a list of people. So, what we're going to, and I guess the second input would be depth. And I think we're going to use a BFS search, we'll have an asset to keep just to make sure we're not double counting people. And we are going to need a queue. And the only thing we the only other special consideration for this BFS search is we do need to keep track of the levels. There are multiple ways of doing this. One method is to add every depth. You can add like a normal person and use that track of what level you're on the other ways and imbedding another while loop inside, but I'm not too familiar with that message. So I'll just write special considerations. Keep track of depth with null person object. Okay and we need to make sure that we add ourselves to visited and, and the queue before we start the loop. While queue add person. Can I go ahead and start coding it.

Orange Malamute: Yeah, I mean, this is this is a very good high level description, right? We don't you don't have that much time left. You know, and this is especially your use, I think the fancy term is sentinel. But the use of nulls is great. This, this definitely will work. I'm curious, why did you choose BFS, instead of some other graph search methods?

The Incredible Squirrel: With BFS, it's really easy to keep track of depth, just because like, if you have a yeah, because this, this will be the first on the queue this would be second thing added to the queue. And these would be on third level. And if you separated by null then, it's just really easy to keep track of. I think there might be a way of doing it with DFS and one of the traversal message, I'm just not too familiar with which traversal method would yield.

Orange Malamute: Cool. For graphs, let's just say there's only two depth first search and breadth first search. So let's just assume as a way to. And so something this, BFS, this iterative BFS is my favourite technique or traversing graphs in interviews, but something to consider is you can practice this yourself. You know, I'm sure you can implement it correctly. But can you keep track of depth in DFS? What what does that look like and does it work? Can you enforce depth using a BFS search?

The Incredible Squirrel: Could you repeat that question once more, please?

Orange Malamute: Sure. So, your your method for using BFS with sentinels works. That's, that's, that's a little interviewing techniques I'm aware of. Maybe we could use DFS with a stack and enforce a maximum stack size. Does that work or does that not work? It's something for you to consider and play with.

The Incredible Squirrel: So you're asking if there's a way of adding a stack to our BFS search to keep track of

Orange Malamute: Doing a DFS search with a stack of which you enforce a maximum size.

The Incredible Squirrel: Is there a way of doing that? Yes, I, I think you can. My mind, I can only really explain if you use recursion and the implicit call stack instead of itteratively. It's a bit more ambiguous to me as to how you would do that. But I imagine it is definitely possible.

Orange Malamute: Cool. In an interview what it always comes down to is, it's fun to talk about it. But ultimately, my next question would be what, what would be the time and space complexity trade offs between the two? And then that's where the discussion would go.

The Incredible Squirrel: Right.

Orange Malamute: I think in this case. I don't think there's gonna be a trade off.

The Incredible Squirrel: Yeah, I think it should be about the same. It's just with the BFS search, the largest size the queue will ever be would be at the bottom depths. Whereas using a DFS of the largest size the stack will ever be is and will be it would be log N of the total number. It was a maximum size it'll ever be is. It's just whatever our depth limit is.

Orange Malamute: Yeah, that's a good argument. I understand that. And then you can you can easily say that the null are just a constant additional space.

The Incredible Squirrel: Yeah.

Orange Malamute: Cool. Thanks. I buy that. I understand that argument. So thanks so much for your time. So that's, that is the interview. Do you have any questions for me?

The Incredible Squirrel: Yeah, I think yeah. When I'm, do you have any, with the places. Sorry, you're completely right. When you said that with like FAANG adjacent companies they have skipped or sometimes they skipped the behavioural interview. And that is the case on with one company I'm applying for. I guess my main question is, if I ever do apply to a FAANG company, and I do have a behavioural interview, right after the technical portion. What advice would you give on like, on how to prepare, or like what I should expect?

Orange Malamute: Yeah. Just very briefly, you. There are books about it. And you know, the most popular book is Cracking the Coding Interview, which frankly, has pretty shockingly poor technical questions, but it has a very good description of behavioural interviewing. Cracking the Coding interview, interview, bad technical questions. But you know, good behavioural, good explanation of behavioural interviewing. And if you want more details on that, and then interviewing.io offers specialised preparation for behavioural interviewing, including me. Cool, I can see that your mic is disconnected. I'm going to leave you with a a written summary of the feedback but thanks a lot for your time. And good luck with your interviews. Yeah. Thank you so much.