Microsoft Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
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)
Why use a binary mask?
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
straightforward steps instead of using advanced recursion
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)
def permute_binary_mask(length):
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:
seen_permutes.add(p)
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
def mask_list(src_list, mask):
result = [src_list[i] for i in range(0, len(mask)) if mask[i]]
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)
for bin_mask in permute_binary_mask(list_len): # generate all possible binary masks
masked_list = mask_list(flat_list, bin_mask) # use this mask to generate only sorted list permutations
# not all sequences are valid. Verify that the sequence alternates sources
if verify_sequence(masked_list):
print ''
for item in masked_list:
print item,
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)
Why use a binary mask?
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
straightforward steps instead of using advanced recursion
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)
def permute_binary_mask(length):
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:
seen_permutes.add(p)
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
def mask_list(src_list, mask):
result = [src_list[i] for i in range(0, len(mask)) if mask[i]]
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)
for bin_mask in permute_binary_mask(list_len): # generate all possible binary masks
masked_list = mask_list(flat_list, bin_mask) # use this mask to generate only sorted list permutations
# not all sequences are valid. Verify that the sequence alternates sources
if verify_sequence(masked_list):
print ''
for item in masked_list:
print item,
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)
Why use a binary mask?
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
straightforward steps instead of using advanced recursion
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)
def permute_binary_mask(length):
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:
seen_permutes.add(p)
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
def mask_list(src_list, mask):
result = [src_list[i] for i in range(0, len(mask)) if mask[i]]
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)
for bin_mask in permute_binary_mask(list_len): # generate all possible binary masks
masked_list = mask_list(flat_list, bin_mask) # use this mask to generate only sorted list permutations
# not all sequences are valid. Verify that the sequence alternates sources
if verify_sequence(masked_list):
print ''
for item in masked_list:
print item,
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.
#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;
}
#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;
}
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]) {
matches.add(String.valueOf(arrA[position])+"-"+String.valueOf(arrB[countB]));
for(int _count = position; _count<arrA.length; _count++) {
if(arrA[_count] > arrB [countB] ) {
matches.add(String.valueOf(arrA[position])+"-"+String.valueOf(arrB[countB])+"-"+String.valueOf(arrA[_count]));
addElementsFromB(dictionary, matches, arrA[_count], arrA[position], 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()) {
matches.add(String.valueOf(elementA) +"-"+ String.valueOf(elementB) +"-"+ itr.next());
}
}
}
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();
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
namespace ConsoleApplication5
{
class Program
{
public static void printList(LinkedList<int> l)
{
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())
{
l.AddLast(a[i]);
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())
{
l.AddLast(b[i]);
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);
Console.ReadKey();
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
namespace ConsoleApplication5
{
class Program
{
public static void printList(LinkedList<int> l)
{
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())
{
l.AddLast(a[i]);
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())
{
l.AddLast(b[i]);
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);
Console.ReadKey();
}
}
}
The Question is not clear. Can you provide an example.
- DarkKnight July 28, 2015What is the expected solution for
10 20 30
5 15 20 30 35