Interview Question: Nth-to-last Linked List Element
Vložit
- čas přidán 28. 08. 2024
- Coding interview question from www.byte-by-byt...
In this video, I show how to find the nth-to-last element of a linked list.
Do you have a big interview coming up with Google or Facebook? Do you want to ace your coding interviews once and for all? If so, Byte by Byte has everything that you need to go to get your dream job. We've helped thousands of students improve their interviewing and we can help you too.
Stuck on Dynamic Programming? Check out our free ebook: www.dynamicprogrammingbook.com
Need an interview coach? Send in an application: www.byte-by-byte.com/coaching
You can also find me on
Twitter: / bytebybyteblog
Facebook: / bytebybyteblog
Email: sam@byte-by-byte.com
This video saved me at my final round interview with Microsoft internship explore.. I watched this video two nights before. Am back here just to comment haha 😂
These videos are fantastic, using these to help prepare for a Google Interview and can't thank you enough
you're welcome!
Im currently prepping for an Interview with Goolgle and this is helping me get more confident. Thanks Byte By Byte!
Love your tutorials! Not only do they help with solving the problem, but your explanation helps beginner coders as well :) Thank you!
Thanks I'm really glad you're finding them helpful! :)
Very nice explanation, pointing out most hiccups that could come up during an interview, this is very good, thanks a lot.
Thank you for that. I'm in bootcamp and we do algorithms in the morning. We just had this one a few days ago. Unfortunately, if no one gets the answer right, they won't give you the solution and we move on to another. Thanks again!
Brilliant solution. Which is depressing cause I didn't think of anything close to that. My solution took O(N) time and O(N) space, I basically created a stack and push items to it, then pop n times.
your run time is exactly same either way.. you're running through the list once, but with two pointers, so essentially thats O(2n) as well.
fair enough
That's a really good point
@Byte by Byte I think you should add this in your video through an annotation
Complexity wise, yes. They are both O(n) in the worst case. We usually don't care about the coefficient. However, if you are talking about a finely-tuned efficient program, access of the elements in the second example is less costly because the data that curr points to would still be in the cache when follow tries to access its place in memory. You would get a cache hit probably every time. However, traversing the list twice, assuming an extremely large list, would likely not have any cache hits and you would need to keep loading the data from ram into the registers (much slower)
He explains it at 3:30 that O(2*n) and O(n) are essentially the same but that you should still show you are not being wasteful and got for the O(n).
I had previously solved this question on a site
1. Counted total number of nodes
2. Made the pointer run accordingly
In this question the person does not try to count the number of nodes but instead maintains a fixed distance between the 'current' and 'follower' node so that when the 'current' pointer reaches the end, The 'follower' pointer will be on our required node
Thank you very much for the clear explanation! I just started to learn coding interview questions and your playlist is awesome :)
Thanks!
Thanks a lot Sam . You explained it beautifully
So in cracking the coding interview book the solution is wrong because the for loop is as follow:
for(int i=0;i
[Python solurion]
def n_to_last(list, element):
return len(list) - (list.index(element) + 1)
I am totally astonished that this actually works that simple
What happens if n = 5 for your test case? Your code would crash because the second while loop tries to access next node of null.
yeah you're right. if you click over to the website, though (www.byte-by-byte.com/nthtolastelement/) I've updated the code so that issue is resolved
This case can be easily handled by placing the if condition after curr=curr.next.
for (int i = 0; i < n; i++) {
curr = curr.next;
if (curr == null) return null;
}
Such test-case would be invalid becz N can never be >= length of linked list.
Becz here we're considering N as element after the last element and not from end of the list.
Thank you for explaining so well! Really enjoyed this video.
If the list has exactly n items the "while (curr.next != null)" test will be evaluated when curr is null. Won't that throw an exception?
yep good catch. One easy fix is to just check if curr is null before the while loop
No it won't. Cuz in that case when curr becomes null it will return null (in the for loop ) and will come out of the function without even checking the following while loop .
THIS IS AWESOME!
Thank you so much for the interview preparation help!!!
Ajay Curam you're welcome!
what I'm curious about is why in the brute force method where you count the list, why does it go through it twice? Don't you just go through it once to count? Thanks for the video by the way.
Solving this with just one iteration is a good question otherwise the problem is trivial.
We can soulve this problem with O(n) passing through the list once and store in a hashmap with index. So having this map
[0:5,1:4,2:3,3:2,4:1]
Now just get val at key n.
In this case we go through the list once and we dont need to use a for loop
It will still be O(2n) because he is returning a node which means whatever you get from the hashmap you still have to iterate down the list so that you can return the node. Also, you used extra space.
@@kevinm4210 O(n) = O(2n)...
@@mbefokam4607 Still your solution is poor as you are using O(n) extra memory
Thanks for the video!
why not
public static int FromNth(int input, Node node){
Node Current = node;
//find length
int length = 0;
while(Current.next != null){
Current = Current.next;
length ++;
}
Current = node; //refresh
for(int i = 0; i < length - input ; i++){
Current = Current.next;
}
return Current.val;
}
like, am I mentally ill or ...
This is my solution, slightly different:
def count_next_to_n(root, x):
count = -1
while root != None:
if root.name == x:
count += 1
root = root.next
elif count >=0:
count += 1
root = root.next
else:
root = root.next
return count
Very good explanation. Thanks.
thanks!
The condition of the 'if loop' inside the 'for loop' should be changed to (curr.nextlink==null). In your example, the code will not work, when n=5 unless the above change is not made.
Can you explain your logic?
thanks for this awesome video!
Faaaaaaaaaannnnnntastic! Position n is counting backwards from 0 in this case. Assume no cycles too.
ajr m thanks!
very well explained... Muchas Gracias !
you're welcome :)
In this example, when n=10, it returns "NullPointerException" right? Do we need to handel that exeption, or it's ok to leave as it is?
what do you mean? he returns null in his implementation
oops, i miss that part earlier. Thanks tho
Awsome . But can you guide me how to think at the time of interview if we dont know the logic.
sometimes is not catch in mind? how you think like this
why in the first solution that you suggest, you can't use list.size() instead make two iterations?
i mean to calculate the len - n
@@ronmalka92 If I give you a Node, that node doesn't have a .size() function. In this case we're implementing the list ourself
i'm a noob but - we are assuming that the list has already been implemented, establishing the .next relationships?
Yes the input is a preexisting list
in the for loop, why not just do curr = curr[n] instead of iterating through the list n times?
Thanks!!
that works in Python, but look at how we are implementing our list
How does curr.next work?
It doesn't seem it would actually get the next Node.
Wouldn't you need an actual linkedlist and an iterator?
This seems like pseudocode.
Yeah, you can't even access it if it is private. It isn't really thought out.
Thank you
lol this is like a one liner in javascript
Do you have a video to do this with a double-linked list?
If you think about it, it's super straightforward with a doubly-linked list because you can just iterate backwards from the end
very useful
Why is it not return follower.value?
You tell me. What is our return type here?
Great!)
Are these solutions done in C++?
Java, but it's pretty similar
java
Integer ntToLast(Node node , int n) {
HashMap map = new HashMap();
Node current = node;
int index = 0;
while(current !=null) {
map.put(index, current.value);
index++;
current = current.next;
}
if (n> index-1)
return -1;
return map.get(n);
}
Hello,
I am a cab driver I may need lot of fuel to heat up.
Why not return integer and put this code in the second loop.
int nToEnd =0
while (curr.next!=null){
nToEnd++;
curr=curr.next;}
return nToEnd;
The one I bombed
:(
Byte By Byte just couldn’t think with them there, if I was doing it at home, I feel like I would’ve got it with time.
Definitely do some mock interviews. You want to get used to that before you walk into your interview
this should have been a 5min video
In case anyone is interested in Leetcode solution in Swift, for removing Nth node from end of Linked List and returning the head of the updated list:
func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
guard head?.next != nil else {
return nil
}
var curr = head
var prevN = head
for i in 0..