C++ Interview with a Snap engineer

Watch someone solve the copy list with random pointers problem in an interview with a Snap engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Copy list with random pointers

Interview question

Given a linked list with an additional pointer referring to another node in the list, return a deep copy of the list.

Interview Feedback

Feedback about Parallel Prism (the interviewee)

Advance this person to the next round?

Yes

How were their technical skills?

3/4

How was their problem solving ability?

4/4

What about their communication ability?

2/4

Going directly for the most optimal possible approach was a risky move. You did end up getting far enough that I would have put you through to an onsite, but it was close to the time limit and ideally I would have liked to be able to spend some more time cleaning up your solution. I would say that overall you did a very good job of figuring out an approach to the problem, but you could probably benefit from some more practice just doing linked list manipulations, because you struggled a little bit to turn the algorithm you came up with into actual code. The other thing to watch out for is just to make sure that you communicate frequently and try to take hints about direction from the interviewer. Generally you'll maximize your chances of a strong performance by starting with a basic solution and then moving towards more complicated approaches as necessary

Feedback about DJ Cyclone (the interviewer)

Would you want to work with this person?

Yes

How excited would you be to work with them?

1/4

How good were the questions?

4/4

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

4/4

Interviewer provided me right amount of hints that kept me moving. One thing I was not sure was if my first solution was good enough or shall I optimize it further. Interviewer was able to guide me with that. Overall it was a good experience and I enjoyed it!

Interview Transcript

Parallel Prism: Hello.

DJ Cyclone: Hi, can you hear me?

Parallel Prism: Yeah, I can hear you. How are you doing?

DJ Cyclone: Good. How are you?

Parallel Prism: I'm good, thank you.

DJ Cyclone: Alright, well just to get things started. I'm Rodney. It's good meet you. Cool, so just give you a little idea of how it's going to go. We don't really have a strict schedule, but I'm going to try to keep it to about 45 minutes just so that we get, you know, a chance to kind of work like in a typical interview time frame. It is, of course, an anonymous interview, so if you have, or sorry if I ask you anything the you don't want to answer because you're afraid it might reveal your identity, feel free to say so, we can always move on. And we're just going to spend the time working through some technical problems together. So for these you can use a language you want. I see you already found the syntax highlighting, that's good. And at the end, I'm just going to start trying to stop you a little bit early, take about five minutes to ask me any questions that you have. If that all sounds good, we'll go ahead and get started.

Parallel Prism: Yeah, that sounds good.

DJ Cyclone: Okay, cool. So let's go ahead and start out with a little linked list problem. So, we're going to give you a linked list structure here. And I'm just going to write this as a basic struct, we don't need a whole class for this. So each node is just going to have a single integer for data. It's going to have a pointer to the next node in the list, so in that respect it's a very basic singly linked list. We're also going to add one extra pointer to each node in this list. And we're going to call it the random pointer. So this is what's going to make our list a little bit different. And the random pointer is allowed to point to any other node in the same list. So it won't be null, it won't point outside the list, but aside from that it can point anywhere. So, just to give you an example, I'm actually going to go to the draw tab right now. If you look at the bottom left hand side of the screen here. If you just want to go ahead and switch over to draw, I will illustrate an example here. So imagine that we have an example list. And we'll say that it has nodes that we'll call one two, and three. List is terminated by a null, so the next pointer goes from one to the next, totally normal singly linked list. The random pointers, however, could go anywhere. So in this example, we'll say that the random pointer from one maybe goes over to three. Random pointer two maybe points to itself. And the random pointer from three maybe points back to one, right? So these can be self-referential, they can have cycles, there's no particular rhyme or reason reason to. So your goal is going to be to write a function which accepts the head node, one of these lists, and it's going to return a deep copy. So we want you to return the head node of a new list, which has the same elements, so we'll call them one prime, two prime, and three prime for the new list. And this new list should have random pointers that mirror the structure of the random pointer in the original list, so one prime's random pointer would point to three prime, two prime's would point to itself, and three prime's would point back to one. Does that all makes sense?

Parallel Prism: Yep, so when you say one prime, do you mean the actual data, or even the data is referenced?

DJ Cyclone: Sorry, say that again.

Parallel Prism: So the one prime is... the data remains the same right? Whatever the value of node one is, the same value for the node one dash, one prime?

DJ Cyclone: Yes, that's correct.

Parallel Prism: Okay. Alright. I see. Okay, what I'm thinking is... Yeah, I think it's clear to me, what are we doing here.

DJ Cyclone: Okay.

Parallel Prism: I'm trying to think like how can we solve those things? I think that random pointers are a little tricky here. Next pointers are pretty easy because for the next pointer you go through the node one by one, create a next value. Two prime and then one point, two prime, keep going next, next, next, and keep reading the new values, prime values and updating the node. So next is simple, the tricky part here is random. I'll say because I don't know when I say node one or two, I don't have a node three yet, so where should my random point point to? So what we can do is... I don't know this is a very... No it's probably not a good idea, but it's one of the approaches, storing the address in the hash map. So I know that one points us to three, and I know for my three what is the corresponding three dash, and my one dash should point to the three dash. But it's like almost an unnecessary wastage, like for every node, I need to have a value in the map. Like one point in the one dash, two point to two dash, three point to three dash. And then I want to point from one to three random pointer, I look at the value from the map and my one dash is pointed to the three dash, so that way.

DJ Cyclone: Yeah, I think that sounds like a good approach.

Parallel Prism: Yeah, the only thing we're not... It is going to be based off of memory, because for every node we need to have an entry in the map.

DJ Cyclone: Yeah, that's fine. Would you like to start on that?

Parallel Prism: Yeah, I'm just thinking about there should be a better way of doing it. Is there any other way other than map? I'm just thinking about that.

DJ Cyclone: So, I will tell you that there is a better way. I've given this problem probably two dozen times, I think one person has come up with the better solution. So generally speaking I don't expect people to find it and I think that the hash map solution is actually very acceptable.

Parallel Prism: I see, I see, okay. Alright. Can I just take five more minutes to think about the problem before I go to the hash map. If I cannot find a better approach, I will go with the hash map. Is that okay?

DJ Cyclone: Yeah, go ahead.

Parallel Prism: So we cannot modify these nodes right, to store any other data?

DJ Cyclone: No, you can modify them if you want.

Parallel Prism: Let me tell you what I was thinking. Okay, it's similar to map, what I was thinking, if my one point to one dash, two points to two dash, and three points to three dash, what I would have done is with my extra pointer, which is pointing to one to one dash, two to two dash, three to three dash, I know that one goes to three, and from three, I can go to three dash. So my one dash can go to three dash directly. I can explain with the drawing. It would be something like this. But the thing is I need to modify... this additional pointer I need to keep.

DJ Cyclone: Alright, yeah.

Parallel Prism: So what I'm saying is, I know I can go from one to three. And from two to three dash. So I know my one dash should point to three dash. Instead of a map, I'm manipulating a pointer which is pointing to the copy.

DJ Cyclone: Okay, so you are free to modify the data that gets passed in, but the actual structure of the nodes needs to remain the same. So if we had an extra pointer, that would be basically equivalent to that, right? If you wanted to reuse the existing pointers, however, you are free to do that.

Parallel Prism: Well if I can use that existing pointer... Okay, so you're saying that it's not probably right thing to do like this, right?

DJ Cyclone: Right.

Parallel Prism: Are you able to see my code?

DJ Cyclone: Yes, yeah. Right, so you have to keep the same two pointers, but you can do whatever you want with them.

Parallel Prism: Okay. So like if I cannot have this thing, what else I can have? Let's see, let's see. So I cannot modify my random pointer, because I need to know where I'm going. What if I modify my next pointer, what will happen here? Another question is, shall I return the original list as it is?

DJ Cyclone: So you just have to return the copied list. We will say we don't care what condition you leave the original list.

Parallel Prism: Okay, okay if that's the case, what I'm thinking is, when I create one and one dash and I create my next is two, so I modify my next to point to this one. So this will be broken like this. And I create from this point to this eventually. And this will be broken. And this will point to this eventually. So my original list next will be broken. But my randoms will be restored. Now how do I traverse the original one back? Because my randoms... I need to travel the original list back for the random pointers.

DJ Cyclone: Very close. So let's say that you do this thing that we talked about, right? So let's say you do this, right? You now have a pointer from two to two prime, okay. So do you still need one prime's next to point to two prime or you use it for something else?

Parallel Prism: You know. It can be like this. And this points to two prime. If my one prime points to two, two points to two prime, two prime points to three, then probably I'm okay.

DJ Cyclone: Yeah. That would do it.

Parallel Prism: Just, I need to do every time instead of a next, I would go from one to two, I have to next next.

DJ Cyclone: That looks like a good idea.

Parallel Prism: Yeah, yeah. I hope. It's going to be complicated, but let's... okay, I'll give it a try. Let's say...

DJ Cyclone: Oh, you don't need a main, you can just write a function that accepts the input and returns the output list.

Parallel Prism: Okay. Will we need to run this one?

DJ Cyclone: Oh no.

Parallel Prism: So if my head is null, then we just return head. You don't have to do anything. Otherwise, what should we do? Let's make a copy. This equals head. so that we never lose track of my base. And, let's say we make it as temp pointer. So while pointer not equal to null pointer, keep going like this. So what I'm doing here. Let's say my constructor is such that node, it takes data. And it copies data like this. So, I will do one thing for node star equals new node, which is the base data. So what I've done is after the new base, this is my original base and final base. And we have moved the pointer here. This is pointer one. Okay. while pointer one next is not equal to null pointer, so this means my next is not null so I have some data there. So I will create a new node. And my pointer two next contributes, new node n. And my pointer two now moves to this end. And pointer one equals pointer one. So basically, just copying the whole list. So if my original list is one, two, three, I create a base using this one. I copied into one prime, two prime, and three prime like this. So I have done up till this much right now. Now I need to modify the next. So that one points to one dash. Either I can do it in a separate routing, in which I travel the linked list again and making next point to the next one. I'll do right now in the second routine to just not confuse things, maybe we can do it in this routine itself.

DJ Cyclone: Okay.

Parallel Prism: This is an operation we can do, but I just right now don't want any kind of confusion to make it work, and then we can try to optimize it. So which means my temp one will be two. So this is node number two. Now my pointer one becomes temp one. So it becomes two. And my pointer two advances ahead. Okay, so what I've done is, I have changed the mapping into something like this. Next pointer one next to two. One to one, temp one, yeah. Okay, now what I need to do is I need to travel the original list again. And now I need to change the random pointers. I should setup the random pointers for this one. So what I'll do is... Okay, let's do this setting again. Okay, now what I'm doing here. Now, I'm thinking now what I've done can could have been otherwise, which will have been if my one dash converted to one. I could have done that one dash next, which is random. What I will do is. Now pointer one next. The pointer one, they will always be next for the pointer one, which will give me one prime and it's random is nothing but pointer one random.

DJ Cyclone: So pointer one's random, it's going to point to a node in your original, right?

Parallel Prism: Yeah, that's right. The pointer was random's next. So point to one, next random is pointer one's random next. The trouble I'm having now is how to advance pointer one ahead. What I'm struggling with right now is, I cannot go from one to two, right? Because I've broken the next one, so had I done...

DJ Cyclone: So right now, you know, one prime's next is two prime. Two prime's next is three prime. Do you not necessarily need those next pointers in place, or can you use them for something else?

Parallel Prism: You know, what I could have done, so for two prime, this mapping, their random are right now nothing, they're bogus. So if I had done the other way, one dash pointing to one, I could have done my one dash random is one, two dash random is two. And now what I could have done is I could have traversed this whole node, my random would have given me this one, and from this random, I could have gotten the value.

DJ Cyclone: Okay. So the problem there is that we're going to want to write to random. What if one prime's next pointed to...

Parallel Prism: Oh that's what we just got right, this goes here and this is going here. Yeah. That is also going to, yeah, I think that also going to work. I need some code changes here. So my temp one is pointer one's next. Sorry it is two initially, let's go back to the original diagram. I have something like this. What I want is my temp one is this. Temp two is pointed towards next, which is two prime. My pointer one next is pointer two. My pointer two's next is temp one. It doesn't give me one dash pointing to two. My pointer one is temp one, which is two. And my pointer two is temp two, which is two prime. I'l just go through this again, maybe I'm missing a case. And I should do this. So what will happen here, my pointer one points to. Pointer one. Pointer two. I'm just noting down all the variables and seeing how the values will change. So my pointer one initially changes to one. Pointer two points to one prime. My temp one pointer is not equal to none, so my pointer temp one will be pointer one next, which is one's next too. And temp will be equal to prime, initially the state is like this. Now what I do is, my pointer one next points to pointer two, so this next is gone and this has been here. And pointer two's next points to temp one. So we have something like this. And since I'm changing the next, this will go away. My pointer one is temp one now. And my pointer two is temp two. Just do the prime. And now we go ahead and two points to three, only temp two will be one to two is next, two dash which is three dash, yeah this looks fine to me.

DJ Cyclone: Okay.

Parallel Prism: Now. Yeah. With them, pointer one's next is nothing but pointer two. And two goes to this. Three. And two prime goes to temp one, which is three, which is also right. I just want to make sure this part is correct because this is the key here. Now my temp one is pointer one's next. Sorry, this is three, this becomes three prime. My temp one is null pointer here. Temp two is also null pointer. Pointer one's next is one to two, which is correct. And pointer two's next is the null pointer, which is correct. Pointer one becomes temp null, so this is fine, yeah. This will become null, and this will become null, too. So we'll have this linked list ready. And now if I traverse here, I'll go to the pointer one here, pointer two new base. Okay. Pointer one's next is random. I advance the pointer one more. Okay, except the last case where there is no next next, I should be careful there.

DJ Cyclone: So pointer one will always point to a node in the original list, right?

Parallel Prism: Right, so pointer one is one here. And from one, it goes next next to two, next next to three, but if I do a next next, there's nothing.

DJ Cyclone: So, the next next pointer is... I mean, so three has a next, right, which is three prime. And then you can take the next of that, right, which is null.

Parallel Prism: Oh yeah. Which is null. So pointer one is three dash, and next is null, so it should be fine. And I will break down the... Oh I need to correct the pointers again, so that original is back, but I have to return in the end new base. But I need to the point that's because the next are wrong, so let's do this activity. So okay, so in this case both the original list and the new list will be fine, intact, which I was worried about initially, but I will... the first linked list will be destroyed, like it will be really wrong state when I leave it, but no, we can fix that too. So, probably what I want to do is... Sorry, this is wrong, my temp 1 is next, which is one prime. And my pointer two is new basic one, which is two. My pointer one next is equal to two. And my pointer two's next is temp two next. So temp one is this. So what I'm doing here is now pointer one next is not this anymore, but with it temp two, this one. And my pointer two, which was one, it's next is nothing but temp two's next, this two prime. Okay. My pointer one is nothing but pointer one's next, because we have already the right pointer from one, we can move to this and pointer two. I think I could have done this with just one pointer because it's going zigzag.

DJ Cyclone: That's okay, it's a first try. I think that looks pretty much good, and we're also coming up on the end of our time here, so at this point, I will stop you, and be glad to answer any questions you have.

Parallel Prism: So I was not sure like about had I gone with the hash one, would have that been acceptable or would there have been some negative point for that?

DJ Cyclone: Yeah, so when I use this for real, I just expect people to do a hash solution. I have only one person ever come up with this approach before, so you know, very good job coming up with it. Obviously if this was a real interview, I wouldn't recommend like going straight for the optimal one, like you know, it always helps to get something that works down first. Then optimized from there. For just an exercise, that was very well done.

Parallel Prism: Okay, like one thing which I'm not sure is, when do we decide that okay it's time to spend some more time with the optimal one, go for the optimal one, but what might happen if I could have started coding the hash one method, and later on I have realized, oh I could have done this way, but at that time, there was not enough time left to write the code. Any input on that side?

DJ Cyclone: So I mean, the big thing is always communicate with the interviewer and usually they'll give you an idea of what they want. Generally speaking, you're going to want to go for kind of a basic solution first, so there are you know, there are problems that I give where there are more optimal versions that I expect. But when I give those problems, generally I have them kind of written down in my head, so there's like a progression that I'm expecting, like they'll probably do this basic version first, and then I'm going to prompt them to see if they do this optimization. Generally with those, like if I have multiple versions of the problem in mind, I also have, you know, I also make sure that there's time in the interview to do multiple versions.

Parallel Prism: Okay, okay, that makes sense. Yeah, that's all I have for questions. Thank you so much.

DJ Cyclone: Yeah, thank you, thank you for your time and I hope you have a great rest of your day.

Parallel Prism: You too, and thank you so much for taking time to interview me, it helped me a lot and really thank you for that.

DJ Cyclone: Awesome, have a great day. Thank you.

Parallel Prism: You too, bye.

DJ Cyclone: Bye.