Coding for interviews: LinkedLists and Ruby

linkedlists.rb

################
# Tasks 
################
# 1. A linked list is just a collection of linked nodes. 
# Each node is linked to another node, which we call "next" in a singly linked list.
# In a doubly linked list, each node is linked to a "previous" and "next" node. 
# These are the constraints that define our collection of nodes as a linked list.

# Extra! : http://softwarecake.com/post/29053008425/what-is-a-linked-list :) best description ever.

# 2. No need for much more than this: (ruby)

Node = Struct.new(:next, :value)

class LinkedList
  attr_reader :head

  def initialize(value)
    @head = Node.new(nil, value)
  end

  def search(value)
    current = @head
    while (!current.next.nil?) 
      return current if current.value == value
    end
    nil
  end
  
  def insert(value)
    old_head = @head
    @head = Node.new(old_head, value)
  end

  def delete_node(node)
    previous_to_node = @head
    while (!previous_to_node.next.nil?) 
      if previous_to_node.next == node
        old_node = node
        previous_to_node.next = node.next.next
        return old_node
      end
    end
    
    nil
  end

  def delete(value)
    node_to_delete = search(value)
    delete_node(node_to_delete)
  end

end

################
# Interview questions using linkedlist implementation above
################
################
# 1.
################
# Generalizing this question is far more fun :)
# I use two pointers, separate them by K nodes, so when
# the one that is on the 'right' reaches the end of the list,
# first pointer is kth to last element

def remove_kth_from_last(list, k)
  return if k <= 0
  
  p1 = list.head
  p2 = list.head

  0.upto(k - 1) do 
    return if p2.nil? #list is too short 
    p2 = p2.next
  end

  return if p2.nil?

  while !p2.next.nil?
    p1 = p1.next
    p2 = p2.next
  end

  node_to_delete = p1

  list.delete_node(node_to_delete)
end   


###########################
# 2. 
###########################

# Put all the elements in a hash where key is the element, value is the 
# number of duplicates found. Then run delete(element) as many times
# as necessary per entry found so that no duplicates remain in the list.
#
# Can you do it without storing extra data? 
# Yes. Problem is it would take n squared, since I would be checking 
# every single element against the remaining elements, 
# and that is very inefficient.
# Another (more efficient) approach is to order the linkedlist first,
# then check every node against its "next" and that way detecting dups
# is easy and fast, but then again, most sorting algorithms require
# storing extra data temporarily.

def remove_duplicates(list)
  duplicates_hash = find_duplicates(list)

  duplicates_hash.each do |value, repetitions|
    1.upto(repetitions - 1) { list.delete(value) }
  end
  
  list
end

def find_duplicates(list)
  hash = Hash.new(0)
  current = list.head

  while (!current.nil?)
    hash[current.value] += 1
    current = current.next
  end

  hash
end