Microsoft Interview Question
Software DevelopersCountry: United States
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;
}
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)
//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;
}
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
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]
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]
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;
}
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;
}
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)
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?
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;
}}}
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)
This is a recursive solution.
- settyblue July 28, 2016