Directi Interview Question for Developer Program Engineers






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

void Array_Swap(int a[],int size){

	int diff = 0;
	int swap_index = 0;
	int j =0;
	for (int i = 0 ;i < (size-1) ;i++){		
		j = i + 1; 		
		//skip numbers until we get number smaller than a[i]
		while((a[i] - a[j++]) < 0);
		diff = a[i] - a[j-1];
		swap_index = j -1 ;
	
		//find the number which will have lowest postive difference with a[i] 
		// save that number`s index and swap it with a[i]
		for (;j < size -1 ; j++){
			 		 
			 if((a[i] - a[j]) > 0 && (a[i] - a[j]) < diff)
			 {
				diff = (a[i] - a[j]);
				swap_index = j;
			 }
		}
		swap(a[i] ,a[swap_index]);			
	}
	
}


int main( )
{	
	int a[] = {4,5,6,3,1};
	Array_Swap(a,5);
	for(int i = 0 ; i < 5; i++)
		cout << a[i] << endl;

	int a[] = {4,5,6,-3,-1};
	Array_Swap(a,5);
	for(int i = 0 ; i < 5; i++)
		cout << a[i] << endl;

	return 0;
	
}

- sachin323 October 06, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

First step in Bubble sort

- chennavarri October 06, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

it is just like selection sort with not considering present element.....

- Just October 09, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

there is an O(n) solution to it :p

- Aditya October 17, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hey Aditya,

Post the solution, if you know.

Cheers,
Mike

- Mike D'Souza February 10, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hey please post the idea of your O(n) solution.

Thanks

- Pulkit July 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

how can we do in O(n)

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

use the stack,it is like finding histograms.
O(n) solution

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

Does anyone know the O(n) sol ?

- Kirti December 28, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution using stack.

take a stack S

for example array A = {3,7,4,9,10,2,1}
Now algo:
1) Push the element in the stack if that element is greater than the top of the stack
as soon as this condition fails
2) pop the top of the element and put in solution array. Repeat step 2 till step 1 doesnt hold true.

The solution array will be 7,10,9,4,3,2,1 which is the required answere.

time O(n) ans space O(n)

- Rasmus January 24, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hey Rasmus,

Your solutions is incorrect. Read the Problem again.

The Output array should be : 2 4 3 7 9 1 10

Anyone with O(n) solution please come forward and post the solution.

Cheers,
Mike

- Mike D'Souza February 10, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) solution is simple. just think as finding longest increasing subsequence :P

- pankaj March 11, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

pankaj can u plz explain how is tht possible in O(n).....or the solution which u r thnkng of....

- amrit July 12, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Please post your O(n) solution

- anurag August 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The question is not very clear :-( there can be multiple outputs based on what you do after swapping. Increment i or start from i again.

O(n) solution can start from behind

consider 1 , 4, 7, 2, 5

for 5 smallest element on right is 5 so decrement counter
for 2 smallest element is 5 but compare it with smallest 2 < 5 so make smallest=2

so far nothing changes
1,4,7,2,5
for 7, smallest is 2 so swap.
1,4,2,7,5 smallest is still 2.
for 4, smallest is 2 so swap
1,2,4,7,5
for 1 smallest is 2 but 2 < 1 so no change.

1,2,4,7,5

there can be some other solutions as well if question is better defined.

- Anonymous August 24, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Question is not so clear. What should be the exact output for 1,4,7,2,5 ?

- Nitish May 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Move from last node to first node while constructing a bst
for each element first search it in the BST....add element to Bst..also note the last right movement(this will be the req element) and replace a[i] by that..
worst case would be o(n^2) but if we use augmented trees it wud be O(nlogn)

- guneesh June 25, 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