Microsoft Interview Question Developer Program Engineers
Team: BING
Country: India
Interview Type: In-Person
No quick sort partition wont work. The above method is correct. Also, change
" if (A[i] < 0) posStartIndex++;"
to
"if (temp < 0) posStartIndex++; "
Took me a while to understand the solution. First of all, note that we have to preserve the relative order of the positive & negative numbers. Here's my understanding of the solution. Use a "posStartIndex" to mark the index of the first zero. As you traverse the array, if you encounter a number <= 0, then we want to inject it at the "posStartIndex". To do so, of course we need to first copy each element after the "posStartIndex" one to the right. Finally, if the number we are injecting is < 0, then we increment the "posStartIndex".
Several notes if my understanding is correct:
(1) posStartIndex throws me off because it sounds like the index of the first positive number, which zero isn't
(2) I think checking "A[i] < 0" at the end is a bug because by then A[i] isn't the number we are injecting anymore. Should use "temp" instead.
Given (1) & (2), I am not sure whether I understand his algorithm correctly.
We can solve this problem with two temporary arrays, one for positive elements and one for negative elements in O(n) time.
Scan the input array if you hit a negative element store it in the negative array, if its a positive element store it in the positive array.
In the end simply scan these two arrays and copy the elements back to our original array
void sort(int *input, int n)
{
int *negative = malloc(sizeof(int) * n);
int negativeIndex = 0;
int *positive = malloc(sizeof(int) * n);
int positiveIndex = 0;
int zero = 0;
int i, temp;
for (i = 0; i < n; i++)
{
if (intput[i] < 0)
negative[negativeIndex++] = intput[i];
else if (intput[i] > 0)
positive[positiveIndex++] = input[i]
else
zero++;
}
for (i = 0; i < negativeIndex; i++)
input[i] = negative[i]; /* copy negative elements */
for (temp = 0; temp < zero; temp++, i++)
input[i] = 0; /* copy zeroes */
for (temp = 0; temp < positiveIndex; temp++, i++)
input[i] = positive[temp]; /* copy the positive elements */
}
build a binary tree set 0 as root node and first negative number as left child and first positive number as right child, then for every negative number we get make it a right child to the leaf node of left subtree and similar for positive numbers in right subtree. then get the inorder of the tree.
array=(-2,0,2,-3,8,6,-7,-1,4)
0
-2 2
-3 8
-7 6
-1 4
inorder= -2,-3,-7,-1,0,2,8,6,4
Use counting sort. Just use a 3 element array for counting. 0 -> -ve numbers, 1 -> 0, 2->positive numbers
Prepare a binary tree structure with '0' as root , the first -ve number will be left child and first +ve number will be the right child of the root. Now parse through the array of elements to append all -ve numbers as right childs sequentially to the left tree. And add all the +ve number as right childs Sequentially to the right tree. Once the tree is prepared, read it in Inorder to get the answer
but this way, we would sort -ve and +ve numbers, where you are asked to preserve their original order
While preparing the tree dont sort the numbers. but maintain the order of -ve and +ve numbers by sequentially adding them as right childs in their respective left and right sub trees. The question itself is having restriction over the order of numbers..right?
If a separate data structure can be used as an aid, wouldn't it be simpler to create a second blank array and then parse the original array three times to copy first negative, then zero, then positive values? Technically it does more work than the binary tree, but it's still O(n) and would require much less testing.
#include<iostream.h>
#include<stdlib.h>
#include<conio.h>
class Queue{
int queue[20],front,rear;
public:
Queue() {
front=0;
rear=0;}
int get() {
if(front==rear) {
cout<<"Queue is empty";
getch();
exit(1); }
return(queue[front++]); }
void put(int a) {
if(rear==20) {
cout<<"Queue is Full";
getch();
exit(1); }
queue[rear++]=a; } };
void main(){
int A[20],i,j=0,n,k=0;
clrscr();
Queue q;
cout<<"Enter the number of terms :";
cin>>n;
for(i=0;i<n;i++)
cin>>A[i];
for(i=0;i<n;i++) {
if(A[i]==0)
k=1;
else if(A[i]>0)
q.put(A[i]);
else if(A[i]<0)
A[j++]=A[i]; }
if(k==1)
A[j++]=0;
for(;j<n;j++)
A[j]=q.get();
cout<<" The sorted list : "<<endl;
for(i=0;i<n;i++)
cout<<A[i]<<endl;
getch();}
Create a temporary index array which store the index values corresponding to the input
array. Now scan the array and place index corresponding to -ve numbers in the index array followed by +ve numbers. finally print the input array based on the index array.
Eg., input array = {-2,3 ,5, 0,-3, 7 -1}
index array after scanning -ve, 0, +ve numbers,
temp index array = { 0, 4, 6, 3, 1, 2, 5} => print input array[index array[i]] to the get the required sorted order list.
let given array be a[n], of size n. Take an array of same size b[n]
traverse a[n] and put all negative numbers as encountered
put 0
traverse again and put all positive numbers
int j=0;
for(int i=0; i<n; i++)
{
if (a[i] < n){
b[j++] = a[i];
}
}
b[j]=0;
for(int i=0; i<n; i++)
{
if (a[i] < n){
b[j++] = a[i];
}
}
NOTE: this is not applicable if no extra space is allowed
The following uses extra space, but running time in only O(n). Any comments?
private static int[] sortarrayintonegativezeropositive(int a[],int size){
int[] sorted=new int[size];
int[] positives=new int[size];
int[] negatives=new int[size];
int zerocount=0;
int positivecount=0;
int negativecount=0;
for(int i=0;i<size;i++){
if(a[i]==0)
zerocount++;
else if(a[i]>0){
positives[positivecount++]=a[i];
}
else{
negatives[negativecount++]=a[i];
}
}
int count=0;
for(int i=0;i<negativecount;i++){
sorted[count++]=negatives[i];
}
for(int i=0;i<zerocount;i++){
sorted[count++]=0;
}
for(int i=0;i<positivecount;i++){
sorted[count++]=positives[i];
}
return sorted;
}
for(int i = 0; i < _countof(iSrcArray); i++)
{
int iMinVal = iSrcArray[i];
for(int j = i; j < _countof(iSrcArray); j++)
{
if(iMinVal > iSrcArray[j])
{
iMinVal = iSrcArray[j];
iSrcArray[j] = iSrcArray[i];
iSrcArray[i] = iMinVal;
}
}
}
for(int i = 0; i < _countof(iSrcArray); i++)
{
if(i == 0)
printf("%s","[ ");
printf("%d ", iSrcArray[i]);
if(i == _countof(iSrcArray) -1)
printf("%s\n", "]");
}
system("Pause");
Using the idea of quick sort but with small tweak. In order to maintain the order, starting low pointer from 0th element and high pointer from index of element with value zero + 1. And doing normal partition of quicksort.
Code: this is not very elegant code but it works.
static void findPivot()
{
int low = 0;
int index = 3;
int high = index + 1;
int []input = { -2, 3, 5, 0, -3, 7, -1};
while(low < index && high < input.length)
{
while(input[low] < 0 && low < input.length)
low++;
while(high < input.length && input[high] > 0)
high++;
if(low < high && high <input.length)
{
int temp = input[low];
input[low] = input[high];
input[high] = temp;
}
}
for(int i =0; i < input.length; i++)
{
System.out.println(input[i]);
}
}
#include<iostream.h>
#include<conio.h>
void shift(int a[], int b[], int size)
{
int i;
int m=0;
for(i=0;i<size;i++)
{
if(a[i]<0)
{
b[m]=a[i];
m++;
}
else
continue;
}
for(int j=0;j<size;j++)
{
if(a[j]==0)
{
b[m]=a[j];
m++;
}
else
continue;
}
for(int k=0;k<size;k++)
{
if(a[k]>0)
{
b[m]=a[k];
m++;
}
else
continue;
}
cout<<"Copied array:"<<endl;
for(int r=0;r<size;r++)
{
cout<<b[r]<<" , ";
}
}
void main()
{
clrscr();
int arr1[20];
int arr2[20];
int s;
cout<<"Enter size of array: "<<endl;
cin>>s;
cout<<"enter elements: "<<endl;
for(int u=0;u<s;u++)
{
cin>>arr1[u];
}
shift(arr1,arr2,s);
getche();
}
this should be the simplest way
I guess, I have one solution which works on basis of merge sorting .
Only we need to change the merging procedure a little :
{{//L & R are two subarray
if(L[i]<=R[j]) A[k]=L[i]; i++;k++;
else
if(L[i]>R[j] && oppSigns(L[i],R[j])) A[k]=R[j];j++;k++;
else
A[k]=L[i]; i++;k++;
}}
oppSigns(a,b) is a function that determines whether the two numbers of one + nd other -ve or not.If not,pick the element from left subarray
public class insert {
public static int[] ins(int[] a){
{
for(int i=1;i<a.length;i++)
{
int key=a[i];
int j=i-1;
while(j>=0&&a[j]>key)
{
a[j+1]=a[j];
j=j-1;
}
a[j+1]=key;
}
return a;
}
}
}
class test {
public static void main(String[] args) {
int[] a={-2,3,5,0,-3,7,0};
int[] b=insert.ins(a);
for(int i=0;i<b.length;i++)
{
System.out.println(b[i]);
}
}
}
O(nlogn) algorithm. sorry about the previous post. not formated
def stable_dutch_national_flag(array):
def map_key(v):
if v < 0: return -1
elif v == 0: return 0
else: return 1
return sorted(array, key = map_key)
- amfaheem October 05, 2012/** * @author Ahmed Fahim * Created on October 5, 2012, 058:20 AM */ public static void DutchNationalFlag(int[] A) { int posStartIndex = 0; for (int i = 0; i < A.length; i++) { if (A[i] <= 0) { int temp = A[i]; for (int j = i; j > posStartIndex; j--) { A[j] = A[j-1]; } A[posStartIndex] = temp; if (A[i] < 0) posStartIndex++; } } }