Find the maximum difference in an unsorted array with the index of max greater than min. array cant be sorted

Question

Anonymous · Accepted Answer

This should do in single pass O(N), with min value being always before the max:

int max_dist(const vector& data, size_t& start, size_t& 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] > data[end] - data[start])
            {
                // found new biggest distance
                start = min;
                end = max;
            }
        }
    }
    return data[end] - data[start];
}

candidate · Answer

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 >= 0; --i) {
  if(curMax > a[i])
    diff = max(diff, curMax - a[i])
  curMax = max(curMax, a[i])
}
// curMax will have max diff

Anonymous · Answer

It could have been solved by traversing the array, maintaining min , its index and max and its index (maxindex > 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.

Theja · Answer

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 < input.length-1; i++){
            if(input[i] < input[i+1]){
                int temp = input[i];
                input[i] = input[i+1];
                input[i+1] = temp;
            }
        }
       return input[input.length-1];
    }
}

anonymously · Answer

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

Anonymous · Answer

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.

Himanshu Verma · Answer

#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
", dist);
                        continue;
                }
                if(array[i] < array[min])
                {
                        min=i;
                }
        }
        printf("dist= %d
", dist);
}

Bloomberg

Bloomberg Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches