## Microsoft Interview Question for Software Engineers

Country: United States
Interview Type: Phone Interview

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

The Question is not clear. Can you provide an example.
What is the expected solution for
10 20 30
5 15 20 30 35

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

when array A (first) is taken first then.
10 15
10 15 20 30
10 15 20 35
10 15 30 35
10 20
10 20 30 35
10 30
10 35
20 30
20 35
30 35
when array B (second) is taken first then.
5 10
5 10 15 20
5 10 15 30
5 10 20 30
5 20
5 30
15 20

These are all outputs for your test case.

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

If all A is smaller than all B, or all B is smaller than all A, there is only one possible array from any direction. If this is not the case, an exact answer depends on the specific arrays involved.

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

``````import itertools

'''
Example

list1 = [10, 20, 30]
list2 = [5, 15, 21]

Step 1:
Flatten the 2 lists into 1 sorted list.
This can be done in O(n) time where n = len(list1) + len(list2)

Step 2:
Go through all permutations where each element is either "in" or "out"
e.g. given the flattened list [3, 4] you would get
[3]
[4]
[3, 4]

This can be achieved by applying all permuations of a binary mask of length(n)
to the flattened list. This looks like the following:
[]			comes from mask --> [0, 0]
[3] 		comes from mask --> [1, 0]
[4] 		comes from mask --> [0, 1]
[3, 4] 	comes from mask --> [1, 1]

Step 3:
Not all sequences generated above will follow the invariant that
sequential elements must come from alternating lists. Therefore we
must check this invariant. This can be checked for each permutation in o(m) time
where m = len(permutation)

If you simply generated all permutations of the "flattened list" most would
violate the sorting invariant and wouldn't be worth checking. This would
consume a lot of extra time.

Final analysis:
It may not be the most efficient, but it is still fairly good, and follows

The following is implemented in Python
'''

class List_Item(object):
def __init__(self, value, source):
self.value = value
self.source = source

def __str__(self):
return str(self.value)

lists = []
for i in range(0, length):
seen_permutes = set()
tmp_list = [0 for j in range(0, i)] + [1 for j in range(0, length-i)]
for p in itertools.permutations(tmp_list, length):
if p not in seen_permutes:
yield p

# flatten the list into 1 long list
def flatten_lists(list1, list2):
list1_it = 0
list2_it = 0

flat_list = []
while list1_it < len(list1) or list2_it < len(list2):
if list2_it >= len(list2) or list1[list1_it] < list2[list2_it]:
flat_list.append(List_Item(list1[list1_it], 1))
list1_it += 1
else:
flat_list.append(List_Item(list2[list2_it], 2))
list2_it += 1

return flat_list

return result

def verify_sequence(src_list):
last_src = None
for item in src_list:
if last_src == item.source:
return False
else:
last_src = item.source

return True

####################
#				Main
####################

# Input lists
list1 = [10, 20, 30]
list2 = [5, 15, 21]

flat_list = flatten_lists(list1, list2)
list_len = len(flat_list)

# not all sequences are valid. Verify that the sequence alternates sources
print ''
print item,``````

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

``````import itertools

'''
Example

list1 = [10, 20, 30]
list2 = [5, 15, 21]

Step 1:
Flatten the 2 lists into 1 sorted list.
This can be done in O(n) time where n = len(list1) + len(list2)

Step 2:
Go through all permutations where each element is either "in" or "out"
e.g. given the flattened list [3, 4] you would get
[3]
[4]
[3, 4]

This can be achieved by applying all permuations of a binary mask of length(n)
to the flattened list. This looks like the following:
[]			comes from mask --> [0, 0]
[3] 		comes from mask --> [1, 0]
[4] 		comes from mask --> [0, 1]
[3, 4] 	comes from mask --> [1, 1]

Step 3:
Not all sequences generated above will follow the invariant that
sequential elements must come from alternating lists. Therefore we
must check this invariant. This can be checked for each permutation in o(m) time
where m = len(permutation)

If you simply generated all permutations of the "flattened list" most would
violate the sorting invariant and wouldn't be worth checking. This would
consume a lot of extra time.

Final analysis:
It may not be the most efficient, but it is still fairly good, and follows

The following is implemented in Python
'''

class List_Item(object):
def __init__(self, value, source):
self.value = value
self.source = source

def __str__(self):
return str(self.value)

lists = []
for i in range(0, length):
seen_permutes = set()
tmp_list = [0 for j in range(0, i)] + [1 for j in range(0, length-i)]
for p in itertools.permutations(tmp_list, length):
if p not in seen_permutes:
yield p

# flatten the list into 1 long list
def flatten_lists(list1, list2):
list1_it = 0
list2_it = 0

flat_list = []
while list1_it < len(list1) or list2_it < len(list2):
if list2_it >= len(list2) or list1[list1_it] < list2[list2_it]:
flat_list.append(List_Item(list1[list1_it], 1))
list1_it += 1
else:
flat_list.append(List_Item(list2[list2_it], 2))
list2_it += 1

return flat_list

return result

def verify_sequence(src_list):
last_src = None
for item in src_list:
if last_src == item.source:
return False
else:
last_src = item.source

return True

####################
#				Main
####################

# Input lists
list1 = [10, 20, 30]
list2 = [5, 15, 21]

flat_list = flatten_lists(list1, list2)
list_len = len(flat_list)

# not all sequences are valid. Verify that the sequence alternates sources
print ''
print item,``````

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

``````import itertools

'''
Example

list1 = [10, 20, 30]
list2 = [5, 15, 21]

Step 1:
Flatten the 2 lists into 1 sorted list.
This can be done in O(n) time where n = len(list1) + len(list2)

Step 2:
Go through all permutations where each element is either "in" or "out"
e.g. given the flattened list [3, 4] you would get
[3]
[4]
[3, 4]

This can be achieved by applying all permuations of a binary mask of length(n)
to the flattened list. This looks like the following:
[]			comes from mask --> [0, 0]
[3] 		comes from mask --> [1, 0]
[4] 		comes from mask --> [0, 1]
[3, 4] 	comes from mask --> [1, 1]

Step 3:
Not all sequences generated above will follow the invariant that
sequential elements must come from alternating lists. Therefore we
must check this invariant. This can be checked for each permutation in o(m) time
where m = len(permutation)

If you simply generated all permutations of the "flattened list" most would
violate the sorting invariant and wouldn't be worth checking. This would
consume a lot of extra time.

Final analysis:
It may not be the most efficient, but it is still fairly good, and follows

The following is implemented in Python
'''

class List_Item(object):
def __init__(self, value, source):
self.value = value
self.source = source

def __str__(self):
return str(self.value)

lists = []
for i in range(0, length):
seen_permutes = set()
tmp_list = [0 for j in range(0, i)] + [1 for j in range(0, length-i)]
for p in itertools.permutations(tmp_list, length):
if p not in seen_permutes:
yield p

# flatten the list into 1 long list
def flatten_lists(list1, list2):
list1_it = 0
list2_it = 0

flat_list = []
while list1_it < len(list1) or list2_it < len(list2):
if list2_it >= len(list2) or list1[list1_it] < list2[list2_it]:
flat_list.append(List_Item(list1[list1_it], 1))
list1_it += 1
else:
flat_list.append(List_Item(list2[list2_it], 2))
list2_it += 1

return flat_list

return result

def verify_sequence(src_list):
last_src = None
for item in src_list:
if last_src == item.source:
return False
else:
last_src = item.source

return True

####################
#				Main
####################

# Input lists
list1 = [10, 20, 30]
list2 = [5, 15, 21]

flat_list = flatten_lists(list1, list2)
list_len = len(flat_list)

# not all sequences are valid. Verify that the sequence alternates sources
print ''
print item,``````

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

I agree with everyone above. The question is not clear. Merging two sorted arrays to produce a sorted array can only be done in one way. If that is what we're trying to do, the merge step from mergesort is a simple algorithm to follow.

however, we will only end up with one possible array.

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

``````#include <iostream>
using namespace std;

int ans[1010];

void dfs (int *arr1, int* arr2, int s1, int s2, int e1, int e2, int now, int flag){
for (int i=0;i<now;i++)	printf ("%d ", ans[i]);
if (now)	printf ("\n");

if (flag == 0){
for (int i=s1;i<e1;i++){
if (i != s1 && arr1[i] == arr1[i - 1])	continue;
if (now == 0 || arr1[i] > ans[now-1]){
ans[now] = arr1[i];
dfs (arr1, arr2, i+1, s2, e1, e2, now + 1, flag ^ 1);
}
}
}
else{
for (int i=s2;i<e2;i++){
if (i != s2 && arr2[i] == arr2[i - 1])	continue;
if (now==0 || arr2[i] > ans[now-1]){
ans[now] = arr2[i];
dfs (arr1, arr2, s1, i+1, e1, e2, now + 1, flag ^ 1);
}
}
}
}
int main() {
int arr1[] = {2,10,15,30,43};
int arr2[] = {4,18,33};
int n = sizeof (arr1) / sizeof (arr1[0]);
int m = sizeof (arr2) / sizeof (arr2[0]);
dfs (arr1,arr2,0,0,n,m,0,0);
dfs (arr1,arr2,0,0,n,m,0,1);
return 0;``````

}

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

``````#include <iostream>
using namespace std;

int ans[1010];

void dfs (int *arr1, int* arr2, int s1, int s2, int e1, int e2, int now, int flag){
for (int i=0;i<now;i++)	printf ("%d ", ans[i]);
if (now)	printf ("\n");

if (flag == 0){
for (int i=s1;i<e1;i++){
if (i != s1 && arr1[i] == arr1[i - 1])	continue;
if (now == 0 || arr1[i] > ans[now-1]){
ans[now] = arr1[i];
dfs (arr1, arr2, i+1, s2, e1, e2, now + 1, flag ^ 1);
}
}
}
else{
for (int i=s2;i<e2;i++){
if (i != s2 && arr2[i] == arr2[i - 1])	continue;
if (now==0 || arr2[i] > ans[now-1]){
ans[now] = arr2[i];
dfs (arr1, arr2, s1, i+1, e1, e2, now + 1, flag ^ 1);
}
}
}
}
int main() {
int arr1[] = {2,10,15,30,43};
int arr2[] = {4,18,33};
int n = sizeof (arr1) / sizeof (arr1[0]);
int m = sizeof (arr2) / sizeof (arr2[0]);
dfs (arr1,arr2,0,0,n,m,0,0);
dfs (arr1,arr2,0,0,n,m,0,1);
return 0;
}``````

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

``````import java.util.*;

/*
1. Recurse through array A, until you reach the last element (let's say ith)
2. Find all element on the array B which are greater than ith element in A
3. Add those elements in a set, put that set (let's call it result set) in a Map (let's call it dictionary) where key is the ith element in A
4. Now, recusrion call goes back to the previous (i-1) th element in array A
5. Find an element in the array B which is greater than  (i - 1)th elemnt in A
6. If found, check if there in any elemnt in array A, from location (i-1) to arrayA.length
7. If found, let's say A[smallerThanB] add combination of A[i-1],element in B and result set of A[smallerThanB] in A to the result set of A[i-1]
also add   A[i-1],element in B and elemnt found in A to result set of A[i-1], put the whole thing in dictionary
8. Keep recursing
*/

class TestMatch {

public void findMatchedArray(int[] arrA, int[] arrB, int position, Map<Integer, Set<String>> dictionary) {

if(position == arrA.length ) {

return;

}

findMatchedArray(arrA, arrB, position + 1, dictionary);

Set<String> matches = new HashSet<String>();

for(int countB = 0; countB < arrB.length; countB++) {

if(arrA[position] < arrB[countB]) {

for(int _count = position; _count<arrA.length; _count++) {

if(arrA[_count] > arrB [countB] ) {

}
}
}
}

dictionary.put(arrA[position], matches);
}

private void addElementsFromB(Map<Integer, Set<String>> dictionary, Set<String> matches, int element, int elementA, int elementB) {

if(dictionary.containsKey(element)) {

Set<String> belongsToElement = dictionary.get(element);

Iterator itr = belongsToElement.iterator();

while(itr.hasNext()) {

}
}
}

public static void main(String [] args) {

Map<Integer, Set<String>> dictionary = new HashMap<Integer, Set<String>>();

new TestMatch().findMatchedArray(new int[] {10, 15, 25, 40}, new int[] {1, 5, 20, 30, 50}, 0, dictionary);

Iterator mapItr = dictionary.keySet().iterator();

while(mapItr.hasNext()) {

Set<String> set = dictionary.get((Integer)mapItr.next());

Iterator setItr = set.iterator();

while(setItr.hasNext()) {

System.out.print(setItr.next()+",");
}

System.out.println();
}
}

}``````

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

``````using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication5
{

class Program
{

{
foreach (int i in l)
{
Console.Write(i + " , ");
}
Console.WriteLine();
}

public static void printListByOrder(LinkedList<int> l, int[] a, int[] b, int ia, int ib, bool useA)
{

if (useA)
{
for(int i = ia; i < a.Length; i++)
{
if(l.Count == 0 || a[i] > l.Last())
{
if(l.Count > 1)
{
printList(l);
}

printListByOrder(l, a, b, i + 1, ib, !useA);
l.RemoveLast();
}
}
}
else
{
for (int i = ib; i < b.Length; i++)
{
if (l.Count == 0 || b[i] > l.Last())
{
if (l.Count > 1)
{
printList(l);
}

printListByOrder(l, a, b, ia, i + 1, !useA);
l.RemoveLast();
}
}
}

}
public static void printListByOrder(int[]a, int[] b,bool useFirst = true)
{
printListByOrder(new LinkedList<int>(), a, b, 0, 0, useFirst);
}

static void Main(string[] args)
{
int[] a = { 10, 20, 30 };
int[] b = { 5,15,20,30,35 };
printListByOrder(a, b,false);

}
}
}``````

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

``````using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication5
{

class Program
{

{
foreach (int i in l)
{
Console.Write(i + " , ");
}
Console.WriteLine();
}

public static void printListByOrder(LinkedList<int> l, int[] a, int[] b, int ia, int ib, bool useA)
{

if (useA)
{
for(int i = ia; i < a.Length; i++)
{
if(l.Count == 0 || a[i] > l.Last())
{
if(l.Count > 1)
{
printList(l);
}

printListByOrder(l, a, b, i + 1, ib, !useA);
l.RemoveLast();
}
}
}
else
{
for (int i = ib; i < b.Length; i++)
{
if (l.Count == 0 || b[i] > l.Last())
{
if (l.Count > 1)
{
printList(l);
}

printListByOrder(l, a, b, ia, i + 1, !useA);
l.RemoveLast();
}
}
}

}
public static void printListByOrder(int[]a, int[] b,bool useFirst = true)
{
printListByOrder(new LinkedList<int>(), a, b, 0, 0, useFirst);
}

static void Main(string[] args)
{
int[] a = { 10, 20, 30 };
int[] b = { 5,15,20,30,35 };
printListByOrder(a, b,false);

}
}
}``````

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

Congrats on providing the worst ever description of a question.

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

Merge into one array and pairs all possible array.

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

Merge into one array and pairs all possible values as arrays

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.