Question Name: Deviation
Question Description: 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, and print the value on 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, 2^31 -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
1 2 3 4 5 6 7 8 9 10 11 12 | Input: v: 6, 9, 4, 7, 4, 1 d: 3 Output: 6 Explanation The sequences of length 3 are: 6 9 4 has the deviation 5 (the minimum value in the sequence is 4 and the maximum is 9) 9 4 7 has the deviation 5 4 7 4 has the deviation 3 7 4 1 has the deviation 6 The maximum value among all deviations is 6<br> |
The solution is inspired by Codility’s Lesson 13: Caterpillar Method.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 | #---------------------------------------------------------------- # Author: Sheng Yu codesays.com # Written: 09/04/2014 # Last updated: 09/04/2014 # # Filename: deviation.py # Python Used: 2.7 #----------------------------------------------------------------- import random def deviation_caterpillars(input, sliceLen): ''' Find the max deviation in a caterpillars manner. Time complexity is O(N). @param input: an array of integers @param sliceLen: the length of computing slices. @return: the maximum deviation of all slices. ''' # Check the input. if len(input) == 0: return None if sliceLen == 0: return None if sliceLen == 1: return 0 if len(input) < sliceLen: return None # Each element in input will enter and exit these two array at most once. # A linked list might be better here, because there is no random access. # Anyway, we assume the operations on these two array being O(1). minInSlice = [] maxInSlice = [] # Read the first slice. for number in input[:sliceLen]: while len(minInSlice) != 0 and minInSlice[-1] > number: minInSlice.pop() minInSlice.append(number) while len(maxInSlice) != 0 and maxInSlice[-1] < number: maxInSlice.pop() maxInSlice.append(number) # Move the slice in a caterpillars manner. maxDeviation = maxInSlice[0] - minInSlice[0] for index in xrange(sliceLen, len(input)): # The new number to append to the current slice newNumber = input[index] # The number to be removed at the head of current slice removeNumber = input[index - sliceLen] if maxInSlice[0] == removeNumber: maxInSlice.remove(removeNumber) if minInSlice[0] == removeNumber: minInSlice.remove(removeNumber) while len(minInSlice) != 0 and minInSlice[-1] > newNumber: minInSlice.pop() minInSlice.append(newNumber) while len(maxInSlice) != 0 and maxInSlice[-1] < newNumber: maxInSlice.pop() maxInSlice.append(newNumber) # Update the deviation if needed. deviation = maxInSlice[0] - minInSlice[0] maxDeviation = max(maxDeviation, deviation) return maxDeviation def deviation_brute(input, sliceLen): ''' Find the max deviation with a brute force method. ''' if len(input) == 0: return None if sliceLen == 0: return None if sliceLen == 1: return 0 if len(input) < sliceLen: return None maxDeviation = input[0] - input[1] for start in xrange(len(input)-sliceLen+1): slice = input[start : start + sliceLen] sliceMax = max(slice) sliceMin = min(slice) deviation = sliceMax - sliceMin maxDeviation = max(maxDeviation, deviation) return maxDeviation def main(): TEST_COUNT = 1000 random.seed() for i in xrange(TEST_COUNT): test = random.sample(xrange(10000000), 1000) testlen = random.randint(2,50) if deviation_caterpillars(test, testlen) == deviation_brute(test, testlen): print "Test Case #" + str(i) + ": PASS." else: print "Test Case #" + str(i) + ": FAIL!" if __name__ == "__main__": main() |