## Facebook Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

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

So, there are a couple approaches, and picking one without mentioning the others is likely a failure here.

First, I'd ask if there's any chance of a big value for K; if K will always be within a constant factor of N, O(K) == O(N).

If K is guaranteed to stay small, we can:

- look at all lists with items remaining to find the smallest element, O(K).
- pop it off it's current list , O(1).
- push it onto the merged list, O(1)
- repeat until all lists are finished; O(N).

The problem again is if O(K) == O(N), that's O(N ^ 2)... which isn't great.

If we can spend more memory on this, O(N) more memory, we can speed it up for that case.

- for each list K, push all nodes into a min-heap. O(N lg N)
- repeated pop items off the heap and add to a merged list. O(N lg N)

(Each individual pop is O(lg N) because it has to re-heap itself.)

You'd want to test this with empty lists, some empty lists, lists of different sizes, lists of size == 1, and a single list as input.

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

I don't think the min heap approach is cheaper if we consider what N really means here. The total number of nodes is M= K*N, correct?

So if you keep adding nodes to a min heap that is O(Log M) i.e. min-heapify. If you do a heap sort on the heap, you will need to build the heap which is O(M) and for every node, call into min-heapify which is O(Log M) and so the final result is O(MLogM) which is > O(M).

What am I missing here? Thoughts?

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

@tdot M is not basically K*N. Because min-heap height will never be more than K. So its basically NLog(K), where N is the maximum length of K arrays.

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

We can use min-heap with merge sort for this.

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

We can solve this with min-heap.

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

Question isn't clear if the resultant linked list needs to be sorted. Otherwise you can just directly merge the lists in O(k)

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

If the question is to make 1 singly linked list out of K lists, then it could be done thusly:

``````public static ListNode<T extends Comparable>{
ListNode next;
T value;
}

public static ListNode<T> mergeLists(ListNode<ListNode<T>> lists){
if(lists == null){
return null;
}
//build the head of the results
Object[] minObj = getMin(lists);
while(resultTail != null){
lists = (ListNode<ListNode<T>>)minObj[0];
minObj = getMin(lists);
resultTail.next = (ListNode<T>)minObj[1];
resultTail = resultTail.next;
}
}

private static Object[] getMin(ListNode<ListNode<T>> lists){
//[0] will be the modified list
//[1] will be the min
Object[] results = new Object[2];
if(lists == null){
return results;
}
ListNode<ListNode<T>> newListsTail = null;
ListNode<ListNode<T>> temp = lists;
ListNode<ListNode<T>> minListHolder == null;

//set the new lists head and the first min
while(temp != null){
if(temp.value != null){
if(minListHolder == null || minListHolder.value.value.compareTo(temp.value.value)){
minListHolder = temp;
}
//since the value is not null, keep it around for the next search
newListsTail = temp;
}
else{
newListsTail.next = temp;
newListsTail = temp;
}
}
temp = temp.next;
}
//remove any dangling empty lists
newListsTail = null;
if(minListHolder != null){
ListNode<T> minNode = minListHolder.value;
minListHolder.value = minNode.next;
}
results[1] = minNode;
return results;
}``````

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

Alternately the following could be done that would be much faster (O(n log m) instead of O(nm) )

``````public static class LinkNode<T extends Comparable<T>>{
T value
}

//build a heap of the contents
@Override
return list1.value.value.compareTo(list2.value.value);
}
});
while(lists != null){
if(lists.value != null){
}
lists.next = null;
lists = next;
}

//if there is stuff in the heap
if(!heap.isEmpty()){
//build the head of the results
lists = heap.dequeue();
lists.value = node.value;
resultTail = node;
//don't add back an empty list
if(lists.value != null){
}
//while there is still content in the heap, keep working
while(!heap.isEmpty()){
lists = heap.dequeue();
node = lists.value;
lists.value = node.value;
resultTail.next = node;
resultTail = node;
//don't add back an empty list
if(lists.value != null){
}
}
}
}``````

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

``````struct Node {
Node * next;
int value;
};

Node* mergeSList(Node* lists[], int count)
{
Node *end;
Node *start;

if (count > 0)
start = lists[0];

for(int i = 1; i < count; i++)
{
start = merge(start, lists[i]);
}

return start;
}

Node * merge (Node * list1, Node * list2)
{
Node *start = 0;
Node *end = 0;
Node *cur1 = list1;
Node *cur2 = list2;

while (cur1 || cur2)
{
Node *next = 0;
//if list1 reached the end
if (!cur1 && cur2)
{
next = cur2;
cur2 = cur2->next;
} else if (cur1 && !cur2)
{
next = cur1;
cur1 = cur1->next;
} else if (cur1->value > cur2->value)
{
next = cur2;
cur2 = cur2->next;
} else {
next = cur1;
cur1 = cur1->next;
}

if (!start)
start  = end = next;
else{
end->next = next;
end = next;
}
}
return start;
}``````

This algorithm is equivalent to the merge operation of merge sort since each list is already sorted.

Running time will O(N), where N is total number of elements in K sorted linked lists.

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

``````Class mintree  {

insert();
isempty();
getmin();
initminTree(v,  minTree t )  {

for(int i  = 0 ;  i <  v.size() ; i ++){
t.insert(make_pair<int, int> (v[i][0],  i) ) ;
}

}

boolean mergenarray (vector<vector<int>> v ) {
minTree t = new minTree() ;
t.initminTree(v)  ;
vector<int>  index  ;
vector<int>  final  ;
for(int j = 0 ; j < v.size() ; j++ )
index[j] = 0 ;

while(!t.isempty())  {
ind =  t.getmin().second() ;
final.pushback(v[index]) ;
index[ind] ++;
if !(v[index].size () <= [index[ind]])
t.insert( make_pair<int, int> (v[i][index[ind]],  i))

}
}``````

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

``````class MergeList{

private List<List<Integer>> listOfLists = new ArrayList<ArrayList<Integer>>();

private List<Integer> output =  new ArrayList<Integer>();

this.listOfLists = intializeInput(); // TODOs
}

// T(n) = m * O(n); where m =  # of sorted Lists
public List<List<Integer>> mergeAll(){
for(int i = 0; i < listOfLists.length(); i++){
this.output = merge(this.output, listOfLists.get(i));
}
return this.output;
}

// T(n) = O(n); where n is the length of the longest sortedList
private List<Integer>  merge(List<Integer> list1, List<Integer> list2){
List<Integer> list = new ArrayList<Integer>();
int i = 0, int j = 0;
for(; i < list1.length() && j < list2.length();){
Integer element1 = list1.get(i);
Integer element2 = list2.get(j);
if(element1 < element2){
i++;
}else{
j++;
}
}
if(i == list1.length()){
// list1 is expended
for(; j < list2.length(); j++){
}
}
if(j == list2.length()){
// list2 is expended
for(; i < list1.length(); i++){
}
}
return list;
}

}``````

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

``````class MergeList{

private List<List<Integer>> listOfLists = new ArrayList<ArrayList<Integer>>();

private List<Integer> output =  new ArrayList<Integer>();

this.listOfLists = intializeInput(); // TODOs
}

// T(n) = m * O(n); where m =  # of sorted Lists
public List<List<Integer>> mergeAll(){
for(int i = 0; i < listOfLists.length(); i++){
this.output = merge(this.output, listOfLists.get(i));
}
return this.output;
}

// T(n) = O(n); where n is the length of the longest sortedList
private List<Integer>  merge(List<Integer> list1, List<Integer> list2){
List<Integer> list = new ArrayList<Integer>();
int i = 0, int j = 0;
for(; i < list1.length() && j < list2.length();){
Integer element1 = list1.get(i);
Integer element2 = list2.get(j);
if(element1 < element2){
i++;
}else{
j++;
}
}
if(i == list1.length()){
// list1 is expended
for(; j < list2.length(); j++){
}
}
if(j == list2.length()){
// list2 is expended
for(; i < list1.length(); i++){
}
}
return list;
}

}``````

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

Java code implementation with min-heap (PriorityQueue); O(N log M) where N is the size of all elements in the lists.

``````private static List<Integer> kWayMerge(List<List<Integer>> lists) {
Queue<List<Integer>> queue = new PriorityQueue<List<Integer>>(new Comparator<List<Integer>>(){
public int compare(List<Integer> l1, List<Integer> l2) {
return l1.get(0) - l2.get(0);
}
});

for (List<Integer> list : lists)
{
}

while (!queue.isEmpty()) {
List<Integer> minlist = queue.remove();
}
return result;
}``````

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

we simply have to merge the first two linked list and loop thru all the k linked list to merge.

``````public class LinkedList {
public int value { get; set; }
LinkedList next { get; set; }

value = v;
next = null;
}
}

for(int i=2; i<k; i++) {
result = merge(result, a[i]);
}

return result;
}

while( p1 != null && p2 != null ) {
if(p1.value < p2.value) {
prev.next = p1;
p1 = p1.next;
}
else {
prev.next = p2;
p2 = p2.next;
}

prev = prev.next;
}

if(p1 != null) prev.next = p1;
if(p2 != null) prev.next = p2;

}
}``````

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.