## 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);
}``````

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.

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