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.
[4, 5, 1, 5, 3, 2, 3, 6, 3], the output array should NOT contain the repeating elements
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
resultto 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
- Once all items are iterated, return the
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
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.