iLabs Interview Question for Java Developers


Country: India
Interview Type: Phone Interview




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

answer was asked within last week
click next once or twice on main careercup page

- mike tyson November 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- siva November 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- nothing special here November 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

- Jim November 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry. Wrong answer. Heap sort first (nlgn), then loop through the array from the end and search the correct position in heap (n*lgn). So the complexity is nlgn.

- Jim November 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

>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)

- RAM November 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This would probably work if peek before you pop. If the current elem is less than your read-in elem, pop the stack. Not sure if you meant to be inclusive in your 'pop until' or not.

- nothing special here November 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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+" ");
		}
	}

- shashi_kr November 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- alok.net November 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Stupid Developer November 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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
}

- qbatyqi November 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- EulGam05 November 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)).

- EulGam05 November 07, 2013 | Flag


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