gistfile1.rb

def find_deviation(v, d)
    max_dev = 0
    iterations = v.length - d + 1
    index = 0
    iterations.times do
      sub = v[index...index+d]
      sub_max_dev = sub.max - sub.min
      max_dev = sub_max_dev if sub_max_dev > max_dev
      index +=1
    end
    p max_dev
end

v = [6,9,4,7,4,1]
d = 3

find_deviation(v,d)

This is the challenge question as posed:

Given an array of integer elements and an integer d please consider all the sequences of d consecutive elements in the array. For each sequence we compute the difference between the maximum and the minimum value of the elements in that sequence and name it the deviation.

Your task is to

write a function that computes the maximum value among the deviations of all the sequences considered above
print the value the standard output (stdout)

Note that your function will receive the following arguments:

v
    which is the array of integers
d
    which is an integer value giving the length of the sequences

Data constraints

the array will contain up to 100,000 elements
all the elements in the array are integer numbers in the following range: [1, 231 -1]
the value of d will not exceed the length of the given array

Efficiency constraints

your function is expected to print the result in less than 2 seconds

Example
Input Output

v: 6, 9, 4, 7, 4, 1
d: 3

6

Explanation

The sequences of length 3 are:

6 9 4 having the median 5 (the minimum value in the sequence is 4 and the maximum is 9)
9 4 7 having the median 5 (the minimum value in the sequence is 4 and the maximum is 9)
7 4 1 having the median 6 (the minimum value in the sequence is 1 and the maximum is 7)
The maximum value among all medians is 6

one liner... not much to do lately...

def find_deviation(arr, d)
  arr.each_cons(d).inject(0) { |max_dev, slice| [max_dev, slice.minmax.reverse.reduce(:-)].max }
end

trying to make stuff fast instead of fancy..

The idea is to avoid calling min and max (iterating twice to find them) and using .minmax that would find both with only one iteration

the improvement is really insignificant for small d

I kept your logic this time

def find_deviation(v, d)
  max_dev = 0
  iterations = v.length - d + 1
  index = 0
  iterations.times do
    slice_minmax = v[index...index+d].minmax
    dev = slice_minmax[1] - slice_minmax[0]
    max_dev = max_dev < dev ? dev : max_dev

    index +=1
  end

  max_dev
end

I decided to tackle this since I haven't had much to do lately either, here's a comparison of the solutions proposed so far. My solution is similar to Thomas's.

However, I added an if statement to the loop that would check the last digit of each sub_array and only run the code inside the loop if the digit was greater than the last sub_max or less than the last sub_min.

I also tested it against an array of 100,000 random digits in range 1..231 and with d being a random integer in range 1..5000. The if statement seems to help the method loop through a lot faster once the array increases in size.

def find_deviation_thomas(v, d)
    max_dev = 0
    iterations = v.length - d + 1
    index = 0
    iterations.times do
      sub = v[index...index+d]
      sub_max_dev = sub.max - sub.min
      max_dev = sub_max_dev if sub_max_dev > max_dev
      index +=1
    end
    p max_dev
end


def find_deviation_bruno(v, d)
  max_dev = 0
  iterations = v.length - d + 1
  index = 0
  iterations.times do
    slice_minmax = v[index...index+d].minmax
    dev = slice_minmax[1] - slice_minmax[0]
    max_dev = max_dev < dev ? dev : max_dev

    index +=1
  end
  max_dev
end

def find_deviation_andy(v,d)
  max_dev = 0
  max = 0
  min = 0
  v.each_with_index do |n, i|
    last_num = v[i + d -1]
    if i == 0 || last_num == nil || last_num > max || last_num < min
      sub = v[i..i + d - 1]
      max = sub.max
      min = sub.min
      sub_max_dev = max - min
      max_dev = sub_max_dev if sub_max_dev > max_dev
    end
  end
  p max_dev
end

v = [6,9,4,7,4,1]
d = 3

test = []
100_000.times { test << rand(231) }
test_d = rand(5000)

require 'benchmark'

puts Benchmark.measure {find_deviation_thomas(v,3)}
puts Benchmark.measure {find_deviation_bruno(v,3)}
puts Benchmark.measure {find_deviation_andy(v,3)}


# puts Benchmark.measure {find_deviation_thomas(test, test_d)}
# puts Benchmark.measure {find_deviation_bruno(test, test_d)}
puts Benchmark.measure {find_deviation_andy(test, test_d)}

Andy's solution is by far the fastest. If you wanted to get even faster use a for loop vs an each (2x-4x faster).

def find_deviation_lionel(array, sequence_number)
  largest_difference = 0
  max = 0
  min = 0
  for i in 0..(array.length-sequence_number)
    last_num = array[i+(sequence_number-1)]
    if last_num == nil || i == 0 || last_num > max || last_num < min
      sub_array = array[i..(i+(sequence_number-1))]
      max = sub_array.max
      min = sub_array.min
      max_min_difference = max - min
      largest_difference = max_min_difference if max_min_difference > largest_difference
    end
  end
  p largest_difference
end

def find_deviation_andy(v,d)
  max_dev = 0
  max = 0
  min = 0
  v.each_with_index do |n, i|
    last_num = v[i + d -1]
    if i == 0 || last_num == nil || last_num > max || last_num < min
      sub = v[i..i + d - 1]
      max = sub.max
      min = sub.min
      sub_max_dev = max - min
      max_dev = sub_max_dev if sub_max_dev > max_dev
    end
  end
  p max_dev
end

test = []
100_000.times { test << rand(231) }
test_d = rand(5000)

require 'benchmark'

puts Benchmark.measure {find_deviation_andy(test, test_d)}
puts Benchmark.measure {find_deviation_lionel(test, test_d)}