Microsoft Interview Question Software Engineer / Developers
similar to quick Sort method of quick sort. Instead of making equal to less than decision make < 0 and > 0 decision.
we must do it with no extra memory , if we use insertion sort model we can arrange them as needed as insertion sort is a stable sort but time complexity is o(n2) because it involves shifting .Is there any way we can do it less than that .
Interviewer gave a hint saying we can use partitioning like quick sort
/// Use merge sort with a modified merge operation.
/// While merging instead of choosing the smaller among the two lists, choose the /// negative number. This ensures that, at each step the negative numbers are to the /// left, in their original order
/// Complexity will be NlogN. Any linear solution?
#include<stdio.h>
#include<malloc.h>
void modifiedMergeOperation(int* input, int left, int mid, int right)
{
//if(right == left) return;
int* temp = (int*)malloc(((right-left)+1)*sizeof(int));
int i = 0, j = 0;
int index = 0;
for(i = left, j = mid+1; i <= mid && j <= right;index++)
{
//Modified step. Choose the negative numbers first
if(input[i] < 0)
{
temp[index] = input[i];
i++;
}
//Modified step. Choose the negative numbers first
else if(input[j] < 0)
{
temp[index] = input[j];
j++;
}
else
{
temp[index] = input[i];
i++;
}
}
while(i <= mid){ temp[index] = input[i]; i++; index++;}
while(j <= right){ temp[index] = input[j]; j++; index++;}
for(i = left; i <= right; i++)
{
input[i] = temp[i - left];
}
free(temp);
}
void splitOperation(int* input, int left, int right)
{
if(left < right)
{
splitOperation(input, left, (right+left)/2);
splitOperation(input, (right+left)/2 + 1, right);
}
modifiedMergeOperation(input, left, (right+left)/2, right);
}
int main()
{
int input[] = {3, -6, 8, 3, 1, -56, -8, 90, 45, 2, 86, -12 ,8, 34, 1, -83, 26, -8};
splitOperation(input, 0, 17);
for(int i = 0; i < 18; i++) printf("%d ", input[i]);
}
Disadvantage of mergesort is it uses additional space of O(n). I think we shld solve this without any additional space.
If we want to use O(n) additional space then dont go for mergesort, just start copying -ve no's to new array and then copy all +ve no's. This will still make time complexity as O(2n) which is equal to O(n)...
Am checking if it can solved in O(n) without additional space.
it can be solved in place...
you just maintain beginning of string with one type, and end of string with another type.
both groups will grow toward center of string.
after having processed all elements you'll have first type properly ordered and second type inverted.
after that, just reverse in place second part of string.
I got some working solution. TC: O(n+k) = O(n) .. K is some constant which is always less than n.
#include<stdio.h>
void swap(int *a, int *b)
{
int temp;
printf("\nSwapping %d and %d",*a,*b);
temp = *a;
*a = *b;
*b = temp;
}
int main()
{
int a[10] = {-5,2,3,-4,-6,7,8,9,-1,0};
int n1=-1,n2=-1,k=-1;
int p1=-1,p2=-1,l=-1;
int i = 0;
int pos = 0;
int count = 0;
printf("Given array: ");
for(i=0;i<10;i++)
printf("%d ", a[i]);
printf("\n");
i=0;
if(a[0] > 0)
{
p1 = 0;
pos = 1;
}
else
n1 = 0;
if(!pos)
{
do
{
while(i<10 && a[++i] > 0);
if(a[i] < 0)
{
n2 = i;
while(n2 > n1+1)
{
swap(&a[n2], &a[n2-1]);
count++;
n2--;
}
n1++;
}
}while(i<10);
}
else
{
do
{
while(i<10 && a[++i] > 0);
if(a[i] < 0)
{
n2 = i;
while(n2 > n1+1)
{
swap(&a[n2], &a[n2-1]);
n2--;
}
n1++;
}
}while(i<10);
}
printf("\n");
printf("Output: ");
for(i=0;i<10;i++)
printf("%d ",a[i]);
printf("\nTotal swaps: %d",count);
return 1;
}
{public static void main(String[] args) {
int arr[] = { 0,-4,37,4,66,5,-2,-3,65,-6,60,39,50,-8,42,33,20,29,53,36,0,-20 };
int nIndex = -1;
int pIndex = 0;
int tIndex = 0;
while (pIndex < arr.length) {
if (arr[pIndex] >= 0) {
if (nIndex < 0)
pIndex++;
else {
tIndex = pIndex++;
while (tIndex > nIndex) {
int temp = arr[tIndex];
arr[tIndex] = arr[tIndex - 1];
arr[tIndex - 1] = temp;
tIndex--;
}
nIndex++;
}
} else {
if (nIndex < 0)
nIndex = pIndex++;
else
pIndex++;
}
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
}
}
void groupNumbers(int[] num, int i, int j)
{
if (i >= j) return;
int k = i+(j-i+1)/2;
groupNumbers(num, i, k-1);
groupNumbers(num, k, j);
groupMerge(num, i, k, j);
}
void groupMerge(int[] num, int i, int k, int j)
{
int l = i, m = k;
for (; l < k && num[l] >= 0; l++);
for (; m <= j && num[m] >= 0; m++);
reverse(num, l, k-1);
reverse(num, k, m-1);
reverse(num, l, m-1);
}
void reverse(int[] num, int i, int j)
{
while (i < j)
{
int tmp = num[i];
num[i] = num[j];
num[j] = tmp;
i++; j--;
}
}
Basic idea is to use the identity (ArBr)r = BA where Ar is the reverse of A.
To clarify further, if you have a group B of positive numbers and group A of negative numbers you can swap them by reversing both A, B and BA to get AB. Basic divide & conquer.
public void segregateNumbers(int [] a){
int [] b = new int [a.length];
int j =0;
for(int i =0; i < a.length; i++){
if(a[i] < 0){
b[j++] = a[i];
}
}
for(int i =0; i < a.length; i++){
if(a[i] >= 0){
b[j++] = a[i];
}
}
return;
}
I have a solution which uses extra space. But the extra space is equal to the number of negative numbers in the array.
Iterate through the array: When you find a positive number add it to the left end and increment the length of positive numbers by 1 and iterator by 1.
If you find a negetive number add it to a linked list.
When you reach the end of the original array, you would have all the positive numbers from position - 0 to (num. +ve numbers - 1). Now fill the rest of the places with the
elements from the list freeing the list as you proceed from head till the last node.
The time complexity is O(n). Space complexity is 0(number of negetive numbers)
Why is everyone writing code like undergrad freshmen?
I look at the posted codes and all the time i see variables as i, j, p1, p2, k, l, ...
What about using variable names like:
positiveNumberIterator, originalArraySize, negativeNumberCount and etc??
Since the aim is sharing your ideas, it should be understandable, right?
If i were the interviewer, i would directly eliminate the candidate because of using variables like a, b, k, m, n.
If the condition of same order is relaxed, then this is how u can modify the partition algorithm of Quicksort by appending a 0 into the array, and selecting it as the pivot element.
Once we are done with partitioning, we can simply delete the pivot.
I just realized, we dont even need to append the 0. We can simply use 0 as the pivot element and do the partitioning.
Then omit the last step of partition where it swaps Pivot element.
--Chander
public static int[] OrderNumbers(int []arr)
{
int len=arr.Length;
int totalNegativNumbers=0;
int []arrnew=new int[len];
for(int i=0;i<len;i++)
{
if(arr[i]<0)
totalNegativNumbers++;
}
int negCounter=0;
int posCounter=totalNegativNumbers;
for(int i=0;i<len;i++)
{
if(arr[i]<0)
arrnew[negCounter++]=arr[i];
else
arrnew[posCounter++]=arr[i];
}
return arrnew;
}
I think following should do :
- p = start ; q = end;
- if (a[p] < 0 ) -> p++;
- else swap (a[p] and a[q]); q--;
The order of the positive number will be reversed. We can reverse positive numbers again in o(n) without using extra space.
Time : o(n)
Space : o(1)
guys what are u doing its so simple maintain numbers in a link list and go through the list maintain 2 pointers initially both are pointing to start when you find an negative number stop the first pointer and increment the second pointer for next +ve number and as in link list you just have to change some pointers insert that positive elment before the negative number in this case al +ve will be in front in the same order and -ve in end in same order
Here while moving elements the order of elements must be preserved
- Anonymous October 06, 2010