## IBM Interview Question for Software Engineer in Tests

Country: India
Interview Type: Written Test

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

Isn't it a one loop of quick sort separated by zero?

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

yea

``````void sortN( int * x, int N ) {
int i = 0;
int j = N-1;
int pivot = 0;

while( i <= j )
{
while ( x[i] < pivot && i  < N ) i++;
while ( x[j] >= pivot && j >= 0) j--;
if ( i < j ) swap( x[i], x[j] );
}
}

void swap( int & x, int &y ){
int temp = x;
x = y;
y = temp;
}``````

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

QuickSort wont work because it'll take O(NlgN) time.

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

We are not running whole quick sort but an iteration of it. Actually doing partition of the array using a virtual 0 partitionIndex, so it should be O(n)

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

The dynamically created array is language dependent and seems targeted towards knowledge of C/C++.
Apart from that the algorithm seems fairly simple.
Set current_index as 0.
Now run through the array looking for negative numbers.
If a negative number is found, swap it with number at location current_index and increment current_index by 1

A sample run through (taking integers only for simplicity)
input 1 -4 -2 3 4 6 -3 -4 6
-4 1 -2 3 4 6 -3 -4 6 (swapped 1 and -4)
-4 -2 1 3 4 6 -3 -4 6 (swapped 1 and -2)
-4 -2 -3 3 4 6 1 -4 6 (swapped 1 and -3)
-4 -2 -3 -4 4 6 1 3 6 (swapped 3 and -4)

Should work with 0 too.

Also need separate code for menu creation and random array creation.

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

Partition the array around 0 if it is present. Else, add a 0 in the array and then partition.

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

``````int i = 0;
int j = 0;
for (j = 0; j < N; j++)
{
if (arr[j] < 0)
{
swap(i, j);
i++;
}
}``````

this makes the output semi-correct :-5 -8 -20 -100 -51 10 30 0 100 21
There will be max two more passes to put the 0 in the right position if it exists

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

Where should zero be?
The question only mentions to put negative before positive?

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

I am not sure...but this can be done in one pass: see below example

-1, 4, 6, 7, -9, 5, - 3, -4, -7, 8, -6

one variable will store the index of first positive number in the list

if index is a variable:
-1, 4, 6, 7, -9, 5, - 3, -4, -7, 8, -6
while traversing index = 4
as soon as we encounter a negative number we swap it with index and make index ++
we can do index ++ because there is two possibilities of a number next to index number either number is -ve: then in the pass we must have swapped it with +ve number in that case also index++
or number is +ve: then we find the -ve number and swap it with that number and still index ++

-1, 4, 6, 7, -9, 5, - 3, -4, -7, 8, -6
index =1
in for loop now we encounter -9 then swap it with 4 and index++
-1 -9 6 7 4 5 -3 -4 -7 8 -6
index = 2 now we encounter -3 the swap it with 6 and index++
-1 -9 -3 7 4 5 6 -4 -7 8 6
index = 3 now we encounter -4 then swap it with 7 and index++
-1 -9 -3 -4 4 5 6 7 -7 8 6
index=4 now we encounter -7 then swap it with 4
-1 -9 -3 -4 -7 5 6 7 4 8 6
now till the end we did not encounter any -ve number so this is it

I hope we need not the list to be sorted!!

please correct me if i am doing wrong somewhere

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

Yeah you are not wrong... but we need complexity O(N),
in your code for every (next) positive number you encounter, you have to look for a negative number to swap it with... the complexity doesnt remain linear anymore...
Sorry if i m wrong

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

1. Create two index i =0, j = N-1
2. do while ( i<=j)

2.1 Increment i while array[i] < 0
2.2 decrement j while array[j] >=0
2.3 swap i and j
3. end while

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

``````var arr = [-1, 4, 6, 7, -9, 5, -3, -4, -7, 8, -6];
console.log(arr);
for(var i = 0,j = arr.length;i < j;i++){
if(arr[i] >= 0){
var last = arr[j];
if(last < 0){
arr[j] = arr[i];
arr[i] = last;
console.log(arr);
}else{
i--;
}
j--;
}
}
console.log(arr);``````

[-1, 4, 6, 7, -9, 5, -3, -4, -7, 8, -6]
[-1, -6, 6, 7, -9, 5, -3, -4, -7, 8, 4]
[-1, -6, -7, 7, -9, 5, -3, -4, 6, 8, 4]
[-1, -6, -7, -4, -9, 5, -3, 7, 6, 8, 4]
[-1, -6, -7, -4, -9, -3, 5, 7, 6, 8, 4]

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

``````we can try like this.Please comment me if I am wrong,
first check number of -ve numbers(1 pass).say x.take two indices one from 0 another from x.check a[0] and a[x].
case 0: + and - ---> swap them and move both indices one step ahead
case 1: - and - --->move the first index till a + is found and swap them and then move both one step ahead
case 2: + and - viceversa of case 2``````

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

``````int []A={5,4,9,-1,-3};
int j=A.length-1;
for(int i=0;i<A.length;i++)
{
if(A[i]>0){
while(i<=j && j>=0)
{
if(A[j]<0){//swap(A[i],A[j]);
int temp=A[i];
A[i]=A[j];
A[j]=temp;
break;
}
else
j--;
}
}//end if
}``````

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.

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