Microsoft

  www.microsoft.com
  www.microsoft.com

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.
Answer

Interview Answer

2 Answers

0

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:

http://codercareer.blogspot.com/2013/02/no-37-missing-number-in-array.html

Harry on Feb 3, 2013
0

2) Here's a recursive solution:

#define NOT_FOUND -999999
int findMissing(const vector<int>& arr, int start, int end)
{
    //cout << "start: " << start << ", end: " << end;
    if (start >= end)
        return NOT_FOUND;

    int mid = (start+end)/2;
    //cout << ", mid: " << arr[mid] << endl;

    // if the prev. number (arr[mid-1]) does not equal to current # less one (arr[mid]-1), return current #
    if ((mid-1 >= 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.