## Microsoft Interview Question for Development Support Engineers

• -3

Country: India
Interview Type: Phone Interview

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

Cannot understand the question - Please re-state. What do you mean by " Find array b is found continuously in array a".

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

This is what I would have done.

- For each value in arrB, use binary search to find if value exists in arrA
- If any value does not exist in arrA, return false
- If all values exist:
- Find min of arrB
- Find max of arrB
- Find index in arrA at which min of arrB is present; let's call it minIndex
- Find index in arrA at which max of arrB is present; lets call it maxIndex
- If ((arrB.size() - 1) != (maxIndex - minIndex)), return false
- else return true

There might be some better way of solving this; suggestions are always welcomed.

Comment hidden because of low score. Click to expand.
0

Some correction should be applied for the last step as it will not work because of this condition 'another which is not sorted and have duplicates'

a = 1, 3, 3, 3, 2, 5, 6, 6, 6
b = 3, 3, 2, 5, 6

Comment hidden because of low score. Click to expand.
0

a is sorted dude....looks like ali is right. i only see one case, look for all min elements in array a. since it also can be a duplicate.

Comment hidden because of low score. Click to expand.
0

Ali- Your code will fail for below use case
a = 1,2,2,3,3,3,4,4,4,5
b = 2,4,3,3
((arrB.size() - 1) != (maxIndex - minIndex)), hence it will return false
But if you check all of arrB's element exist in arrA.

Comment hidden because of low score. Click to expand.
0

hii

Comment hidden because of low score. Click to expand.
0

@Jack read the question, return true if continous elements of b are present in a.

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

bnv\
km

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

Create hash of array b from ints to counts (occurrences in b).
Use sliding window approach on a where window size is size of b. As you encounter new values in a, keep a counter of how many you encounter before the value changes. When value changes, see if count encountered is the same as that in the hash. If not, toss out the current sliding window and start a new one.

The special case is when the value is the first or last in b. In this case, the count encountered in a must be >= that in b, but doesn't have to be the same.

Alternatively, convert the array a and b into arrays of arrays where for example, a.length = number of occurrences of a.
Ex. [1, 1, 1, 2, 2, 3, 3, 3] -> [[1, 1, 1], [2, 2], [3, 3, 3]]
Apply sliding window similar to before, except now you simply need to compare a[i] === b[i] && a[i].length === b[i].length. If this is false, restart the sliding window, otherwise continue.
This has the benefit of simplifying the sliding window when dealing with duplicate values.

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

``````As the first array is sorted,  so we don't need to binary search all elements of b in a. We can just (modified)bsearch first element of array b in array a and then can check if it continuously matches or not. Please point out if i am wrong or missing something important.

int bsearch(int a[],int l,int r,int e) {
if( (r-l) > 1 ){
int m = (l+r)/2;
if ( e < a[m] )
return bsearch(a,l,m-1,e);
return bsearch(a,m,r,e);
}
return ( (a[r] == e ) ? r : ( (a[l] == e) ? l : -1 ) );
}
bool check(int a[],int n,int b[],int m,int &f,int &l) {
int firstRightIndex = bsearch(a,0,n-1,b);
if( firstRightIndex == -1 ) {
return false;
}

int prev = b;
int i = 0,j;
while(b[i] == prev) i++;

if(firstRightIndex - i + 1 < 0 || a[ firstRightIndex - i + 1] != b ) {
cout << "out of Index "<<endl;
return false;
}

f = firstRightIndex - i + 1;

for(i=f,j=0;i<n && j<m;i++,j++) {
if( b[j] != a[i] )  {
cout << "Not proper subarray"<<endl;
return false;
}
}
l = i;
return true;
}

int main()
{
int a[] = {1,2,2,3,3,3,3,4,4,5,5,5,6,6,7,8};
int sz_a = sizeof(a)/sizeof(a);

int b[] = {1,2,4,5,5,5,6,6,7};
int sz_b = sizeof(b) / sizeof(b);
int f =-1,l = -1;
cout << "Result : "<< ( check( a, sz_a, b , sz_b , f ,l) ? "True" : "False")<<endl;

cout<<"Matched from "<<f<<" to "<<l<<endl;
cout<<"Matched array : ";
if( f != -1 && l != -1) {
for(int i=f;i<l;i++)
cout<<a[i]<<" ";
}
cout<<endl;

return 0;
}``````

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

i think the question is to figure out the longest subarray from second array which also an subarray of first array.
here is the solution of this problem

``````Assuming the Array A is sorted in non decreasing order
Figure out the sorted subarrays from Array B and check if they are also present in Array A.
i = 0, j = 0
For i from 0 to A.Size
If A[i] > A[i-1]
j++
else
if j > i
check if Array B[i,...j] is alos present in A[1,M]
if Yes, and j-i > currentMax then j-i is the current max size which is present upto this point
end
i = j;
end
end
Return CurrentMAx and I, J, which are correspond to max``````

Complexity : Space O(1)
Time : O(M*K) where K is number of sorted subarrays of A.

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.