## Google Interview Question for Software Engineers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
10
of 12 vote

1. Put numbers between 0 and n-1 to a[number]
2. Process array and if (a[i] != i) -> number "i" is missing
3. Put numbers between n to 2*n-1 to a[number-n]
4. Process array and if (a[i] != i + n) -> number "i + n" is missing

``````public class AbsentNumbers {

public static void main(String[] args) {
int[] array = new int[]{8,4,12,0,7,3,1};
printAbsentNumbers(array);
}

private static void printAbsentNumbers(int[] array) {
//sort 0 to n-1
for (int i = 0; i < array.length; i++) {
if (array[i] < array.length){
int temp = array[array[i]];
array[array[i]] = array[i];
array[i] = temp;
}
}
//check 0 to n-1
for (int i = 0; i < array.length; i++) {
if (array[i] != i){
System.out.print(i + " ");
}
}
//sort n to 2*n-1
for (int i = 0; i < array.length; i++) {
if (array[i] >= array.length){
int temp = array[array[i] - array.length];
array[array[i] - array.length] = array[i];
array[i] = temp;
}
}
//check n to 2*n-1
for (int i = 0; i < array.length; i++) {
if (array[i] != i + array.length){
System.out.print(i + array.length + " ");
}
}
}

}``````

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

There is a small error in the code. You need to add additional condition for the if. Here is a working solution:

``````public static void findMissing(int array[])
{
for (int i = 0; i < array.length; )
{
if (array[i] < array.length && array[i] != i)
{
int temp = array[array[i]];
array[array[i]] = array[i];
array[i] = temp;
}
else
i++;
}

//check 0 to n-1
for (int i = 0; i < array.length; i++) {
if (array[i] != i){
System.out.print(i + " ");
}
}

//sort n to 2*n-1
for (int i = 0; i < array.length; ) {
if (array[i] >= array.length && array[i] != i + array.length)
{
int temp = array[array[i] - array.length];
array[array[i] - array.length] = array[i];
array[i] = temp;
}
else
i++;
}

//check n to 2*n-1
for (int i = 0; i < array.length; i++) {
if (array[i] != i + array.length)
{
System.out.print(i + array.length + " ");
}
}
}``````

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

There is a small mistake. You will need to add additional condition in your if to deal with case of 8 in this case which is printed in output. Here is the working solution:

``````public static void findMissing(int array[])
{
for (int i = 0; i < array.length; )
{
if (array[i] < array.length && array[i] != i)
{
int temp = array[array[i]];
array[array[i]] = array[i];
array[i] = temp;
}
else
i++;
}

//check 0 to n-1
for (int i = 0; i < array.length; i++) {
if (array[i] != i){
System.out.print(i + " ");
}
}

//sort n to 2*n-1
for (int i = 0; i < array.length; ) {
if (array[i] >= array.length && array[i] != i + array.length)
{
int temp = array[array[i] - array.length];
array[array[i] - array.length] = array[i];
array[i] = temp;
}
else
i++;
}

//check n to 2*n-1
for (int i = 0; i < array.length; i++) {
if (array[i] != i + array.length)
{
System.out.print(i + array.length + " ");
}
}
}``````

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

Swapping alone wont work here is an example,
Array => 0,5,3,1,2

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

Yep, that's the correct idea. Here is python variant ideone.com/xQbxeJ

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

sorry my bad. the code is fine.

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

GobSmack is right. Here is the test case which doesn't work:
0,7,4,2,1

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

The problem with this solution is that the final array is not equal to the original array. Am i wrong?

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

I think while loop would be more readable here instead of using for loop with index that is only sometimes incremented.

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

This is wrong. Swapping will not work. example: 0,5,3,1,2 becomes 0,5,2,3,1 and then 1 is printed as missing.

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

is the array sorted or not ?

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

Seems the input array is sorted as mentioned in the space requirements

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

``````Here is an algorithm that takes O(1) space and O(N) time and meets all these weird requirements.

1. take tow variable: index=-1,value=-1.

2. Imp: Traverse the array from i=0 to n-1. If a[i]==i or a[i]==i+n then move ahead else there will be the following cases:
(i) If a[a[i]] ! =a[i] && a[a[i]]!=a[i]+n : Swap a[i] and a[a[i]].
(ii) else if index==-1 : index=i; value=a[i] and a[a[i]]=value
{iii) else a[a[i]]=value;

3. Now again traverse the array and do the following:
(i) If a[i] == value and i==index: Print i and i+n.
(ii) else If a[i] != value && a[i]==i : Print i+n
(iii) else If a[i] != value && a[i]==i+n : Print i
(iv) else If a[i] !=value : Print i and i+n
(v) else if a[i]==value: continue.``````

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

Hi, technoapurva. The problem requires "sorted(initial_array) must equal sorted(array_after_executing_program) "

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

``````def findmissing(array):
#trivial cases
if(len(array) < 1):
return []
if(len(array) == 1):
if(array[0] == 0):
return [1]
else:
return [0]
#stores output
outList = []
if(array[0]==0):
#don't want to include 0 in the multiplication
multArr = reduce(lambda x, y: x*y, array[1:])
else:
multArr = reduce(lambda x, y: x*y, array)
outList.append(0)

#multiply all numbers from 1 to 2*n
maxTotal = reduce(lambda x, y: x*y, list(range(1,2*len(array))))

for i in range(2*len(array)-1,0,-1):
#take care of division by 1... which will of course return true
#for all numbers besides 0 (unless multArr is 0 also)
if(i==1):
if(array[0]==1 or array[1]==1):
break
else:
outList.append(1)
break
if(maxTotal/i >= multArr):#keep dividing by the largest factor
outList.append(i)
maxTotal = maxTotal/i
return outList

#array = [0,2,4]
#array = [1]
array = [0,1,2,3,4,5,6,7]
print(findmissing(array))``````

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

Compress array.
{0, 2, 3, 4, 5, 9} => {9, 0, 2, 2, 5, 9}

[2, 2, 5] means [2, 3, 4, 5]. [0, 0, 100] means [0, 1, ..., 100].
If 2n-1 number is stored in not end of array, it is empty space.
Then, you can fill missing number from left to right.

``````void findMissing(vector<UINT32>& arr) {
int i, j;
UINT32 last, start, prev, count, firstFrom, firstTo, secondFrom, secondTo;

if (arr.size() == 0) return;
if (arr.size() == 1) {
arr[0] = (arr[0] + 1) % 2;
return;
}

sort(arr.begin(), arr.end());

last = arr.size() + arr.size() - 1;

// find continuous sequence
start = last;
prev = last;
count = 0;
for (i = 0; i < arr.size(); i++) {
if (prev + 1 == arr[i]) {
count++;
if (count > 3) {
arr[i - 3] = last;
arr[i - 2] = start;
arr[i - 1] = start;
}
} else {
start = arr[i];
count = 1;
}
prev = arr[i];
}

// move empty element to first
for (i = arr.size() - 2; i > 0; i--) {
if (arr[i] != last) continue;
for (j = i - 1; j >= 0; j--) {
if (arr[j] == last) continue;
arr[i] = arr[j];
arr[j] = last;
break;
}
}

// skip empty space
for (i = 0; i < arr.size(); i++) {
if (arr[i] != last) break;
}
j = 0;
firstFrom = 0;
firstTo = 0;
secondFrom = 0;
secondTo = 0;
while (j < arr.size()) {
// find first empty sequency
firstFrom = secondTo;
firstTo = secondTo;
for (; i < arr.size(); i++) {
if (arr[i] <= firstFrom || (i > 2 && arr[i - 2] == arr[i - 1])) {
firstFrom = arr[i] + 1;
firstTo = last + 1;
} else {
firstTo = arr[i];
break;
}
}

// find second empty sequency
secondFrom = firstTo;
secondTo = firstTo;
for (; i < arr.size(); i++) {
if (arr[i] <= secondFrom || (i > 2 && arr[i - 2] == arr[i - 1])) {
secondFrom = arr[i] + 1;
secondTo = last + 1;
} else {
secondTo = arr[i];
break;
}
}

for (; j < arr.size(); j++) {
if (firstFrom == firstTo) break;
arr[j] = firstFrom;
firstFrom++;
}

for (; j < arr.size(); j++) {
if (secondFrom == secondTo) break;
arr[j] = secondFrom;
secondFrom++;
}
}
}``````

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

sort(...) takes O(n*log(n)) time alone

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

I think the following solution. Let's split the array in two sets - one that contains elements lower than N [0-N) and other that contains elements greater or equal to N [N,2N-1)
I reorder two sets one after another for the reason to sort each of the sets and iterate all numbers from 0 to 2*N - 1 to print absent elements. Time complexity is O(n) and space complexity o(1)
{{
void swap (int i, int j, int[] data) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}

void findCountInSplit(int[] numbers, int N, boolean lessThanN) {
int index = 0 ;
while (index < numbers.length) {
if (lessThanN) {
if ((numbers[index] < N) && (numbers[index] != index))
swap(index, numbers[index], numbers);
else
index++;
} else {
if ((numbers[index] >= N) && (numbers[numbers[index]-N] != numbers[index]))
swap(index, numbers[index] - N, numbers);
else
index++;
}
}
int upperBound = 0;
int lowerBound = 0;
if (lessThanN) {
upperBound = N;
lowerBound = 0;
}
else {
upperBound = 2*N;
lowerBound = N;
}
for (index = lowerBound ; index < upperBound; index ++) {
if (lessThanN) {
if((numbers[index] >= N)){
System.out.print(index +" ");
}
} else {
if((numbers[index - N] < N)){
System.out.print(index +" ");
}
}
}
}

void printAbsentNumbers(int[] numbers) {
int N = numbers.length;
for (int element : numbers) {
if ((element < 0) || (element > (2 * N - 1)))
throw new IllegalArgumentException();

}
findCountInSplit(numbers,N, true);
findCountInSplit(numbers,N, false);

for(int t:numbers ){
System.out.print(t);
}

}
}}

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

N cant be arbitrarily large so radix is possible

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

How about the working of this code ?

``````public void findMissingNumbers(int[] num) {
int j=0;
for(int i=0;i<2*num.length;){
if(num[j] == i){
i = num[j]+1;
j++;
}
else{
while(i!=num[j]){
System.out.println(i);
i++;
}
}
}
}``````

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

How about working of this code ?

``````public void findMissingNumbers(int[] num) {
int j=0;
for(int i=0;i<2*num.length;){
if(num[j] == i){
i = num[j]+1;
j++;
}
else{
while(i!=num[j]){
System.out.println(i);
i++;
}
}
}
}``````

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

Python code:

``````def find_missing(lst, n):
lst.insert(0, -1)
lst.append(2*n)

print ",".join(["%d-%d" if item2 - item1 > 1 else "%d" \
for item1,item2 in zip(lst[:-1], lst[1:])])``````

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

I have a solution with time complexity o(n) and space complexity o(1).
Iterate all number from from 0 to 2*n-1(lets call it i) and compare each number with a[j](j start from 0). If current number matches with a[j] then increment j, otherwise output the number i(this one is the missing). If j goes beyond n then just output the number i.

``````#include<stdio.h>
main()
{
int arr[]={0,1,4,5};
// int arr[]={0,2,4};
// int arr[]={0};
// int arr[]={};
int n = sizeof(arr)/sizeof(arr[0]);
int i,j;
j=0;
for (i=0;i<2*n;i++)
{
if(j<n)
{
if(i == arr[j])
j++;
else
printf("%d,",i);
}
else
{
printf("%d,",i);
}
}
printf("\n");
}``````

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

I have a solution with time complexity o(n) and space complexity o(1).
Iterate the numbers from 0 to 2*n-1(lets call it i) and compare with a[j](j starts from 0). If i and a[j] matches then increment j, otherwise output the number i. If j goes beyond n then just output number i.

``````#include<stdio.h>
main()
{
int arr[]={0,1,4,5};
// int arr[]={0,2,4};
// int arr[]={0};
// int arr[]={};
int n = sizeof(arr)/sizeof(arr[0]);
int i,j;
j=0;
for (i=0;i<2*n;i++)
{
if(j<n)
{
if(i == arr[j])
j++;
else
printf("%d,",i);
}
else
{
printf("%d,",i);
}
}
printf("\n");
}``````

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

I have a solution with time complexity o(n) and space complexity o(1).
Iterate the numbers from 0 to 2*n-1(lets call it i) and compare with a[j](j starts from 0). If i and a[j] matches then increment j, otherwise output the number i. If j goes beyond n then just output number i.

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

I have a solution with time complexity o(n) and space complexity o(1).
Iterate the numbers from 0 to 2*n-1(lets call it i) and compare with a[j](j starts from 0). If i and a[j] matches then increment j, otherwise output the number i. If j goes beyond n then just output number i.

``````#include<stdio.h>
main()
{
int arr[]={0,1,4,5};
// int arr[]={0,2,4};
// int arr[]={0};
// int arr[]={};
int n = sizeof(arr)/sizeof(arr[0]);
int i,j;
j=0;
for (i=0;i<2*n;i++)
{
if(j<n)
{
if(i == arr[j])
j++;
else
printf("%d,",i);
}
else
{
printf("%d,",i);
}
}
printf("\n");
}``````

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

processing each element. Put in each index i, -1: if only i exists, -2, if both i and i + n exist, -3, if only i + n exists, and -4 if none exists.

``````int a[5] = {1 , 4 , 5 , 7, 2};
n = 5;

for (int i = 0; i < n; i++){
int temp = a[i];
while (temp >= 0 ){
int temp2 = -4;

int j = temp % n;
if (i == j ) {
if (temp == j)
a[i] = -1;
else
a[i] = -3;
break;
}

if (a[j] >= 0){
temp2 = a[j];
if (j == temp)
a[j] = -1;
else
a[j] = -3;
temp = temp2;
}else if (a[j] == -1 || a[j] == -3){
a[j] = -2;
break;
}else if (a[j] == -4){
if (j == temp)
a[j] = -1;
else
a[j] = -3;
break;
}

}
}

for (int i = 0; i < n; i++){
int temp = a[i];
switch(temp):
case -1:
cout << i + n << endl;
break;
case -2:
break;
case -3:
cout << i << endl;
break;
case -4:
cout << i << endl;
cout << i + n << endl;
break;
default:
cerr << “error in processing all the elements \n” ;

}``````

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

``````public int[] findMissing(int[] arr)
{
int tmp=0;
int start=0;
int fillIdx=0;
if(arr[0]!=0)
{
int end=arr[0];
for(int i=0;i<end;i++)
{
tmp=arr[i];
arr[i]=i;
start++;
}
}else
{
start++;
tmp=arr[0];
}
while(start<=arr.length-1 && fillIdx<arr.length-1)
{
if(arr[start]-tmp>1)
{
for(int i=tmp+1;i<arr[start];i++)
{
arr[fillIdx++]=i;
}
tmp=arr[start++];
}else
{
tmp=arr[start++];
}
}

for(int i=tmp+1; i<2*arr.length && fillIdx<arr.length)
{
arr[fillIdx++]=tmp

}
return arr;

}``````

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

Here is my solution, I have tested it and it works

Step I: Find missing numbers less than n
Loop through the array( i ), if (a[i] != i && i < n) => put i in the i'th position, and do the same for the item that was in the i'th position. This second loop ends either when you have an item that is in it's correct position or you see a number greater than n.

Step 2: Find missing numbers greater than or equal to numbers
Similar approach :)

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

here's the code

``````#include "stdafx.h"
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include<conio.h>

using namespace std;

int MissingNumbers( std::vector<int> * original_p, std::vector<int> * missing_p )
{
size_t n = original_p->size();

int current;
int temp;
size_t i;

for ( i = 0 ; i < n ; i++ )
{
current = original_p->at(i);

while ( 1 )
{
if ( ( current < n ) && ( original_p->at(current)!=current ) )
{
temp = original_p->at(current);
original_p->at(current) = current;
current = temp;
}
else
{
break;
}
}

if ( current >= n )
{
original_p->at(i) = current;
}
}

for ( i = 0 ; i < n ; i++ )
{
if ( original_p->at(i)!=i )
{
missing_p->push_back( i );
}
}

for ( i = 0 ; i < n ; i++ )
{
current = original_p->at(i);

while ( 1 )
{
if ( ( current >= n ) && ( original_p->at(current-n)!=current ) )
{
temp = original_p->at(current-n);
original_p->at(current-n) = current;
current = temp;
}
else
{
break;
}
}

if ( current < n )
{
original_p->at(i) = current;
}
}

for ( i = 0 ; i < n ; i++ )
{
if ( original_p->at(i)!=i+n )
{
missing_p->push_back( i+n );
}
}

return 0;
}

int _tmain(int argc, _TCHAR* argv[])
{
std::vector<int> Original;
std::vector<int> Missing;

int i,j,k,temp;

int x,y;

int array_size;

for ( i = 0 ; i < 100 ; i++ )
{
Original.clear();
Missing.clear();

array_size = rand()%5 + 3;

for ( j = 0 ; j < array_size ; j++ )
{
if ( rand()%2 )
{
Original.push_back(j);
}
else
{
Original.push_back(j+array_size);
}
}

//scramble

for ( k = 0 ; k < 100 ; k++ )
{
x = rand()%array_size;
y = rand()%array_size;

temp = Original[x];
Original[x] = Original[y];
Original[y] = temp;
}

//print original
cout << endl << "-----------------------" << endl << "Original  Array: " ;
for ( j = 0 ; j < array_size ; j++ )
{
cout << Original[j] << ", ";
}

cout << endl;

MissingNumbers( &Original, &Missing );

//Print Missing
cout << "Missing Numbers: " ;
for ( j = 0 ; j < array_size ; j++ )
{
cout << Missing[j] << ", ";
}
}

getch();
return 0;
}``````

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

and samples:

-----------------------
Original Array: 0, 5, 3, 6,
Missing Numbers: 1, 2, 4, 7,
-----------------------
Original Array: 3, 12, 8, 13, 11, 9, 0,
Missing Numbers: 1, 2, 4, 5, 6, 7, 10,
-----------------------
Original Array: 2, 0, 4,
Missing Numbers: 1, 3, 5,
-----------------------
Original Array: 8, 9, 13, 5, 0, 11, 3,
Missing Numbers: 1, 2, 4, 6, 7, 10, 12,
-----------------------
Original Array: 2, 3, 4,
Missing Numbers: 0, 1, 5,
-----------------------
Original Array: 4, 7, 5, 6,
Missing Numbers: 0, 1, 2, 3,
-----------------------
Original Array: 0, 5, 4,
Missing Numbers: 1, 2, 3,
-----------------------
Original Array: 3, 2, 4, 5,
Missing Numbers: 0, 1, 6, 7,
-----------------------
Original Array: 4, 1, 7, 2,
Missing Numbers: 0, 3, 5, 6,
-----------------------
Original Array: 7, 11, 6, 4, 9, 8,
Missing Numbers: 0, 1, 2, 3, 5, 10,
-----------------------
Original Array: 0, 11, 9, 2, 4, 7,
Missing Numbers: 1, 3, 5, 6, 8, 10,
-----------------------
Original Array: 4, 6, 2, 0, 3,
Missing Numbers: 1, 5, 7, 8, 9,
-----------------------
Original Array: 4, 0, 5,
Missing Numbers: 1, 2, 3,
-----------------------
Original Array: 0, 7, 6, 5,
Missing Numbers: 1, 2, 3, 4,
-----------------------
Original Array: 3, 2, 6, 5, 9,
Missing Numbers: 0, 1, 4, 7, 8,
-----------------------
Original Array: 0, 6, 7, 8, 9,
Missing Numbers: 1, 2, 3, 4, 5,
-----------------------
Original Array: 8, 13, 5, 3, 7, 11, 9,
Missing Numbers: 0, 1, 2, 4, 6, 10, 12,
-----------------------
Original Array: 6, 7, 5, 4, 3,
Missing Numbers: 0, 1, 2, 8, 9,
-----------------------
Original Array: 8, 1, 0, 4, 2,
Missing Numbers: 3, 5, 6, 7, 9,
-----------------------
Original Array: 8, 9, 5, 10, 0, 7,
Missing Numbers: 1, 2, 3, 4, 6, 11,
-----------------------
Original Array: 0, 5, 2, 3,
Missing Numbers: 1, 4, 6, 7,
-----------------------
Original Array: 1, 0, 2,
Missing Numbers: 3, 4, 5,
-----------------------
Original Array: 7, 5, 10, 6, 3, 2,
Missing Numbers: 0, 1, 4, 8, 9, 11,
-----------------------
Original Array: 2, 5, 6, 4, 3,
Missing Numbers: 0, 1, 7, 8, 9,
-----------------------
Original Array: 4, 6, 1, 2, 9, 11,
Missing Numbers: 0, 3, 5, 7, 8, 10,
-----------------------
Original Array: 7, 0, 6, 1,
Missing Numbers: 2, 3, 4, 5,
-----------------------
Original Array: 3, 4, 5,
Missing Numbers: 0, 1, 2,
-----------------------
Original Array: 6, 8, 5, 4, 2,
Missing Numbers: 0, 1, 3, 7, 9,
-----------------------
Original Array: 0, 8, 7, 6, 4,
Missing Numbers: 1, 2, 3, 5, 9,
-----------------------
Original Array: 3, 2, 1,
Missing Numbers: 0, 4, 5,
-----------------------
Original Array: 11, 12, 3, 2, 13, 1, 7,
Missing Numbers: 0, 4, 5, 6, 8, 9, 10,
-----------------------
Original Array: 1, 7, 4, 5, 8,
Missing Numbers: 0, 2, 3, 6, 9,
-----------------------
Original Array: 6, 4, 5, 7,
Missing Numbers: 0, 1, 2, 3,
-----------------------
Original Array: 4, 0, 2,
Missing Numbers: 1, 3, 5,
-----------------------
Original Array: 2, 0, 4,
Missing Numbers: 1, 3, 5,
-----------------------
Original Array: 3, 12, 6, 9, 11, 8, 0,
Missing Numbers: 1, 2, 4, 5, 7, 10, 13,
-----------------------
Original Array: 0, 4, 5,
Missing Numbers: 1, 2, 3,
-----------------------
Original Array: 1, 11, 2, 3, 10, 0,
Missing Numbers: 4, 5, 6, 7, 8, 9,
-----------------------
Original Array: 9, 8, 7, 4, 5, 6,
Missing Numbers: 0, 1, 2, 3, 10, 11,
-----------------------
Original Array: 3, 4, 1, 2,
Missing Numbers: 0, 5, 6, 7,
-----------------------
Original Array: 0, 5, 1,
Missing Numbers: 2, 3, 4,
-----------------------
Original Array: 4, 5, 2, 3,
Missing Numbers: 0, 1, 6, 7,
-----------------------
Original Array: 4, 2, 3,
Missing Numbers: 0, 1, 5,
-----------------------
Original Array: 10, 8, 7, 9, 6, 11,
Missing Numbers: 0, 1, 2, 3, 4, 5,
-----------------------
Original Array: 3, 5, 4,
Missing Numbers: 0, 1, 2,
-----------------------
Original Array: 3, 12, 11, 9, 0, 8, 13,
Missing Numbers: 1, 2, 4, 5, 6, 7, 10,
-----------------------
Original Array: 2, 1, 7, 4,
Missing Numbers: 0, 3, 5, 6,
-----------------------
Original Array: 10, 1, 7, 6, 2, 12, 4,
Missing Numbers: 0, 3, 5, 8, 9, 11, 13,
-----------------------
Original Array: 4, 0, 5, 7, 8, 9,
Missing Numbers: 1, 2, 3, 6, 10, 11,
-----------------------
Original Array: 13, 1, 11, 9, 10, 7, 5,
Missing Numbers: 0, 2, 3, 4, 6, 8, 12,
-----------------------
Original Array: 4, 5, 3,
Missing Numbers: 0, 1, 2,
-----------------------
Original Array: 7, 8, 6, 3, 10, 11,
Missing Numbers: 0, 1, 2, 4, 5, 9,
-----------------------
Original Array: 1, 3, 6, 10, 8, 11,
Missing Numbers: 0, 2, 4, 5, 7, 9,
-----------------------
Original Array: 1, 0, 11, 2, 4, 9,
Missing Numbers: 3, 5, 6, 7, 8, 10,
-----------------------
Original Array: 6, 7, 0, 1,
Missing Numbers: 2, 3, 4, 5,
-----------------------
Original Array: 1, 0, 2, 3,
Missing Numbers: 4, 5, 6, 7,
-----------------------
Original Array: 2, 8, 5, 6, 3, 11, 7,
Missing Numbers: 0, 1, 4, 9, 10, 12, 13,
-----------------------
Original Array: 9, 13, 5, 7, 1, 3, 11,
Missing Numbers: 0, 2, 4, 6, 8, 10, 12,
-----------------------
Original Array: 7, 8, 0, 6, 9,
Missing Numbers: 1, 2, 3, 4, 5,
-----------------------
Original Array: 6, 4, 7, 2, 3, 11,
Missing Numbers: 0, 1, 5, 8, 9, 10,
-----------------------
Original Array: 0, 4, 5,
Missing Numbers: 1, 2, 3,
-----------------------
Original Array: 1, 9, 10, 5, 0, 2,
Missing Numbers: 3, 4, 6, 7, 8, 11,
-----------------------
Original Array: 6, 5, 7, 3, 4,
Missing Numbers: 0, 1, 2, 8, 9,
-----------------------
Original Array: 5, 4, 6, 1, 2, 3, 7,
Missing Numbers: 0, 8, 9, 10, 11, 12, 13,
-----------------------
Original Array: 8, 2, 5, 4, 1,
Missing Numbers: 0, 3, 6, 7, 9,
-----------------------
Original Array: 6, 8, 7, 2, 5, 3, 4,
Missing Numbers: 0, 1, 9, 10, 11, 12, 13,
-----------------------
Original Array: 4, 3, 2, 5,
Missing Numbers: 0, 1, 6, 7,
-----------------------
Original Array: 7, 4, 6, 0, 8,
Missing Numbers: 1, 2, 3, 5, 9,
-----------------------
Original Array: 5, 3, 4,
Missing Numbers: 0, 1, 2,
-----------------------
Original Array: 1, 6, 0, 3,
Missing Numbers: 2, 4, 5, 7,
-----------------------
Original Array: 5, 0, 1,
Missing Numbers: 2, 3, 4,
-----------------------
Original Array: 5, 1, 3,
Missing Numbers: 0, 2, 4,
-----------------------
Original Array: 9, 7, 3, 5, 1,
Missing Numbers: 0, 2, 4, 6, 8,
-----------------------
Original Array: 3, 0, 2, 1,
Missing Numbers: 4, 5, 6, 7,
-----------------------
Original Array: 12, 2, 1, 11, 13, 10, 0,
Missing Numbers: 3, 4, 5, 6, 7, 8, 9,
-----------------------
Original Array: 4, 5, 3,
Missing Numbers: 0, 1, 2,
-----------------------
Original Array: 4, 6, 2, 1, 10, 5, 7,
Missing Numbers: 0, 3, 8, 9, 11, 12, 13,
-----------------------
Original Array: 4, 3, 2,
Missing Numbers: 0, 1, 5,
-----------------------
Original Array: 0, 13, 1, 12, 10, 11, 2,
Missing Numbers: 3, 4, 5, 6, 7, 8, 9,
-----------------------
Original Array: 3, 6, 5, 7, 2, 10,
Missing Numbers: 0, 1, 4, 8, 9, 11,
-----------------------
Original Array: 4, 0, 2,
Missing Numbers: 1, 3, 5,
-----------------------
Original Array: 12, 2, 6, 7, 1, 11, 10,
Missing Numbers: 0, 3, 4, 5, 8, 9, 13,
-----------------------
Original Array: 0, 4, 2, 5, 7, 3,
Missing Numbers: 1, 6, 8, 9, 10, 11,
-----------------------
Original Array: 3, 2, 1, 9, 0,
Missing Numbers: 4, 5, 6, 7, 8,
-----------------------
Original Array: 1, 5, 3, 8, 6, 10,
Missing Numbers: 0, 2, 4, 7, 9, 11,
-----------------------
Original Array: 0, 2, 1,
Missing Numbers: 3, 4, 5,
-----------------------
Original Array: 0, 5, 1,
Missing Numbers: 2, 3, 4,
-----------------------
Original Array: 8, 7, 9, 5, 6,
Missing Numbers: 0, 1, 2, 3, 4,
-----------------------
Original Array: 3, 7, 6, 8, 10, 5,
Missing Numbers: 0, 1, 2, 4, 9, 11,
-----------------------
Original Array: 8, 7, 10, 2, 6, 11, 5,
Missing Numbers: 0, 1, 3, 4, 9, 12, 13,
-----------------------
Original Array: 4, 8, 0, 5, 7, 3,
Missing Numbers: 1, 2, 6, 9, 10, 11,
-----------------------
Original Array: 0, 7, 6, 4, 8,
Missing Numbers: 1, 2, 3, 5, 9,
-----------------------
Original Array: 5, 1, 0,
Missing Numbers: 2, 3, 4,
-----------------------
Original Array: 10, 6, 2, 3, 11, 1,
Missing Numbers: 0, 4, 5, 7, 8, 9,
-----------------------
Original Array: 8, 13, 9, 3, 0, 4, 12,
Missing Numbers: 1, 2, 5, 6, 7, 10, 11,
-----------------------
Original Array: 0, 9, 1, 4, 10, 6, 12,
Missing Numbers: 2, 3, 5, 7, 8, 11, 13,
-----------------------
Original Array: 7, 5, 0, 2,
Missing Numbers: 1, 3, 4, 6,
-----------------------
Original Array: 4, 5, 3,
Missing Numbers: 0, 1, 2,
-----------------------
Original Array: 2, 1, 5, 4, 0, 9,
Missing Numbers: 3, 6, 7, 8, 10, 11,
-----------------------
Original Array: 0, 6, 9, 2, 8,
Missing Numbers: 1, 3, 4, 5, 7,

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

Use bitwise OR.
First: Assuming n <= 16 (we'll talk about n>16 after, but it's easier to understand with this constraint.

1) initialize int x = 0
2) iterate through input array, and for each a[i] just do: x = x | (1 << a[i]);
Ex: if a[i] == 3, then x = x | (1 << 3), which puts a 1 in the 4th bit.
3) At the end of iteration, there will be a 1 in each bit that exists and a 0 in each bit that is missing. O(n)
4) Build the answer array (which you already know is size n) by x&(1 << i) in a for loop with i = 0 to n. This has the added bonus that the resulting array is sorted. O(n)

Final time complexity: O(2n) = O(n)
Final space complexity: O(1)

5) Instead of step 1, initialize an int[] x = new int[n/16]

Should be fairly simple to write code to do the above

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

int[] input = new int[] {0, 2, 4}; //given input, range should have [0->5]

int indexInInput = 0;

for(int i = 0; i < 2 * input.Length; i++)
{
if(i = input[indexInInput])
{
//skip
indexInInput++;
}
else
{
Console.WriteLine(i);
}

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

Time: O(n), Space: O(n)

``````public static int[] getMissingArr(int[] a) {
if (a == null) {
return null;
}
int n = a.length * 2;

boolean present[] = new boolean[n];
int i = 0, j = 0;
int numMissing = n;

for (i = 0; i < a.length; i++) {
present[a[i]] = true;
numMissing--;
}

i = 0;
j = 0;
int[] r = new int[numMissing];
while(i < present.length && j < r.length) {
if (!present[i]) {
r[j] = i;
j++;
}
i++;
}
return r;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````public void printNotInArr(int[] arr) {

if(arr == null)
return null;

int len = arr.length;
int max = 2 * len;

for(int i = 0; i < len; i++) {
System.out.println(max - arr[i] - 1);
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````public void printNotInArr(int[] arr) {

if(arr == null)
return null;

int len = arr.length;
int max = 2 * len;

for(int i = 0; i < len; i++) {
System.out.println(max - arr[i] - 1);
}
}``````

Comment hidden because of low score. Click to expand.
-2
of 2 vote

``````vector<int> findMissing(vector<int> arr, int n){

priority_queue(int, vector<int>, greater<int>) min_heap;

vector<int> result;

for(int i=0; i<n; i++){
min_heap.push(arr[i]);
}

int prev = 0;

while(!min_heap.empty()){

int temp = min_heap.top();
min_heap.pop();

while(temp-prev > 0){
result.push_back(++prev);
}
prev = temp;

}

//Add all elements that are greater than last element but smaller than 2*n
while(prev < 2*n -1){
result.push_back(++prev);
}

return result;

}``````

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

Space complexity is not O(1)

Comment hidden because of low score. Click to expand.
-2
of 2 vote

``````vector<int> findMissing(vector<int> arr, int n){

priority_queue(int, vector<int>, greater<int>) min_heap;

vector<int> result;

for(int i=0; i<n; i++){
min_heap.push(arr[i]);
}

int prev = 0;

while(!min_heap.empty()){

int temp = min_heap.top();
min_heap.pop();

while(temp-prev > 0){
result.push_back(++prev);
}
prev = temp;

}

//Add all elements that are greater than last element but smaller than 2*n
while(prev < 2*n -1){
result.push_back(++prev);
}

return result;

}``````

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.