Hunan Asset Interview Question
Country: China
Interview Type: Phone Interview
Got the solution...
1. Find the min and max: takes O(n)
2. Divide the interval between min and max into n-1 buckets of equal size (note that we are dividing the interval instead of the array): takes O(n)
3. For each of the remaining n-2 numbers, determine which buckets it belongs to: takes O(n)
4. For each bucket, compute the min and max in this bucket (if the bucket is empty return empty; if the bucket only has one number, min = max): takes O(n)
5. Since there are n-1 buckets and n-2 numbers: there must be one empty bucket. That indicates that the maximum gap must be at least the length of the bucket. We don't need to compare the gap between any numbers in the same bucket.
6. So all we need to do is to compare the inter-bucket distance and find the maximum one. That takes at most O(n).
In total the time complexity is O(n)
The solution can also be found by google "Maximum-Gap-Problem"
First you need to get maximum value of the array and after that allocate array of this size and loop over it to find maximum difference
//code in C#
int GetMax(int[] arr)
{
int max = 0;
for(int i=0;i< arr.Length;i++)
{
if(max < arr[i])
{
max = arr[i];
}
}
int []rank = new int[max+1];
for(int i=0;i < arr.Length;i++)
{
rank[arr[i]] = arr[i];
}
int maxDiff = 0;
int first = 0;
int diff = 0;
for(int i=0;i < rank.Length;i++)
{
if(rank[i] != 0)
{
diff = rank[i] - first;
if(diff > maxDiff)
{
maxDiff = diff;
}
first = rank[i];
}
}
return maxDiff;
}
To be more considerate about space, the type of rank array can be bool/bit. Also the initial maxDiff should be from the first two available elements, to handle the case when all integers in the array are negative.
About negatives, actually this algo cannot handle it. The requirement should mention it.
It's possible to handle negative numbers with a modification of this approach. But the issue is that we assume that the range of numbers is small. Actually if the range of input numbers is d, the algo is O(n+d). If d is large, this could be huge complexity.
For a given array of length n , one can find Max element and 2nd Max Element in O(n) time.
The idea here is while traversing through the loop along with max and 2nd max element, keep track of their differences as well.
First solution, bitmap. Time complexity O(n), space complexity O(1).
Second solution, by bucket. Time complexity O(n), space complexity O(n).
Check my analysis: allenlipeng47.com/PersonalPage/index/view/199/nkey
Check my code on 2nd solution github: github.com/allenlipeng47/algorithm/blob/master/src/main/java/com/pli/project/algorithm/array/MaxGap.java
This is O(max(N)), so not quite right, but the only thing I could think of that doesn't require sorting.
int biggest_gap(vector<int> values) {
int maxVal = 0;
for (int i = 0; i < values.size(); i++) maxVal = max(maxVal, values[i]);
vector<bool> seen(maxVal, false);
for (int i = 0; i < values.size(); i++) seen[values[i]] = true;
int prev = -1;
int maxGap = 0;
for (int i = 0; i < maxVal; i++) {
if (!seen[i]) continue;
if (prev < 0) { prev = i; continue; }
maxGap = max(maxGap, i-prev);
prev = i;
}
return maxGap;
}
int max_diff(int *a, int arr_len) {
int i=0, j=1;
while(j<arr_len - 1) {
if((abs(a[i+1]-a[i])) > (abs(a[j+1]-a[j])))
j++;
else
i=j++;
}
return i;
}
#include<stdio.h>
int main(){
int a[]={2,1,1,-23,155,-50};
int size = sizeof(a)/sizeof(int);
int largestgap;
int firstno;
int i,nextno,templargestgap;
largestgap=a[0];
for(i=0;i<size-1;i++){
firstno=a[i];
nextno=a[i+1];
templargestgap=nextno-firstno;
if(templargestgap<0)
templargestgap = -(templargestgap);
if(largestgap<templargestgap){
largestgap=templargestgap;
}
}
printf("\n%d",largestgap);
return 0;
}
using counting sort it is possible ie in o(n)..............bt space complexity will be more
- Amresh September 30, 2012