Python Interview with a Facebook engineer

Watch someone solve the remove nth node from end of list problem in an interview with a Facebook engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Remove Nth Node From End of List

Interview question

Remove the Nth Node from the end of the list

Interview Feedback

Feedback about Massively Parallel Nougat (the interviewee)

Advance this person to the next round?

How were their technical skills?

4/4

How was their problem solving ability?

3/4

What about their communication ability?

4/4

Positives: 1. Excellent articulation of thought process with the aid of examples. You kept the interviewer engaged and following throughout solutioning. 2. Almost exhaustive list of clarifying questions (missed just one about double-link list) 3. Produced functional code, and quick to amend it as we discovered edge cases 4. Proactively dry-ran the code with good set of edge cases to identify bugs. 5. Responsive to hints and quick to implement them (pre-empt parsing the entire list if K =0) 6. Discussed multiple approaches and compared tradeoffs of them with correct complexity analysis. Can do better: 1. Dont miss any clarifying questio1/4ssumptions 2. Try to keep time for complex followups if interviewing for a senior role. This is particularly applicable if the asked question is a simple one. You can also clarify with the interviewer if there might be followups after the initial question is mentioned to manage time better. However, best is to finish the solution as fast as possible without compromising on quality. 3. Improve problem solving with distributed workers (very large datasets).

Feedback about Laser Tardigrade (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

great interview. appreciate the guided approach to explore problem space, discuss solution, then to code. also great follow up discussion.

Interview Transcript

Massively Parallel Nougat: Hello?

Laser Tardigrade: Hi, can you hear me?

Massively Parallel Nougat: Yes, I can hear you. Hello can you here mere?

Laser Tardigrade: All right here, I can hear you. Let's get started

Massively Parallel Nougat: Right sounds good.

Laser Tardigrade: Okay, so we'll jump right into the question um we are going to have an interview on uh coding and problem solving right?

Massively Parallel Nougat: Yes.

Laser Tardigrade: Yeah, that's the expectation. Okay, so I'm gonna ask you a very simple question and I would encourage you to ask me follow up questions to disambiguate the problem and also lay out any assumptions that you're making. Uh don't jump to problem solving directly or writing the code. I would encourage you to also discuss the problem with me, the approach, how you're thinking about the problem. And eventually once we agree we can start thinking about the code and then writing the code as part of this interview, I would expect you to disambiguate. Like do all these things, discuss these things with me and then eventually also produced the working code for the problem that I want to ask you. All right?

Massively Parallel Nougat: Great, that sounds good.

Laser Tardigrade: Alright, great. And so the problem I wanted to ask you was suppose that you have a link list and you need to delete a specific node from the back of the list. Right? So suppose you have a linked list containing uh 10 nodes and you will be given this linked list and you would be also given something like you need to delete the kth node from the back which maybe five or which may be something like three or which may be the very last node. So this is what you need to you need to have the node read it from the end of the linked list. That position of the linked list and then return and then uh like return the linked list back to the um client.

Massively Parallel Nougat: Gotcha Okay okay sounds good. Um so to clarify um can I just write an example here? So it feels like can you see this here on the message?

Laser Tardigrade: Yeah yeah

Massively Parallel Nougat: yeah yeah so if k was like k equal to one then we want to return the list like that right?

Laser Tardigrade: Yep

Massively Parallel Nougat: or sorry if it was it was too maybe it was too like the second from the end I guess but some some number. Right okay okay. Um Are there and then by returning the list we'd return the head the same head right?

Laser Tardigrade: Yeah exactly yeah.

Massively Parallel Nougat: Okay. Okay. Are there cycles in the list?

Laser Tardigrade: Um there

Massively Parallel Nougat: I guess I wouldn't make sense because then it couldn't be K from the end right?

Laser Tardigrade: Exactly. That's a very good question. Okay let's assume that they are no cycles on the list.

Massively Parallel Nougat: Okay no cycles. Um Okay and will k always be greater than, K be less than the length of the list.

Laser Tardigrade: It might be but it could also be greater than.

Massively Parallel Nougat: Yep.

Laser Tardigrade: Okay um let's see here can the list be can the head node be null

Massively Parallel Nougat: Yep

Laser Tardigrade: Like the the pointer. Okay okay um let's see is there anything else here? Um yeah I don't know I don't think there's any other questions I have I think that's pretty quite well, what's the length of the list roughly? It can be like quite long. Right?

Massively Parallel Nougat: Uh Yeah it can be. So what do you mean by quite long? Like what is the thing that you're getting at?

Laser Tardigrade: Oh just like what's the length of it? What what's basically trying to figure out the upper bound of the input, length of the list essentially, but I guess it can be really, really large if necessary right so?

Massively Parallel Nougat: It can be really, really large if necessary. So I want to understand what you mean by really really large.

Laser Tardigrade: Oh I I don't know like uh like millions, billions of items on the list or something, I mean maybe is it something that can fit in memory? Is it all going to fit in memory?

Massively Parallel Nougat: Okay let's assume yeah, that's a good question. Let's assume that for now it is it can be large but not that large that it won't fit in the memory, so it is memory basically.

Laser Tardigrade: Okay, sounds good. Cool. Um Yeah okay that sounds good I think um yeah any is there anything else I might miss that may be critical in terms of the constraints of this input? I know I'm supposed to prod and find them but this is kinda.

Massively Parallel Nougat: No I think this is pretty exhaustive.

Laser Tardigrade: Okay okay that sounds good. Um shall we now go into kind of maybe my first pass, pass of the approach or we're good here, I can kind of talk to you about it not code it but yeah. Okay. Okay. So naively the thing that I think can be done is in um one pass. Well okay so to get the k from the end naive, totally naive here um Iterate over the entire list to figure out how many items are in the list. And then uh super naive. Super dumb. But like I iterated over again up until N minus K. And then you just performed the operation to strip that out from the link list and return the head again. So it's like a O Of N time and then O of one space. Um Yeah, that's the super naive version. Um we can improve I suppose. I don't think we can do any better than O of N. But I think I think yeah. Yeah, maybe like constant factor less right?

Massively Parallel Nougat: Uh Yeah, exactly. Something like where you don't really like reiterate over the linked list more than one or don't read it basically, you traverse through it once.

Laser Tardigrade: Yeah. Okay. Um uh and is this something that we can expect to do with constant memory or is it acceptable to have like up to K. O of k memory?

Massively Parallel Nougat: Let's talk about both the approaches.

Laser Tardigrade: Sorry, can you repeat that?

Massively Parallel Nougat: Let's talk about let's explore both the approaches.

Laser Tardigrade: Both approaches. Okay.

Massively Parallel Nougat: If you have anything in mind, yeah, let's talk about that. Yeah.

Laser Tardigrade: Sure. Um Okay so another naive one. Uh not naive but you could just walk down the list and maintain um K pointer like uh I suppose like a queue of the last K nodes, you've seen um double ended queue as you see them, you add it to the end and if the queue length exceeds K, you pop off the left most front most element. Um and that way you kind of keep this window of either last k elements. Um yeah and then once you reach the end of the node, once you reach the end of the list, uh if assuming that K is less than the number of elements you've seen, which makes it valid, then you can take that that element at the front of the queue. Um since you have a point of reference to it you can actually you need K plus one because you need to have the previous pointer um and then you can strip it out from the list and just return the head. So that's another, that's the way to do it O of K.

Massively Parallel Nougat: Okay. Just one clarifying uh clarification that would be that you need to delete the kth elements from the back. So what you described to me would delete the kth elements from the front right?

Laser Tardigrade: Uh uh Yeah for example, up here, if we were doing yeah I can show you kind of an example, so if I run through it would be like um uh so for this top one like 12345 here. Right? So by the time you reach the end of the and the once you reach the fifth element this is what the this is what the queue would look like. And so what yeah yeah so it would be second from the end and then you take the the parent pointer of the one you want to strip out which is the first element and then you would uh reassign to that element to point to the cape, to the to the element adjacent after after that.

Massively Parallel Nougat: Yeah, maybe it becomes 2 and 5.

Laser Tardigrade: Then it would become like that.

Massively Parallel Nougat: Okay, but then it becomes two and 5. But how do you plug it on to the next of one?

Laser Tardigrade: Oh well you just maintain a pointer to one at the beginning, you just maintain a pointer to the head because like it would oh did you want this to be done? Sorry. Maybe clarifying question is can we do we want to modify this in place or do we want to generate a new list?

Massively Parallel Nougat: I think yeah, what you're describing is modifying it not in place, generating a new list but uh okay

Laser Tardigrade: Oh no I'm talking about. Sorry. Yeah the approach I'm describing, Sorry, is to keep it um to modify it in place. So this q is just for reference just for references to the to the input list if that makes sense right? So it's not this is not gonna be this is not gonna be the return list or anything. Um what I'll do at the very beginning is maintain a pointer to the to the head of the list and then return that at the very end after after performing the surgery to remove this to remove that kth element. So yeah, it would be in place. Yeah.

Massively Parallel Nougat: Let's All right, let's go over this approach once again. So uh how do you how do you uh so how do you determine this? It would be a three length list can you maybe show me with explain with another example. Let's say you this list is longer, something like

Laser Tardigrade: Yeah, let me add some elements here. Um I guess if the numbers don't really matter, yeah, I'll keep them unique here, just for the sake of whatever, 11. And then let's say like 13, something like that and K is equal to specify

Massively Parallel Nougat: Three let's go with three.

Laser Tardigrade: Three? Okay, cool. So at the very beginning, what I would do is maintain a head pointer, a head point of reference which would just equal one, so it's just kind of like a keeping a reference to the first one. This is naive, there's some edge cases here, but this is kind of the rough idea and then we maintain some kind of queue here, right? And so um uh you know, we go to the first node add it. Um and then if we go to the second node we add it and we keep going until until the queue becomes K plus one equals max length of this is basically what this is if that makes sense right? And then once we visit the nine, what ends up happening is this becomes nine and then we pop off the first one. So it becomes like that and we proceed until we get to 13, 11, 9 and this would be at the very end here. Once we've, once we've reached the end of the list, this is what the queue would end up looking like.

Massively Parallel Nougat: Ok, so essentially you are keeping a kind of a double ended queue and all right.

Laser Tardigrade: Yeah, I know it's not necessary. Sorry we're spending a lot of time on this. Oh sorry yeah

Massively Parallel Nougat: Yeah that's fine. So now you have 5, 9, 11 and 13. What do you do next?

Laser Tardigrade: Uh What I do next is I will take so once we've reached the end we we so this five here is a pointer to this five in this in this list. So I'll revisit this here. So we take the first element in this queue. And we re assign it to this second element. Oh sorry. The third element which is the element after the this is K here. So nine is K. So we would essentially update the linked list to look like this and then leave return head pointer which is equal to one which is the beginning of the list and that'd be it.

Massively Parallel Nougat: Alright, Alright, got it. Now I understand completely. And over here what would be the time? What would be the space complexity?

Laser Tardigrade: Yeah, time complexity should still be O of N. Because the queue operations are of one, both sides on the double ended queue uh space is O of K. Okay. Yeah. They should be O of K. Um yeah I'm sorry the linked list removal process is just to be assigned pointer, so that's constant time. Um that would be O of one. Sorry, to make that clear. Yeah, so overall time would be open but with one pass essentially in a sense and but O of K memory, which I think is not optimal. I'm pretty sure there's a way you can do it with O of one time. Oh sorry space.

Massively Parallel Nougat: Yeah. So what is the okay, so do you have a O of one approach in mind with space?

Laser Tardigrade: Yeah. Yeah. I'm guessing you could just uh I mean once you perform K iterations, yeah, once you perform K iterations, you get out to like k of three, let's say we're out at five. Once you've reached that point you can start having a second pointer follow. It becomes like yeah. Yeah. I think that'd be the more efficient way to do it. And that becomes O of one memory. So this example here would be like yeah, first pointer I think you got it should just code it.

Massively Parallel Nougat: Yeah. Yeah definitely.

Laser Tardigrade: Yeah. Yeah, I think you understand. Right. So yeah, that efficiently

Massively Parallel Nougat: And I think one of the other assumptions that we made for this question was that it's a singly linked list. If it had been a doubly linked list then it would have been easier but yeah, I think we started off with the assumption that it's a singly linked list so that's fine.

Laser Tardigrade: Ah yeah yeah yeah, I should have asked that. That's a good question. Um Yeah, I don't know why. Okay, okay, cool. So I think that makes sense sense, so kind of like a two pointer runner system. Right?

Massively Parallel Nougat: Yeah

Laser Tardigrade: Yeah. Does that work? Shall I shall I code that, would you like me to clarify the solution a bit more or?

Massively Parallel Nougat: No. I I think I got the solution, it's essentially the same solution as the curious approach just that you're not keeping the elements in the middle of the queue, it's just the head and the tail of your queue that you're maintaining.

Laser Tardigrade: Yeah exactly yeah. Okay, cool, that sounds good. Um Nice. Should I code it changing the language, changing the yeah.

Massively Parallel Nougat: Yeah, whatever you're comfortable with, switched to that.

Laser Tardigrade: Okay, sounds good. Um Okay, do you have a function signature I can use or is there um?

Massively Parallel Nougat: Come up with you own.

Laser Tardigrade: Okay, sounds good. So we're calling this remove Kth case

Massively Parallel Nougat: And I would also want you to handle the different edge cases so keep that in mind.

Laser Tardigrade: Yes, yes, yeah, I'm gonna get the meat of the algorithm down if you don't mind and then I'll kind of approach the edge cases as we go. Yeah, like where case greater than the length of the list and such and stuff like that so um Okay yeah let's do that. Ok, so input is gonna be head of list and k okay, basically. Right. Yeah. And this is gonna be let's assume we have some optional node and this is an int I guess this is a uint well there's no uint in python but and then we're returning a optional. Oops, sorry, optional. Okay. And then it will be just uh and then it's got uh it has a value, it has a a next basically yeah yeah that's right. Okay, we're good, yep integer. Okay cool, sounds good. Um okay, so what are we gonna do, high level steps here. Um high level we are going to run so we have two pointers um Okay, mid two pointers. Main pain reference to had a list. Um Probably with sorry? Uh with dummy header important for edge case for later I think when that yeah, yeah because we're gonna it's possible that the head is the one you have to remove. Right? So you got to think about that later. Um Okay, so the meat of this loop is here let me think about this. So we're gonna run out one list. What's the termination case here? So pointer essentially it's gonna be something like ah Okay uh while pointer two I'll say first pointer while it exists, what we're gonna wanna do is reassign to next. Next pointer? Yes, I can next but also update uh following pointer, what's the condition when we update the following pointer to the next when we when we when count? Uh we've processed K plus one nodes I think this is edge case. I'm not sure if it's K plus one but we have to keep a reference to the previous node. Yeah. Yeah. Yeah. Right. And then we assigned first pointer. I'll call it lead pointer. Yeah. Yeah lead pointer to next. Um Okay. And then after we've done that now here we have here at this point we have a reference to the, reference to the presumably parent node of the one we gotta remove So we want to remove the the next node of the following pointer from linked list. That's kind of the rough idea. And then return the the head of the list plus next of dummy head I think that's the rough algorithm. Hopefully that makes sense. Yeah, does that kind of makes sense? Yeah. Anything odd here?

Massively Parallel Nougat: Um no I think it's more about the edge cases but overall the approach I think looks fine.

Laser Tardigrade: Okay, sounds good. Okay, so let's go lead pointer equals head following dummy head equals, what do we want to do here? Maybe node, just empty nodes. We can sort this out dummy head equals head dot next for now. Okay. Yeah. Okay. And then we need a count process I'll just say count so for sure. At the end of this we've got to increment the count. One thing we gotta do. We also want to check the count. We also want to reassign. So lead pointer dot next equals oh sorry lead pointer equals leader pointer dot next. And then here we also want to check if count is greater than or equal to greater than K. We'll come back to this. This is edge case here and I'll talk about it later. But roughly Yeah, count is greater than K. Then we want to increment the following pointer equals dot next. So yeah. Okay, so this should walk down the list and eventually lead pointer will hit the case where there's nothing this loop will terminate ideally barring edge cases. The following pointer is gonna be pointing to the uh yeah, it's child will be the kth element from the list. Hopefully I'll think about edge cases in a bit, but yeah, and then here let's um say node, maybe just do it in line. Fine. Okay, so here you want to remove, let me see. Following pointer dot next. No wait, from Yeah, maybe something like that, handle this up here and then return dummy head dot next. Okay, something like that, now removing this node. Okay, so we're going to take this, we need to keep a let's see, node dot next dot next. I believe this is what we need to do now, it's possible that edge case possible. Next dot next or next is null. Right. So I think in the case that it's not, is it sufficient? I think it is right to remove it

Massively Parallel Nougat: Remove next? Do you need to delegate some memory?

Laser Tardigrade: I don't think in python it's necessary, but uh if I was using some memory managed language, it would be I think necessary to de allocate the memory, but I think python is uh it's automatically memory managed, so yeah, big garbage collected or Yeah, I don't think it's reference counted, so I think it's garbage collected, um but yeah, but I do need to check if the next one doesn't exist. Right?

Massively Parallel Nougat: Exactly, exactly.

Laser Tardigrade: Yeah, if not node dot next, node dot next equals none. Basically it just point nothing to nothing. Yeah, otherwise, else, I need to select that. So if the node next does not exist. Yeah. And then we also have to make sure if following pointer

Massively Parallel Nougat: If node next doesn't. Yeah, so if node next does not exist, what kind of a scenario, like what kind of an input would give rise to such a scenario?

Laser Tardigrade: Good question. That would be if k is equal to zero, would that be zero from the end meaning?

Massively Parallel Nougat: Yeah. So in such case, do you want to iterate over the entire list and then find this out or you want to basically preempt the computation

Laser Tardigrade: You can pre emptive for sure. That would be yes, that'd be somewhat of an edge case, but I guess it's somewhat of an edge case, but that is a good point. Um I suppose, yeah, this would not be necessary.

Massively Parallel Nougat: But you can still keep it because someone else use the content

Laser Tardigrade: Yeah, yeah, that's a good point. We can add that up here. So it basically preempt everything here. Yeah, essentially if an edge cases if K is equal to, oh, we don't know the length of list at this point though, so. But yeah, actually, you know, the thing is we don't know the length of the list. Right? So we have to iterate over the whole list anyway. There's no way if we if if we knew the length of the list then we just compare to K at the beginning right?

Massively Parallel Nougat: It gives you case the position of the note from the back of the list. Right?

Laser Tardigrade: Oh yes, of course, sorry, Yeah, I understand that. Yeah, so if K is equal to zero return head. Essentially that'd be that'd be 1 edge case. Yeah, yeah, yeah. Um yeah, so remove next. Okay, um okay, so let me walk through this. So there's a possible case possible case where following pointer is null, is that possible? Yeah, I think that's

Massively Parallel Nougat: How can that be a case?

Laser Tardigrade: Um let's take k is equal to the length of the list. Okay then I think one thing I have to do is check so yeah, okay, here's an edge case here. Um If count is equal, is if k is greater than or equal to count. Hmm. Right then then actually so because because following pointers head um I need to exit out early here because that would be kind of an invalid case here. Um we wouldn't want to remove the head. Right, so I let me I'll think about it more clearly with an example

Massively Parallel Nougat: Why would you not want to remove, why would you not want to remove the head? Suppose you have something like uh three element list, 123, the nodes are 12 and then three and you have came close to three, so in that case you return two three, Right?

Laser Tardigrade: Oh I Oh I actually thought if K was 0.

Massively Parallel Nougat: K is three K is three.

Laser Tardigrade: 1st element from the end. Yeah, Okay, that makes sense. Okay. Yeah, it would be if K is strictly greater than count. Yeah, and then that would mean that this would have to actually start with dummy head because it needs the point, it has to be the parent of the node to be removed. Yeah. Right, I think that makes sense. Yeah, yeah, that's a good point though. Thank you I appreciate that. If k is strictly greater than we gotta return uh what's the, what's the desired behavior if K is greater than, just return the old head?

Massively Parallel Nougat: If K is... no, I mean I really how do you deal with it? Like if you're calling an api and if you have some invalid input then what what would what would you typically expect in a production environment?

Laser Tardigrade: Uh yeah, I'd be able to throw an exception or throw raise an error or something. Yeah yeah yeah let's do that let's throw exception.

Massively Parallel Nougat: Throw exception here and then uh you know. Uh Okay greater than uh length of list. Yeah something like that. Uh Yeah it's kind of something something like that. Um Okay How we doing for time here? We got 15 minutes or so?

Laser Tardigrade: Yeah

Massively Parallel Nougat: Okay let me run through it with an example to kind of nail down some of the edge cases here or let me write some test cases and we can kind of go through them. I think the meat of the algorithm is here is there anything missing aside from edge cases?

Laser Tardigrade: Um edge cases are only remaining there but it's fine.

Massively Parallel Nougat: Okay okay sounds good let me process it up here. Um okay so let me think of some edge test cases here. Uh okay so null one element you know I'll just represented as a list here. Um I mean one or two. That could be a weird case. Where and this would be with K equal to zero or even K. equal to one. All these boundary cases K equal to two in this case. Okay so if if not head right away we can handle this one. If not head return head return like none doesn't matter. We can just yeah that handles that case. Okay so we'll go through all these boundary cases um let's see what else we can handle here so with two pointers. Well zero we already handled that so we don't have to worry about that. But the ones we care about are around the boundaries of let's say one. Oh hello.

Laser Tardigrade: Yeah yeah go on go on. I'm here.

Massively Parallel Nougat: Oh sorry I think oh sorry okay sorry I think I actually went to the white board I got teleported. Okay two, three try those cases. And then I think this yeah okay five times I'll go for the rest but let's go through these. Okay? So if we're with one, one element so lead pointer becomes becomes one, dummy head is null. Not null, but it's a node essentially. Null and then dummy head is now equal to one. Oh next okay. Actually okay. Which points to one following pointer was going to be um non pointing to one, basically. None counter Okay. So what will happen here if counter K it's not counter zero. K. Is uh K is equal to Oh yeah. And assuming, sorry, K. Here in this example K is equal to one. So zero is not greater than K. So we don't follow in this here. Um three pointer next pointer now becomes none count is now equal to. Yeah so lead pointers next is equal to yeah. So this is not right, this is already an edge case that's failed. Yeah. Yeah. So we got to start actually with head I guess is equal to maybe wonder if this makes sense. Actually. Let me just think about it. Okay, so if we pointed at one sort of just widely Okay, so if the pointer is pointed at something in front of that, it operates once it goes to one count now becomes count as one and then it's still about in the next iteration of K. Is greater actually, you know what this is Okay, this is okay if it's one, if it's empty because what happens is our, let me back it up to what it was before, so it starts at head. So following pointer um it's pointing at the dummy head, we end this execution count as one, we exit out. K is one K greater than count not true K. And one is one is equal to one and one, so we don't throw an exception then we remove the next of the following pointer which is the dummy head next, which is actually the head, which is one. Right? So now we end up yeah, so dummy head now then. Okay, the edge case here is where yeah, so the edge case here is if the dummy, if the following pointer is equal to the dummy head, then we removed the first node and we need to update the dummy heads update the dummy heads.

Laser Tardigrade: Exactly

Massively Parallel Nougat: Pointers yeah, dummy head return none basically, I think that makes sense. Yeah, so you turned down there. Okay, so that handles the case Yeah.

Laser Tardigrade: Do you think there's anything this is missing or have you covered everything?

Massively Parallel Nougat: Sorry?

Laser Tardigrade: Yeah I am asking if you think there is anything missing here.

Massively Parallel Nougat: Edge cases I don't know for sure. I kinda wanted to run through one more but I think it's under Yeah. Just in case here yeah.

Laser Tardigrade: I think the fact that K, K might be negative because you can't have unsigned int over here. You might want to check that out.

Massively Parallel Nougat: Yeah. Yeah. Yeah. Yeah that's true. Yeah that's a good one too. Yeah. Um and the desired behaviors just or k well I guess if k is less than or equal to zero return head maybe and actually there was less if K was negative then it would be a return on error.

Laser Tardigrade: Right exactly exactly.

Massively Parallel Nougat: Yeah exception invalid K something like that. Um Yeah okay. I think that's roughly what I could run through some more cases but I think this is pretty good. I think it's okay.

Laser Tardigrade: Now let's try to discuss the approach. If you are not able to fit this in memory you don't need to quote that one out. I want to talk about the approach.

Massively Parallel Nougat: Sure. Um yeah good question. Okay so it's not in memory. So I suppose it's on disk somewhere in the database. These pointers or something or maybe a graph database or something. Right. Okay. I suppose what we could do so naively, naively just loading in chunks whatever will fit in memory at a time. And you can perform the same algorithm essentially where there's just a delay you know at this yeah, so basically when you're looking for the next pointer like here at this step, it's possible that at this step may be necessary to to load next load next X Oh, actually, no, because you don't know what the next ones are. Well, maybe maybe you could perform that query in the graph database, I don't know. Maybe maybe this is something that could be well

Laser Tardigrade: No then you'd go through the entire thing right? Okay. Let's assume you that you just the next exists. Let's assume you you know that

Massively Parallel Nougat: Let's assume that you know the next but it's in it's in Okay.

Laser Tardigrade: Yeah. Because, you know, you get to see that whether the next is pointing to something or the point is or it's pointing to null. Right?

Massively Parallel Nougat: Yeah. Like if you mean if you create the database, if you create like a crafty B or something. Yeah, but the problem is like if you yeah, the problem is though, like doing it, like having this, having this, have to do a network hop for every calls to slow, like that just doesn't make sense to do. So you have to kind of like almost loading chunks at a time or query the graph db in a particular way where you set like limits on how far it travels or like how many iterations it tries to go. Maybe that makes sense. Does that make sense, or no?

Laser Tardigrade: Uh yeah, yeah, that does make sense. So let's say there's a way by which you can uh actually pull in chunks, let's say there's something like that, there's an which is basically managed by, you know, like in a graph dB, even though you have a graph database, you still have the connections stored in a different list. So usually what it would be that there would be the next pointers, they're stored somewhere and the entire body of the node is stored in some other place. And these are essentially the place where you have the connections, it's essentially also has a pointer to the rest of the body of the node. So you can you can load multiple nodes at the same time if they're neighbors of each other.

Massively Parallel Nougat: If they're okay. Uh sorry, can you clarify that last little bit? One more time really quickly sorry

Laser Tardigrade: Yeah so I'm saying that let's assume that there's a way by which you can load the next k next m elements Next m nodes in the list. Suppose you can load that in memory, how would you do that?

Massively Parallel Nougat: Right, okay. Gotcha. Yeah. Okay. Yeah. So basically what I would do then here is um we we at the beginning kind of load M elements or chunks and then essentially decrement some counter like um have another counter that we track which determines how far along those m elements we've travelled or m nodes we've gone through um and then once we've now we know there's no elements left in that in that chunk we've loaded so we can fetch the next m elements and we just continue through the same algorithm but basically it's batching, it's like batch loading from memory um and performing the same thing. Um now the challenge is when we've reached the end of the list uh does it make this following pointer? I think it still should have a reference, It can maintain a reference to whatever unique identifier that that element has. Okay so we have to we have to store two things. We have to store the following as well as its. Oh no we could just keep the following point or whatever like maybe an I. D. of whatever the role is for that entry in the data in the graph database. Right. And then we could we have to make maybe another query to get the next one or we can store the IDs of both or all three I guess. Yeah because the round trips can be expensive. So what we want to ideally do is have enough have enough stored on in the application layer in this code where we can just make one call to the database to kind of update the the the the following pointers next right or whatever whatever it points to next with the I. D. Of the um it's next next. Does that kinda makes sense? So like remove node.

Laser Tardigrade: What if the value of K is more than would that cause any problem in this approach?

Massively Parallel Nougat: If the value of. Okay if m. Is could you ask the question again?

Laser Tardigrade: So m is the count of the number of nodes that you can load at a single time from your memory right now, if the value of K is more than M would that be a problem?

Massively Parallel Nougat: Yes, I think that would um yeah, yeah, that's a good point. It would be since um getting the, getting the K then yeah, it would be because now you don't have that you don't have K. K next loaded memory. Right, so good point. So I think what you want to do is maybe maintain a window around both if possible. So you iterate up till you iterate up until m up until count, keep loading chunks of m until you reach where you now run into you processed K nodes if that makes sense then

Laser Tardigrade: Yeah, I think it makes sense. Now another thing to consider is suppose m is not m is configurable. You have this unique database where you can configure m so how do you determine the size of? How would you come up with the size of m?

Massively Parallel Nougat: Mm good question, good question um okay, come up with the size of m could maybe use well, one, it definitely has to be less than the amount of um uh well you take a look at like how big the data, the size of the uh individual like data entries are coming back like in the graph database, like whatever you like, whatever that size of a chunk of data is for one node and then figure out how much memory you have on a particular server or whatever. Um You know server size you're using? Right. Yeah.

Laser Tardigrade: But Okay. But are we maintaining two such blocks or one block?

Massively Parallel Nougat: We would maintain two. So because we'd be keeping a window around both the K and the leading the lead and the following pointer it has to be like um roughly service size divided by two for each window with some buffer because obviously you can't like have it like packed on that server maybe give it a little bit of room but yeah more or less like server size divided by two for each window

Laser Tardigrade: And you do server size divided by two by for each window. You do this divided by two only if k is such that you can't fit k nodes into the memory at the same time. Right?

Massively Parallel Nougat: Yes that would be correct. Whereas if you could you can just maintain one window of size uh I mean the larger they are the better because you'll pull in you'll reduce your network trips you can have one big window and process it as you go if K was less than in that case. Yeah.

Laser Tardigrade: All right. Yeah. I think that kind of sums of our approach. Um so yeah I think we have also crossed our time so it's supposed to be 45 minutes. Right?

Massively Parallel Nougat: I think so yes. Yeah that's correct.

Laser Tardigrade: Alright, alright then, do you have any questions for me?

Massively Parallel Nougat: No, I don't think so. Um yeah, are these questions supposed to be like um well actually I guess this is a mock interview, so I should pretend like we're an interview. Uh um no, I don't I don't think so. Maybe, maybe out of curiosity, what would be another good follow up question to this kind of question that you might ask other candidates or you know? Or is it? Yeah, it's like the memory, is the memory follow up question one that that is is a typical follow up or

Laser Tardigrade: I mean it depends on the level of the candidate, right? If the candidate has significant, it's not about the experience, it's it's basically for uh if you're if the I'm interviewing the candidate for senior level of staff level, then I would expect this kind of uh thinking as well, but someone just out of college or maybe after one or two years of experience, I would typically not expect them to think of a distributed structure for solving the problem. Another approach would be, well, it's not really relevant in this problem, but uh is there any way by which you can maybe I would try to tweak the problem and try to see that if the if on a single machine can they employ concurrency to solve the problem faster. That might be another question.

Massively Parallel Nougat: Mm Gotcha relevant to this question specifically or is it general follow up to any kind of question?

Laser Tardigrade: I mean whenever there's any graph traversal questions or any traversal questions and there are two ways like one is obviously if the data is so used, you can't fit it in memory and the second one is what you have multiple workers and multiple workers are essentially uh then you introduce some level of concurrency uh if you can plug both of these, if your question is such that you can plug both of these two aspects together, then it might be also a question where your database is distributed and you are having different machines are in different machines and they are working concurrently. It's like a very big distributed clusters so that can be okay.

Massively Parallel Nougat: Okay, that makes sense. That's a that's a good one. So like yeah, I see, I see concurrent on a single machine or distributed. Like distributed processing for this, right? Yeah. Um Cool. Um Sorry and are these questions I can ask you like, is this um as if we were in the interview or like just generally as somebody who's conducted lots of interviews

Laser Tardigrade: As in I did not get the question. Sorry.

Massively Parallel Nougat: Oh, sorry, uh is it okay if I ask you questions? Like just feedback really quick right now like getting out of the mock interview phase or

Laser Tardigrade: I am not sure. I'm not sure actually whether we're allowed to do that, but yeah, I would I think yeah, I'll just write it on your feedback I'm supposed to I have prepared them anyway. But yeah, I think it went pretty well. Yeah.

Massively Parallel Nougat: Gotcha. Okay. Okay. Okay. That's good. Yeah. Cool. Um Yeah, I don't think I have. Yeah. Any other questions. That was great. Yeah, that was great. Thank you very much.

Laser Tardigrade: Yeah. Thank you. Bye bye.

Massively Parallel Nougat: Thank you. Take care. Bye.