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

- Alex October 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple trick.
[1] Do a binary search to find lowest value index in array.
[2] Then just a regular binary search to look for target value, but use index from [1] 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;
}

- mr.robot.fun.society October 31, 2017 | Flag Reply
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; } } } }} - sudip.innovates October 31, 2017 | Flag Reply
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[0] < 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[0] as pivot to find K.

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

  lo := 1
  hi := N - 1
  while lo <= hi
    mid := (lo + hi) / 2;
    if R[mid] > R[0]
      lo := mid + 1
    else if R[mid - 1] >= R[0]
      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.

- Anonymous November 01, 2017 | Flag Reply
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));
    }
}

- annu025 February 18, 2018 | Flag Reply
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);
    }

- dpslackbot January 22, 2019 | Flag Reply


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