Work in HR? Unlock Free Profile

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 [?]

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

Answers & Comments

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

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

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

- vs on Feb 18, 2013
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];
    return total;

- Anonymous on Feb 18, 2013
of 0

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

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.