Write a function that takes in two sorted lists and outputs a sorted list that is their union.

Question

Sigiloso · Accepted Answer

Second part of merge sort. Don't answer with sort(a), etc. Anyone can do that...

def merge(A, B):
	i=0
	j=0
	sorted_list = []

	while i < len(A) and j < len(B):
		if A[i] <= B[j]:
			sorted_list.append(A[i])
			i += 1
		else:
			sorted_list.append(B[j])
			j += 1
			
	if i < len(A):
		sorted_list.extend(A[i:])
	elif j < len(B):
		sorted_list.extend(B[j:])	
		
	return sorted_list

TheProf · Answer

write 2 helpers: 1) INSERT(A, b) =  put element b within A in the sort order
2) DEL(A, a) = delete element a from A

Then do this recursion:
f(A,B) : if max(A) <= min(B)  return [A B]
            else { B = INSERT(B, max(a));
                      A = DEL(A, max(a);
                      f(A,B);
                     }

something like that. try coding and testing. I haven't.

Sigiloso · Answer

f(a,b) { return sort(unique(a,b)) }

TheProf · Answer

Oops, check/write a termination condition

Sigiloso · Answer

I assumed that we can not use any "sort" function and we want it with linear time.

so here it is:

def my_sort(list_a, list_b):
            if len(list_a) ==0:
                return list_b
            elif len(list_b) ==0:
                return list_a
            else:
                if list_a[-1] > list_b[-1]:
                    return( my_sort(list_a[0:-1], list_b) + [list_a.pop(-1)])
                else:
                    return(my_sort(list_a,list_b[:-1]) + [list_b.pop(-1)])

Sigiloso · Answer

google merge sort

Seyi · Answer

In SQL
SELECT List1
FROM Table1
UNION
SELECT List2
FROM Table2
ORDER BY List1, List2;

wp · Answer

On Python, you could do:

from sets import Set 

def merge_sort(a,b): 
    return sorted( Set(a).union(Set(b)) )

JC · Answer

def sorted_union(list1, list2):
    union=set(list1).union(set(list2))
    sorted_union=sorted(list(union))
    return sorted_union

Sigiloso · Answer

def sortedUnion(list1,list2):
	list3 = [x for x in list1 if x in list2]
	return sorted(list(set(list3)))

Meta

Pergunta de entrevista da empresa Meta

Respostas da entrevista

Empresas seguidas

Buscas de vagas