HELLO, I’M SERHAT AND THIS IS MY FANCY TITLE.

Max Common Array Slice with Ruby

Question: We need a program which takes a comma delimited array of numbers from STDIN and will output the maximum slice of the array which contains no more than two different numbers. Your result should be written to STDOUT.

Example 1:

[1, 1, 1, 2, 2, 2, 1, 1, 2, 2, 6, 2, 1, 8] = 10 because the array slice of (0, 9) is the largest slice of the array with no more than two different numbers.

Example 2:

[53, 800, 0, 0, 0, 356, 8988, 1, 1] = 4 because the slice of (1, 4) is the largest slice of the array with no more than two different numbers. The slice (2, 5) would also be valid and would still give a result of 4.

'Max common array slice' (also known as Maximum sub-array problem) is a classical programming test question requiring some knowledge of O(n2) or O(n3). It is often asked in technical interviews in two different ways; a) maximum sum of array elements with no more than two different numbers, b) maximum length of array elements with no more than two different numbers. You can see more about Max Common Array Slice on Codility and Wikipedia.

Most of the solutions for this problem is complex as hell. So I just tried to follow a more simple, and humanistic approach. Here is my small solution:

def subarray_length(arr)
  maximum = []
  n = 0

  while n < arr.length-1
    for i in n..arr.length-1
      if arr[n..i].uniq.count == 2
        maximum << arr[n..i].length
      end
    end
    n += 1
  end

  print maximum.max
end

Test cases:

subarray_length([1, 1, 1, 2, 2, 2, 1, 1, 2, 2, 6, 2, 1, 8]) # 10
subarray_length([53, 800, 0, 0, 0, 356, 8988, 1, 1]) # 4

I know this is not the best practice or the best solution, but it works and does the job only with 15 lines of code ;)

Cheers.


Share this post!


Blog Comments powered by Disqus.