Algorithms - Prefix Sum

genomic_range_query.rb

# 100% - O(N + M) - https://app.codility.com/demo/results/trainingFZS58R-ENQ/
def solution(s, p, q)
  nucleotides = { "A" => 1, "C" => 2, "G" => 3, "T" => 4 }
  occurrences = { "A" => [0], "C" => [0], "G" => [0], "T" => [0] }
  
  1.upto(s.length).each do |index|
    nucleotides.keys.each do |nucleotide|
      previous = occurrences[nucleotide][index - 1]
      occurrences[nucleotide][index] = s[index - 1] == nucleotide ? previous + 1 : previous
    end
  end

  results = []

  p.length.times.map do |k|
    occurrences.each do |nucleotide, occurrence|
      if occurrence[p[k]] != occurrence[q[k] + 1]
        results << nucleotides[nucleotide]
        break
      end
    end
  end
  
  results
end

require 'minitest/autorun'

class Tests < MiniTest::Test
  def test_example_input
    assert_equal [2, 4, 1], solution('CAGCCTA', [2, 5, 0], [4, 5, 6])
  end
end

slice_sum.rb

# Reference: https://codility.com/media/train/3-PrefixSums.pdf
def solution(a, slices)
  p = [0]

  # Compute sums: [1, 2, 3, 4, 5, 6] => [0, 1, 3, 6, 10, 15, 21]
  (1..a.length).each do |k|
    p[k] = p[k - 1] + a[k - 1]
  end

  slices.map do |low, high|
    p[high + 1] - p[low] # p[high + 1] => "p" has one more element than "a" so querying it requires to fix the index.
                         # p[low]      => it needs to take the sum right before the low index to return the sums difference,
                         #                but since it's already one index ahead it doesn't require to make p[low - 1].
  end
end

require 'minitest/autorun'

class Tests < MiniTest::Test
  def test_example_input
    assert_equal solution([1, 2, 3, 4, 5, 6], [[0, 2] , [3, 5], [2, 4], [0, 0]]), [6, 15, 12, 1]
  end
end