Problem type

Linked list intersection

Interview question

Return the node that begins the intersection of two linked lists.

Feedback about Ghost Armadillo (the interviewee)

Advance this person to the next round?

How were their technical skills?

2/4

How was their problem solving ability?

2/4

What about their communication ability?

2/4

Strengths: They were able to come up with an algorithm to solve the problem. This shows that they were able to wrap their head around the problem and work towards the solution. This also shows they have the nerves to withstand pressure and stress and not lose their focus and cool. Improvements: Study theory and the basics of datastructures and solve simpler + basic problems to gain deeper understanding and build muscle in the area. Then slowly move to more advanced problem solving. This will require patience and perseverance but I assure you that you are on the right track. Stick with learning the basics and solving simpler problems to reinforce your learning and you will amaze yourself in 6 months time! I wish you all the best, good luck and success.

Feedback about The Masked Hedgehog (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

1/4

Ghost Armadillo: Hello.
The Masked Hedgehog: I can hear you.
Ghost Armadillo: Okay, now I can hear you. Yeah. Cool.
The Masked Hedgehog: Okay, cool. Thank you. Yeah. How's the day going?
Ghost Armadillo: Yeah, good. Thanks. How's yours?
The Masked Hedgehog: My days also good. Thank you for asking.
Ghost Armadillo: Shall we get started?
The Masked Hedgehog: Yes, please. Yes, I'm ready.
Ghost Armadillo: Are you interviewing me or?
The Masked Hedgehog: Oh, I believe you are interviewing me if I'm not mistaken. Oh, interviewer the Master Hedgehog. Oh, I am the interviewer I guess.
Ghost Armadillo: Yeah. Yeah, I think okay.
The Masked Hedgehog: Okay, cool. Cool. I'm so sorry. I thought... nevermind, it's okay. I hope it's okay with you.
Ghost Armadillo: What was that? Sorry?
The Masked Hedgehog: Okay. Oh, okay, cool. Okay, cool. So let me introduce myself, first of all, and I'll do a quick introduction so that you have enough time to solve the problem. And don't worry, I'm not gonna rush you or, you know. So I have been in industry for about 14 years. I'm at a senior level, worked at a couple of big companies and a couple of startups. I think coding interviews are challenging. And I have been on both sides. I have interviewed myself several times and failed several times. And there are a lot of, you know, technicalities, like I understand the challenges like there are algorithms. And then there are different kinds of problems. And then there's choice of language and choice of concerts, and every interviewer is looking for something different. So I try to make interviews, you know, as pleasant as possible. So that's my short and brief introduction. Like, it's up to you. If you want to speak a few words about yourself. What are you looking for from this experience? I'll be happy to, you know, answer any other questions?
Ghost Armadillo: Yeah, sure. Yeah, look, I've been doing software for about, you know, less, just a bit less than a decade. Okay, started. Yeah, interviews are challenging. And I've been practicing for a while now, but I never really did any algorithms or data structures at university. Okay. That's why it was a bit of a challenge. But yeah, look, I've been practicing and trying to get into probably the FAANG companies. And yeah, look, I failed a few times. Still still trying and getting more experience and learnings along the way. So I think just probably need strategies on how can you solve solve the problems? But yeah, I mean, I need to practice that. I've been practicing that sometimes. There's a bit of luck that that comes into it. So yeah. Yeah. That's what I'm doing.
The Masked Hedgehog: Cool. Cool. Fair enough. Well said, there's definitely luck involved. So without further delay, what I'll do is I'll ask you to pick a programming language of your choice. It's totally up to you whichever one you want to pick.
Ghost Armadillo: I'll just choose Python3.
The Masked Hedgehog: Perfect. Yeah, that sounds great. And I'll adjust the screen a little bit. Okay. So what I'll do is I'll delete this text. I believe you're familiar with the coding environment already?
Ghost Armadillo: Yeah, yeah, sure.
The Masked Hedgehog: Oh, Cool. Cool. So here is a simple problem. And since you said, algorithms, data structures are sort of challenging for you. I thought I'll give you a simple data structure problem.
Ghost Armadillo: Okay.
The Masked Hedgehog: Okay. So you know, think about it like this, we have a linked list. So we have this is a linked list, I'm drawing a linked list or trying to draw a linked list. So this is 1 3 4 7. This is one linked list. Now imagine, there is another linked list. And the way I would represent that, well, I, okay, I can type up arrow. Imagine this is my linked list, a second link list. So my first link list is 1 3 4 7 9. And it terminates here, like nine terminates, there's nothing here. I would I don't know how to put it, but I'll say this termination, it's terminating there. And then there is another link list, which is 100 4 7 9. Right? And let me add another node here. You know. So there are two linked lists here, one starts at seven then goes to one then goes to three, then four, and then so on, and nine, and then another starts at 100. And it it goes to four, seven, and nine, right? So there are two linked lists. The length of one linked list is, can you tell me the length of the two linked lists here?
Ghost Armadillo: Okay, so this one is... This is the top one is six. The second one would be 3. Am I right, or is it four? Because it's 100 points to four? Oh, yeah. Yeah, there was.
The Masked Hedgehog: Yeah, there was no good way for me to represent like, I don't know how to do... Oh, maybe I can do this. Yeah. So this is 100 4 7 9. Right? Yeah.
Ghost Armadillo: Yep. Yep. Yep. Hello.
The Masked Hedgehog: Can you hear me?
Ghost Armadillo: Now I can. Yep. Hello?
The Masked Hedgehog: So yeah, can you hear me?
Ghost Armadillo: Yeah, yeah. Sorry. You keep cutting out I think.
The Masked Hedgehog: Okay, there's Yeah, it's better now? Good. Everything good?
Ghost Armadillo: Yeah, yeah, that's much better now. Yeah.
The Masked Hedgehog: Okay. So there are two linked lists in memory. And they occupy memory positions. And then there is an intersection. So four is the intersection of the two linked lists that I've drawn. So linked list contains memory locations contains 7 1 3 4 7 9. The second one has 100 4 7 9. And as you can see, four, seven and nine memory locations are common to the two lists, correct?
Ghost Armadillo: Yes, that's correct. Yep.
The Masked Hedgehog: Right. And then the intersection point I would do I'm trying to define terminology here. So that it's easy for us to talk. Four is the intersection point of the two lists. If it's an intersection, because that's the first node which is common to both the lists. Yeah, right. Make sense?
Ghost Armadillo: Yep. Okay. Now, what your goal is, essentially to implement the function and I'm going to write a function prototype, find intersection, and you will be given linked list one and linked lists two. Linked list one and linked list two are basically head pointers. So, you get a you get a seven, you get a like a L1 contains reference to seven and L2 contains reference to 100. Now, what you have to do is you have to find the intersection. You have to tell me what is the, either you so you can return to me the node where the two lists intersect. So you have to return the node 100... sorry, node 4. Right? And it might be, the two lists don't intersect at all. So for example, I can give you another scenario where you have, let's say, just like this, you have 100 and you can have something like this where you can see that this seven, it's not seven, said it is six. And this is, I don't know, 34. So, you know, these are the other two layers, which don't intersect, even though there is a node four common the value is common, but the they don't intersect at all because there is no common memory location, right? And the class node, the definition is given to you, class node inherits from object and what it has is the F in it. So, this is given to class node is given to you, you have to implement this function. Right? Implement to be done. So, that's what you have to do.
The Masked Hedgehog: Okay. Okay, so the only time that actually intersect is if it's actually equal in memory. If it's not equal in memory, it's not an intersection. Is that correct?
Ghost Armadillo: Yeah. Yeah. Equal in memory. What if memory addresses the same?
The Masked Hedgehog: Yes. Sorry, memory address is the same.
Ghost Armadillo: Yes. Correct.
The Masked Hedgehog: Okay. And let me see. What did you want me to return, the actual node itself? So does it the actual intersecting node? And then it could be like four in this case here, so I'll just return that one. Right? And then that would just link to seven? Or it doesn't really matter. Which one? Because once it intersects in memory, should actually be detail. Sorry, the next node should be actually equal as well. Yep. So for example, 4 when I return it, that should actually be returned before seven, and nine, like so? Right?
Ghost Armadillo: Yeah. Right. So it doesn't matter because if you give me four, then I'm only worried... I'm only concerned with four. And the job of your function is done, as soon as you return me the four I'm good. And the client, let's say the client code, can use that reference to node four, and maybe print it or maybe do something else. So that that is not your, like, a consideration if I can see that. All you have to do is just tell them, Hey, this is the node where the intersection happens and I'm returning you that node. Now you can do whatever you want with it. And then if they don't intersect, you just return a none. Right? Yeah. Yeah. Okay. So you don't have to get confused with the fact that if you return a four then you're returning seven, nine or none. None is the ending thing? Yeah. But yeah, but I just, I just wanted to help you there. That's all.
The Masked Hedgehog: Yeah, that's okay. Okay, um, okay, I guess the first thing I was thinking of, actually was to iterate through the first lists and second list and build up... You see, I can solve this using if it's an array. So if I'm building this, the problem with this is that I don't know if it's actually exactly in memory. If that actually in the same memory allocations, if I for example, if I build this one here, I mean, that's my thought. Then I can actually find the intersection with by just using pointers like so by incrementing this one, are they in in order or anything like that they're not in order, are they?
Ghost Armadillo: They're not sorted. No, they're not.
The Masked Hedgehog: They're not sorted. So that's not going to help me either. If I built that, how do I know for a fact they're actually intersecting?
Ghost Armadillo: Yeah, so I'll give... you that's a good. That's a fair consideration, you know, I think Yeah. And I, I can tell you that without giving away the answer in Python, let's say if you have L1, right? You have for less this one, and you have L2, which is 789. And 10. Right? This is an L1 one equal to equal to L2, what do you think it should give me?
The Masked Hedgehog: False?
Ghost Armadillo: False correct. Why the false? It gives false because if you do, ID is the way to get the address. So this is ID of L1. And this is the ID of this, these two IDs are different. Right? The list equality basically. So even if you had like, let's say, L1 Is this right? You did L2 equal to this? Even then L1 equal to equal to L2. Okay, so now it is true. And the reason it is true, is because I think the ID is either the IDs are the same, no the IDs are different. So the list equality basically is implemented by the contents, you know, that's how the list equality is defined. But for nodes, for our node class, we don't have the default like we don't the way we have implemented equality, just think about it. Is that the, the IDs should be same. We are worried about the IDs, the ID the ID, that I was referring here, this ID one, Id L1 and Id l L2. They should be the same. Right? Yeah. So that's how, so let's say if you have n1 equal to node three, none type object is not callable. What happened?
The Masked Hedgehog: I think you meant to call none node not none.
Ghost Armadillo: Yep. Oh, yeah. Sorry, node not defined. Okay, now I think I... So you see, n1 and n2, n1 equal to n2, this will be false. And it will, if you do ID of n one will be different from ID of n2. Sorry, like this. So they are different. But yeah, but in case of lists, they're over. They have over it in the equality operator to to disregard ID, but we are going to consider ID. So that's our before, that's our like, implementation for node that they have the same data, it doesn't matter, they have to have the same address. So that's so you have to... Yeah. Right? So this is how you would find if they are the same node, you just compare the IDs of the two nodes, or you can also say n1 equal to equal to n2.
The Masked Hedgehog: Okay, I guess that's one thing we could do is actually just go through the link lists for list one, and fill in the IDs in an array. I mean, that's probably thinking brute force first. So you basically have ID, but thanks for that. That's helpful, as it could be ID two ID three, this would be for link this one. Sure. And and link, these two would be the same here. And then it will have its own IDs here. Okay. And then I am just spitballing. Here, these other different numbers. Find the intersection if there is one, there is a Python simple way of doing it, basically, is to see whether it's not the intersection of those ideas.
Ghost Armadillo: Right, right.
The Masked Hedgehog: And then I should get an intersection here. And that will be an array that I get from memory. So for example that would be like that, and I'll have an array here. Then the thing is I have the id, but I don't have the actual node. So I need to just, I think I just I just return the first one, I believe, is all I need to do. And that is the ID although. Okay. The other option is, as I build this up, I'm consuming more memory, but the id can reference, like being a hashmap, and the actual node, for example. But I was actually thinking, so then, when I find the answer, the intersection of it, I could just return, let's say this is the dictionary, then I can return the actual, for example, the dictionary of the first result, I believe, is all I need. If there is one, if the length of the result is more than zero, otherwise, I just return none. Right? Yeah. Because there is no intersection there. That's what I was thinking. Does that sound doable?
Ghost Armadillo: Okay. Let's, let's think about it for a second. Look at it closely. So your approach is iterate over the list, create a hashmap of id to node, for L1, do the same for L2. So now you have two dictionaries, that are map of IDs to node, correct? Now, you are saying. So remember, dictionaries are unordered collections, there is no order. Right? So you will not be capture. Unless you do something special, you will not be able to capture which node came first, right? Which is like the intersection node like you have to capture ID of four basically, right? You're interested in Node four. But if you do this, so you will have 713479. And you will have 100 479. And then if you do an intersection to do an intersection in dictionaries, like so let's say we had lists here, right? We had lists, okay, and lists are gone. So you cannot use intersection operator on a dictionary? I don't think so. You can only use it on a set. You see what I mean?
The Masked Hedgehog: So when I, when I initially gone, I was actually going to build like a list first, the dictionary just to denote what the ID to node is. That's actually all I'm doing. But yeah, but I could build this as a set. So I'll just iterate like basically, these are two sets, right? And then and then these are the IDs. And then I'll do an intersection there. And then this one is the only have actually one dictionary, that that's all actually one dictionary, the reference the ID and then those two, yeah, that's, it should be ID here. And then ID for here, and then there's a need for something like that. And then hints. Sure. And then once I get the result, I need to get the first one. It should be ordered when the set otherwise.
Ghost Armadillo: Sets are also not ordered, sets also not ordered.
The Masked Hedgehog: Yup, it is unordered and I know that there's an ordered dictionary, but I'm not sure that's going to help me be able to use the intersection while doing it. I mean the other way I could do it is sorry, go on.
Ghost Armadillo: No, no. So what what I was... Sorry to interrupt you or were all I was saying is that i think i think you need two dictionaries, right? How would you only need one dictionary if you went with this approach. You need one dictionary to keep a mapping for L1, another dictionary to keep mapping for L2 right? And then you find an intersection and then you take the first match basically you take the first match and that is and then you go to either dictionary and you reference it and you get the node that was your algorithm right?
The Masked Hedgehog: I wasn't thinking of using two because the IDs should all be hypothetically different unless they're intersecting. So the intersecting doesn't matter. For one dictionary would be sufficient. That's what I thought.
Ghost Armadillo: But then let's say they are intersection intersecting, and you got the all the ideas in a hashmap, like a dictionary, then how will you? How will you get the node that is the intersection of the two lists. That would be just through the ID.
The Masked Hedgehog: No, but how will we know that is the ID? That is the ID of the node that the two lists are intersecting? Like, how will you identify that ID?
Ghost Armadillo: It should actually be in the dictionary because I'm building it all up. If because what matters is the fact that I'm building two lists. And the node is the same,the references to the same node ID four, so that's why we only need really one. So I still can find it. Because this line 38 is what gives me the ID if it's intersecting. So if it's not there, then it wouldn't be in the dictionary.
The Masked Hedgehog: So you're saying you create one dictionary, and then you iterate over the second list? And see if one of the IDs appears in the list? In the dictionary? Right? That's how you're going to do it.
Ghost Armadillo: No, I was just going to use... Well, I'm just doing the intersect here between the two. The other endpoint between L1 and L2. So this, what is that one? This is list one.
The Masked Hedgehog: This is called a list or set?
Ghost Armadillo: Okay, let's go let's call this set2. If I intersect that that should give the result, I should get a list of ideas.
The Masked Hedgehog: You'll get a set, you'll get a set of IDs that you need.
Ghost Armadillo: And then all I need to do is just get the first one.
The Masked Hedgehog: How do you create set one? How do you create set one?
Ghost Armadillo: Yep. So I'll go through the list, the linked list.
The Masked Hedgehog: Okay, and you create set one, and then you go to set two. Then you create set two, right? Okay. Okay. Okay, I see what you're saying. So you create a dictionary. That's a mapping of everything. And then, and then you create set one that only contains IDs you create set two only contains IDs, you find the intersection. And then you go to the dictionary and find a node.
Ghost Armadillo: Yes, that's correct. Yeah. Right.
The Masked Hedgehog: Okay. But you have to ensure while you're creating a dictionary, is that? Well, it doesn't matter whether it's... okay. So you do realize that when you interest when you do an intersection, right, you will get four? In this case, you will get four items in your intersection. Sorry, three items, four, seven, and nine, correct?
Ghost Armadillo: Yep, that's right.
The Masked Hedgehog: You'll get IDs of four seven and nine correct. Now, you are doing an intersection you are getting a you are getting a four seven and nine, but this is going to be unordered you will not you will not necessarily get it in order for seven and nine. You could get it like this. nine four and seven. Right, because sets are unordered. So let me write it down. You get it like this. How will we know that four is the node. Four is the iD, iD four is ID that is the ID of the node with which is an intersection.
Ghost Armadillo: I guess there's several ways I could do this. Firstly, I could without actually iterating through the set, okay, like, if I get this list, what I could do is I just go through my linked list the first one, for example, if if there is something in the list to maintain that ordering, this is going to be another extra iteration. But I can just go through, they say the first node, second node third node and then it's only when I reached a third node it's in the ID is in the actual set, then that's how I know that's the first one.
The Masked Hedgehog: Okay, so basically, what you're saying is, you create a mapping, right? And then you create all the sets for IDs, you do an intersection, and then you iterate over your first list, or second list. And then the first, the ID of the first node that appears in the set. You that is your intersection node ID, and you go to the dictionary and get the node and send it back.
Ghost Armadillo: That's exactly right. Yeah. I mean, it's I know, it's not the most space of the most efficient way. But that's probably one way.
The Masked Hedgehog: Yeah. Yeah. So let's think about the time complexity for algorithm, you know, before you start writing code, so you will get a dictionary. So let's say so your one list contains so let's say L1 has n elements, right? Yeah. And L2 has m elements, right? Now you create a dictionary so that you have to iterate, right? So this is O(n) let's say, right? Now we have to create a set. So that is again, O(m) agreed?
Ghost Armadillo: Yep, that's right. Yep.
The Masked Hedgehog: And the second one would be O(m). Right? So let's say we call this or correct? And then you do an intersection. That's the intersection of the search. Probably implemented, and I don't know, I guess... Yeah. And yeah, yeah. So or, right. Now, you got your intersection. And then you iterate... to iterate over that list, one of the lists. And then the first one, which is in the ID. So for every item, you do a search. So that would be I guess, we'll call the first within a set of constant time, let's say, yeah, social status constant time. Again, yeah, but you. You do it like this. So it's O(m) or O(n), because you have to right? search every item in one of the lists. Okay. So how many, what's your cost? O(n) + O(m) + from multiple, right? You see, it's multiple of like your so it's oversee into big O(n) that is your cost? Right? So which is seen as big O(n)? Correct? That is your runtime. Memory complexity. So, coming timely, you need to maintain a dictionary so that is O(n). Right? Then you have to create a set. So that multiplied by two, you have to create a second set that multiplied by three and perhaps the intersection, you need to store the intersection. So it's like three intersection. So you need. So it's like four times. You have to store your intersection also, right? So four times O(n) so that's your memory complexity. Right? Agreed more or less? Yeah. Okay. Yeah, the solution I'm looking for is okay... Yeah, you're. So first iteration second iteration. And then let's call it third iteration. So memory is O(1), constant memory, no extra memory. And runtime is O(n), so, you know, it's like, three times. So you can do three iterations. Okay. Expected solution I'm looking for.
Ghost Armadillo: Okay. Let me think, Okay. Let's go back down here. So, the, what that's telling me is, I could have create a list and say, list one, and actually say, let's say seven, and the actual ID here are the seven, perhaps. And then it's the same. When I say seven, I'm talking about the node seven. So I have reference to it. And then I'll do the same all the way through. And I mean, just do that. And that would be four, and then ID four. And then this would be just like a tuple. Who actually need a tuple of list. And then this is all the way to nine. And then I'll have another list here, which is list two. And that starts at 100. And that would be 100. Id and this would be all the way to like... So what I could do is use pointers. Let's say we start from this one. They're both let's say this one, let me explain call this i and let me call this one j. So what I could do is just iterates through each one, so compare them. If they're both not equal then other one, I thought you'd write the first one, or do I iterate the second one? I don't know that.
The Masked Hedgehog: If you create two lists like this... Then you are already using extra memory, right? Like, but the requirement is that you don't have to use any extra memory. You see what I mean?
Ghost Armadillo: Yes, yep. I see that. Okay. So instead of creating it, I need to loop through the link list. Exactly. compare them. I guess it's just name thinking. But I'm just looping through using lists. So I'm just wondering how I do that anyway. Well, when I loop I use dot next. Yeah, yeah. While it's still available, let me just go...
The Masked Hedgehog: So think about it like this. So first of all, we need to come up with a with a... look at the list. What is one possible way that we iterate over the lists and we jump on and we arrive at four at the same time. So you have one pointer, that is iterating over list one another pointer iterating over list two, right? Yes. You are at your point is that server one, then three? pointer two is that 100 then 4? Then seven, right? And then you're pointed to is at nine your point one is at four. So, when you run out of pointer two, what if you started iterating over list one. So, you are, so what will happen is think about it like this. So, this is p one, you will think of a way. So P one is at seven and P two is at 100. Right? Then you are at one p one p two is four, agree? Then you are at three is that so on, then you are at four, and you are at nine. And then after p two is at nine, you're done, right? P two is done. But what if you switched? You, so this will go to seven p one still alive, it goes to seven. But from nine, it goes to seven, like it goes to seven, right? And then like, okay, let's call it 17, so that you get the idea without getting confused. So 17 134, 100 479, then p one goes to seven, p two goes to 17. Right? And this goes to nine, goes to one. You see what I'm doing? Essentially, after p two runs out, it starts iterating over p one. Right. And after p one runs out, it starts iterating over p two. This formatting a little bit more extra. Yeah, it's a it's sort of a trick. So after p one goes to 100 and then p one will go to after 100 will go to four, right? And then p two goes to one. And then it will go to three. And then it will also arrive at four. There you go. You got a match. Yeah. It's a cycle thing, right? If you had let's say 100 like this, you had something like this, right? So, what will happen is in this case, now think about what will happen here and see, you know, you will wander until how long do I have to do this because I can go in an endless loop. You know, my P one ran out It started with P two like my P one ran out It started with list two. My P two ran out It started with this one. And then when my P one runs out again should I start again? No, all you have to do is a trait of using the two pointers on both the list only once. So now you have p one and p two here. So you have what 17 and then one it won't match, then three won't match than for one match, then seven won't match. The Nine won't match. And then for P two, your 100 won't match, then four and seven have nine it won't match right? After nine, if you go to 17 then it'll go to one and then from nine if you go to 100 to four to seven to nine and then 17 will go to 1 3 4 7 and 9. But this is when you stop, because your P two is flipping here, right? It is flipping here. We do flips. And where does your P one flip. P one flips here. This is where p one flips, p one flips, right? And then after p two flips, and it reaches end, you stop, and after p one flips, and it reaches the end, you stop. Yep, that makes sense. Yeah. And you will, you just have to do it for length of L one plus length of L two, that much time only. You see how many times you go? 10? There were 10 iterations. 10 times 1 2 3 4 5 6 7 8 9 10. So your loop runs 10 times only, which is equal to the length of L one plus length of L two. Right?
Ghost Armadillo: Yep. This reminds me a problem. Yeah, go on.
The Masked Hedgehog: Yeah. So this is one way to do it. Another way to do it is even simpler, which even I do not know. And I had a look up the answer. Yeah, I mean, you always learn right? So what you have to do is find a length of L one is length. So let's say Len one is this, and this is len two, right? So you find the difference between the length, what is the difference between the length, it is in this case, it is two. The difference is two. So you make the largest list, and you skip the head pointer by the number which is equal to the difference between the two lengths. So in this case, the difference is two. So you skip the head pointer of the larger one by two, which means you bring from 17 to one and from 1 to 3. Right? So plus two, right? I'm not saying modify the head pointer, I'm saying, take up, store your head pointer in a temporary variable, and move it forward by two. And now you start your iteration. So you say three, your pointer one will be a three pointer two will be at 100. Pointer 1 will be at four, your point one will be at four, then seven, and then so on the nine and nine, but the IDs won't match. So it will not work out. It will say no, there is no match. Look here. So you are at three, three and 100. Then four and four, you are at the same node. Right? And then you do the ID you say okay, I'm at the same ID and you return that. Right? So this is how, yeah... What is that?
Ghost Armadillo: The time complexity for the second one that you showed us is still three n because you still need to get the length of the linked lists.
The Masked Hedgehog: Right. Exactly. Yep. I fully agree with you. So as I said, the time complexity is... Yeah, it's like O(3n). Right, which is, you know, upper bound. Yeah.
Ghost Armadillo: So yeah, that's interesting. Do you have a link to this problem?
The Masked Hedgehog: Let me find a meaning of this problem for you.
Ghost Armadillo: And this reminds me of the problem where you have two strings and you want to see the string to for example, the rotation of the other string one. It's very similar.
The Masked Hedgehog: Yeah, exactly. Intersection of two lists, or two linked lists. So yeah, you can you can find this follow if you Google it, you'll find it. It's on LeetCode. Yeah. You can can find it there. Okay. All right.
Ghost Armadillo: Sure. No worries. No worries. Yeah. Good. Okay.
The Masked Hedgehog: I think I wanted to give you some feedback.
Ghost Armadillo: Go ahead. Go ahead. Yes. Yeah, that's okay. Give me feedback.
The Masked Hedgehog: Yeah. Sure. Go ahead. What are you going to say something you were going to ask something?
Ghost Armadillo: I just said, Yeah, I didn't get to implement it. But I think this part is more important, the discussion, to be honest implementation on like, Hey, I can do it.
The Masked Hedgehog: Yeah. Yeah, yeah. Sorry about that. Yep. So. So actually, the what of what feedback I was going to give you is that, I think you should you, I think you, you are able to come up with an algorithm that is important, you know, you were able to come up with a way of doing it. So that's really positive. Got a problem, even though your algorithm was not like the most efficient, but you still were able to formulate a solution in your head. So that's excellent. Now, I think where you need to brush up is your fundamentals like, we're trying to, you're thinking that you can take an intersection and then take the first element, but then you can only apply intersection on sets, and then sets are unordered, so you cannot really index them. So you have to brush up over there. And then what I would suggest is, pick up a textbook, read the theory, and then solve problems at the back. Right? So, if you do that, if you do that, that will help you build your muscle around the basics. And then you know, once you're you have solid muscle, your foundation is solid on the basics, then you can build like more complicated concepts on top of that. So I think so that's how I did it. You know, I started off with the basics. I slogged through the basics, I did like a lot of problems on the basics. And once I felt comfortable with the basics, I had internalized the basics. Then I started building more advanced concepts on top of that. So that's how, that's what you should do. It takes some time. But if the basics are good, your fundamentals are strong, then I think you will you will be cruising, but before you can cruise you have solid, your basics, solid. That was my feedback.
Ghost Armadillo: Yeah, sure. Sounds good. No, I appreciate that. I think I think it's good that you explained. Yeah. The the solution and how to go about it. Interesting. Yeah. I appreciate your time for that.
The Masked Hedgehog: Well, most welcome most welcome. I always try to help interviewees with feedback. I've always done that during live interviews, also, like actual interviews, because I think it is important for people who are interviewing to go back thinking that okay, even though I couldn't, you know, even though my intro like, so what they should go back is they should feel that, okay, I learned something from this interview, and I have a way forward to improve my skill, that is more important than just knowing that okay, I didn't, I couldn't do it. And I don't know what to do next. It is important to you know, have a way forward.
Ghost Armadillo: Yeah, that's great. Not everyone's like that. And not everyone thinks the way you do, I do appreciate it. Not easy these algorithms take a long time to get good at.
The Masked Hedgehog: Oh, yeah, it will it will. Yeah, definitely. But, but I will tell you this, if you start on a path, on a pace that is comfortable for your learning, you will eventually things will start falling into place for you. For me, it happens. You know, once you find your groove, once you find your rhythm in the learning process, you will find a way to it will happen naturally you will find a way to start following more difficult problems and you know, mastering the subject. So everybody's path is different towards following these kinds of, you know, that's how it is. So that's I mean, everybody learns differently. Everybody has a different path. The goal is the same but the path is different. So don't compare your learning paths with somebody else's, even though you can look at somebody else's learning path and maybe take elements that are more suited to your learning style. But everybody's path is different. It's everybody learns.
Ghost Armadillo: Yeah, exactly. Okay. No worries. Yeah. Thanks for that. That was very helpful.
The Masked Hedgehog: Keep practicing, I guess. Yeah. Okay. Study the theory and then follow the problems. But I think in your case, I think you brush up on the material.
Ghost Armadillo: Yep, sure.
The Masked Hedgehog: Okay, anyway. Yeah, I think that's it.
Ghost Armadillo: Yeah, that's it. Okay, it was okay.
The Masked Hedgehog: Sure. I'll thank you for your time. And thank you for talking to me today. I really appreciate it. And I wish you all the best. And please have a nice day.
Ghost Armadillo: Yep, thank you. Okay. Bye bye.
The Masked Hedgehog: Bye Bye. Take care. Thanks.

Netflix Interviewer

Binary array partition

Heuristic Panda, a Netflix engineer, interviewed Orange Storm in Python

Watch interview

Slack Interviewer

Transformation dictionary

Spasmodic Pizza, a Slack engineer, interviewed Winter Griffin in Python

Watch interview

LinkedIn Interviewer

Reverse word in string

Space Dragon, a LinkedIn engineer, interviewed Ice Gyro in Java

Watch interview

Airbnb Interviewer

Missing item list difference

The Legendary Artichoke, an Airbnb engineer, interviewed Supreme Werewolf in C++

Watch interview

Ready to practice with a mock interview?

Book mock interviews with engineers from Google, Facebook, Amazon, or other top companies. Get detailed feedback on exactly what you need to work on. Everything is fully anonymous.