TestTask ruby

tt.rb

require 'benchmark'

ARRAY = (1..20_000).to_a.shuffle.first(10_000)

def solution_1(a)
  result, arr1, arr2 = 0, a, a

  arr1.each.with_index do |el, index|
    another_index = arr2.rindex(el).abs

    next if (index - another_index).abs < result

    result = (index - another_index).abs
  end

  result
end

def solution_2(a)
  max = 0

  indices = a.each_with_index.inject(Hash.new { Array.new }) do |hash, (obj, i)|
    hash[obj] += [i]
    hash
  end

  indices.select do |_, v|
    attempt = v.max - v.min
    max = attempt if max < attempt
  end

  max
end

# this one is O(N)
def solution_3(a)
  max = 0

  a.each_with_index.inject(Hash.new { Array.new }) do |hash, (el, index)|
    hash[el] += [index]

    els_diff = (hash[el].last - hash[el].first).abs

    if max < els_diff
      max = els_diff
    end

    hash
  end

  max
end

def solution_original(a)
  n = a.length
  result = 0

  for i in 0 .. (n - 1)
    for j in 0 .. (n - 1)
      if (a[i] == a[j])
        if (i - j).abs > result
          result = (i - j).abs
        end
      end
    end
  end

  return result
end

Benchmark.bm do |bm|
  puts "SOLUTION 1"
  bm.report do
    solution_1(ARRAY)
  end

  puts "SOLUTION 2"
  bm.report do
    solution_2(ARRAY)
  end

  puts "SOLUTION 3"
  bm.report do
    solution_3(ARRAY)
  end

  puts "SOLUTION original"
  bm.report do
    solution_original(ARRAY)
  end
end

# ➜  Desktop ruby tt.rb
#        user     system      total        real
# SOLUTION 1
#    0.320000   0.000000   0.320000 (  0.324191)
# SOLUTION 2
#    0.020000   0.000000   0.020000 (  0.017886)
# SOLUTION 3
#    0.010000   0.000000   0.010000 (  0.010939)
# SOLUTION original
#    9.650000   0.030000   9.680000 (  9.726582)