2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ A minor thing, I would write previous_node.next = previous_node.next.next as previous_node.next = node.next \$\endgroup\$ – Marc Rohloff Sep 16 at 16:18
2
\$\begingroup\$

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.


\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – Marc Rohloff Sep 16 at 16:14
  • 1
    \$\begingroup\$ Looking at that, you should only update previous if you didn't delete the node. \$\endgroup\$ – Marc Rohloff Sep 16 at 16:24
  • \$\begingroup\$ @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 :) \$\endgroup\$ – dfhwze Sep 16 at 16:27
  • \$\begingroup\$ 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 \$\endgroup\$ – Steven Aguilar Sep 27 at 15:12
  • \$\begingroup\$ I believe it would breach that condition: geeksforgeeks.org/merge-sort. \$\endgroup\$ – dfhwze Sep 27 at 15:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.