Hunan Asset Interview Question


Country: China
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
1
of 3 vote

using counting sort it is possible ie in o(n)..............bt space complexity will be more

- Amresh September 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 vote

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"

- fenghaolw October 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Beautiful.

- chris October 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

superb solution

- sukusuku October 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 4 vote

Impossible to do it in O(n)..

- Anonymous September 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

There must exists a tricky method which does not require sorting

- Anonymous September 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 4 vote

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;

}

- calculator.fcis September 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

works ok..but not feasible if max in the array is very large number

- rkt September 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Xiang October 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

About negatives, actually this algo cannot handle it. The requirement should mention it.

- Xiang October 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous October 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this is a special case O(n). If the max value is close to the arr.length and if we have only positive values. In that private case we can also do count sort, index sort etc. all in O(n) time.
I do not think if there is a variant to do it O(n) in general case.

- GKalchev October 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- pradegup October 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

my mistake, this logic won't work.

- pradegup October 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use RadixSort to sort in O(n) and then search

- Anonymous October 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def maximumGap(A):
    # if array lenght is less than ,max_gap not possible
    if len(A) <  2:
        return 0
    # sorted method will take time near to linear.
    A=sorted(A)
    max_gap=A[1]-A[0]
    for i in range(2,len(A)):
        max_gap=max(max_gap,A[i]-A[i-1])
    return max_gap

- Badal gupta August 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- allen.lipeng47 November 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

using counting sort it is possible ie in o(n)..............bt space complexity will be more

- Amresh September 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Martin September 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

int i=0, j=1

- Anand October 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- anand October 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

incorrect.

- Anonymous October 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Amarkant October 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

it take O(n) time to execute.....and no hashing.....enjoy.....!!!

- Amarkant October 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Check the problem again... you need to find the maximum gap for a sorted array in O(n)

- Anonymous October 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Impossible to do it in O(n)..

- Prashant September 30, 2012 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More