Baidu Interview Question
Financial Software DevelopersIf its an integer array, there is a possibility to use hash table equal to size of integer bounds. I cant think of any other method for that.
Call first element the pivot
Find largest number > pivot and to the right of array. Call it A. If you cannot find one A = pivot
Find smallest number < pivot and to the right of array. Call it B. If you cannot find one B = pivot
Ans : A-B
Sort the array O(nlg(n)). Then in O(n) time i.e. single pass, you can get the maximum distance.
Heapify the array - takes O(n). Then since every node satisfies the heap property (for instance, so that every parent > children) find the max difference between each parent and its 2 children (which represent neighboring numbers) - again O(n). Overall: O(n).
just use count sort
codeļ¼
#include <cstdio>
#include <cstdlib>
#include <memory.h>
using namespace std;
int csort(int key[], int len)
{
int *sort;
int max = key[0];
int min = key[0];
int step = 0;
int tmp = 0;
for(int i = 0; i < len; i++)
{
if(key[i] >= max)
max = key[i];
if(key[i] <= min)
min = key[i];
}
step = -min;
for(int i = 0; i < len; i++)
{
key[i] = key[i] + step;
}
sort = (int *)malloc((max - min + 1)*sizeof(int));
if(sort == NULL)
printf("malloc error\n");
memset((int *)sort, 0, (max - min + 1)*sizeof(int));
for(int i = 0; i < len; i++)
{
sort[key[i]] = 1;
}
for(int i = 1; i<max - min + 1; i++)
{
sort[i] += sort[i-1];
}
for(int i = 0; i < max - min + 1; i++)
{
if(sort[i] == tmp)
continue;
else
{
key[sort[i]-1] = i;
tmp = sort[i];
}
}
for(int i = 0; i < len; i++)
{
key[i] = key[i] - step;
}
free(sort);
sort = NULL;
return 0;
}
int count_max(int key[], int len)
{
int max = 0;
for(int i = 1; i < len; i++)
{
if((key[i] - key[i-1]) >= max)
max = key[i] - key[i-1];
}
return max;
}
int main()
{
int key[10] = {3,7,9,8,-22,6,22,11};
csort(key, 8);
for(int i = 0; i < 8; i++)
printf("%d ",key[i]);
printf("\n");
printf("The max distence is:%d\n",count_max(key,8));
}
Is there any method to find max distance neighboring number where the array is integer array in O(n)?
- If_else July 04, 2011