Thursday, February 6, 2014

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
o    which is the array of integers
·         d
o    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




package com.my.hired;

import java.util.Random;

public class MyClass {

 public static void main(String[] args) {
  Integer[] xx = new Integer[100000];
  Random generator = new Random();
  for (int i = 0; i < xx.length; i++) {

   xx[i] = generator.nextInt(100);

  }
  find_deviation(xx, 3);

 }

 public static void find_deviation(Integer[] v, Integer d) {
  long start = System.currentTimeMillis();
  int finalArrayCount = 0;
  for (int count = 0; count < v.length; count++) {
   int min = 2147483647;
   int max = 1;
   for (int j = count; j < count + d; j++) {

    if (count + d > v.length) {
     break;
    }
    if (v[j] > max) {
     max = v[j];
    }
    if (v[j] < min) {
     min = v[j];
    }

   }
   if (finalArrayCount < (max - min)) {
    finalArrayCount = max - min;
   }

  }
  System.out.println(finalArrayCount);
  System.out.println((System.currentTimeMillis() - start) / 1000);

 }
}

No comments: