Reverse Nodes in k-Group

Watch someone solve the reverse nodes in k-group problem in an interview with a FAANG engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Interview question

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list. k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is. You may not alter the values in the list's nodes, only nodes themselves may be changed.

Interview Feedback

Feedback about Swift Thunder (the interviewee)

Advance this person to the next round?

Yes

How were their technical skills?

4/4

How was their problem solving ability?

4/4

What about their communication ability?

4/4

Strong pass - candidate crushed it, no major notes Good talking through possible solutions and discussing tradeoffs Asking questions and clarifications at start - good! Discussing algorithm before coding - good! Typing out example - good! Good thinking about the edge case (e.g. not enough remaining nodes) Good discussion of options for dealing with edge case Good discussion of time complexity in tradeoffs Pseudocode vs real code - i’m fine with real code, weigh time tradeoff Good asking about boundaries of the input variables Good use of functions Creating stubs and filling out later - good technique! Good bounds checking One thing to keep in mind with recursive solutions: stack depth! Consider using python types - good style and helps clarity Not a bad idea to throw in a couple of comments Can sometimes be good to run through examples on top of the actual code using comments Walking through an example to “test” your code is a great practice, but don’t spend too much time vs *actual* testing Good testing practice, don’t forget to test all edge cases

Feedback about Existential Cronut (the interviewer)

Would you want to work with this person?

Yes

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

I really enjoyed the interview, you did really well in giving me the right level of assistance to keep under the time constraints. It was also pretty useful that you had prepared some extra code for testing, not all interviews are like that. I don't really have an idea of how you could improve your interviews per say.

Interview Transcript

Swift Thunder: Hello.\nExistential Cronut: Hi how's it going?\nSwift Thunder: Hi. It's going well. How are you doing?\nExistential Cronut: I'm good. Thank you for signing up for the service. So you're looking to do an algorithmic interview, right?\nSwift Thunder: Yes, I am.\nExistential Cronut: Just making sure.\nSwift Thunder: Yes.\nExistential Cronut: So I think generally the way I run these is that I have a question that, to be honest, is probably harder than what I would ask most candidates, but I like to ask it in these practice ones, because I think it's better to kind of maybe expose weaknesses that we can then kind of talk about and improve upon.\nSwift Thunder: Right, yeah, that makes a lot of sense.\nExistential Cronut: Yeah. Generally I'll run these kind of like I would a normal interview. So not going to kind of hand hold you too much unless I kind of feel like you really need it, and then I'll probably give more help. But I generally try to do it as I would a normal interview, where I'm going to let you kind of drive it and I'm there to give you feedback or maybe give some tips and hints and things like that. And then at the end, if you hear me typing, it's probably me making notes at the end, we'll kind of discuss any kind of feedback I can give you that kind of hopefully helps you going forward. Does that all make sense? If you want to run differently, that's definitely an option, too.\nSwift Thunder: No, I'm okay with that. Let's go with that. Cool.\nExistential Cronut: And then, I guess just one other thing before we dive in. This is an anonymous platform, but if you want to tell me a little bit about what your experience level is, what kind of jobs you're targeting, that can help me calibrate a little bit, too.\nSwift Thunder: Okay, so I have one year of experience. I've been working full time at a startup company while I've also been finishing my college, my undergraduate, and I'm targeting SD One positions. SD One or two positions at a level. Big tech firm. I'm working in an AI startup, but I want to move into a big firm now. Got it.\nExistential Cronut: Okay.\nSwift Thunder: Yeah.\nExistential Cronut: Makes sense. Yeah. That just kind of helps me kind of calibrate expectations a little bit. If you're coming and you're saying, yeah, I'm looking for staff roles, obviously, like, I kind of judge a little bit differently than people that are looking for SD One. SD two roles, right?\nSwift Thunder: Yes.\nExistential Cronut: Okay, so if you don't have any questions, I can paste a problem in and we can jump in.\nSwift Thunder: Yeah, let's go with that.\nExistential Cronut: Great.\nSwift Thunder: Okay.\nExistential Cronut: Give me 1 second to paste this in. We're doing Python.\nSwift Thunder: Yes. Great.\nExistential Cronut: Okay. So I pasted a problem in. You can see that?\nSwift Thunder: Yes, I can. Yeah.\nExistential Cronut: Okay. So I can tell you about it a little bit, and I can also just let you read it as well. So basically, I am going to give you the head of a Linked list, and I would like you to reverse that linked list, k at a time where k is some positive integer less than or equal to the length of the linked list. So looking at we got a couple of examples down here. Given this linked list, that looks like 12345, and I know this looks like an array, this is just a representation and a K of two. We would want to reverse these two at a time. So we would have 2143. And then because there are not enough elements left at the end, we leave that last one alone. We have five. Similarly, if we do the same thing with k equals three, we wind up reversing the first three. We get three, two, one, and then because there's only two elements left, we leave those alone.\nSwift Thunder: Okay, that makes sense because there's not a whole set of three, then you don't make any modification. Okay, exactly, that makes sense. Okay. So in terms of how I would go about solving this, I feel like the common weak space wise, like the weak space solution, it would still be oben, would just be go through it once and add all the nodes to a list. And that makes it very easy to deal with it because now you basically have in list format rather than as a linked list format. But I feel like that's kind of like against the nature of the problem. And also it's a weak solution, at least in terms of space complexity.\nExistential Cronut: So I give you credit for coming up with the easy solution. But yeah, let's do it in place for a solution.\nSwift Thunder: Yeah. So if I was to think about how I want to do it properly, obviously I'm going to need to have so I'm going to traverse in some means whether that be recursion or iteratively. I haven't decided which one I would use yet, but I think I want to take a little bit to think about what I would need, and then I'll decide which method I would do that. So one, I'm probably going to need to have some counter that counts up to the value of k. We can call it, I guess it would be like let's call it count and that would be like current group. So if I start at the value of one, two or five, and I know that I have k of two, my current node I'd count, but k equals one and my second node, I know K equals two. How would I look backwards? Because it's just reversing. I guess you could just keep reversing until wait, the idea is it goes one, two, two. The idea is you keep reversing until you hit a point. So two, one. I guess the point of complexity when it comes to k is rather than at each value, just swapping it. You want to know that the last value has to point towards the value on the next group. The first value of the next group. That's kind of important. So I think that what that means is I have to keep the value of count. But I also need to remember specifically what is the first node. When I enter like a new group, I'm going to need to save that node specifically. And then I can kind of iterate forward, continuingly adding the count. And then as soon as count hits K, count becomes equal to K, then I know at this point, I've already reversed this group. I just need to take the node that I've saved and point it towards the next node. And then when I go into the next node, I can restart count and I can restart count from there. Let me try and work that out in terms of actually typing that process, like a dry run of what the idea would be. Let's do with a longer group than two. Because I feel like that'd be a bit more indicative. So 12345, let's do six for now. So it'll be a full group, two full groups. If I start with my count at equal to zero and I have my saved node, it will be empty or it'll be none. I look at my first node. I'm setting count equals one here. So I'll see one and I'll save. I will indicate where I'm at currently in the duration. So if I start at one, then I know that I can set count equals one. And I can save this value. Because now count is equal to one. Whenever count equals one, I'll save that current node so I can say the value of one. Then I'll push forward. When I push forward, all I want to do is set. I don't want to set so one currently points to two. I will not change what one points do. I just move forward and I'll say yes, I also need to maintain previous. So I'll need a node for previous, which will be just every node I'm at save that value. Because it's a single linked list, right? It's not a double linked list. Yeah. Okay. So I'll need a previous variable which will save the previous node. So I'll put one to previous. When I move forward, I can set two to point towards previous. And I can set after I say basically current, something like current next previous. I will then set previous to the current node. Then I will save, let's say count not equals two. Previous will not equal to this line. It's not necessary anymore, but one will stay saved. Then I'll push forward again. At this point, I now have count equal to three. I will set it equal to previous. I can save three as previous. I don't think that matters yet. And I have my safe node. So now I know that K equals three. Does that matter when I enter here? Does that matter when I go forward? The only issue with this method would be, since this is reversing as I go along, if I run into a group that does not that does not have K enough, then now I have an issue where I've already reversed some of the inner nodes, but I wasn't actually supposed to. So that's actually the pitfall of this method of reversing as I go along. Okay. To solve that, it could either be if I hit the end and I haven't hit the end and I haven't reached K, do I want to go backwards and try to reverse it again? I feel like that seems a little bit counterproductive to do it that way. The other way would be to not do any reversing until I've hit K. So I guess it would be instead of setting previous as I go along, I iterate forward until I've hit K, and then I go back to the value that I've saved because I have the head of that, and then I iterate forward again. And at that point, I start doing the reversing. That could make sense. It basically end up being like it would be O of N twice. So I think that'd still be fine because you're still just touching every node twice at that point, so it still counts as an oven solution, I believe, at that point.\nExistential Cronut: That sounds right to me. You can do either one of those, but one of them sounds easier to me.\nSwift Thunder: I think the second one sounds easier. I feel like going backwards and reversing after reversing once seems like a pain.\nExistential Cronut: Yeah, I agree.\nSwift Thunder: Yeah, I definitely think so. Rather than reverse as I go forward, I have to go forward until I hit the end and then go back to that saved value and set it now that okay. I know that I can reverse these K values, and then it'll be the same thing in terms of at the very end, set save next equal to the next value before I yeah. Okay. That makes sense. Okay. I can start writing out a code for it. I could write out a pseudo code, or I can go forward and start writing, like, regular Python code for it. It's up to you.\nExistential Cronut: If you feel comfortable going straight to Python code, that's fine by me. I think I understand the algorithm you're proposing, and it makes sense to me. So whichever you want to do.\nSwift Thunder: Okay. I would write a little bit of pseudocode, but I feel like Python is so similar to pseudocode, I kind of end up writing something similar to I guess I will do this. Will I do this recursively or I do this? Iteratively the benefit of doing it recursively would be I could have one function that recursive forward, and I can just name another function to call for when I know that I can actually reverse these values. So, like, have one function for just iterating forward, and that calls the reverse function, which will then reverse the previous k values just pass in that node. I could do something like that. That doesn't cause any efficiency increase. That just might be easier to have that separation of when I'm doing the reversing. When I'm not doing the reversing.\nExistential Cronut: Yeah.\nSwift Thunder: Okay. So I think I might do it that way and I'll just do it recursively. Iterative can sometimes be like nominally faster, but it won't be faster by a.\nExistential Cronut: Significant thing recursive or are you just adding a function call?\nSwift Thunder: I guess both of them work. I don't think there's any difference in the so I guess I'll just do iteratively. I'll just iterate forward and then I'll call a function to reverse the previous.\nExistential Cronut: Whichever solution I think that you want to do. I think either one could work.\nSwift Thunder: Okay, I'll start with an iterative outer loop and then have a function call. Okay, so I guess we're going to have an input. Let's define the function. Let's call it verse k. It will take in a root node and it'll take in a value k. Okay. A couple of base cases would be is there any constraints on this?\nExistential Cronut: Only what's given. So k is a positive integer less than or equal to the length of the linked list. And then root is this list node that I've provided for you.\nSwift Thunder: K is a positive integer that's less than or equal to the length of the link list. Okay, sounds good. So let's do if not root, let's do a quick return none. If there is nothing reversed then we'll return nothing. That sounds good. So let's start with I'll have a value called current or current will equal root. I'm going to need a value for previous will equal none and save. I won't need to save previous until I actually start doing reversing. So this won't actually be necessary. And save will equal none. Initially, I will save the value at welcourt next. But next. Okay, let's do wildcard next. It's never run into an empty empty one. That could be annoying. So while cure next we can do count plus equals one. And all that important is if count equals equals one, then we need to say save equals current.\nExistential Cronut: Okay.\nSwift Thunder: And if count equals equals k, then we're going to need a call of our function. I can just define the function real quick. Let's say define to reverse or let's say reverse helper. That will take in current node and it'll take in also no value k. So how many to reverse makes sense for now, just pass that. Can you writing the outside. Okay, so here we'll just call reverse helper, we'll pass in print and we'll pass in k. Otherwise then all we'll do is set cur equals cur next. Yeah. Okay. Notice that these are both saying graded out. Just save a special word. In this case I think it should be.\nExistential Cronut: I don't think so.\nSwift Thunder: I don't think it's supposed to be. At least unless there's, like, a version of it. But it should be fine, I guess. Yeah.\nExistential Cronut: It's not highlighting as anything, so I think you're okay.\nSwift Thunder: Yeah. I haven't used this platform in a bit over a year, or nearly a year, so I don't know if they made any changes to no worries.\nExistential Cronut: Well, I mean, if it breaks.\nSwift Thunder: Yeah. Then I'll just change the variable name. Okay, so for reverse helper itself, the idea will be here. We'll need a previous value. So we'll set previous to none initially and we will move forward. Okay. We will set previous to none. Will we actually need to just making sure. It is important that we set. At some point I'm going to need to make sure I have some way of setting save because there will be at some point where I need to set save next to current next.\nExistential Cronut: Yeah.\nSwift Thunder: This will be important. There are scenarios where I'll need to do.\nExistential Cronut: You discount there?\nSwift Thunder: Yeah. I don't know what I'm seeing right now. I'm seeing the whiteboard. Is that what that is? Okay. I closed it. Okay, I closed that. Okay, so I know at some point I need to set save next to current next. I'll probably be in this outer loop after the service has happened. Okay, but let's not do that yet. Because one thing is this should happen in place. I believe that if I pass in root, it should make the in place changes. I believe it should happen. Python. I don't think it's going to create a whole new copy. It won't be able to create a deep copy. So it should make in place be.\nExistential Cronut: A copy of the reference.\nSwift Thunder: Yeah, but the actual nodes themselves should be changed. Like if I say curve next, it should change. Yeah. Okay, so let me just write this real quickly. Previous on Next while current next? No. Current will always while count is less than we can do. So if not current, there's an issue anyways. Sure. At this point, we know that we have to have k values. So we should never run into a none value. Except unless the final next might be none. But what do you want to do? We want to say next equals curve. Next. We want to set curve next previous. And then we want to say curve equals next. And then we want to set previous equals current and set curve equals next.\nExistential Cronut: Okay.\nSwift Thunder: Yeah, I think that's and then also count plus equals count plus equals one. Okay. And then I think that should work out fine. Say we're in a scenario where we pass in this node. Oh, wait. Also, we'd not be passing in Cur. We'd be passing in Save. Okay.\nExistential Cronut: Yeah.\nSwift Thunder: There we go. Okay, so say we pass in one. We'd say next would be equal to two. Current next would equal none because previous is none. At this point. There might be a scenario where we need to pass in. Do we want to ever pass in the initial none, or do we want to set that afterwards? Because it's going to be important that we set what the first previous is going to be. So maybe we actually pass in what the first previous sounds like a weird way of saying it, but if I was, I might need to pass in the note of three. Either I need to do it here or I need to do it here. The question is, what do I pass back when I want to pass back?\nExistential Cronut: You're saying when you say here wait, what? I can't necessarily see what you're saying when you say like, put it here or put it here, just so you know.\nSwift Thunder: Oh, okay. I guess. Can you see code when I highlight it?\nExistential Cronut: I can, but I think it lags a little bit.\nSwift Thunder: I'll take that into account. Yes. Okay. So basically if I'm trying to reverse four, five, six, I know that I'm going to want to set four sixes previous to three. I'm going to be saying six is previous to three. So is there four is previous is going to be five. So what I'll be doing is next equals curd on next, which is five. Curtain. Next will be equal to previous will equal to previous, which at this point is none. So we'll be setting four is next to none. We'll be setting five. Fine. Previous equals current. So previous equals current. So yeah, previous holder now equal to four. Yes, previously, now equal to four. Okay. Current, next. Let me just actually just type it out. So if I was currently at four and we were actually reversing, we had the values previous, current, and next. We know that current is equal to four because it starts off that way. Previous is equal to none. Okay, initially. And next is also equal to none initially because it gets set. So we set four. We instantly set next to five. We set current next to previous. So we know that four will point to none. Current on next equals previous. Previous equals current. So we'll set previous to four. Current equals next. So four will equal to five and count forward. So then when we come back through the loop, we'll have five. Next equals cur. Next five. Next is six. Six will be equal to previous. So five x will be equal to four. So we know five will point to four. Current will equal to next. Next is six. Or previous will be equal to car first. So previous will be equal to five. At least at the six. Okay, that makes sense. I feel like that's working on this part. So we know that at the end. Well, let me just I mean, there's only one more side, but we'll do the final part of that loop quickly. So next will be equal to current next. So if we set current to six, next will be equal to current next, which is none current next is equal to previous current next. So six will point to five. Previous will equal current. So previous will be equal to six and current will equal next. So current will equal none will go forward. Okay.\nExistential Cronut: Yeah.\nSwift Thunder: So we'll end up having six, five, four, and nothing after that point will be changed. Will anything be pointing at six anymore? No, nothing will be pointing at six anymore. But we will have to return previous at that point as well. And then we can change what will point to six. Because we know what we want to point to six, it's going to be save so we could return the value. We can return the value previous. If you return previous here very end. And then after we run this helper, we can set save next equals previous or save next will equal actually, this will equal what's next. What's pointed to is that true? Is save what we want to because save no, what would have been passed in as save here was four. So we don't want four is next equals six. Yeah, we want the one before we want three to point to it. Do we have previous saved in this scenario? We don't. We could save it and we could actually just keep track of previous and this would be the only case we'd use it. That's one way of doing it. I think that's fine. Yeah, I think that maybe I'll keep it variable equal to previous. Should we set to none and here we just set next. That seems okay with me. Why is this an issue unknown none for next? Is it just because it doesn't know that previous is a list node yet? Okay, we just have to make sure previous exists in this case. The only case we would run into this if previous doesn't exist would be if like k equals one. Because in the first loop, previous is not set yet. Okay. And in that case, if k equals one, then we're not reversing at all. So I guess I could just we're not really doing anything if k equals equals one, we could just make sure to return root. We don't want to do anything at that point. That way we don't have to run to that issue of previous equaling none when we run through this. Otherwise, when we do what is set here, previous equals curve. And then we can do curve equals curve next. Sure, that takes care of doing the reversing and making sure the previous one points to the part that's reversed. Okay, I need to make sure that this is everything I have for now. I also need to make sure that if count equals k, then we can also set count back to zero.\nExistential Cronut: Yes.\nSwift Thunder: Current equals equals one, save equals current. Yeah, that's fine. Then we just keep going past that part. Yeah, that's the main adjustments that need to be made there and then at the end of the day. Well, we also need to save the route and return the route at the end of the day. Well, no, the new route is going to be like if this was the route, right? Because if we reverse this way, we're going to need to save the first time we reverse. Okay. So let's create a variable. Let's call it final because it'll be the final thing we pass. Okay. Final route just to be a good naming. Final route. Next. Let's see, in this scenario, previous is the previous will end up being the new head. No. Will previous end up being the new head? Because what if we have the scenario of the first one that gets reversed? In this case, we're passing through to three. At this point, previous is only equal to two. And we're calling this again. Oh, wait, this would end up making oh, wait, this was a mistake. Actually. I just realized this is a mistake because I'm setting previous is only the last value. But we don't want because we're not calling this loop here, we're calling the loop here when we're at six. So that was a mistake, actually. So we cannot want previous to point to six. We want the previous head kind of to point to six.\nExistential Cronut: Sure.\nSwift Thunder: So I need a way of keeping track of what is the previous head. How do I keep track of what.\nExistential Cronut: Is that was your pre value, right?\nSwift Thunder: Yeah, but I just realized so I have this previous value. So each turn previous will get pushed forward. Right. But I'm calling this whole reverse helper only when count equals K. So I would end up calling that helper when I'm at the value of six. Like one of the times I'd call it would be at the value of six. At that point, I'd return the value of six. But at this point, my previous is still equal to five. I don't want to set five next equal to six. I want to set three next equal to six.\nExistential Cronut: I thought that's what you with the pre value, but maybe it's not. So then yes, you do want to keep track of what I guess one needs to point to is this the K equals three case? The K plus two case. What are we doing again?\nSwift Thunder: K equals three.\nExistential Cronut: Okay. This is the K equals three case. Then ultimately we're going to be wanting pointing to one to six, right?\nSwift Thunder: Oh, yes, that's true.\nExistential Cronut: Final thing is going to be three, two, one final output.\nSwift Thunder: Yeah. So this was the idea of what I wanted with previous. But I realized just by setting previous equal to current every turn, this won't actually keep track of the right value.\nExistential Cronut: I think that might not be the right way to set previous.\nSwift Thunder: Yeah. So what I need to do is the only time I want to set previous will be at the first value. So actually what I might want to do is something like when I know that I'm going to be running this, at this point, I see why I did something like save because I want actually the previous value to save. But how about every time I set a save? Is it every time I set a save? No, it will be every time I set a save. Because the save is going to be the first value. It's the one I'm going to jump back to. So I'm going to want to save this value in some fashion.\nExistential Cronut: The save previous is the previous one I think is what you're trying to.\nSwift Thunder: Save is a new save because it's actually oh yeah, I want to set previous before I create a new save because I want to save the last save. There's a lot of same words. I'm saying it over and over again.\nExistential Cronut: This problem that gets a little bogged down in the naming sometimes, but I think you have the gist of it.\nSwift Thunder: Yeah. Okay. So I'm setting save equals curve at this point. I also want to set pre equals save. So I want to save this value only when I create a new save. Okay, so then when will previous not exist? Previous will not exist if, well, if ken equals one previous does exist, will previous always exist? I think previous should always exist this way. So we should never have an issue of like a none next call with previous specifically. So if I had the values of 123456 and I'm in the outer loop, let me delete these values. I'm in the outer loop and I'm going to the values of 123456. What variables am I keeping track of? I'm keeping track of current, save, and previous and count. Okay, either values, current, save, previous, and count. So current starts at root. Save will start nothing. Previous to start nothing. Count starts at zero. So I go into the first value. First value. We'll set count to one. At this point, we'll set previous will be set to save. So previous will be set to none at this point. Just fine. And save will be set to current. Oh, wait, you're actually wait, previously set to none. It's an issue. Okay. Save will be set to current, so it'll be saved to one. There is actually a scenario where I'm kind of before, but if brief temporary new variable is being added, I guess let me delete this. If prev next equals temp.\nExistential Cronut: Yeah, makes sense.\nSwift Thunder: Otherwise if there is no previous, actually, that would be the final route. So we can actually so that actually gives us a way of keeping track of which one is the final route as well. So that's actually convenient. Okay, going back to this, so we know previous equal to none, save count. I guess I'll also keep that value here. Okay, so in this case, because previous is set to well, we're. Not going there yet. So this starts at none. So we iterate forward, make sure k equals three. If we iterate forward, we'll set count to two. Nothing happens here. We write forward again, count equals three and at this case we go through this value and we set temp equals reverse helper. So at this point current is equal to three. Save and previous are equal to the same thing. Okay? So at this point we will run our caller function and the end of our function should be we'll have a new value temp which will be equal to temp will be equal to one in the day because that should be what it's set to. We have passed in save just fine. We don't do anything with that value anymore right now. Temple be equal to one, template equal to one. We'll set previous next. In this case we don't have a previous so we'll just set final route to temp. So we set final route to one and then we set count back to zero. Okay? And then we just loop forward, right? Yeah. If we loop forward into cur next. Now cur is equal to four. And because now count is equal to one, we set previous equals save. So what is save equal to? Save is equal to one. So previous will equal one. And we also set save equals ####. So #### is three. So save will equal wait, no curse. Equal to four. I just didn't count that forward. Okay, cure is equal to four and save is equal to four. Also at this point we don't expected to send out be three, two, one, something done by the other function. Okay? Yeah. And that's all that happens at that point. We just iterate forward again. We'd say cur equals card next and count equals one. Okay, so we do curry next. Current next is five. Count is two. We don't do anything here, so we just count for it again. Counts is equal to three and current is equal to three. Current is equal to six. When we call the function again, we'll set temp equal to we would end up doing six, five, four. We would set temp equal to four. Right? Yes. Temp equals four. Oh, wait, it returns previous and it should return the new head. Oh, no, it returns six. Temp is equal to six. Yes, it will return six because it's going to return the new head of that point. At that point, we know previous exists. So we would set one previous next equal to six, which is good. Finally set. We don't do anything there. We set. Count back to zero. Previous is set. Okay. And we just move forward. That looks correct on that. And the only thing I can think of as being an issue is at the end of the day, we want to return final root. But if the size of our entire list was less than K, we'll have never created a final route because we'll never have gone into this loop.\nExistential Cronut: You're guaranteed that k is less than or equals the length of the list.\nSwift Thunder: Oh, so there'll always be at least one reversal.\nExistential Cronut: Yeah, there should be.\nSwift Thunder: Okay, so then final root should always exist.\nExistential Cronut: Value is the length of the list, in which case you're just doing like a full length list reversal. Right?\nSwift Thunder: Full lengthless reversal, yes. But in that case, final route still gets set, right? Yes, it does. Okay, so that means final route should always exist. So that means I can just return final route at the end of the day.\nExistential Cronut: Great.\nSwift Thunder: Okay, I've done a very convoluted dry run. I could write up some test cases and try and run on that.\nExistential Cronut: I think it'd be a great idea to write up some test cases. And to save you time, I have some helpers for making link lists for you.\nSwift Thunder: Hang on, that'd be very nice.\nExistential Cronut: Yeah, it just feels like a waste of time to make you write out something like making a link list or something.\nSwift Thunder: So hopefully this makes sense. Okay, we'll do things like test one will equal create test case from one to six. Is it inclusive? I wrote it as inclusive.\nExistential Cronut: That's a good question. Yes, I wrote it as inclusive.\nSwift Thunder: If you just pass in none, or if you do test three equals, just take a note there's a node or list node. List node is list node. Okay, let's do list node and a value of zero and it'll be no next value. Okay, this will be one of the test cases as well. Are there any other? Well, these will be the three main lists I'll test on, and then I'll test it with various k's. So let's do print list on what is a function called reverse k? Yeah, reverse k. We'll take in test one and we'll do a k of two. And.\nExistential Cronut: I think you got to do that printless doesn't taking a second parameter.\nSwift Thunder: Yeah, I'm treating as if it's a regular print statement.\nExistential Cronut: It's not quite that clever.\nSwift Thunder: Yeah, I think it's fine if I just yeah, it's fine.\nExistential Cronut: Let's make sure it's working.\nSwift Thunder: Yep. Two. Oh, well, it's guaranteed to be the length of it, so it has to be one in this case. Oh, then.\nExistential Cronut: K can't be zero.\nSwift Thunder: Yeah. So actually, this case can never actually happen because we're guaranteed that it can't be zero. And we're guaranteed that the length of this has to be equal to that.\nExistential Cronut: Assuming that you'll always have at least one list node passed in.\nSwift Thunder: Okay, we can hear that. What are these? Because it does return it, I think it's okay, let me run this. See, that does not look correct. Okay.\nExistential Cronut: So I think that's maybe we should put some again, I didn't make this that clever.\nSwift Thunder: Right?\nExistential Cronut: So maybe let's yeah, put some just for the sake of oh, also I'm.\nSwift Thunder: Passing in test one twice. This might also be an issue because using the same list, I might have to recreate it. So why don't we do I'll do.\nExistential Cronut: This a little bit easier to read? I didn't get that clever with these testing functions.\nSwift Thunder: Yeah, that makes.\nExistential Cronut: Yeah, looks like.\nSwift Thunder: Okay, so it seems like the connecting of the separate groups is not going as planned. It seems like. Yeah, that's what I guess because we do want to initially reverse two and then one. But then we also wait two and then one, and then we also want that one to point to the next value, which would have been four in this case. But that's not happening. So let's figure out where that's going wrong. That should be happening here. That's the idea. This is where we want it to happen. If previous set preview next else. Oh, wait, but where do I set previous previous save. So we would expect that next time this happens, the previous should get set to a real number or real node. But I guess it's not saying it's happening.\nExistential Cronut: Let me give you a hint because I think I see where it is. Take a look at where your curve pointer is.\nSwift Thunder: My curve pointer. Okay. Current equals current next save count. My curve pointer would be wait, is it because after I start doing the reversing, my curve pointer would end up if I was going through one, two, three, my curve would be at three, and then I call the reverse. And then when I call curd next, it's going to go into two because I've already just now set curd next to two rather than it being six. Okay, I see. So if count equals equals K, we actually want #### to go forward before that point anyways. Will we always want curd to go forward before that point? Can I not just move this? Because we don't touch cur at all in this case. So we could actually just like that and have it jump to the next spot before we call the reverse anyways.\nExistential Cronut: Seems reasonable.\nSwift Thunder: Yeah, that might fix it. Let's try running that. Okay.\nExistential Cronut: 2143. Okay, so we're missing the back two, but that's progress, right? So we know we've seen succeed properly. It looks like it failed based on these three tests. It looks like it's failed last chunk.\nSwift Thunder: Yeah, it's not connecting the final chunk. So what would be different in the final chunk? Oh, well, I mean, what could be different about the final chunk that would cause this to be an issue? Well, I mean, curs being set to cur is going to be none in the final chunk. Would that matter? I don't know for sure if that shouldn't matter, I don't think.\nExistential Cronut: Final chunk. What is #### going to be none in the final chunk?\nSwift Thunder: Well, only effectively, when we get to this point, #### will be set to none. That is like, because if we're going to jump forward so if the final chunk is going to be like six by four when we're matt sex six, I'm jumping #### to none and then I'm doing the reversal of it. I don't think #### doesn't have any effect afterwards, so I don't know if that would matter. But something I was thinking of.\nExistential Cronut: I'm going to ask again. Are you sure that #### can ever be none?\nSwift Thunder: Am I sure that #### can never be none? Well, the loop is supposed to not allow that. Yeah, check only happens after it.\nExistential Cronut: That's something you want, right? Because you said, like, you're going to be at six and then you're going to jump to none, right?\nSwift Thunder: Yes.\nExistential Cronut: But that couldn't happen, right.\nSwift Thunder: That couldn't happen by this point in the code. But by this point in the code it could. Right. Because if I'm setting it to none here, it's not going to do this check until I can go through the finish this current iteration of the while loop and then check up here. Right?\nExistential Cronut: Well, think about if you were at curve five, right, and you go through this and then you set cur equals cur next occur is going to be six.\nSwift Thunder: Right? Because cur next does exist. Okay, I see. If I go to cur five, I guess actually it's important that we're doing the check is actually going to be because I want to go to the last loop while current exists. I see. Okay. I normally do a current check this time, just how to do current next. And I should have thought about that. It's important that I actually touch the last value. Okay.\nExistential Cronut: 365-32-1654 and zero.\nSwift Thunder: Okay.\nExistential Cronut: Those look pretty good. One other case I would like to check is one where we don't have a list of a length that's divisible by our K. Right. So we had our example above that was like 12345. Right. Where the last, like, two, if it was K equals three and 12345, the last two don't get reversed.\nSwift Thunder: Oh, yes. Okay. Makes sense. Actually, there is actually one other case I want to check, which is for when K is equal to the length of list. I didn't actually check that as well. Do both them. Why not? Five, four, and we'll give it the value of three and we'll take in test five. Give it the value of five. Okay. Running that this is accurate. Three, two, one did run into an issue. Okay. Because wait, why would that be an issue? Because the idea is the only place where we set previous next is here. It is because of this case of setting previous next, we need to make sure we do that. If we run into a case where if you run into a case where we've gone over and we've not done the reversal part, we need to make sure that we still set previous next to save. So what we can do is just after the while loop, we can check if count. So if count is not equal to zero okay. That would mean that we have not because if we're at a perfectly divisible value, count should always be equal to zero at the very end. But if we weren't able to do that, then we know that we need to set pre next eight, I believe. I think that out there. Yes. Okay. And that fixes that. Okay. I was a bit convoluted.\nExistential Cronut: You probably also could have checked, like, if pre next is none, but yeah, either one. I think both of those make sense.\nSwift Thunder: That's true. Yeah.\nExistential Cronut: Cool. Yeah.\nSwift Thunder: Okay.\nExistential Cronut: I think you got it, and I think you did it in pretty much the amount of time you're going to have, which is about 45, 50 minutes. Cool. Congrats. You're the rare candidate to actually solve this problem in the interview. I would say, like the vast majority of people I ask this question to do not solve it in this interview. And within the time constraint, I tend to let people run over and stuff, too, in some cases. Like, you've solved it well within, I think, the constraint you would see in a real interview. And yeah, usually I don't think you'd probably see questions this hard most of the time in real interviews. I ask this mostly to see how people deal with a hard problem. But yeah, congrats on getting this. Most people do not get the whole thing, including doing tests and like oh, yeah, and you even did the time complexity, which I was going to ask you and forgot about. Great. Let's see, I made a bunch of notes. Most of my notes are like, saying that you did good job doing things.\nSwift Thunder: So let's see.\nExistential Cronut: I'm just going to kind of go down my list in kind of no particular order. Let's see. So we started off you kind of went through the problem and then started talking about some different solutions and weighing trade offs between them. I think that's really good. Convince the interviewer that you actually do understand the problem. Let them give you some feedback on if one is easier or better or something like that. And I think that discussing trade offs between your different solutions makes you look really good as a candidate. Right. I think that's something we look for in higher level candidates than SDE One, SDE Two in particular. So I think that puts you ahead of the curve. Let's see, you asked some good questions at the beginning about the value of K. That's always a good thing. Always kind of get that, try to have a good understanding of what inputs you're actually being given. So always good to ask those clarifying questions at the beginning. I liked a lot how you discussed the algorithm before we jumped into coding. I think this format of writing out some kind of variables and going through some cases to discuss the algorithm is a really good way for you to understand it and also a good way to convey to the interviewer that you understand the problem and what the solution you're actually proposing is. I do something similar when I do interviews.\nSwift Thunder: Nice.\nExistential Cronut: Yeah. Typing out the example. That's always great. Let's see, I think you did a pretty good job thinking about what the edge cases were. You saw kind of the case right away where there's not enough remaining nodes and how do we deal with that? And thinking about, okay, you need to count forward and then you kind of discussed a couple of different options for how to do it, which is like, do you want to fix go back and change the links back or do you want to just count forward and you weighed the time complexity of that. I thought that was all really good. I think at one point you talked about doing pseudocode first and then jumping into real code. That's fine, but I agree with your statement that Python is pretty similar to pseudocode anyway. And just from like a time constraint perspective, you probably would have run out of time if you tried to write pseudocode for this problem. I personally lean towards not writing extensive pseudocode before jumping into actually coding the problem. Just because you are on a timer here.\nSwift Thunder: Right, okay. Yeah.\nExistential Cronut: But again, it's kind of case by case and everyone has their own workflow. So I'm not saying definitely don't do it, but it seemed like you had a strong enough understanding of this algorithm that it kind of wasn't necessary to do example and then pseudocode of the algorithm and then write the actual code. The number one thing you're going to get kind of graded on, I think, is does the code work right? I think most interviews where you especially in SD One, SD Two, I think if you have working code, that's going to be kind of the first line of all your feedback. Right. And everything else is not icing on the cake. But it's going to be hard to not get moved forward at those levels if you solve the problem with working. Right. So always a thing to prioritize. Let's see, we talked a little bit about the boundaries on K. That's always a good thing to ask. I think you went straight to using pulling some of this out for use as a function. I think this problem becomes a lot easier if you recognize that reversing the linked list, like the sub linked list and then stitching together the linked lists are like two separate problems. And if you factor that out into another function, it makes it way easier. I've seen candidates that try to do it all in one big function and they lose the thread. It becomes always a good thing to think about how can I refactor or how can I factor my code into logical blocks? Right. I think you were doing a little bit of this where you stubbed out the function and then you put like a pass in there. I think one of the ways that I like to think about problems like this is take a piece of logic and just think about what you want the input what do you want the input and output of that thing to be. And then just assume you have it, and then you can kind of run with the rest of the problem. Assuming you have it and go fill in the other part.\nSwift Thunder: Yeah, I like doing it that way as well.\nExistential Cronut: Yeah, it seems like that's pretty much what you're going for. I think that's like a really powerful technique for a problem like this. Let's see. Okay, I had a couple of slightly more, maybe constructive comments. One thing is you talked about doing a recursive solution. I think we ultimately landed on an iterative one here and I think you're right that they would be the same. I think the recursive one is probably harder. Most of the solutions I've seen are iterative, but even nonetheless, the thing I was going to point out to be sort of mindful is that with recursive solutions, even if you're not actually adding any memory you do, sorry.\nSwift Thunder: Yeah. They can be more costly on your memory. Right? Yeah.\nExistential Cronut: You have to think about the stack depth. Right. The stack depth does add memory and potentially if it's like a very large case, you will run out of memory. So there are certain problems that you basically can't do with recursion unless it's like tail recursion, which is not something I want to get into. Just like a thing to think about weighing solutions. I doubt you'll run into that too often in kind of an interview format, but a good thing to make an interviewer aware that you're aware of. And if for some reason the recursive solution wasn't going to work, that might be a moment where you can give them the opportunity to wave you off.\nSwift Thunder: Yeah. I do mean to usually say because I usually like the recursive solution because it makes more sense logically in my brain a lot of times, but I recognize that the iterative is usually better so I force myself to go iterative anyways, but I kind of forgot to say why I was doing it. One of the reasons why I chose it was because I'll think, okay, recursive is going to end up being costly on memory. I should have yeah, you can ask.\nExistential Cronut: The interviewer, right, like, hey, the recursive solution is going to consume some stack depth. Do I have any bounds on the size of my input? Right, I didn't tell you the maximum length of the list or anything like that. Right, that's something you could probably ask the interviewer like, hey, am I going to run out of stack depth? And if they say no, you're fine, go ahead and do however you want. Right? Yeah, let's see, I would consider maybe taking advantage of Python's types, not a requirement, but I think something that looks nice from a coding style standpoint. If you're familiar with how this in line 82 and line 94, where you have the types of the inputs, types of return type, I wouldn't get too bogged down into it, but I think it looks nice from a coding style standpoint. And every once in a while it might help you out if you're passing the wrong thing, help you realize you're doing that. I think your code is pretty clear and well written and your variables are pretty well named. That being said, it's not a terrible idea to throw a comment in here and there just on a big block, just so you both, for you and for the interviewer to kind of keep track of what logical blocks are doing. And that could be as simple as something like maybe on line 70 here, stitch together separate list, something like that, right. Just makes it a little easier for everyone. But again, I don't think you really lost the thread at all. So not minor knit. We went through a lot of examples kind of up here, which I think is great. One other technique that you can do is when walking through your code that I like to do sometimes is.\nSwift Thunder: Put.\nExistential Cronut: Comments out here and be like, okay, if count is equal to one, or put a comment here and be like, okay, prev is going to be equal to one here, right. And then say equal to, I forget, four, or something like that, right?\nSwift Thunder: Yeah.\nExistential Cronut: Again, this is just like a tip, but might be easier to visualize as you step through the code.\nSwift Thunder: Let's see, run a couple of example.\nExistential Cronut: I think it's really great that you tested your code by walking through an example. We did a lot of that towards the end. That being said, I wouldn't spend too much time doing that versus actual testing. Right. Because even after doing that, we found two or three bugs by doing actual testing. I think it's always good to find your bugs before you run the code. That being said, you don't want to run out of time, right?\nSwift Thunder: Yeah.\nExistential Cronut: We found these bugs pretty quickly, but sometimes debugging can take a little while. I wouldn't wait too long before actually running the code.\nSwift Thunder: Yeah, that's why I was kind of worried about it as well. I was like, normally I'd want to find them all myself, but I was like, there was two issues of one, the process of dry running was quite slow and I didn't want to end up adding extra confusion, especially because I didn't know I was conveying it properly. So I was like, okay, I think running will be more clear. So I just decided to take that hit this time. Just run quicker. Yeah.\nExistential Cronut: I mean, it's always good to find it beforehand, but again, best thing to have is working code at the end of an interview, I think. And then yeah, try not to or try to cover your bases with tests. I think you did a pretty good job, but one of the things you kind of didn't come up with right away was not having an evenly divisible list length, even one of the kind of examples given. And it's not a big deal people forget, but it's kind of always good to, I think, show the interviewer that you have a good grasp of what you want to test and what all the edge cases were. And ultimately that was like a thing that was broken, right?\nSwift Thunder: Yeah.\nExistential Cronut: So just a thing to keep in mind overall. Yeah, this is a strong pass. I think you did really well. This is a very impressive interview and any of the comments I'm having are pretty much nits. Yeah. You hadn't seen this problem before, right?\nSwift Thunder: No, I had not. I've done reverse link lists. It's like question like two or three on leak code probably or something like that. Yeah, I think I've probably done something like in the similar but it's been so long that I had forgotten the problem, basically. I feel like this is a question I can imagine seeing on leak code, but I haven't done it in a long time, so I didn't remember it.\nExistential Cronut: Yeah, this is like listed as a hard right. And I think it is okay.\nSwift Thunder: I haven't done that many hards on leak code, so maybe I've not done that.\nExistential Cronut: I think it's a pretty hard problem. So good work. By the way, here's the link to it. I pasted it in the comments up top just in case you wanted to look more at it. But we already solved it, so huge deal there. Okay. That's pretty much everything I can think of comments wise. Do you have any questions, any thoughts, anything you wanted to discuss? Things you thought went well, things you thought didn't go well.\nSwift Thunder: In terms of the you kind of got to hit all the big things I was going to ask in terms of how you thought about me, the clarity. I was a little bit concerned in terms of this dry running method I was doing. I felt like slightly it was even easy for me to lose myself. So I was worried about if I was going to lose my interviewer, I think I should have done something more similar to stepping through the code. I was just worried because the comment was so high up and my code is so low, I should have just brought the comment down. I don't know why I did not do that actually. So I think next time I'll try doing like a step to the code method better. I think that might be also easier to keep the interviewer along because sometimes it's easy for you to not be confused because your method. But if it's another person's method. They might get confused.\nExistential Cronut: Running was, like, overly confusing, but yeah, it might be a little bit easier to see on the code. It kind of depends what works for you. By the way, I did really like using this index pointer here, this thing online, 29. That's, like, a good tip that I give people sometimes as well for the interviewer. Interviews got kind of weird post covid, like, the online interview kind of became the norm instead of standing in front of a whiteboard.\nSwift Thunder: Yeah, I haven't done a whiteboard interview yet at all, so I'm going to need to learn how to do those.\nExistential Cronut: I don't think I've had one since covid It's true.\nSwift Thunder: Actually. Kind of hope I don't have to, but I'll probably have to learn to prepare for them anyways just in case the job market is not exactly the best. Got to prepare for everything. Yeah, that's a new one.\nExistential Cronut: Not a lot of people are even doing in person on sites anymore, so it's very possible you never encounter it.\nSwift Thunder: Yeah, that's true. Actually.\nExistential Cronut: Not that old, but slightly older.\nSwift Thunder: Yeah, it is an honest interview, so I can't I don't know any details on that part, but yeah. Thank you so much for the interview. You said you would pass me, so that's great. Happy to hear. And then I forgot what the rules are when it comes to this when it comes to linking with your interviewer or not.\nExistential Cronut: Yeah, there's a thing afterwards where you can hit, like, yes or no if you want to be put in touch with the interviewer. It's optional.\nSwift Thunder: Okay. Well, I mean, I'd love to connect with you on LinkedIn or something like that afterwards, if you're okay with that.\nExistential Cronut: Yeah, sure. I'll check Next on the form, and I think as long as we both check next, it shares contact info.\nSwift Thunder: Okay, sounds good. Great. All right, well, thank you so much for the interview, and thank you so much for your advice. I'll take the account.\nExistential Cronut: No problem. Thanks so much. And there's a survey after this. It really does help out if you fill that out, so I appreciate it.\nSwift Thunder: We'll do cool. Okay.\nExistential Cronut: Have a good rest of your day.\nSwift Thunder: Yes, you too. Thank you.