dines dines - 4 months ago 18
Ruby Question

Advice needed with optimization when solving Kata's

I'm doing Katas at codewars and I on occasion pass all the tests but fail due to timeout reasons. Could you please help with comments on how to improve my code by refactoring the code below.

are arrays,
is a range and
is either "odd" or "even". I need to return an array that holds numbers that exists more than once in each array, and is within the range and is either odd or even.

def find_arr(arrA, arrB, rng, wanted)
common = arrA && arrB

range = (rng[0]..rng[1]).to_a.select {|num| common.include?(num)}

range_wanted = range.select {|num| wanted == "odd" ? num.odd? : num.even?}

numbers_twice = range_wanted.select {|num| arrA.count(num) > 1 && arrB.count(num) > 1}


There is a lot of issues here, mainly time complexity is O(n^2) because of the last line which counts number occurrences in both arrays. For each number in range_wanted it needs to iterate over all elements of both arrays. This is highly inefficient.

Try to run your code in irb with those arguments find_arr([], [], [1, 10_000_000], "odd") or bigger range.

Here are some suggestions how to improve this code:

  1. Count occurrences yourself by storing them in a hash
  2. When counting you can skip those numbers that don't meet requirements, range and odd/even
  3. If you want to check if value is in a range, you should use cover? method from Range class. Do not change range into array and iterate over it.
  4. In this line range_wanted = range.select {|num| wanted == "odd" ? num.odd? : num.even?} you are testing wanted == "odd" in every iteration, but this won't ever change as it is passed as argument. You can move this condition outside of loop

Here is refactored code. I wrote it out of my head, so there may be some issues but it should give you an idea on how to write your own solution.

def find_arr(arrA, arrB, rng, wanted)
  countA = Hash.new(0)
  countB = Hash.new(0)

  # If wanted == "odd" we want to test elem % 2 == 1, otherwise elem % 2 == 0
  remainder = wanted == "odd" ? 1 : 0
  range = (rng[0]..rng[1])

  arrA.each do |elem|
    if range.cover?(elem) && (elem % 2 == remainder)
      countA[elem] += 1

  arrB.each do |elem|
    if range.cover?(elem) && (elem % 2 == remainder)
      countB[elem] += 1

  result = []

  countA.each do |elem, count|
    if count > 1 && countB[elem] > 1