InMobi Interview Question

• 0

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)

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

I think the question asks for smallest positive number missing from the array, not the smallest positive number.

Comment hidden because of low score. Click to expand.
0

My bad, how would you find 6?

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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}

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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.

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.

Comment hidden because of low score. Click to expand.
0

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).

Comment hidden because of low score. Click to expand.
0

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..

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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...

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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)

Comment hidden because of low score. Click to expand.
0

@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]

Comment hidden because of low score. Click to expand.
0

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;
}``````

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>();

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();
}
}

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();
System.out.println("The least positive missing number ="
+ mpn.findMissingSmallestPosNumber());
}
}``````

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.

Comment hidden because of low score. Click to expand.
0

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

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;
}``````

Comment hidden because of low score. Click to expand.
0

Correction:

``while (missingInt < lastIndex + 1)``

Comment hidden because of low score. Click to expand.
0

Correction:

``while (missingInt < lastIndex + 1)``

Comment hidden because of low score. Click to expand.
0

Correction:

``while (missingInt < lastIndex + 1)``

Comment hidden because of low score. Click to expand.
0

Correction:

``while (missingInt < lastIndex + 1)``

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

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);``````

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;
}

}

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.

Comment hidden because of low score. Click to expand.
0

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

-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

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

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;
}``````

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

``````int missing(int *a,int n)
{
int i,pos;
for(i=0;i<n;i++)
{
if(a[i]>0 && a[i] <= n)
{
pos = a[i] -1;
if(a[pos] != a[i])
{
swap(a[pos],a[i]);
i--;
}
}
}

for(i=0;i<n;i++)
{
if(a[i] != i+1)
return i+1;
}
return n+1;
}``````

Name:

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

Books

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

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.

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.

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.