Remove duplicates from an unsorted Linked List in Ruby Currently I'm going over the cracking the coding interview. I'm in the Linked List 2.1 question which is as follow:


  Remove Duplicates, write code to remove duplicates from an unsorted
  Linked List. How would you solve the problem if a temporary buffer is
  not allowed?


I used a Hash, which breaks the temporary buffer not allowed conditioned. Not sure how one can go about solving this without using an extra data structure. The above is the method I used.

# CTCI-2.1: Write code to remove duplicates from an unsorted LinkedList
  def remove_duplicates
    node = @head
    h = Hash.new(0)
    return false unless node.next
    h[@head.data] += 1
    while (node = node.next)
      h[node.data] += 1
      if h[node.data] &gt; 1
        previous_node = find_previous(node.data)
        previous_node.next = previous_node.next.next
      end
    end
  end


This is a \$O(n)\$. How can this be improved? How one will go about solving this without using an additional data structure(Temporary buffer?) Here is the rest of the Linked List:
require 'pry'

class Node
  attr_accessor :next
  attr_reader :data

  def initialize(data)
    @data = data
    @next = nil
  end

  def to_s
    "Node with value: #{data}"
  end
end

class LinkedList
  def initialize
    @head = nil
  end

  def append(value)
    if @head
      find_tale.next = Node.new(value)
    else
      @head = Node.new(value)
    end
  end

  def find_tale
    node = @head

    return node if !node.next
    return node if !node.next while (node = node.next)
  end

  def find(value)
    node = @head 

    return false if !node.next
    return node if node.data == value 

    while (node = node.next)
      return node if node.data == value
    end
  end

  def append_after(target, value)
    node = find(target)
    return unless node

    old_next = node.next
    node.next = Node.new(value)
    node.next.next = old_next
  end

  def find_previous(value)
    node = @head 

    return false if !node.next
    return node if node.next.data == value 

    while(node = node.next)
      return node if node.next.data == value
    end
  end

  def delete(value)
    if @head.data == value
      @head = @head.next
    end

    node = find_previous(value)
    node.next = node.next.next
  end

  def display
    node = @head

    puts node
    while (node = node.next)
      puts node
    end
  end

  # CTCI-2.1: Write code to remove duplicates from an unsorted LinkedList
  def remove_duplicates
    node = @head
    h = Hash.new(0)
    return false unless node.next
    h[@head.data] += 1
    while (node = node.next)
      h[node.data] += 1
      if h[node.data] &gt; 1
        previous_node = find_previous(node.data)
        previous_node.next = previous_node.next.next
      end
    end
  end
end


Here is the test I used:

# TEST 
list = LinkedList.new

list.append('A')
list.append('B')
list.append('A')
list.append('A')
list.append('C')
list.append('D')


puts "Display the list"

list.display

list.remove_duplicates
puts 'Answer should be A B C D'
list.display
Alternatives

There are other alternatives (spoiler alert) with around the same time complexity, that adhere to the specification of in-place removal.



Review


  This is in \$O(n)\$.


I'm not sure it is. The outer iteration while (node = node.next) is \$O(n)\$.


while (node = node.next)
  h[node.data] += 1
  if h[node.data] &gt; 1
    previous_node = find_previous(node.data)
    previous_node.next = previous_node.next.next
  end
end



And find_previous(data) is \$O(\log{n})\$.


 def find_previous(value)
    node = @head 

    return false if !node.next
    return node if node.next.data == value 

    while(node = node.next)
      return node if node.next.data == value
    end   
 end



This makes remove_duplicates to be \$O(n\log{n})\$. 

If you keep track of the previous node while iterating the nodes, you could optimize your algorithm to be \$O(n)\$, but as you are using a hash table, it fails to meet the requirements of the challenge.