Skip to content

Instantly share code, notes, and snippets.

@matthewrudy
Last active May 23, 2016 20:37
Show Gist options
  • Save matthewrudy/8677812 to your computer and use it in GitHub Desktop.
Save matthewrudy/8677812 to your computer and use it in GitHub Desktop.
Hired.com - can't finish fast enough
#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);
}
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

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
@Duffycola
Copy link

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

@cirosantilli
Copy link

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

@krutipandya
Copy link

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

@andrewsalveson
Copy link

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment