Microsoft Interview Question for Software Developers


Country: United States




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

This is a recursive solution.

public class Main {

	public static void main(String[] args) {
		int[] array = {1,2,3,5,8,7,6,9,5,7,3,0,5};int[] subArray = {5,7};
		printMinLength(array,subArray);
	}
	
	public static void printMinLength(int[] array, int[] subArray){
		int minLength = Integer.MAX_VALUE, startIndex = -1;
		for(int i=0; i<array.length-subArray.length; i++){
			if(array[i] == subArray[0]){
				int end = find(array,i,subArray,0);
				if(end != -1 && minLength > end-i+1){
					minLength = end-i+1;
					startIndex = i;
				}
			}
		}
		if(startIndex != -1){
			int[] answer = Arrays.copyOfRange(array, startIndex, startIndex+minLength);
			System.out.println("minimum length = "+minLength+"; start index = "+startIndex);
			System.out.println(Arrays.toString(answer));
		}else{
			System.out.println("No solution exists.");
		}
	}
	
	public static int find(int[] array, int startArray, int[] subArray, int startSubArray){
		if(startSubArray == subArray.length)return startArray-1;
		if(subArray.length - startSubArray > array.length - startArray )return -1;
		if(array[startArray] == subArray[startSubArray]){
			return find(array,startArray+1,subArray,startSubArray+1);
		}else{
			return find(array,startArray+1,subArray,startSubArray);
		}
	}
}

- settyblue July 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

O(n) solution provided.
Keeping track of an index range [start, end] and counts of excessive integers
within the range in a hash map.
The negative count value means the corresponding integers are
absent (or insufficient) in the current range.
The range head is advanced when there is any integers with negative counter (i.e., insufficient),
while tail is advanced when all of integers in sub-array are contained in the range
(i.e., all of count values are non negative)
The variable numNeed is used to ease the decision which pointer to move.

Assumed any integer (>= 10 or < 0) can be included in the array and
same integer can appear in the sub-array multiple times.

pair<int,int> smallestSubsubay(vector<int> arr, vector<int> sub)
{
  unordered_map<int,int> S;
  int numNeed = 0;
  pair<int,int> minRange = make_pair(-1, arr.size());

  for(int i = 0; i < sub.size(); i++){
    S[sub[i]]--;
    if(S[sub[i]] == -1)
      numNeed++;
  }

  int start = 0;
  int end = -1;

  while(start < arr.size()) {
    if(numNeed > 0){
      end++;
      if(end >= arr.size())
        break;

      S[arr[end]]++;
      if(S[arr[end]] == 0)
        numNeed--;
    }
    else {
      S[arr[start]]--;
      if(S[arr[start]] == -1)
        numNeed++;
      start++;
    }

    if(numNeed == 0 &&
        end - start < minRange.second - minRange.first){
      minRange = make_pair(start, end);
    }
  }

  return minRange;
}

- linuxchain October 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C++ solution

#include <vector>
#include <string>
#include <iostream>
using namespace std;

vector<int> _findMinSubArray(int *S, int *A, int i, int j, int mbf);
#define ARRAY_SIZE(array) (sizeof((array))/sizeof((array[0])))
int main()
{
	int S[] = {1,2,3 ,5,8,7,6,9,5,7,3,0,5 };
	int A[] = {5,5};
	int mbf = 0;
	vector<int> out = _findMinSubArray(S, A, ARRAY_SIZE(S)-1, ARRAY_SIZE(A)-1, 0);
	cout<<"length = "<<out[1]<<" index = "<<out[0]<<endl;
	return 0;
}

vector<int> _findMinSubArray(int *S, int *A, int i, int j, int mbf) {
	vector<int> r1(3,0);
	vector<int> r2(3,0); // r[0] is pos, r[1] is len, r[2] is if_found=true/false/0/1
	static int end=0,start=0;
	
	if (i<0 || j<0) {
		return {0,0,0};
	}

	if (S[i] == A[j]) {
		if (j==0) {
			return {i, 1, 1};
		} else {	
			r1 = _findMinSubArray(S,A,i-1,j-1,1);	
			r1[1] += 1;
		}
	}
	r2 = _findMinSubArray(S,A,i-1,j,mbf);
	if (mbf) r2[1] += 1;
	
	if (r1[2] && !r2[2]) {
		return r1;
	} else if (!r1[2] && r2[2]) {
		return r2;
	} else if (r1[2] && r2[2]) {
		return ((r2[1]>r1[1])?r1:r2);
	} else {
		return {0,0,0};
	}
}

Becomes efficient after adding DP (storing function outputs)

- razorm4 July 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//pair<index, length>
pair<int, int> findMinimalLength(int A[], int m, int S[], int n)
{
	pair<int, int> ret(-1, INT_MAX);
	if (m == 0 || n == 0)
		return ret;
	unordered_map<int, int> mpSub;
	int i;
	for (i = 0; i < n; i++)
		mpSub[S[i]] = 0;

	int startIndex = -1, len = -1;
	unordered_map<int, int>::iterator itr;
	for (i = 0; i < m; i++)
	{
		if (mpSub.find(A[i]) != mpSub.end())
		{
			if (startIndex == -1 || mpSub[A[i]] == 1)
			{
				startIndex = i;
				if (mpSub[A[i]] == 1)
				{
					for (itr = mpSub.begin(); itr != mpSub.end(); itr++)
						itr->second = 0;
				}
				mpSub[A[i]] = 1;	
			}else
			{
				mpSub[A[i]] = 1;
				for (itr = mpSub.begin(); itr != mpSub.end(); itr++)
				{
					if (itr->second != 1)
						break;
				}
				if (itr == mpSub.end())
				{
					if (len == -1 || len > i - startIndex + 1)
					{
						len = i - startIndex + 1;
						ret = make_pair(startIndex, len);
					}
					for (itr = mpSub.begin(); itr != mpSub.end(); itr++)
						itr->second = 0;
					startIndex = -1;
				}
			}
		}
	}

	return ret;
}

- LANorth July 31, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Short and Simple Python solution with Backtracking:

def getMinLengthSubsequence(nums, sub):
    def search(nums, sub, startn, starts):
        if starts >= len(nums) or startn >= len(nums):
            return -1, -1
        for idx in range(startn, len(nums)):
            if nums[idx] == sub[starts]:
                if starts == len(sub) - 1:
                    return idx, idx
                start, end = search(nums, sub, idx + 1, starts + 1)
                if start >= 0:
                    return idx, end
        return -1, -1

    start, end = 0, float('inf')
    for idx in range(len(nums)):
        if sub and nums[idx] == sub[0]:
            startx, endx = search(nums, sub, idx, 0)
            if startx != -1 and endx - startx < end - start:
                start, end = startx, endx
    return start, end

- frestuc August 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def find_suba(arr,subarr):
	dict = {}
	for i in subarr:
		dict[i] = []
	for i in range(len(arr)):
		if arr[i] in dict:
			dict[arr[i]].append(i)
	for i in range(len(subarr)):
		globals()['var%s' % i] = dict[subarr[i]]
	diff = [globals()['var%s' % (len(subarr)-1)][i]-var0[i] for i in range(len(var0))]
	idx = diff.index(min(diff))
	return diff[idx]+1, arr[var0[idx]: globals()['var%s' % (len(subarr)-1)][idx]+1]

- montu August 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def find_suba(arr,subarr):
	dict = {}
	for i in subarr:
		dict[i] = []
	for i in range(len(arr)):
		if arr[i] in dict:
			dict[arr[i]].append(i)
	for i in range(len(subarr)):
		globals()['var%s' % i] = dict[subarr[i]]
	diff = [globals()['var%s' % (len(subarr)-1)][i]-var0[i] for i in range(len(var0))]
	idx = diff.index(min(diff))
	return diff[idx]+1, var0[idx]

- montu August 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's a simple iterative solution with comments for better understanding

private static int[] findSubArrayPos(int[] a1, int[] a2){
		int[] out = new int[2];
		out[0] = -1;
		out[1] = -1;
		//error case - either of the arrays is null; sub array length is more than main array
		if(null == a1 || null == a2 || a2.length > a1.length){
			return out;
		}
		
		int startIndex = 0;
		int j = startIndex;
		for(int i=0;i<a1.length && startIndex == 0;i++){
			if(a1[i] != a2[startIndex]){
				continue;
			}
			else{
				//first element of subArray is matched; iterate over the rest and check
				startIndex = i;
				while(j < a2.length && i < a1.length){
					if(a2[j] != a1[i]){
						//part of subArray is not mateched; re-initialize the startIndex,j to 0 and look further
						startIndex = 0;
						j = startIndex;
						break;
					}
					j++;
					i++;
				}
			}
		}
		//entire subArray is matched!
		if(j == a2.length){
			out[0] = startIndex;
			out[1] = j;
		}
		return out;
	}

- Vinoth September 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's a simple iterative solution (java) with comments for better understanding.

private static int[] findSubArrayPos(int[] a1, int[] a2){
		int[] out = new int[2];
		out[0] = -1;
		out[1] = -1;
		//error case - either of the arrays is null; sub array length is more than main array
		if(null == a1 || null == a2 || a2.length > a1.length){
			return out;
		}
		
		int startIndex = 0;
		int j = startIndex;
		for(int i=0;i<a1.length && startIndex == 0;i++){
			if(a1[i] != a2[startIndex]){
				continue;
			}
			else{
				//first element of subArray is matched; iterate over the rest and check
				startIndex = i;
				while(j < a2.length && i < a1.length){
					if(a2[j] != a1[i]){
						//part of subArray is not mateched; re-initialize the startIndex,j to 0 and look further
						startIndex = 0;
						j = startIndex;
						break;
					}
					j++;
					i++;
				}
			}
		}
		//entire subArray is matched!
		if(j == a2.length){
			out[0] = startIndex;
			out[1] = j;
		}
		return out;

}

- vinothatub September 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Dynamic programming:
Assuming we have array "a" w/ length n and subarray "sa" w/ length k.
At worst case we have O(nk) operations.

Idea:
Go via a and on each step calc closest position there starts best solution for sa[1]. For solution sa[1]sa[2]. and so on until sa[1]sa[2]...sa[k].

Example:

i = 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
a = 1  2  5  2  8  5  7  1  1  1  8  7  7  7  5  8  7
sa= 5  8  7
------------------------------------------------------
-1 -1 -1  2  2  2  5  5  5  5  5  5  5  5  5 14 14 14 
-1 -1 -1 -1 -1  2  2  2  2  2  2  5  5  5  5  5 14 14
-1 -1 -1 -1 -1 -1 -1  2  2  2  2  2  5  5  5  5  5 14
                      ^              ^              ^
                      solution 2, 5  |              solution 14, 3 and it is the best solution
                                     |
                                solution 5, 7 but we already have better

Hope you get the idea.

Code on python3

def find(a, sa):
    res = [-1] * len(sa)
    min_i = -1
    min_len = -1
    for i in range(len(a)):
        for j in range(len(sa)):
            if a[i] == sa[j]:
                res[j] = res[j - 1] if j > 0 else i
                if j == len(sa) - 1:
                    if min_len == -1 or min_len > i - res[j] + 1:
                        min_len = i - res[j] + 1
                        min_i = res[j]
        # print('{:3} {:3} {}'.format(a[i], i, res))

    return min_i, min_len

print(find([1,2,5,2,8,5,7,1,1,1,8,7,7,7,5,8,7], [5,8,7]))
print(find([1,2,5,2,2,8,5,1,1,7,1,8,7,7,7], [5,8,7]))
print(find([1,2,3,4,5], [1,2,3,4,5]))
print(find([1,2,3,4,5], [1,2,3,4,5,6]))

Output:

(14, 3)
(6, 7)
(0, 5)
(-1, -1)

- Sergey September 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int[] array = { 1, 2, 3, 5, 8, 7, 6, 9, 5, 7, 3, 0, 5 };
            int[] subArray = { 5, 7 };

            for (int i = 0; i < array.Length - 1; i++)
            {
                if (array[i] == subArray[0] && array[i + 1] == subArray[1])
                {
                    Console.WriteLine("Index is {0}", i);
                }
            }

Did i get it correct? What mistake have I made in this approach?

- Newbie December 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int[] array = { 1, 2, 3, 5, 8, 7, 6, 9, 5, 7, 3, 0, 5 };
            int[] subArray = { 5, 7 };

            for (int i = 0; i < array.Length - 1; i++)
            {
                if (array[i] == subArray[0] && array[i + 1] == subArray[1])
                {
                    Console.WriteLine("Minimum index is {0}", i);
                }
            }

Is this correct? Please respond

- Newbie December 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This looks to me like a KMP Algorithm but taking integers into consideration. Pattern is the SubArray and We have to find that pattern with index in the main Array. Code below:

int [] pat = {5,7};
int [] text = {1,2,3,5,8,7,6,9,5,7,3,0,5};



int a [] = new int[pat.length];
int j =0;
a[j] = 0;
for(int i =1;i< pat.length;i++) {

if(pat[i] == pat[j]) {
a[i] = j+1;
j++;
}

else {
if(j >0) {
j = a[j-1];
while(pat[j] != pat[i] && j >0)
{
j = a[j-1];
}

if(pat[j] == pat[i]) {
a[i] = j +1;
j++;
}
}
if(j==0)
a[i] = j;

}
}

//for(int i =0;i<a.length;i++)
//System.out.print(a[i] +"\t");

StringBuilder sb = new StringBuilder();

int count = 0;
int []index = new int[10];
j =0;
for(int i =0; i < text.length;i++){

if(pat[j] == text[i]){
//count++;
j++;
if(j == pat.length){
index[count] = i - pat.length+1;
System.out.println("Index:" + (i-pat.length+1));
count++;
j=0;
}
}

else {

if(j>0 && i >0) {
j = a[j-1];
i--;
}
else
{
j=0;
}}}

- Srikanth Raj April 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Python code. Traversing through large array.

def find_subarray(main_array, sub_array):
	start_index = 0
	end_index = 0
	current_length = 0
	min_length = 0
	min_length_start_index = 0
	
	for i in range(len(main_array)):
		if main_array[i] == sub_array[0]:
			start_index = i
		
		if main_array[i] == sub_array[1]:
			end_index = i

		if start_index < end_index:
			current_length = end_index - start_index

		if (current_length != 0 and min_length == 0) or (current_length < min_length):
			min_length = current_length
			min_length_start_index = start_index

	print "start index: {0}".format(min_length_start_index)
	print "length: {0}".format(min_length)


if __name__ == "__main__":

	# For example: Sub array [5,7] with minimum length 1 starts at index 17.
	main_array = [1,2,3,5,8,7,6,9,5,2,5,6,9,3,7,3,0,5,7,5,1,2,3,4,7]
	sub_array = [5,7]
	find_subarray(main_array, sub_array)

- NGandhi August 03, 2016 | 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