Microsoft

www.microsoft.com
Work in HR? Unlock Free Profile

# MicrosoftSoftware Development Engineer Interview Question (student candidate)

I interviewed in Redmond, WA and was asked:
"You have an array of length n consisting of the integers from 0 through n-1 exactly once each, except for one which is missing. Find the missing number. The numbers can be in any order."

Part of a Software Development Engineer Interview Review - one of 3,408 Microsoft Interview Reviews

0
of 0

This problem can be solved in two ways:

// 1st approach
- if the array can be modified, sort it
- go through the sorted array until you find an element which does not equal its index
- O(n logn) time + 0 space

int findMissing1(vector<int>& arr)
{
// sort the array
std::sort(arr.begin(), arr.end());

// all elements should equal to their index, except for the missing one
for (int i = 0; i < arr.size(); ++i)
if (i != arr[i])
return i;

// should not happen
return -1;
}

// 2nd approach
- else, create a set (or vector, etc.) which contains elems 0 through N (inclusive)
- iterate through the stack, erasing all of the arrays elements
- in the end, the stack will contain one element -- the missing one
- O(n) time + O(1) space

int findMissing2(const vector<int>& arr)
{
// create a set to hold ALL elements from 0 to N
std::set<int> numSet;
for (int i = 0; i < arr.size() + 1; ++i) // note +1
numSet.insert(i);

// now delete all arr's elements from the set
for (int i = 0; i < arr.size(); ++i)
numSet.erase(numSet.find(arr[i]));

// the remaining element is the missing one
return *numSet.begin();
}

- vs on Feb 18, 2013
7
of 7

/* getMissingNo takes array and size of array as arguments*/
int getMissingNo (int a[], int n)
{
int i, total;
total = (n+1)*(n+2)/2;
for ( i = 0; i< n; i++)
total -= a[i];
}

- Anonymous on Feb 18, 2013
0
of 0