dines - 1 year ago 64
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.

`arrA`
and
`arrB`
are arrays,
`rng`
is a range and
`wanted`
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}
end
``````

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
end
end

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

result = []

countA.each do |elem, count|
if count > 1 && countB[elem] > 1
result.push(elem)
end
end

result
end
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download