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
Answer

Interview Answer

9 Answers

1

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.

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 < 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];
    }
}

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& 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];
}

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] < 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 >= 0; --i) {
  if(curMax > 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 >= 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]);
}

anonymously on Dec 29, 2014
6

https://oj.leetcode.com/problems/best-time-to-buy-and-sell-stock/

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

Add Answers or Comments

To comment on this, Sign In or Sign Up.