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.

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& 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