Remove duplicates from an unsorted Linked List in Ruby

Question

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] > 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] > 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

• Marc Rohloff: A minor thing, I would write previous_node.next = previous_node.next.next as previous_node.next = node.next

Answer 1

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

---

• Marc Rohloff: As you point out find_previous is a relatively expensive operation. I would add another local variable to track the previous node. i.e at the top of the function add previous = @head and at the end of the loop previous = node
• Marc Rohloff: Looking at that, you should only update previous if you didn't delete the node.
• dfhwze: @MarcRohloff that's how I would do it as well. But I'll leave it up to OP to come up with a similar solution :)
• Steven Aguilar: would using merge sort violate the no extra buffer condition? I think merge sort uses two arrays but not sure if their created in memory
• dfhwze: I believe it would breach that condition: geeksforgeeks.org/merge-sort.