Nth-to-Last Element in a Singly Linked List
mytechinterviews.com
Nth-to-Last Element in a Singly Linked List
1–10 of 30 posts
Re: Nth-to-Last Element in a Singly Linked List
#2The author points out that a two-stage process consisting of 1. counting the number of elements in the list, and then 2. finding the right element, is quite inefficient -- but he then presents a different approach which uses two pointers instead of one, yet is equally inefficient -- almost every pointer is dereferenced twice.
Challenge: Show how, using three pointers, you can find the kth last element from a linked list of unknown length N with no more than N + O(k) pointer dereferences.
Re: Nth-to-Last Element in a Singly Linked List
#3The author points out that a two-stage process consisting of 1. counting the number of elements in the list, and then 2. finding the right element, is quite inefficient -- but he then presents a different approach which uses two pointers instead of one, yet is equally inefficient -- almost every pointer is dereferenced twice. Challenge: Show how, using three pointers, you can find the k th last element from a linked…
That's a neat one. My solution: pointers A, B, and C. A proceeds through the list. B is always at the largest multiple of k that is at or before A. C is at B-k. Every k steps, set C=B and B=A. When A reaches the end, step C forward B-A times.
Re: Nth-to-Last Element in a Singly Linked List
#4The author points out that a two-stage process consisting of 1. counting the number of elements in the list, and then 2. finding the right element, is quite inefficient -- but he then presents a different approach which uses two pointers instead of one, yet is equally inefficient -- almost every pointer is dereferenced twice. Challenge: Show how, using three pointers, you can find the k th last element from a linked…
heh. thanks for that comment. i had to sit and think for a moment.
Re: Nth-to-Last Element in a Singly Linked List
#5The author points out that a two-stage process consisting of 1. counting the number of elements in the list, and then 2. finding the right element, is quite inefficient -- but he then presents a different approach which uses two pointers instead of one, yet is equally inefficient -- almost every pointer is dereferenced twice. Challenge: Show how, using three pointers, you can find the k th last element from a linked…
It's not equally inefficient. The former will trash the CPU cache on large lists, whereas the latter will not if the k is small.
Re: Nth-to-Last Element in a Singly Linked List
#6The author points out that a two-stage process consisting of 1. counting the number of elements in the list, and then 2. finding the right element, is quite inefficient -- but he then presents a different approach which uses two pointers instead of one, yet is equally inefficient -- almost every pointer is dereferenced twice. Challenge: Show how, using three pointers, you can find the k th last element from a linked…
[deleted]
Re: Nth-to-Last Element in a Singly Linked List
#7As someone currently doing the technical interview tour, I really appreciate this link. Particularly that the author follows the general thought pattern of thinking of an inefficient way and then searching for better ways. Does anyone have any other favorite sites that have these types of questions with answers?
Re: Nth-to-Last Element in a Singly Linked List
#8The author points out that a two-stage process consisting of 1. counting the number of elements in the list, and then 2. finding the right element, is quite inefficient -- but he then presents a different approach which uses two pointers instead of one, yet is equally inefficient -- almost every pointer is dereferenced twice. Challenge: Show how, using three pointers, you can find the k th last element from a linked…
That's a neat one. My solution: pointers A, B, and C. A proceeds through the list. B is always at the largest multiple of k that is at or before A. C is at B-k. Every k steps, set C=B and B=A. When A reaches the end, step C forward B-A times.
Yep, that's it. I like this puzzle because while there are lots of examples where having 2 pointers is better than 1, it's the only (non-contrived) example I can think of where 1 point is just as good as 2, but 3 pointers is much better.
Re: Nth-to-Last Element in a Singly Linked List
#9The author points out that a two-stage process consisting of 1. counting the number of elements in the list, and then 2. finding the right element, is quite inefficient -- but he then presents a different approach which uses two pointers instead of one, yet is equally inefficient -- almost every pointer is dereferenced twice. Challenge: Show how, using three pointers, you can find the k th last element from a linked…
It's not equally inefficient. The former will trash the CPU cache on large lists, whereas the latter will not if the k is small.
True. But the author hadn't gotten to the point of counting operations yet, so I don't think he was trying to make a subtle point about memory hierarchies and non-constant access times. :-)
Re: Nth-to-Last Element in a Singly Linked List
#10The existence of posts like this really highlights the uselessness of "Guess the answer I'm looking for" interview questions. It turns them into "Did you take the trouble to scour the Internet for tech interview questions?"
That being said, if I ever have to interview another programmer who reads zero programming blogs or web sites... I am going to end it all and become a bike messenger.