Hired.com - Deviation Solution

README.md

NAILED IT!

Hired requires applicants to solve 3 out of 5 coding problems. All solutions handle a series of inputs and are required to output the correct solution in < 2s.

I had a real problem with this, running only 3/6 inputs in the 2s timespan alloted, but I don't really understand why. Any ideas?

Also, see this gist by @matthewrudy which also attempts to solve this problem: https://gist.github.com/matthewrudy/8677812

Files

• TASK.md
• results.md
• solution.rb

results.md

Test Results

Test Format: :N_:D_:meth

• N: number of tests
• D: sequence length
• meth: the method used

Rehearsal ---------------------------------------------------
1_3_iterate       0.020000   0.000000   0.020000 (  0.017554)
1_3_each_cons     0.140000   0.000000   0.140000 (  0.140461)
10_3_iterate      0.170000   0.000000   0.170000 (  0.174595)
10_3_each_cons    1.440000   0.010000   1.450000 (  1.459643)
1_50_iterate      0.020000   0.000000   0.020000 (  0.021391)
1_50_each_cons    1.190000   0.010000   1.200000 (  1.275915)
1_100_iterate     0.020000   0.000000   0.020000 (  0.017701)
1_100_each_cons   1.570000   0.020000   1.590000 (  1.590823)
1_500_iterate     0.020000   0.000000   0.020000 (  0.014122)
1_500_each_cons   7.280000   0.080000   7.360000 (  7.366536)
----------------------------------------- total: 11.990000sec

                      user     system      total        real
1_3_iterate       0.020000   0.000000   0.020000 (  0.016613)
1_3_each_cons     0.140000   0.000000   0.140000 (  0.143865)
10_3_iterate      0.160000   0.000000   0.160000 (  0.160185)
10_3_each_cons    1.580000   0.010000   1.590000 (  1.658074)
1_50_iterate      0.010000   0.000000   0.010000 (  0.015919)
1_50_each_cons    0.870000   0.010000   0.880000 (  0.877879)
1_100_iterate     0.020000   0.000000   0.020000 (  0.015006)
1_100_each_cons   1.800000   0.020000   1.820000 (  1.865018)
1_500_iterate     0.020000   0.000000   0.020000 (  0.015679)
1_500_each_cons   8.180000   0.030000   8.210000 (  8.329684)

solution.rb

require 'benchmark'

def iterate(values, d)
  max = values[0]

  sequence = []
  (d-1).times { sequence << values.shift }

  while values.length > 0
    new_max = values.shift
    sequence << new_max

    if new_max > max
      dev = sequence[d-1] - sequence[0]
      max = dev if dev > max
    end

    sequence.shift
  end

  # puts max
end

def each_cons(values, d)
  values.each_cons(d).map {|g| g.max - g.min }.max
end

sample = (1..2**31)
samples = (1..100000).to_a.map { rand(sample) }

Benchmark.bmbm do |x|
  [[1,3], [10,3], [1,50], [1,100], [1,500]].each do |t|
    x.report("#{t[0]}_#{t[1]}_iterate") { t[0].times { iterate(samples.dup, t[1]) } }
    x.report("#{t[0]}_#{t[1]}_each_cons") { t[0].times { each_cons(samples.dup, t[1]) } }
  end
end

TASK.md

Challenge 1: Deviation

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:

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

Output:

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