IBM Interview Question
Software Engineer in TestsCountry: India
Interview Type: Written Test
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;
}
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.
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
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
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]
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
Isn't it a one loop of quick sort separated by zero?
- chenlc626 February 25, 2013