DIR Return Create A Forum - Home
---------------------------------------------------------
techsuns
HTML https://techsuns.createaforum.com
---------------------------------------------------------
*****************************************************
DIR Return to: Puzzles && Algorithms
*****************************************************
#Post#: 359--------------------------------------------------
Microsoft Interview question-2
By: srini Date: December 6, 2012, 10:05 am
---------------------------------------------------------
Given an unsorted integer array, find the first missing positive
integer. ??? ???
For example,
given [1,0,2] returns 3 .
given[1,-1,0,3] returns 2
given[1000] returns 1001.
Give the naive solution then try for O(n) time and constant
space.
#Post#: 361--------------------------------------------------
Re: Microsoft Interview question-2
By: satya Date: December 7, 2012, 2:19 am
---------------------------------------------------------
since we need to find the first missing positive integer,
Firstly, we can find the maximum element in the given list and
allocate an array of that size and initialize it with zeroes.
Then we traverse through the given list and do the following:
!) if we get a negative integer discard it, and
2) if we get a positive integer, just increment that particular
value in the array which we allocated.
and at last the first position where the value is zero gives the
answer................... is it correct?? ::)
???
#Post#: 363--------------------------------------------------
Re: Microsoft Interview question-2
By: kranthipls Date: December 7, 2012, 2:36 am
---------------------------------------------------------
There is a constraint on the usage of memory........
He said you need to use constant memory.............
But you are creating n size array inorder to find the solution.
So you are using linear space but not constant space.
Yes it takes linear time but not constant space.........
#Post#: 365--------------------------------------------------
Re: Microsoft Interview question-2
By: ravusairam Date: December 7, 2012, 2:39 am
---------------------------------------------------------
@satti your solution doesn't work for the following reasons
1) Since there are negative numbers you can't just simply
discard,
because for example if the input is -10,-9,-7,-5 - your method
doen't work - how much size of array will you create for it?
#Post#: 366--------------------------------------------------
Re: Microsoft Interview question-2
By: kranthipls Date: December 7, 2012, 2:43 am
---------------------------------------------------------
Satti's method works because.....
Initially he is finding the maximum and max func returns -5 He
straightway prints 1 which is the first missing positive
integer.
#Post#: 367--------------------------------------------------
Re: Microsoft Interview question-2
By: ravusairam Date: December 7, 2012, 2:44 am
---------------------------------------------------------
I think we can try for O(nlogn) solution by sorting(Quick sort),
where all the elements are sorted and traverse the sorted array
to find the element.
#Post#: 368--------------------------------------------------
Re: Microsoft Interview question-2
By: ravusairam Date: December 7, 2012, 2:46 am
---------------------------------------------------------
Oh sorry I didn't see the question properly, it doesn't work if
we were asked to print the not just the positve integer but
integer.
#Post#: 369--------------------------------------------------
Re: Microsoft Interview question-2
By: satya Date: December 7, 2012, 2:53 am
---------------------------------------------------------
yesh.........if we want to find the first missing integer then
its better to sort as u said..................but here the
question is to find the first postive integer..........so if
there is no positive integer, then instead of allocating array,
just print 1. (if 0 is not considered as positive
integer........) ;) i just gave a naive solution ....
#Post#: 382--------------------------------------------------
Re: Microsoft Interview question-2
By: srini Date: December 10, 2012, 9:36 am
---------------------------------------------------------
Idea:
1) Segregate positive numbers from others i.e., move all
non-positive numbers to left side.
2) Now we can ignore non-positive elements and consider only the
part of array which contains all positive elements. We traverse
the array containing all positive numbers and to mark presence
of an element x, we change the sign of value at index x to
negative. We traverse the array again and print the first index
which has positive value.
Here is the code (Not tested for all test cases):
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int segregate(int *a,int n)
{
int i,j=0;
int temp;
for(i=0;i<n;i++)
{
if(a<=0)
{
//swap
temp = a[j];
a[j]= a;
a= temp;
j++;
}
}
return j;
}
int findMissingPositive(int *a ,int size)
{
if(size == 0)
return 1;
int i;
for(i=0;i<size;i++)
{
if(a>0 && abs(a)<size)
a[a-1] = -1*a[a-1];
}
for(i=0;i<size;i++)
{
if(a>0)
return i;
}
return i;
}
int main()
{
int i;
// int a[] = {0,10,20,-2,-8,1,5,2};
//int a[] = {-1,1000};
int a[] = {1,2,3};
int size = (sizeof(a))/sizeof(int);
int split = segregate(a,size);
if(split==0 )
{
printf("Missing positive number is:
%d\n",a[size-1]+1);
return 0;
}
printf("Missing positive number is: %d\n",
findMissingPositive(a,size-split));
}
#Post#: 391--------------------------------------------------
Re: Microsoft Interview question-2
By: kranthipls Date: December 10, 2012, 10:12 pm
---------------------------------------------------------
Very Good Question
*****************************************************
DIR Next Page