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.