Bloomberg L.P. Interview Question: Find the maximum difference i... | Glassdoor

## Interview Question

Software Engineer Interview

# Find the maximum difference in an unsorted array with the

index of max greater than min. array cant be sorted

1

It could have been solved by traversing the array, maintaining min , its index and max and its index (maxindex &gt; minindex) and returning difference.
I suggested a dynamic programming approach of storing the difference seen till now in a matrix..but I am not sure if it was correct.

Interview Candidate on Nov 28, 2014
1

This solution finds max element, min element in given array with time complexity of O(n). But I still didn't figure out how to use fact that index of max is greater than index of min

public class FindMaxMin{
public static void main(String[] args){
int[] a = {1,3,5,22,15,34,2,674,56};
int min = findMin(a);//O(n)
int max = findMax(a);//O(n)
System.out.println("Max is "+max);
System.out.println("Min is "+min);
System.out.println("Maximum difference is "+max - min);
}
public static int findMax(int[] input){
for(int i = 0; i input[i+1]){
int temp = input[i];
input[i] = input[i+1];
input[i+1] = temp;
}
}
return input[input.length-1];
}
public static int findMin(int[] input){
for(int i = 0; i &lt; input.length-1; i++){
if(input[i] &lt; input[i+1]){
int temp = input[i];
input[i] = input[i+1];
input[i+1] = temp;
}
}
return input[input.length-1];
}
}

Theja on Dec 1, 2014
3

This should do in single pass O(N), with min value being always before the max:

int max_dist(const vector&amp; data, size_t&amp; start, size_t&amp; end)
{
size_t min = 0;
size_t max = 0;
start = end = 0;
if (data.size() == 0)
{
return 0;
}
for (size_t i = 1; i data[max])
{
max = i;
if (data[max] - data[min] &gt; data[end] - data[start])
{
// found new biggest distance
start = min;
end = max;
}
}
}
return data[end] - data[start];
}

Anonymous on Dec 4, 2014
0

#include
#include
int main()
{
int array[]={0,4,6,89,1,5,333,35,67,9,888};
int min=0;
int max=1;
int dist=array[1]-array[0];
int i;
for(i=2; iarray[max])
{
max=i;
if(dist min)
dist=array[max]-array[min];
// printf(" dist is %d\n", dist);
continue;
}
if(array[i] &lt; array[min])
{
min=i;
}
}
printf("dist= %d\n", dist);
}

Himanshu Verma on Dec 11, 2014
1

you can do it by traversing the array from the end in a single pass
int diff = 0;
int curMax = a[a.length-1];
for(int i = a.length - 2; i &gt;= 0; --i) {
if(curMax &gt; a[i])
diff = max(diff, curMax - a[i])
curMax = max(curMax, a[i])
}
// curMax will have max diff

candidate on Dec 17, 2014
0

for(i = length; i &gt;= 0; i--){
for(j = i-1; j &gt;= 0; j--){
if((a[i] - a[j]) &gt; diff ){
diff = a[i] - a[j];
max = i; min = j;
}
}
}
if(diff &gt; 0){
printf("diff: %d, max: a[%d]=%d min: a[%d]=%d", diff, max, a[max], min, a[min]);
}

anonymously on Dec 29, 2014
6

Anonymous on Jan 15, 2015
0

Don't you think it is maximum sum sub-array problem? E.g.: One person already mentioned:
Buy and Sell stocks. You can't sell before you buy. The buying cost must be smaller than selling price.

Anonymous on Mar 3, 2015
0

http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

Anonymous on Mar 3, 2015