Microsoft

www.microsoft.com
Engaged Employer

## Interview Question

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