## iLabs Interview Question

Java Developers**Country:**India

**Interview Type:**Phone Interview

I can think of one option without involving sorting - space O(n) and time O(n log n)

Create a BST from the input array

Loop through the input array and find the next largest number in BST (n * log n) for search and update the input array

I'm assuming you're wanting to traverse the tree until you get to the value matching A[i] and then take its right child. However, once this BST starts to become imbalanced, you'll no longer have O(log n) for searching or inserting. This becomes apparent when the array is already in order.

I suspect you could make it keep balanced and do an in-order search for the next highest value.

Start from the end. Use a doubly linked list to hold a sorted copy of the elements visited so far. When search the doubly linked list, start from the middle. Complexity O(nlogn).

```
>use a stack
>read from right to left
push -1;
while ()
{
>read element
>pop stack untill we found large element or -1.Store large lement in an array.
>push element into stack
}
algorithm is O(N)
```

```
static void greNext(int []A){
int l=A.length;
int j=1;
Stack eleA=new Stack();
Stack index=new Stack();
eleA.push(A[0]);
index.push(0);
while(j<l){
while(!eleA.isEmpty() && A[j]>eleA.getTop()){
A[index.pop()]=A[j];
eleA.pop();
}
eleA.push(A[j]);
index.push(j);
j++;
}
if(j==l){
while(!index.isEmpty()){
A[index.pop()]=-1;
}
}
for(int a:A){
System.out.print(a+" ");
}
}
```

since there is no space restriction i will counting sort to get the elements present in the array and

#include <stdio.h>

#include<string.h>

#define range 500

int main()

{

int a[] = {40,50,11,32,55,68,75};

int b[sizeof(a)/sizeof(a[0])] ={-1,};

int c[range] ={-1,};

int i=0;

int flag =0;

int count =0;

int num=0;

memset(c,-1,range*4);

memset(b,-1,sizeof(a)/sizeof(a[0])*4);

for(i=0;i<(sizeof(a)/sizeof(a[0])) ; i++)

{

c[a[i]] =i;

}

for (i=0; count<(sizeof(a)/sizeof(a[0])); i++)

{

if(c[i] !=-1 && flag ==-1)

{

num =i;

flag =c[i];

printf("\nSearching element =%d index %d",num,flag);

}

else if(c[i] !=-1 && flag !=-1)

{

if(i > num)

{

int k=flag;

count++;

b[flag] = i;

num = i;

flag = c[i];

printf("\nmatch b[%d]=%d and next searching element =%d index =%d",k,i,num,flag);

}

}

}

printf("\nOriginal input\n");

printf("{ ");

for(i=0; i<sizeof(a)/sizeof(a[0]) ; i++)

{

printf("%d, ",a[i]);

}

printf(" }\n");

printf("\nNew Output\n");

printf("{ ");

for(i=0; i<sizeof(a)/sizeof(a[0]) ; i++)

{

printf("%d, ",b[i]);

}

printf(" }\n");

}

Maintain two stacks one for pushing the data while iterating the array and the other while reading and printing the data.

Start from right to left of array

If writing stack is empty push -1. If writing stacks top is greater than current element in the array then push the writing stacks top to the reading stack and current element of array to the writing stack. If it is not greater than starting poping elements from writing stack until the greatest value is found or the stack is empty. If stack is empty and greatest value not found. Push -1 in reading stack and push current element of array in writing stack.

Repeat this for all elements.

```
private void PrintRightLargest(int[] numbers)
{
Stack<int> writingStack = new Stack<int>();
Stack<int> readingStack = new Stack<int>();
for (int i = numbers.Length - 1; i >= 0; i--)
{
if (writingStack.Count == 0)
{
readingStack.Push(-1);
}
else
{
int stackTop = writingStack.Peek();
if (numbers[i] < stackTop)
{
readingStack.Push(stackTop);
writingStack.Push(numbers[i]);
}
else
{
writingStack.Pop();
if (writingStack.Count == 0)
{
readingStack.Push(-1);
}
else
{
stackTop = writingStack.Peek();
while (writingStack.Count != 0 || stackTop < numbers[i])
{
writingStack.Pop();
if (writingStack.Count > 0)
{
stackTop = writingStack.Peek();
}
}
if (stackTop > numbers[i])
{
readingStack.Push(stackTop);
}
else
{
readingStack.Push(-1);
}
}
}
}
writingStack.Push(numbers[i]);
}
while (readingStack.Count != 0)
{
Console.WriteLine(readingStack.Pop());
}
}
```

Javascript:

```
function generateArr(arr){
var result = [];
var point;
var i = 0;
var diff = 1;
while(result[result.length - 1] != -1){
if(!arr[i+diff]){
result.push(-1);
break;
}else {
if(arr[i+diff] - arr[i] > 0){
result.push(arr[i+diff]);
i = i + 1;
diff = 1
}else{
diff += 1;
}
}
}
return result
}
```

Java:

```
public static Integer[] solve(Integer[] array){
Stack<Integer> candidates = new Stack<Integer>();
if (array == null){return null;}
Integer[] solution = new Integer[array.length];
candidates.push(new Integer(-1));
for (int i=array.length-1;i>=0;i--){
while ((candidates.peek() != (-1)) && (candidates.peek()<array[i])){candidates.pop();}
solution[i] = candidates.peek();
candidates.push(array[i]);
}
return solution;
}
```

The solution above finds the next bigger element to the right of the current element. If the requirement was to find the next bigger element in the entire array then a possible solution is as follows:

1. Construct an array of points (element,input_array_index) from the input array.

2. Sort this array according to dictionary order.

3. Go over the sorted array and use the fields element and input_array_index of each sorted array element in order to build the solution array:

solution[sorted[current].input_array_index] = sorted[current+1].element

current iterates from 0 to input.length - 1.

The overall run-time complexity of this algorithm would be O(n log(n)).

It is not possible to improve this bound as doing so will imply that there is a comparison based sorting algorithm (it is possible sort the original input array using an algorithm which returns an array of the nearest next element in the entire array) which performs at a better bound than O(n log(n)). This is a contradiction to the theorem that says that every comparison based sorting algorithm is omega(n log(n)).

answer was asked within last week

- mike tyson November 01, 2013click next once or twice on main careercup page