Facebook Interview Question: Smallest missing natural numb... | Glassdoor

## Interview Question

Software Engineer Interview

# Smallest missing natural number in a linked list in linear

time without a hash table.

1

(sum of 1st n numbers) - (sum of values in linked list)
= n(n+1)/2 - (node1->data +...+noden->data)

Anonymous on Oct 4, 2013
0

There might be more than 1 missing numbers. Also, I suppose it is asking for O(1) space solution; otherwise, just use an array.
If these are the cases, assume there is "no duplicate" in the linked list (and ignore non-positive number,) consider the followings:

1/ first pass => Get the size of the linked list, say, n
2/ second pass => Split list into two, A and B, while A get all data n/2
3/ If the size of A O(n)

Anonymous on Nov 8, 2016
0

(cont'd)

3/ If the size of A O(n)

Anonymous on Nov 8, 2016
0

(cont'd, again. not sure why the comment section messed up)
3/ If the size of A is less than n/2, the missing number must be in A. Split A like in the second step.
4/ If the size of A is equal to n/2, the missing number must be in B. Split B.
Repeat 2 3 4 until base case.
Running time would be n + n/2 + n/4 ... => O(n)

Anonymous on Nov 8, 2016