Hired.com - can't finish fast enough

solution.c

#include <stdio.h>

void find_deviation(int *v, int v_length, int d) {
    int i;
    int j;
    
    int max_deviation = 0;
    int value;
    
    int min;
    int max;
  
    int n = v_length - d;
   
   for(i=0; i<= n;i++) {
     max = 0;
     min = 2147483647;
     for(j=0; j< d;j++) {
       value = v[i+j];
       if(value < min) {
           min = value;
       }
       if(value > max) {
           max = value;
       }
     }
     if((max-min)>max_deviation){
         max_deviation = max - min;
     }
   }
    printf("%d", max_deviation);
}

solution.rb

def find_deviation(array, sequence_length)
  array = array.dup

  sequence = []
  (sequence_length-1).times do
    sequence << array.shift
  end

  max = 0

  while array.length > 0
    sequence << array.shift
    dev = sequence.max - sequence.min

    if dev > max
      max = dev
    end
    sequence.shift
    
  end

  puts max
end

task.markdown

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

Was trying to figure this out in as well: https://gist.github.com/bschaeffer/503f6451823525965e42

Finally figured it out... instead of calculating each, and knowing all integers are positive, only calc the sequence if your newly shifted value is greater than your current max:

sequence << values.shift
if sequence[d-1] > max
  dev = sequence[d-1] - sequence.min
  max = dev if dev > max
end

Yes, well, the same holds for the minimum. The point is not to recompute when the min/max of the sequence don't change.

Doing this in Java I didn't even need the check, maybe because Java is faster than Ruby?

@cirosantilli you did the same way in Java as suggested by Duffycola?

I can't help but think that a company hiring based on tests like these would be like a newspaper hiring a columnist based on how quickly they could solve the crossword.