Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Nth-to-Last Element in a Singly Linked List

mytechinterviews.com

Post reply on HN
Print view View original

11–20 of 30 posts

Re: Nth-to-Last Element in a Singly Linked List

#11

Post by trunnell »

bmalicoat wrote: post #7

As 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?

It's not a website, but _Programming Pearls_ by Jon Bentley is still an excellent way of getting into an algorithms frame of mind. Don't be dissuaded just because it's a few years old. I like the way it presents the thought process of solving the given problems.

Re: Nth-to-Last Element in a Singly Linked List

#12

Post by raganwald »

bmalicoat wrote: post #7

As 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?

A little long in the tooth, and mostly MSFT-style "brain teasers:" http://www.techinterview.org/index.html

Re: Nth-to-Last Element in a Singly Linked List

#14

Post by extension »

basman wrote: post #3
cperciva wrote: post #2

The 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.

Neato.

If reference locality is a big concern and k is small, the following might perform better: allocate a ring buffer of size k+1 (ideally on the stack), enqueue the pointers as you go, when you hit the end, return the tail of the buffer.

Among other things, this problem well illustrates how the rules of optimization can vary wildly depending on low level architecture.

Re: Nth-to-Last Element in a Singly Linked List

#15

Post by cperciva »

extension wrote: post #14
basman wrote: post #3

Earlier quoted context omitted.

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.

Neato. If reference locality is a big concern and k is small, the following might perform better: allocate a ring buffer of size k+1 (ideally on the stack), enqueue the pointers as you go, when you hit the end, return the tail of the buffer. Among other things, this problem well illustrates how the rules of optimization can vary wildly depending on low level architecture.

That doesn't help significantly, since you only save the final O(k) dereferences. The situation (small k) where it's practical to allocate a ring buffer like this is exactly the situation where it isn't useful.

Re: Nth-to-Last Element in a Singly Linked List

#16

Post by cperciva »

machrider wrote: post #13

Alternatively, you could recognize that your data structure doesn't suit your needs, and use a doubly-linked list.

There are many situations where the cost of using a more sophisticated data structure outweighs the advantages of avoiding an occasional excessively slow operation.

Re: Nth-to-Last Element in a Singly Linked List

#17

Post by machrider »

cperciva wrote: post #16
machrider wrote: post #13

Alternatively, you could recognize that your data structure doesn't suit your needs, and use a doubly-linked list.

There are many situations where the cost of using a more sophisticated data structure outweighs the advantages of avoiding an occasional excessively slow operation.

We don't have enough information to know which situation this is. Hence, it's an "alternative" to consider.

Re: Nth-to-Last Element in a Singly Linked List

#18

Post by extension »

cperciva wrote: post #15
extension wrote: post #14

Earlier quoted context omitted.

Neato. If reference locality is a big concern and k is small, the following might perform better: allocate a ring buffer of size k+1 (ideally on the stack), enqueue the pointers as you go, when you hit the end, return the tail of the buffer. Among other things, this problem well illustrates how the rules of optimization can vary wildly depending on low level architecture.

That doesn't help significantly, since you only save the final O(k) dereferences. The situation (small k ) where it's practical to allocate a ring buffer like this is exactly the situation where it isn't useful.

Actually, you're right, it's the larger values of k where this might make a difference. If the list items are scattered in memory, the cost of the buffer increases very slowly with k compared to the cost of hitting those extra k/2 items.

Re: Nth-to-Last Element in a Singly Linked List

#19

Post by caf »

basman wrote: post #3
cperciva wrote: post #2

The 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.

Your "every k steps" operation executes N / k times, which isn't O(k) so I don't think it meets the requirements given.

Re: Nth-to-Last Element in a Singly Linked List

#20

Post by cperciva »

caf wrote: post #19
basman wrote: post #3

Earlier quoted context omitted.

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.

Your "every k steps" operation executes N / k times, which isn't O(k) so I don't think it meets the requirements given.

His "every k steps" operation doesn't dereference any pointers; 0 * N / k is indeed O(k).
Post reply on HN