Difficult to answer in short and first time attempt.

Question

KL · Accepted Answer

Its a forward difference, so you track the smallest number before your current number then you can get the biggest difference with the current number as the subtractor. If it means subtractor must be in earlier position than subtractee, reverse the algorithm.
int min = array[0];
int max = Integer.MIN_VALUE;
for (int i = 1; i  < len; i++){
  max = Math.max(max, array[i] - min);
  min = Math.min(min, array[i]);
}
return max;

KL · Answer

by the way, the above solution is O(n) complexity, and O(1) auxiliary space

Anonymous · Answer

^O(nlogn)

ZW · Answer

If I understand the question correctly, you need to find the maximal difference between any two elements.

But note that this will always be the distance between the array's maximal element, and its minimal element - that is, (max(A) - min(A)) .

You can find the maximal element in O(n) , e.g.:
int maxVal = A[0];
for (int i=0; i maxVal) {
      maxVal = A[i];
      maxValID = i;
   }
}

So in total we've got O(n)+O(n)=O(n) .

Anonymous · Answer

If I understand the question correctly, a merge sort followed up by subtracting the last element with the first element should yield the desired max difference in O(log n)

Google

Google Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches