Facebook Interview Question Software Engineer / Developers
0of 0 votesMerge K sorted singly linked list
Country: United States
Interview Type: Phone Interview
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?
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);
ListNode<T> resultHead = (ListNode<T>)minObj[1];
ListNode<T> resultTail = resultHead;
while(resultTail != null){
lists = (ListNode<ListNode<T>>)minObj[0];
minObj = getMin(lists);
resultTail.next = (ListNode<T>)minObj[1];
resultTail = resultTail.next;
}
return resultHead;
}
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>> newListsHead = null;
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
if(newListsHead == null){
newListsHead = temp;
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[0] = newListsHead;
results[1] = minNode;
return results;
}
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>>{
LinkNode<T> next;
T value
}
public static LinkNode<T> merge(LinkNode<LinkNode<T>> lists){
LinkNode<T> resultHead;
LinkNode<T> resultTail;
//build a heap of the contents
PriorityQueue<LinkNode<LinkNode<T>>> heap = new PriorityQueue<LinkNode<LinkNode<T>>>(new Comparator<LinkNode<LinkNode<T>>>(){
@Override
public int compare(LinkNode<LinkNode<T>> list1, LinkNode<LinkNode<T>> list2){
return list1.value.value.compareTo(list2.value.value);
}
});
while(lists != null){
if(lists.value != null){
heap.add(lists);
}
LinkNode<LinkNode<T>> next = lists.next;
lists.next = null;
lists = next;
}
//if there is stuff in the heap
if(!heap.isEmpty()){
//build the head of the results
lists = heap.dequeue();
LinkNode<T> node = lists.value;
lists.value = node.value;
resultHead = node;
resultTail = node;
//don't add back an empty list
if(lists.value != null){
heap.add(lists);
}
//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){
heap.add(lists);
}
}
}
return resultHead;
}
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.
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))
}
}
class MergeList{
private List<List<Integer>> listOfLists = new ArrayList<ArrayList<Integer>>();
private List<Integer> output = new ArrayList<Integer>();
public void readInput(){
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){
list.add(element1);
i++;
}else{
list.add(element2);
j++;
}
}
if(i == list1.length()){
// list1 is expended
for(; j < list2.length(); j++){
list.add(list2.get(j));
}
}
if(j == list2.length()){
// list2 is expended
for(; i < list1.length(); i++){
list.add(list1.get(i));
}
}
return list;
}
}
class MergeList{
private List<List<Integer>> listOfLists = new ArrayList<ArrayList<Integer>>();
private List<Integer> output = new ArrayList<Integer>();
public void readInput(){
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){
list.add(element1);
i++;
}else{
list.add(element2);
j++;
}
}
if(i == list1.length()){
// list1 is expended
for(; j < list2.length(); j++){
list.add(list2.get(j));
}
}
if(j == list2.length()){
// list2 is expended
for(; i < list1.length(); i++){
list.add(list1.get(i));
}
}
return list;
}
}
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)
{
if (!list.isEmpty()) queue.add(list);
}
List<Integer> result = new LinkedList<Integer>();
while (!queue.isEmpty()) {
List<Integer> minlist = queue.remove();
result.add(minlist.remove(0));
if (!minlist.isEmpty()) queue.add(minlist);
}
return result;
}
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; }
public LinkedList(int v) {
value = v;
next = null;
}
}
public class LinkedListAlgorithms {
public LinkedList Merge(LinkedList[] a, int k) {
LinkedList result = merge(a[0], a[1]);
for(int i=2; i<k; i++) {
result = merge(result, a[i]);
}
return result;
}
private LinkedList merge(LinkedList a, LinkedList b) {
LinkedList p1 = a;
LinkedList p2 = b;
LinkedList head = new LinkedList(0);
LinkedList prev = head;
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;
return head.next;
}
}
So, there are a couple approaches, and picking one without mentioning the others is likely a failure here.
- D June 20, 2015First, 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.