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

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

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)

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

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

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

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

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

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

}

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

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?

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

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

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

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.