C++ Interview with a Snap engineer

Watch someone solve the print linked list reverse 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

Print linked list reverse

Interview question

Print a linked list in reverse.

Interview Feedback

Feedback about Epic Rainbow (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?

4/4

If this was a real phone screen, I would have given a weak recommendation to advance to onsites. "Weak" doesn't mean that your performance was weak, it just means that my confidence wasn't high. The main reason for that is that while you were doing very well for the parts of the problem that we got through, we just didn't have enough time to see if you could follow through and complete that last version. Your communication was very strong, definitely the highlight of the interview. I wish the candidates I usually interview were that thorough. You also did a good job of feeling out the requirements at the beginning (although for future reference, be sure to ask if you can mutate the data you receive as input, because that can sometimes be useful). Your problem solving was strong, and you did a good job of coding up your solutions. Speed could improve somewhat, but I wouldn't want you to rush too much and make mistakes. The main thing I think you could do to utilize the time better is just cut back a tiny bit on the communication. It's great that you explain things as well as you do, and definitely don't stop doing that, but sometimes I think you explained things two or three times when once would have done. The approach I'd suggest is to give an initial explanation with a good amount of detail, and then stop and give the interviewer a chance to respond. If they need clarification they should ask for it, otherwise you can save a little bit of time. Save a minute here, a minute there, and you'll really have the time you need to get all the way through the problem and deliver a great interview.

Feedback about DJ Cyclone (the interviewer)

Would you want to work with this person?

Yes

How excited would you be to work with them?

3/4

How good were the questions?

4/4

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

4/4

It was a fruitful interview for me and I learnt to not assume anything related to the interview process and instead ask about it. Thanks for all the great feedback and your time !!

Interview Transcript

Epic Rainbow: Hello.

DJ Cyclone: Hey, can you hear me?

Epic Rainbow: Yes, I can hear you. Hi, how are you?

DJ Cyclone: Great. How are you?

Epic Rainbow: I'm good, thanks.

DJ Cyclone: Cool. Um, just give you a little idea of how it's gonna go, you know, obviously things are anonymous. So if I ask you a question and you don't feel comfortable answering it for whatever reason, feel free to just, you know, tell me. Aside from that, I'm just going to ask you a couple of questions. You know, start with a little bit of, you know, just kind of generic questions. We'll move on to some technical questions for most of the time. And then I'm going to try to wrap up right about 15 till the next hour, so we'll have about 45 minutes total.

Epic Rainbow: Sure.

DJ Cyclone: And if that all sounds good, let's go ahead and get started.

Epic Rainbow: Sure, definitely.

DJ Cyclone: Cool. So just to get to know you a little bit to begin with, I was wondering if you could maybe tell me of all of the various things that you have built, you know, what is your favorite project to have worked on? Or sorry, what is the product you're the most proud to have worked on, and why?

Epic Rainbow: So the most favorite project I've worked on is that it was a performance improvement project. And I have most of my work, I have done in C, C++ on Linux platform. I have worked on in other languages also, like some time I've worked in Java and very little in Python also, but mostly I've worked in C, C++. So it was a... I have worked mostly in System Programming. So it was a project where we needed to improve the performance of the system. And it was becoming critical because our competitors had better performance than our product we needed that. It was a critical feature in order to succeed in the market. So that was... it was a high pressure and very critical feature for the project. And I enjoyed it most because it was... I was allowed to make decisions like what is best, what I think, how we should proceed. And I was leading that feature, I was leading a team of nine engineers, and it was a lot of fun in terms of the kind of work we did, and the amount of changes we made. Those were enormous and because of that, everybody was literally scared that whether there will be any issues when it goes to the field. But the biggest thing was that we did so much effort in that that there was no issues found in the field when it went, so that was amazing. And I got a lot of recognition also because of that, and it was because of the challenges issued in that in improving performance. Regarding the technical part of that, it was mostly that we have a multi threaded product, where in Linux, it's a server. And we have multiple processes and one of the main process performs a lot of activities in multiple threads. And when we went to the higher end server, we didn't get the performance as we expected, because there were bottlenecks and mainly due to locks, like table locking contention issues, because of which we were not getting the performance what was expected. So we changed our overall threading model. And we change that how the different type of objects are referred by different threads. So mainly we defined a threading ownership model, where we mentioned that these type of objects should be accessed only by this thread. And only one single thread will be the owner for one object, which means that that thread can access all that data within that object without getting without needing a lock, because this is the only owner and only this thread will be creating and deleting and modifying that data members in that object. So because of that ownership, we removed some of the locking. And we needed only the locks for the containers when we will put those objects in a container or when we will delete only that time we need it lock but not while we are accessing any particular data members in those objects. So that was one of the major change. We did some other changes also related to how objects should be created and how those should be accessed. We added some hash maps in our code to have the faster access. So there were a lot of framework changes, which I did really enjoy making those type of changes. So it was really a little longer answer, but that was my favorite project.

DJ Cyclone: Gotcha. Yeah. Sounds like an achievement, what kind of what kind of speed ups did you get out of that?

Epic Rainbow: So we improved 30% performance in that project. So it was quite good. And we achieved the benchmark that we needed to be in order to be able to compete in the market.

DJ Cyclone: Cool. Great. So let's go ahead and let's go to some technical problems now.

Epic Rainbow: Sure.

DJ Cyclone: So for these, feel free to use any language that you're comfortable with.

Epic Rainbow: I will change to C++.

DJ Cyclone: Okay, cool. So I'm going to go ahead and give us a...

Epic Rainbow: Do we need the chat window?

DJ Cyclone: No, you can close anything you want to, the only thing we're going to use is the editor. So let's go ahead and start with a linked list problem. This is going to be called print linked list in reverse. So I'm going to give you a very simple struct. And I'm writing this like it's C, but you can use it like C++ struct. We're gonna say that each struct has an integer for data. And it just has a pointer to the next node in the list. So it's a very basic singly linked list. Your goal is going to be to write a function that accepts the head node in the list, then prints its data members to the screen in reverse order. So for example, if we had a list that went from one to two to three to null, your code should just print one element per line: three and then two and then one. Any questions about that?

Epic Rainbow: So yeah, so what is the maximum number of entries we expect?

DJ Cyclone: Um, so let's go on to say that the list doesn't necessarily have a maximum size, but we'll say that for now it's reasonable, you're not going to like overflow the stack or anything.

Epic Rainbow: Okay, okay. And that data is integer, which is like it can be any negative or positive numbers within the integer data range. Is that right?

DJ Cyclone: Correct.

Epic Rainbow: Okay. You want me to print it in the reverse order on the screen, is that right?

DJ Cyclone: Yup, one node per line.

Epic Rainbow: Okay fine. Okay, I understand the problem. So, there can be different approaches to it. One of the approach can be that basically I traverse this... this is a singly linked list where I can move only forward. So, which means I cannot go back. So, one approach can be that I traverse through this list and keep putting these data members in a stack and then I suppose... because the stack is last in first out, then I can simply print all the elements from the stack that can be one of the approach. That will technically require O(n) space and it will be an O(n) time complexity. So, is that fine? Or do you want me to change the approach or try a different approach?

DJ Cyclone: That's great. Let's go ahead and get that down. And then if we need to, we can optimize from there.

Epic Rainbow: Sure. Okay. So, stack implementation, do you want me to use like... there is a C++ stack object in STL standard template libraries, is it fine if I use that or do you want me to create my own data structure?

DJ Cyclone: Definitely use the built ins.

Epic Rainbow: Okay. And you mentioned like I can, can I change this structure to a C++ object?

DJ Cyclone: Yep, definitely.

Epic Rainbow: Okay. So I will use this as a class Node. So I'll initialize it here and then I will define some public members to access the data. So these are mainly constructor and getter, setter functions I'm defining. So that's the constructor. This is get data to this, get it and set data to set the variable. We don't need it most probably but just to have both of the functions. Okay, so those are the basic, getters, setters. So now, we will need to do insert in this list and so I will define an insert function.

DJ Cyclone: So let's go ahead and let's just leave that. You know, we'll pretend that that already exists. We'll just say the node class is defined and you can just go use it as if it were fully defined.

Epic Rainbow: Okay, so should I insert... in order to test it, should I define? Like, should I insert some default data in this?

DJ Cyclone: Um, I mean, so we're not actually going to run it. So it doesn't have to be fully defined. We're just going to kind of, you know, look at it, make sure it's right.

Epic Rainbow: Okay, fine. So then, should I define just the main function there?

DJ Cyclone: No, you don't even need a main. Let's just write a function called called print list. And a void function that prints it to the screen.

Epic Rainbow: So, this is a function which simply is print, reverse list and it accepts a pointer to this node or head. So now this function will be... first I will check whether the head is valid or not. If not, it will simply return. We can't print anything, list is empty, otherwise we will traverse through the list. So, I will travel through it while the list is not empty. We will traverse through this list and I need a stack. So stack, but structure I need with integer data stack template with integer data, which will basically store the data to be printed. I'm moving through this list, I am traversing through this list and I will have head next... first we have data in the head also, depends how we define that node. We may or may not have data in the head but I will assume that head pointer also has data.

DJ Cyclone: The node you get passed is the beginning of the list and it also has data. So every every node has data.

Epic Rainbow: So I am checking while head is not equal to null pointer, then I insert in the reversed data. And then I move to the next head is equal to head next. So I keep traversing through this and at the end, head will be null and then I will come out of this while loop. So, now I have all the data in my stack and since it has gone into the initial, the first item has gone past, when I will take out the items will come out in the reverse order, so I will simply print it. So, which is the function I can use or I can use iterators for this purpose. So, it is basically, I will define an iterator first in C++, there are different type of iterators, or actually I can use auto variable for that because I have already... This is a function which will return that initial iterator for that list and then I will continue until iterator is not equal to reversed data dot end, which basically returns the end position, because the stack is empty now. And then I'm moving on in the iterator. So now this iterator points to each element by element. And I'm simply printing from here. And then as you mentioned that on each next line I should print, so I will do an endl, so I printed and and endl, so this function will print the overall list in reverse order.

DJ Cyclone: Okay. I think this looks good. So what's the runtime complexity of this?

Epic Rainbow: It is traversing through that two times so it is O(2n) in exact, but in terms of big O notation, it is O(n).

DJ Cyclone: Okay, and memory usage?

Epic Rainbow: Again, that's O(n) because I'm using a stack which will contain n elements, all the elements.

DJ Cyclone: Okay, sounds good. Cool. So what I would like to go ahead and do now is we're going to do this exact same problem. We'll write this next version in a separate function. So this time around, we're going to add a constraint. And we're going to say maybe, you know, maybe the list that you're getting passed is just absolutely enormous to the point where you can't duplicate it in memory. So for this next one, we're very specifically not going to care about runtime. This can be as slow as it needs to be. All I want to see for the second version is if we can get the memory usage down to constant.

Epic Rainbow: Okay, so our objective is to reduce memory consumption and we are trying to increase the time complexity. So which means that one of the method can be the brute force method like I start in the for loop, I start from the head and go up to the end, and I maintain the previous pointer. So when I've reached to the end of the list, and I've also maintained a count. So in the first basically, first time I'm counting all the number of elements and I also at the same time I print the last element and then I know that let's say there are 1 million elements, I have printed one of them. So now I need remaining of those. So which will mean that I will now print, I will go again from this head, I will go till the end, but I will stop one before based on the count and print the 999,999 element. Then next time one less. So basically based on the count, I will keep reducing counter and we'll print one less element. Although this is very unoptimized algorithm from the time complexity perspective, because it means the complexity will be O(n^2). But I will not be... I will be using constant memory which is like one previous pointer and one counter.

DJ Cyclone: That sounds good, let's go and implement that.

Epic Rainbow: Sure. Again it is reverse. And it is mainly it's time complexity, or it's more in terms of without a stack, so maybe I mentioned what the method name is, it's a print reverse without extra space or something.

DJ Cyclone: You can call it print reverse, no worries.

Epic Rainbow: Okay. So okay. So then, I go with the head again. First I check if head is equal to null pointer and simply return. Is it safe if I define a long count?

DJ Cyclone: Yeah, might as well.

Epic Rainbow: I define a temporary previous pointer. And depending on implementation I can avoid this also, but it's anyways constant memory. So now I move through this again with the same loop, while head is not equal to null pointer. But I increase the count and I increase the head pointer. So this will, when it comes out it will give me that count of the elements. And I'm just maybe I'm not planning to use previous, I will simply go by that. So now I know the count of all the elements, I will simply define two for loops. I will go up while it is less than count. And I will actually be going in the first in the inner loop, I will be traversing every time from zero to... or here it doesn't matter. It's not an array. So I can start indexing from one also, generally I'm used to start indexing from zero because in C++, that's how it is. So, I will go from there in the inner loop to the end and print that element and then reduce count by one. So, that next time I go one lesser. So, which means I can go by the... I can define it as count. And now I'm going in reverse, so, I will increment my list index and then I will have another for loop for proceeding according to that. So I could use better names, right now I'm using just l underscore i and j for indexes, which is list i and list J. I should use better names which are easier to recognize. So basically, I'm going from in the outer loop, I'm going from the, in the reverse. First I will print the count. So, in the inner loop will start from one up to count and when it reaches count, or maybe I can within that I can print it. Or that's fine, there are different ways. I will print it outside the loop. So, which means I will go up to that count so I will inside this I'm moving head is equal to head next. So I'm just moving the head to the next and every time I need to reset head so maybe I will use a temporary pointer here because I need to store it even before this actually because we need to reuse the head. So here again I replace next dot node with head. And that's what I will use to traverse. And I can move it and I need it anyways inside. So I will move it inside the inner loop. So now this after this loop I have reached to that count and I will simply print that element where I am right now, which is the next node data, and then it will reset it. So, I'm just checking that that's done. I'm just checking I'm not making any error in the edge cases. So basically, I'm in the inner loop, I start from one and I go up to until I reach the outer limit, which is set by the outer loop function.

DJ Cyclone: So instead of walking through that, let's just go ahead and walk through a test case. So if you could just walk me through kind of line by line from the beginning here. Imagine that we have our test list 123. And let's just go through line by line and kind of track what you know. the value of every variable is going to be as we go along.

Epic Rainbow: Sure. I'm just checking me to make sure I have set all the variables correctly just last time before we start the test loop. So it is going from count to one. So, in this case it will not go on that case on one, it will not go ahead and it will print first one and in the last case it will go up to it if it is three elements or whatever it will go up to that and it will be printed. Yes. So, I was making sure I have right edge cases condition. So, yes so, now to start with with the test case you mentioned. So, first head will be pointing to the data where head is stored, which comes in this list, I check rather than null it is null or not it should not be null where it has three elements. And then I assign this variable count which will have zero initially. And yes count has zero then a next node points to head which is basically it's a temporary variable because I will be changing it. So, next dot goes to the first and then within this while loop, I am checking whether it is null or not. So, it is not null. So, it will go inside the while loop. Count will become one. And next node will point to the next one. So, now next node has come to two yes, then again it will go and check whether it is null or not, it is not null, so count will become two and the next node will point to the next one three then again it will check whether it is null or not it's not so it count will become three and next node will point to null and now it will check whether it is null or not. It is null, so it will not go inside the loop now, so I know the count now, that's how many elements are there and then we proceed to the next for loop, outer for loop here, this integer l_i I will be set to three and the condition will be checked whether it is greater than zero or not. It is greater than zero, so, the condition is true, three is greater than zero, so, it will go inside this loop. And now again I'm be setting next node to the head. So, it points to one. Then it goes into inside loop this new variable l_j is created with value one and it checks whether it is not equal to three, which is right now l_i value is three, so is it equal to three or not, it is not. So it will proceed inside and next node will point to the next one. I move next node to the next one. Now next node is pointing to the next one. l_j is incremented to two, it checks whether it is equal to three or not, it is not. So again, it goes inside and increments it to three. And then again it comes out and it checks whether it is equal to three or not it is equal to three. So, I'm checking for one less here. So, no, that's right, because we are on three, and we don't need to increment anymore. So yes, we are on three so the loop doesn't go in and it comes out and the data is printed from three. So next node data which will print three, and then it goes back to the outer loop. It decrements the l_i value, which becomes two now. And now again, it goes next node. We set it to head value, which is one.

DJ Cyclone: I think we're good. So we've seen that looks like it's got all of our conditions. So I think we're good there. So like you said, the runtime of this is O(n^2). We got the memory down to O(1), which is good. So now with the last little bit of time we have, I was wondering, do you think there's any way that we could get the runtime of this back down to N without increasing the memory usage?

Epic Rainbow: Okay, so without increasing the memory usage, we want to decrease the run time. We can do the stack, but that again indirectly we will be using memory, but it will be the call stack of the process not the auxiliary memory. So, it depends whether when you say not using extra memory is it allowed to use the call stack memory but not any auxiliary memory like if like our own stack operation, for like basically I will be using a recursive solution in that case, I will be going recursively.

DJ Cyclone: So, the stack the call stacks is still going to count in memory usage. So we'll try to avoid that.

Epic Rainbow: Yes, so that solution will again be using same amount of memory. So if not that, we don't want to use memory. The challenge here is once we go to the end element, we don't know the previous node. Somehow...

DJ Cyclone: So let me offer a small hint here, which is that you are not required and I'll actually... so let me change our class slightly and make everything public within it. So there's no requirement that you have to leave the data untouched. So the nodes that are passed into the function, you are free to modify them, if that would help you.

Epic Rainbow: Okay, so before I think about modification part, with traversing through them. One thing I'm thinking about is, while I'm progressing through them, I can put them in a string variable. I can start basically, those integers in a string. But that will require, again memory. So I guess that will also not pass the criteria. But I just want to be sure that whether that will work or not, basically, instead of when I'm going through them, I keep printing them in a string. And I print in front of that every time. I'm instead of printing out, I've mentioned a string.

DJ Cyclone: That would also count as memory usage. So let me... let's look at it this way. If I asked you to print the list out, in forwards order, you can do that very easily, right?

Epic Rainbow: Yeah.

DJ Cyclone: So could you maybe transform the list in a way that you would be able to just print straight through it?

Epic Rainbow: Well, yeah, yes. Yes, that's, that will be much easier. Yeah, definitely. So while moving through the list, we can reverse the list. And then after, so one time I traverse through the list and reverse the links so that the list becomes the reverse list and then I can print it. In the straight forward. Yes. I didn't think about that, reversing the list. I was assuming I think that I can't change the data structure. But yes, if that is allowed, if it is fine, that to change the data structure links, then I can reverse the list and print it that.

DJ Cyclone: Yeah, so let's go ahead and get started on that.

Epic Rainbow: Sure. So basically, it's in the first function, print reverse list, I get the node pointer head and I check again if head is null pointer, return. Otherwise, I call a function. I used a reverse print. I call a function reverse list which will reverse it and give me and then I printed simply with the for loop or by loop like I did earlier. Don't need to count. So, this will basically... based on this function it will it should print it. Now I will implement that function. It is returning node pointer. So again, it will check... Now I need to maintain a temporary pointer... I started with head only. And so I'm just thinking how I will be switching the pointers basically. So, with the head, I will move to the next one and I maintain the previous one and I set the previous one next as null in the start and then after that I will be moved going next and next. So, I might need two pointers, but I have to start with... So, previous I am restoring. And so I have moved to the next element. And then I set the next of head. I'm just thinking out loud that when I'm on a particular node, I want to set it's next to the next one, but before that I need to store its next value. So previous is head. And I store head next and so now head next is equal to previous. But before that I should store head next next. So which means I'm overdoing it right now so I'm just trying to make sure I'm doing it properly. So I store the current value in previous pointer, and I define one more. So first I store the current value in previous, then I move it to the next one. So it's in like in our example one, two and three. Initially my head is pointing to one, previous stores one, head moves to next, which is two. And then I store next as the head next, which is now next is pointing to three. But if any of those is null, I have to check for that.

DJ Cyclone: Sorry, I'm actually gonna go ahead and stop you there. We're kinda come up against her end of our time here. But this is definitely the right direction. At this point, if you have any kind of questions for me right now, I'd be glad to answer them for you.

Epic Rainbow: Sorry, I could not finish it. I think I needed five more minutes. But yeah, we are at the end of the time. So definitely, it's I will really appreciate if you can provide me feedback.

DJ Cyclone: Sure. So I'm gonna kind of write up something a little bit more detailed after we hang up. But just kind of like a quick overview. I think if this was a real phone screen, I would probably recommend that we do bring you on site. I would probably say that I wasn't completely sure about it. So you did a very good job of kind of feeling out the requirements and coming up with solutions. The only problem we ran into is that, you know, it wasn't, you're way behind, but it was a little bit slow. So I would have liked to have seen us kind of finish this one in the time that we had. And I think that you could have made it if you just maybe cut down a little bit on, like, boilerplate type of stuff. So for instance, like, at the very beginning, when he started kind of like filling out the full class definition. You know, it's worth just asking, like, do I need to implement this or can we just assume that it's there. So I think that, you know, if you just maybe gone a little bit quicker, right, maybe spent a little bit less time on that kind of boilerplate type of stuff, it would have been a little bit of a stronger result. But all that being said it was still it was still a solid interview, I think, you know, you didn't go all the way through but you got the first two solutions fine. You definitely knew where you're going with this one, you're just kind of working out the details. So I think overall good, maybe just maybe just go a little bit quicker. And that's kind of the overview.

Epic Rainbow: Sure. Yeah. That's good to know. Yeah. I agree that I should have asked that whether what to assume and what to do, so to remain focused on completing it, yeah.

DJ Cyclone: Yeah, I would say like so most people, their problem is that they they don't communicate enough, right. Like they don't tell me what they're thinking what they're gonna do. And you did a really good job of making sure you were very thorough telling me everything. I would almost say you have the opposite problem. Like you sometimes maybe repeated things a little bit more than you need to. So I don't want to tell you to like, communicate a lot less, because it's very good that you're, you know, being thorough. But maybe just spend a little bit less time on explanations, just a tiny bit less, I think would help you use the time you have available better.

Epic Rainbow: Sure, yeah. That's good to know that feedback. Thank you.

DJ Cyclone: Yeah. And thanks very much for your time.

Epic Rainbow: Yeah, thanks for your time and feedback. Okay, I will note these points and I will try to take care in future. Thanks a lot.

DJ Cyclone: Thank you. Have a great rest your day.

Epic Rainbow: You too. Thank you.

DJ Cyclone: Thanks, bye.

Epic Rainbow: Bye bye.