Microsoft Interview Question: 1: Quite simple question, cal... | Glassdoor

Interview Question

Software Development Engineer Interview(Student Candidate) Redmond, WA

1: Quite simple question, calendar related calculation

 . 2: Something close to binary search, find the missing number from consecutive integers. e.g., 0, 1, 2, 4, 5, should return 3. A little tricky for boundary conditions. Another simple question but cannot remember. 3: Double linked list insert and delete, with some special conditions. Simple. Another OOD question. 4: Something like leetcode jump game. But the jump length depends on the last jump made. For example, in step N, the man jumped M, the next step he can jump M-1, M or M+1.

Interview Answer

2 Answers


To solve the second problem to find the missing number in a sorted array, you may find detailed analysis and solutions in the following blog:

Harry on Feb 3, 2013

2) Here's a recursive solution:

#define NOT_FOUND -999999
int findMissing(const vector& arr, int start, int end)
    //cout = end)
        return NOT_FOUND;

    int mid = (start+end)/2;
    //cout = 0) &&
        arr[mid-1] != arr[mid]-1)
    { return arr[mid]-1; }

    // if the next number (arr[mid+1]) does not equal to current # plus one (arr[mid]+1), return current #
    if ((mid+1 < arr.size()) &&
        arr[mid+1] != arr[mid]+1)
    { return arr[mid]+1; }

    int elem;

    // check left half
    elem = findMissing(arr, start, mid-1);
    if (elem != NOT_FOUND)
        return elem;

    // check right half
    elem = findMissing(arr, mid+1, end);
    if (elem != NOT_FOUND)
        return elem;

vs on Feb 18, 2013

Add Answers or Comments

To comment on this, Sign In or Sign Up.