## Yahoo Interview Question for Software Engineer / Developers

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

generally solved by bit vector.

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

Good solution if k<<N

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

We can simply solve this using XOR technique.

a^a is always zero.

So we can initialize some variable say "value" as 1^2^3^....^k
And then for each element a[i] in the array do "value = value ^ a[i]"

So if initial array is {1,2,4} and K = 4
we'll do value = 1^2^3^4 ^ (1^2^4) = 3, which is the missing number.

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

Good solution if only one element is missing from 1 to K. But this solution won't work in case if multiple elements are missing in this range.

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

Create an array a[k]. Initiaize it to zero. Now for each number encountered increment the value of the array by 1 i.e a[number]++. After all the billion records are traced, run a loop till k and print the index of array for which the value is 0. Thus, in this way we get the missing numbers. Whole operation reuires O(n)time.

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

If k<<N, then make a boolean array of 'k' elements. Scan the N-sized array and keep setting the corresponding value in the k-array to true. Then scan the k-array and the false values are the missing values.

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

this question can be done in O(1) space and in O(n) time too

1.scan the array from 1 to n one by one and as soon as you get a number(check absolute values of numbers) go to its index position and if the value stored in it is positive then multiply it by -1.

this way all the nos. which are present between 1-k would be having negative values stored in their indices while the numbers which are missing would be having positive values stored in their indices.

travel the array again from 1-k and print the value of indices that have positive values stored in it.

this works fine here as there are only positive integers present here :)

and also we save memory which was otherwise wasted in creating either Boolean or even array of size k

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

how many numbers are missing?
if it is one, xor.

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

Xor wont work eg let the numbers be 1,3,4 and k is 4

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

There are several different solutions to the problem. Which one is better depends on how big the k is.

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

if i got the question correct then a number like
a=1000000000 t0 9999999999 so in this we have to just maintain an array of a[10]={0}
and then using modulo and division operator and mainting like
if
algo:
while(n)
{temp=n%10;
a[temp]=1;
n=n/10;
}
for(i=0;i<=9;i++)
{
if(!a[i])
{
printf("missing number");
}
}

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

Most of the above solutions are correct but the real catch lies in whether the problem is time-constrained or space-constrained. Array_sum or bit vector method concern space constraints ( O(n) vs 4-8bytes ), time constraint doesnt really matter since both methods take O(n) time. Can anybody think of a faster solution? say O(log n)?

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

A O(log n) approach would be near impossible. It can't be faster than O(n). One has to analyze all the elements at least once to determine which ones are missing.

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

O(log n) can be thought of if only 1 no is missing out of the given no from 1 to K.
By Binary Search.

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

If array is sorted and K < N:

{k(k+1)/2} - SumOf(1 to K-1),

Time complexcity: O(K)

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

If array is sorted and K < N:

{k(k+1)/2} - SumOf(1 to K-1),

Time complexity: O(K)

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

/// Using BitMap
#define SET_BIT(m, k) (m[k/8] |= (1 << (k % 8)))
#define IS_BIT_SET(m, k) (m[k/8] & (1 << (k % 8)))
#define CLR_BIT(m, k) (m[k/8] ^= (1 << (k % 8)))

int run()
{
const int ARRAY_SIZE = 1000;
int A[ARRAY_SIZE];
for(int i = 0; i < ARRAY_SIZE; i ++) A[i] = i + 1;
A[3] = 1; /// A[3] = 4, before
char * m = new char[ARRAY_SIZE/8 + 1];

memset(m, 0, ARRAY_SIZE/8 + 1);
for(int i = 0; i < ARRAY_SIZE; i ++) {
SET_BIT(m, A[i]);
}
for(int i = 1; i <= ARRAY_SIZE; i ++) {
if(IS_BIT_SET(m, i) == 0) printf("%d is missing\n", i);
}
delete [] m;
m = NULL;
return 0;
}

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

Please note that number lies between 1-k

1) store all the elements in array and find the sum of all array elements.
array_sum; /* Sum of all array elements */
2) sum = k * (k + 1); /* Sum of k elements */
3) missing_number = sum - array_sum;

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

yes This method is efficient if there is only one number missing in n natural numbers.

In case of more than 1 number we can use BitSet.

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

this method wont work. what if value of K is MAX storable value in variable ??

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

i dont think this would give you write solution if duplicacy is allowed among the numbers

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.