## Microsoft Interview Question for Senior Software Development Engineers

Country: United States

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <iostream>
#include <vector>

using namespace std;

int Find(vector<int> const &a, int v, int l, int r)
{
if (l < 0 ||
r < 0 ||
l >= a.size() ||
r >= a.size() ||
l > r)
{
return -1;
}

int m = (l + r) / 2;
if (a[m] == v) {
return m;
}
if (a[m] < a[l]) {
if (a[m] < v &&
a[r] >= v)
{
return Find(a, v, m + 1, r);
} else {
return Find(a, v, l, m - 1);
}
} else if (a[m] > a[l]) {
if (a[m] > v &&
a[l] <= v)
{
return Find(a, v, l, m - 1);
} else {
return Find(a, v, m + 1, r);
}
} else {
int idx = Find(a, v, l, m - 1);
if (idx == -1) {
idx = Find(a, v, m + 1, r);
}
return idx;
}
}

int main(int argvc, char const **argv)
{
vector<int> a = {4, 5, 6, 1, 2, 3};
cout << Find(a, 5, 0, a.size() - 1) << "\n";
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple trick.
 Do a binary search to find lowest value index in array.
 Then just a regular binary search to look for target value, but use index from  to accommodate for rotation.

``````#include<iostream>
#include<vector>

using namespace std;
const int notFoundError = -1;
int findElement( const vector<int>& input, const int target )
{
// Do a binary search and find lowest element in array
int lo=0;
int hi = input.size()-1;

while( lo < hi)
{
int mid = lo + (hi- lo)/2;
if( input[mid] > input[hi] )
{
lo = mid+1;
}
else
{
hi = mid;
}
}

//  save index of minimum value
int minIndex = lo;

// reset lo and hi
lo = 0;
hi = input.size()-1;

// we do binary search for original element
while( lo <= hi)
{
int mid = lo + (hi- lo)/2;
int realMid = ( mid+ minIndex) % input.size();
if( target == input[realMid] )
{
return realMid;
}
else if( target > input[realMid] )
{
lo = mid+1;
}
else{
hi = mid-1;
}
}
return notFoundError;
}
int main()
{
vector<int> input({7,8,2,4,5, 6});
cout << findElement(input, 5);
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote
Binary search - O(log(n)) {{{ public static void main(String[] args) { int[] arr = {7, 8, 2, 4, 6}; int e = 6; search(arr, e, 0, arr.length-1); } //7 8 2 4 6 public static void search(int[] arr, int e, int l, int h){ if(l > h) return; int n = arr.length; while(l <= h){ int mid = (h-l)/2+l; if(e == arr[mid]){ System.out.println(mid); return; }else if(mid-1 >= 0 && mid+1 < n && arr[mid+1] < arr[mid-1] && e > arr[mid] && e > arr[n-1]){ h = mid-1; }else if(mid-1 >= 0 && mid+1 < n && arr[mid+1] < arr[mid-1] && e > arr[mid] && e < arr[n-1]){ l = mid+1; }else if(e < arr[mid]){ h = mid-1; }else{ l = mid+1; } } } }}
Comment hidden because of low score. Click to expand.
0
of 0 vote

Let A the original sorted array of length N and R the result of rotating A to the right K times, 0 < K <= N (if K = N the array didn't rotate at all). We can observe the mapping R[i] = A[(i + K) mod N], so if we know K, we can run a binary search on R mapping positions to A!

If R < R[N - 1], A didn't rotate, and we set K = N. Otherwise, R can be splitted in two halves A and B, such that every element in B is less than any element in A. K is the length of the half A.

We use binary search as follows with R as pivot to find K.

``````findK(R, N)
if R < R[N - 1]
return N

lo := 1
hi := N - 1
while lo <= hi
mid := (lo + hi) / 2;
if R[mid] > R
lo := mid + 1
else if R[mid - 1] >= R
return mid
else
hi := mid - 1``````

Binary search to find element would be as follows

``````findValue(R, N, value)
K := findK(R, N)
lo := 0
hi := N - 1
while lo <= hi
mid := (lo + hi) / 2
if R[(mid + K) % N] = value
return true
else if R[(mid + K) % N] < value
lo := mid + 1
else
hi := mid - 1

return false``````

Time complexity is O(log N) and O(1) extra space.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution in Java:

``````public class FindElementInSortedRotatedArray {
private static int findElement(int [] input, int target){
if(input == null || input.length == 0){
return -1;
}

int start = 0;
int end = input.length - 1;
int mid = (start + end)/2;

for(int i = 0; i < input.length; i++){

// check if start to mid of input array is sorted
if(input[start] <= input[mid]){

// check if target element lies between start and mid
if(input[start] <= target && target <= input[mid]){

// if target lies with start and mid, set end pointer to mid-1
end = mid - 1;
}
else{
start = mid + 1;
}
}
// then check if mid to end of input array is sorted
else {
if(input[mid] <= target && target <= input[end]){

// set start pointer to mid + 1
start = mid + 1;
}
else {
end = mid - 1;
}

}
}
return -1;
}

public static void main(String[] args) {
{
int array[] = { 56, 58, 67, 76, 21, 32, 37, 40, 45, 49 };
findElementUsingBinarySearchTest(array, 45);
}
}

private static void findElementUsingBinarySearchTest(int[] array, int num) {
System.out.println("Element " + num + " found at = " + findElement(array, num));
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static int binarySearchRotated(int [] arr, int val){
//calculate step count
int step = 1;
int i = 1;

while (arr[i]>=arr[i-1]){
step++;
i++;
}

//rotate back
step = arr.length - step;
rotate(arr,step);

//regular binary search
return binarySearchIter(arr,val) ;
}

public static int binarySearchIter(int [] arr, int val){
int low = 0, high = arr.length-1;
while (low <= high){

int mid = (low + high)/2;
if(arr[mid] == val){
return mid;
} else if(val < arr[mid]){
high = mid-1;
} else {
low = mid + 1;
}
}
return -1;
}

public static void reverse(int [] arr, int start, int end){
while (start < end){
int tmp = arr[end];
arr[end] = arr[start];
arr[start] = tmp;
end--;
start++;
}
}

public static void rotate(int [] arr, int step){
//rotate the array to the right by k steps
step %= arr.length;
reverse(arr,0,arr.length-1);
reverse(arr,0,step-1);
reverse(arr,step,arr.length-1);
}``````

Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More