Microsoft
3.6 of 5 7,478 reviews
www.microsoft.com Redmond, WA 5000+ Employees

Microsoft Software 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."
Add Tags [?]
Answer Flag Question

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

Answers & Comments

0
of 0
votes
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 Flag Response
7
of 7
votes
/* 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];
    return total;
}
- Anonymous on Feb 18, 2013 Flag Response
0
of 0
votes
I believe it should be total = (n-1)*(n)/2. The sum of the series 1 - n is (n*(n+1))/2. Subtract 1 since we are starting from zero and we get ((n-1)*(n))/2.
- Anonymous on Sep 18, 2013 Flag Response

To comment on this question, Sign In with Facebook or Sign Up


Tags are like keywords that help categorize interview questions that have something in common.

Glassdoor is your free inside look at Microsoft interview questions and advice. All interview reviews posted anonymously by Microsoft employees and interview candidates.