Interview question: Remove all duplicate items from an array, fully

Here’s an interesting question to ask a candidate during interview. Given an array of items, return an array that doesn’t contain any of the duplicate repeating items.

Example:

Given [4, 5, 1, 5, 3, 2, 3, 6, 3], the output array should NOT contain the repeating elements 5 and 3. The output should only contain the remaining elements.

Note that I’m not saying the output should be this exact array [4, 1, 2, 6]. Rather the output should just have these elements and not the repeating elements. Order doesn’t matter.

Of course, mandating that the order should be preserved is next level on this question.

For now, I only have the solution that doesn’t maintain order.

Here’s the approach used. Lookahead and Lookbehind.

• Initialize an empty array result to hold the elements of the final result. The non-repeating elements.
• Sort the input array
• Iterate through the input array
• During each iteration
  • check if the current element is the same as the next element in the array. If so, skip the current iteration and the next iteration. Do it by adjusting the iteration pointer.
  • Also, check if the current element is the same as the previous element in the array. If so, skip the current iteration (only).
  • If the current element fails both the checks above, then, only then, add it to the result array
• Once all items are iterated, return the result array

Here’s the ruby code:

class NoDupe
  attr_accessor :input

  def process
    @input = @input.sort
    result = []
    i = 0

    loop do
      elem = @input[i]
      next_elem = @input[i + 1]
      prev_elem = @input[i - 1]
      break if elem.nil?
      if (elem == next_elem)
        i += 2
        next
      end
      if (elem == prev_elem)
        i += 1
        next
      end
      result << elem
      i += 1
    end

    result
  end

end

And here’s the testcase for it:

class NoDupeTest < MiniTest::Unit::TestCase
  def setup
    @obj = NoDupe.new
  end

  def test_success
    @obj.input = [1, 2, 3, 2, 4, 1]
    result = [3, 4]
    assert_equal result, @obj.process

    @obj.input = [1, 2, 3, 3]
    result = [1, 2]
    assert_equal result, @obj.process

    @obj.input = [1, 2, 3]
    result = [1, 2, 3]
    assert_equal result, @obj.process

    @obj.input = [1, 2, 3, 2, 3, 4, 5]
    result = [1, 4, 5]
    assert_equal result, @obj.process

    @obj.input = [4, 3, 5, 3, 5, 1, 5, 3, 2, 3, 6, 3]
    result = [1, 2, 4, 6]
    assert_equal result, @obj.process
  end
end

Improvements

This solution isn’t perfect. It doesn’t work if the input array has nil. It doesn’t preserve the order of elements in the output array, and it runs the loop more times that required. But it is O(n) in terms of time complexity. No nested iterations.

I’ll see if I can address these shortcomings when I get some time.