News for hackers. Stuff that matters.
Re:Nth-to-Last Element in a Singly Linked List by cperciva on Sunday January 31, 2010 @01:54PM (#1090848)
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 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 by basman on Sunday January 31, 2010 @02:06PM (#1090876)
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 by cperciva on Sunday January 31, 2010 @02:29PM (#1090927)
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 by extension on Sunday January 31, 2010 @06:23PM (#1091311)
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 by cperciva on Sunday January 31, 2010 @06:37PM (#1091329)
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 by extension on Sunday January 31, 2010 @08:02PM (#1091474)
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 by caf on Sunday January 31, 2010 @08:35PM (#1091528)
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 by cperciva on Sunday January 31, 2010 @08:40PM (#1091537)
His "every k steps" operation doesn't dereference any pointers; 0 * N / k is indeed O(k).
Re:Nth-to-Last Element in a Singly Linked List by caf on Sunday January 31, 2010 @08:51PM (#1091564)
Fair enough, reading comprehension fail.
Re:Nth-to-Last Element in a Singly Linked List by DenisM on Sunday January 31, 2010 @02:11PM (#1090891)
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 by cperciva on Sunday January 31, 2010 @02:32PM (#1090934)
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 by rabidgnat on Monday February 01, 2010 @12:03AM (#1091828)
The way I thought of immediately uses 0 pointers:

  (defun nthFromEnd (lst n)
    (labels ((from-end-helper (lst n)
      (if (null lst)
        0
        (let ((ret (from-end-helper (cdr lst) n)))
          (if (eq ret n)
            (throw 'answer (car lst))
            (+ ret 1))))))
      (catch 'answer
        (when (from-end-helper lst n)
          nil))))

  CL-USER> (nthfromend '(1 2 3 4 5) 6)
  NIL
  CL-USER> (nthfromend '(1 2 3 4 5) 3)
  2
  CL-USER> (nthfromend '(1 2 3 4 5) 0)
  5
I didn't hammer it very hard so maybe I missed a case or two. The other obvious problem is that it's not tail recursive (nor very elegant in general)
Re:Nth-to-Last Element in a Singly Linked List by liamk on Sunday January 31, 2010 @11:05PM (#1091752)
What about going through the list once, put each node onto a stack, then pop n - 1 elements off the stack, and the nth last element will be on the top of the stack. Edit: uses too many pointers as cperciva points out below.
Re:Nth-to-Last Element in a Singly Linked List by cperciva on Sunday January 31, 2010 @11:17PM (#1091765)
That uses N additional memory locations, not 3.
Re:Nth-to-Last Element in a Singly Linked List by andrewcooke on Sunday January 31, 2010 @02:11PM (#1090889)
heh. thanks for that comment. i had to sit and think for a moment.
Re:Nth-to-Last Element in a Singly Linked List by raganwald on Sunday January 31, 2010 @03:43PM (#1091048)
The 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.

Re:Nth-to-Last Element in a Singly Linked List by boredguy8 on Monday February 01, 2010 @02:37AM (#1091986)
I just had that interview. I called it "guess the word" because it was a vocabulary nightmare. "What makes a good program?" "Not crashing is a good start!" They were not impressed.
Re:Nth-to-Last Element in a Singly Linked List by fexl on Monday February 01, 2010 @02:55PM (#1093284)
Naturally my first inclination is to write the thing in a completely self contained purely functional form, which I do below. I think this will be fairly efficient under lazy evaluation, since the bottom line is to count off the given number of positions from the front of the list, and then use the tail of that list to step through the original list.

Here's the whole thing starting from scratch:

  # Optional values (also known as the "Maybe" type) 
  #
  # The (absent) function represents a value that is absent.
  # The (present value) function represents a value that is present.

  \absent = (\absent\present absent)
  \present = (\value \absent\present present value)

  # Natural numbers. 
  #
  # The (zero) function represents the number 0.
  # The (succ n) function represents the number 1+n (the successor of n).
  #
  # A natural number is really just an optional predecessor,
  # so the constructors are just synonyms for the Maybe type.

  \zero=absent
  \succ=present

  # Lists.

  \null = (\null\cons null)
  \cons = (\head\tail \null\cons cons head tail)

  # Subtraction of natural numbers.  Computes z = x - y.
  #
  # Returns (present z) if x >= y.
  # Returns absent if x < y.

  \sub = (\x\y
    y
      (present x)       # y = zero
    \yp
      x
        absent          # y = (succ yp) and x = zero
        \xp sub xp yp   # y = (succ yp) and x = (succ xp)
    )

  # Compute the length of a list.

  \len = (\list list zero \head\tail succ (len tail))

  # Return the item at the position in the list, starting with 0.

  \item = (\list\pos
    list
    absent       # list = null
    \head\tail   # list = (cons head tail)
      pos
        (present head)     # pos = zero, item found
        \np item tail np   # pos = (succ np), keep looking
    )

  # Return the item at the position from the end of the list, starting with 0.

  \item_end = (\list\pos
    sub (len list) (succ pos)  # Subtract 1+pos from length of list
    absent    # that's out of bounds, no item found
    \new_pos item list new_pos   # look for item normally at new pos
    )
Re:Nth-to-Last Element in a Singly Linked List by bmalicoat on Sunday January 31, 2010 @02:19PM (#1090908)
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?
Re:Nth-to-Last Element in a Singly Linked List by trunnell on Sunday January 31, 2010 @04:18PM (#1091117)
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 by raganwald on Sunday January 31, 2010 @05:28PM (#1091236)
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 by goodgoblin on Sunday January 31, 2010 @09:04PM (#1091594)
One I got recently - and blanked on - write a function to generate all the permutations of a string. Recursion preferred.
Re:Nth-to-Last Element in a Singly Linked List by bshep on Sunday January 31, 2010 @10:44PM (#1091726)
Quick and Dirty(probably better ways to do it):

  def permute(string, prefix = ''):
        if len(string) == 1:
  		print prefix + string
  		return
  
        for x in range(0, len(string)):
  		new_prefix = prefix + string[x]
  		unused_chars = string[0:x] + string[x+1:]
  		permute(unused_chars, new_prefix)
Re:Nth-to-Last Element in a Singly Linked List by dodger1 on Monday February 01, 2010 @02:05AM (#1091950)
This same website has a solution for the permutation of a string. http://www.mytechinterviews.com/permutations-of-a-string
Re:Nth-to-Last Element in a Singly Linked List by machrider on Sunday January 31, 2010 @05:47PM (#1091263)
Alternatively, you could recognize that your data structure doesn't suit your needs, and use a doubly-linked list.
Re:Nth-to-Last Element in a Singly Linked List by cperciva on Sunday January 31, 2010 @06:39PM (#1091333)
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 by machrider on Sunday January 31, 2010 @07:58PM (#1091468)
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 by roundsquare on Monday February 01, 2010 @07:28AM (#1092231)
You're missing the point. With the question setup, you are supposed to assume that a doubly linked list is not possible, for whatever reason. Its meant to be an algorithm question, not a data structures question.