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.

Tags:

Updated: