InMobi Interview Question

  • inmobi-interview-questions
    0
    of 0 votes
    36
    Answers

    You are given an unsorted array with both positive and negative elements. You have to find the smallest positive number missing from the array in O(n) time using constant extra space.
    Eg:
    Input = {2, 3, 7, 6, 8, -1, -10, 15}
    Output = 1

    Input = { 2, 3, -7, 6, 8, 1, -10, 15 }
    Output = 4

    - ashu on February 19, 2012 in India Report Duplicate | Flag
    InMobi Algorithm

Country: India
Interview Type: In-Person


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

I am assuming that we need to find smallest non-negative integer in the array, it can easily be extended to smallest positive integer as well.

I am basically use the array itself as the hash-table. Since, solution would be in the range [0,sizeOfArray-1], the array itself would suffice to find the solution.

Basically, while going through the array, I am moving the element to its correct location in array based on the value as the hash-key itself. So, 2 -> index 2, 5 -> index 5, and so on. For elements, which are not in range [0,sizeOfArray-1], I do not care, as they cannot be the answer.

Here is my sample code for doing this:

#include <stdio.h>

int main()
{
	int A[] = {2, 3, 7, -6, 0, 1, 4, 5};
	int size = 8;
	int previousValue = -1;
	int currentIndex = 0;
	int currentValue = A[currentIndex];
	int nextIndex = currentIndex + 1;
	bool isChaining = false;
	
	while (nextIndex <= size)
	{
		if (currentValue != currentIndex &&
			currentValue > -1 &&
			currentValue < size)
		{
			isChaining = true;
			A[currentIndex] = previousValue;
			previousValue = currentValue;
			currentIndex = currentValue;
			currentValue = A[currentIndex];
		}
		else
		{
			if (isChaining)
			{
				A[currentIndex] = previousValue;
				isChaining = false;
			}
			
			currentIndex = nextIndex++;
			previousValue = -1;
			currentValue = A[currentIndex];
		}
	}
	
	int x;
	for (x = 0 ; x < size; x++)
	{
		if (A[x] != x)
		{
			printf ("%d\n", x);
			break;
		}
	}
	if (x == size)
	{
		printf ("%d\n", x);
	}
	
	return 0;

}

The solution above is obviously O(1) in space complexity.
To prove that it is O(n) in time complexity, it can be seen easily that I never visit an element more than twice, so it would traverse the array twice before all required elements are at their required location. Then, one more traverse is required to find the answer. Hence, O(n)

- gimli on February 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if your input is: {12, 8, -1, 7}? How would you find 7?

- Anonymous on February 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Isn't 1 the answer above?
I think the question asks for smallest positive number missing from the array, not the smallest positive number.

- gimli on February 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

My bad, how would you find 6?

- Anonymous on February 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Answer is 1, I don't need to find 6 :)

- gimli on February 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hm, I think I finally got the question :)
Your solution makes total sense now unless there are no negatives there and we have {1,2,3,4}

- Anonymous on February 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It works for array with negatives as well, the example that I used has negative value, and gives correct answer.

- gimli on February 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what if you sort the numbers then traverse till all -ve numbers end. then check for 1 if available or not. if yes then check diff with next element and move ahead until u a[n+1] - a[n] >1 . ur answer is a[n] +1 . if 1 not found then answer is 1

- V on February 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

gimli, I didnt look at the code in detail, but your solution seems to be correct.
Nicely done in the same array... discarding the elements that are not needed.

- Anupam on February 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

not workng..logic fails because the swapped value is lost
@gimli : have you checked it with both the above given example ?

- @ingenious on March 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thats a perfect solution.

Only better thing could be if someone can achive this O(n) time and O(1) space complexity without changing existing array.

- Manas on May 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

Hmm.. this is a very interesting question, so I am going to take a stab at this.

1. Go through the array once and map everything to a hash table. Also keep track of the largest positive vale you find - O(n)
2. Start a second loop from 0 or 1 (depending on your definition of smallest positive integer). - O(n)
3. In every iteration, check if value exists in hash table. If it does not, that is your value

Total time: O(n) runtime, O(n) space.

I will be very interested in a solution that can pull this off in less than O(n) space.

- P.M on February 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Instead of using the hash table, you can shift the wrong values towards the end of the array and decrease end.

eg: int[] a = {12, 2, 1, -5, 6, 18}
Keep a pointer at the start and another at the end of the array.
a[0] = 12 and 12 > a.length() so swap 12 with a[end] and do end--

so my a[] becomes {18, 2, 1, -5, 6}
similarly, 18 is also out of bounds so I repeat and a[] = {6, 2, 1, -5} and then {-5, 2, 1} and then {2, 1}

Now, in this step we see a[start] <= end so what I do is swap a[start] with a[a[start]]
Thus, a[] = {1, 2}

lastly, I have to loop only till whenever a[start] = a[a[start]], in this case till 3 (which is our answer).

- ashu on February 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

1. scan the array for the largest element .
2. Now take the hash table of size = largest element.
3. map the array elements into hash table.
4. Scan the hash table for smallest positive number missing.
....I think this way space complexity is not o(n)....please comment..

- RATS on February 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The largest number can be Integer.MAX so if we have an array of say only 6-7 values, thats an overkill

- ashu on February 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yea....but it dsnt depend on size of the array....My point is that v talk about complexity for the input of millions. In that context m talking abt...

- RATS on February 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Consider a language which can represent arbitrary large integers, in that case Integer.Max doesn't make sense and you cannot have such hash table.

- gimli on February 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

In my view ashu soln is best because it is using constant space O(1) complexity and time complexity is O(n).

- googlybhai on February 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi ashu, I think your solution works when there is no dup positive interger in the array. I can have a long array that every element in there is smaller than array.length. Finding and swapping those dups out can be time consuming.

- Ric on February 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hey Ric I didn't take into notice for the duplicate elements, but the algorithm can be extended for duplicate elements easily.

We are interested in smallest positive number not in array so all duplicate elements can be swapped out of the boundaries similar to a number greater than length of array (i.e. doing a start++ will do the trick)

- Anonymous on February 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Ashu, pretty neat solution, though I do not clearly understand what you in case value < end.
Can you show, how would your algorithm work on following array
[6,5,4,3,2,1]

- gimli on February 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I believe we have to do a Radix Sort O(n) after the elements are deleted,and also compare the absolute values instead of comparing them directly that way we delete large negative numbers also.

I tired this and it worked. But did not use the Radix Sort in my code, went with a more easy O(n log n) sorting algorithm and here is the code, if anyone is interested

public int findSmallestPositiveMissing(int[] array)
	{
		int left = 0;
		int right = array.length - 1;
		
		while(left < right)
		{
			if(Math.abs(array[left]) > array.length)
			{
				int temp = array[left];
				array[left] = array[right];
				array[right] = temp;
				right--;
			}
			left++;
		}
		Arrays.sort(array);
		for(int i = 1; i < array[right]; i++)
		{
			if(Arrays.binarySearch(array, i) < 0)
			{
				return i;
			}
		}
		return array[right] + 1;
	}

- Dev on February 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

Finally, a flawless algorithm based on Quicksort's partition subroutine.

1. Using modified partition routine, move all the -ve elements to the right side of the array and all +ve numbers to the left side of the array
2. Let the size of all the positive numbers be N.
3. Use Quicksort's modified partition subroutine to recursively check for the missing number either in the left half or the right half of the array. This results in an O(n) time complexity algorithm.
4. At each recursive step, for a subarray starting at index S, and ending at index E, the subarray is partitioned around the pivot (S + E)/2. We check if the pivot is correctly positioned at its location. Depending on the existence of the pivot at its correct location, we recurse either in the left half or the right half of the sub array to report the missing element.
5. If no element is missing, return 0.

Java code is below: Tested on the inputs in the following format.
2 3 -7 6 8 1 -10 15
2 3 7 6 8 -1 -10 15
-1 -2 -3 -4 4 3 2 5 7 6
-1 -2 4 3 2 -3 -4 1 7 5 8 -9 -10 -11
-1 -2 4 3 2 -3 -4 1 7 5 8 -9 -10 -11 10 12 6 9 11 13 15

import java.util.ArrayList;
import java.util.Scanner;
import java.util.regex.Pattern;

public class MissingPositiveNumber {

	ArrayList<Integer> numbers = new ArrayList<Integer>();

	public void readInput() {
		Scanner scanner = new Scanner(System.in);
		scanner.useDelimiter(System.getProperty("line.separator"));
		Pattern delimiters = Pattern.compile(System
				.getProperty("line.separator") + "|\\s");
		scanner.useDelimiter(delimiters);
		int i;
		while (scanner.hasNextInt()) {
			i = scanner.nextInt();
			numbers.add(i);
		}
	}

	public int findMinMissing(int[] a, int start, int end, int missingMin) {

		if (end - start <= 0) {
			if (a[start] != start)
				return start;
			else
				return missingMin;
		}

		int mid = (start + end) / 2;
		int j = start, k = end;

		while (true) {

			while (j <= end && a[j] < mid)
				j++;
			while (k > start && a[k] > mid)
				k--;
			if (j >= k)
				break;
			else {
				int temp = a[j];
				a[j] = a[k];
				a[k] = temp;
			}
		}

		if (mid < a[mid])
			return findMinMissing(a, start, mid - 1, mid);
		else if (mid > a[mid])
			return findMinMissing(a, mid, end, missingMin);
		else
			return findMinMissing(a, mid + 1, end, missingMin);
	}

	public int findMissingSmallestPosNumber() {
		int[] vals = new int[numbers.size() + 1];
		for (int i = 1; i <= numbers.size(); i++) {
			vals[i] = numbers.get(i - 1);
		}

		int j = 1, k = numbers.size();

		while (true) {

			while (j <= numbers.size() && vals[j] > 0)
				j++;
			while (k >= 1 && vals[k] < 0)
				k--;
			if (j > k)
				break;
			else {
				int temp = vals[j];
				vals[j] = vals[k];
				vals[k] = temp;
			}
		}
		return findMinMissing(vals, 1, k, 0);
	}

	public static void main(String[] args) {
		MissingPositiveNumber mpn = new MissingPositiveNumber();
		mpn.readInput();
		System.out.println("The least positive missing number ="
				+ mpn.findMissingSmallestPosNumber());
	}
}

- Murali Mohan on June 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Good job! I think this works and is linear time: n + n/2 + n/4 + ... = O(n).

btw, I suggest you read Jon Bentley's Programming Pearls (and do the exercises). I believe this appears as one of the exercises in the first (or maybe second) chapter.

- Loler on June 13, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

@Loler. Thanks a lot for the suggestion, appreciate it.

- Murali Mohan on June 13, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int findTheMissingPositiveNumber(int[] arr) {
        int missingInt = 1;
        int curValue = arr[0];
        int lastIndex = arr.length - 1;

        while (missingInt < lastIndex) {
            if (curValue <= 0 || curValue >= lastIndex + 1) {
                curValue = arr[lastIndex];
                lastIndex--;
            } else if (curValue != missingInt) {
                int tmp = arr[curValue - 1];
                arr[curValue - 1] = curValue;
                curValue = tmp;
            } else {
                while (curValue == missingInt) {
                    arr[missingInt - 1] = curValue;
                    curValue = arr[missingInt];

                    missingInt++;
                }
            }
        }

        return missingInt;
    }

- Jay on March 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Correction:

while (missingInt < lastIndex + 1)

- J on March 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Correction:

while (missingInt < lastIndex + 1)

- J on March 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Correction:

while (missingInt < lastIndex + 1)

- J on March 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Correction:

while (missingInt < lastIndex + 1)

- J on March 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Do a radix sort O(n)

Then { 2, 3, -7, 6, 8, 1, -10, 15 } becomes {-10, -7, 1,2,3,6,8,15}

Now, iterate from left to right and check if a[i] + 1 == a[i+1]

if not then assign a min variable that number .. now go forward and keep checking till u find a minimum int

int[]  arr =  {-10, -7, 1,2,3,6,8,15};
int min = -1;
for(int i =0 i < arr.length - 1; i++){
     if( a[i] < 0 ) continue;

     if( a[i] - 1 != 0 ){
           min = a[i] - 1; break;
     }
     if ( a[i] + 1 != a[i+1] ) {
         min = a[i] + 1; break;
     }
}

sysout(min);

- Khan on March 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

same as code above by gimli here is Pseudocode
Solution --> O(n) worst case + O(1) space

1. iterate array set elements > array.size to -1
2.bring respective elements to index corressponding to their value
for e.g if element=3 then set a[3]=3 and so on;
3. iterate array again and return the index corressponding to first negative value

here is the full code in java
// didn't check special case neither duplicates

package arraysnstrings;

import java.util.Arrays;

public class MinMissingPositiveInteger {

public static void main(String[] args) {

int a[]={-14,-7,7,4,2,5,6,1,0,29,30};

System.out.println(findMin(a,a.length));

}

private static int findMin(int[] a, int length) {
// TODO Auto-generated method stub


for(int i=0;i<length;i++){
if(a[i]>length)
a[i]=-1;
}

System.out.println("before : = " + Arrays.toString(a));
//special case if all integers are -ve return 0
int tempElement = -1;
for(int i=0;i<length;i++){
if(a[i]>=0&&a[i]!=i){

tempElement = a[i];
a[i]=-1;

while(tempElement>=0){
int temp2=a[tempElement];
a[tempElement]=tempElement;
tempElement=temp2;
}

}


}
System.out.println("after="+Arrays.toString(a));

for(int i=0;i<length;i++){
if(a[i]<0){
return i;
}
}

return -1;
}

}

- mystic on May 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Maintain a separate array of type boolean having same size. Iterate through array of given elements and if a +ve element is found mark the corresponding element in boolean array as true. If -ve element, ignore the element.

The start iterating boolean array. The smallest positive integer will be corresponding element, having value as false in boolean array.

- Anonymous on May 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

assuming you are initializing the boolean array with false for each element.

eg: -14,-7,7,4,2,5,6,1,0,29,30
f f f f f f f f f f f
then according to your algorithm

-14,-7,7,4,2,5,6,1,0,29,30
f f t t t t t t t t t
correct answer here is 3 and according to your algorithm its giving -7.

also maintaining a boolean entry for each element
will lead your solution to be of O(N) space complexity.

- mystic on May 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

geeksforgeeks.org/forum/topic/to-find-the-smalest-positive-no-missing-from-an-unsorted-array

- mayank on May 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<conio.h>

int minValue(int *p);
sort(int *p)
int main()
{
	int array[] = {-2,-3,1,2,3,5,6,7};
	int min = minValue(array);
	if(min)
	printf("min value->%d",min);
	else
	printf("No missing value");
}

//First sort the array
int minValue(int *p)
{
	int flag=0;
	int min=0;
	for(int i=0;i<7;i++)
	{
		if(p[i]<0)
		;
		else if(p[i]-min==1)
		{
			min = p[i];
		}
		else
		{
			flag=1;
			break;
			return min + 1;
		}
	}
	if(flag)
	return min + 1;
	else
	return 0;
}

- Monis Majeed on May 07, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More