Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 5 extra - solve hard interview problems email
The question we'll work through is the following: **return a new sorted merged list from K sorted lists, each with size N.** Before we move on any further, you should take some time to think about the solution!

Pull request:
day 5 extra question
Resolves #11 

Patch:
diff --git a/README.md b/README.md
index 29f92b7..764ff76 100644
--- a/README.md
+++ b/README.md
@@ -14,4 +14,5 @@ problems from
 * [Day 3](https://github.com/vaskoz/dailycodingproblem-go/issues/7)
 * [Day 4](https://github.com/vaskoz/dailycodingproblem-go/issues/5)
 * [Day 5](https://github.com/vaskoz/dailycodingproblem-go/issues/9)
+* [Day 5 merge k sorted lists](https://github.com/vaskoz/dailycodingproblem-go/issues/11)
 
diff --git a/mergeKSortedLists/problem.go b/mergeKSortedLists/problem.go
new file mode 100644
index 0000000..be37516
--- /dev/null
+++ b/mergeKSortedLists/problem.go
@@ -0,0 +1,86 @@
+package mergeklist
+
+import (
+	"container/heap"
+	"math"
+)
+
+// MergeKSortedLists merges K-sorted lists into a single list
+// Runtime is O(K*(K*N)) = O(K^2*N) assuming each list of is length N
+// Space is O(K) for the indicies without considering the answer list of O(K*N) size.
+// Use this if K is very small
+func MergeKSortedLists(lists [][]int) []int {
+	idxs := make([]int64, len(lists))
+	var result []int
+	hasMore := true
+	for hasMore {
+		listID := -1
+		smallest := math.MaxInt64
+		// find the smallest next value
+		for i, idx := range idxs {
+			if idx < int64(len(lists[i])) && lists[i][idx] < smallest {
+				smallest = lists[i][idx]
+				listID = i
+			}
+		}
+		if listID == -1 {
+			hasMore = false
+		} else {
+			result = append(result, smallest)
+			idxs[listID]++
+		}
+	}
+	return result
+}
+
+type tuple struct {
+	id, pos, value int
+}
+
+type priorityQueue []*tuple
+
+func (pq priorityQueue) Len() int { return len(pq) }
+
+func (pq priorityQueue) Less(i, j int) bool {
+	return pq[i].value < pq[j].value
+}
+
+func (pq priorityQueue) Swap(i, j int) {
+	pq[i], pq[j] = pq[j], pq[i]
+}
+
+func (pq *priorityQueue) Push(x interface{}) {
+	item := x.(*tuple)
+	*pq = append(*pq, item)
+}
+
+func (pq *priorityQueue) Pop() interface{} {
+	old := *pq
+	n := len(old)
+	tuple := old[n-1]
+	*pq = old[0 : n-1]
+	return tuple
+}
+
+// MergeKSortedListsUsingHeap merges K-sorted lists into a single list using a min-heap.
+// Runtime is O(N*K log K) assuming each list of is length N
+// Space is O(K) for the heap without considering the answer list of O(K*N) size.
+// Use this if K is very large.
+func MergeKSortedListsUsingHeap(lists [][]int) []int {
+	pq := make(priorityQueue, len(lists))
+	for i, lst := range lists {
+		pq[i] = &tuple{id: i, pos: 0, value: lst[0]}
+	}
+	heap.Init(&pq)
+	var result []int
+	for pq.Len() > 0 {
+		tup := heap.Pop(&pq).(*tuple)
+		result = append(result, tup.value)
+		id := tup.id
+		nextpos := tup.pos + 1
+		if nextpos < len(lists[id]) {
+			heap.Push(&pq, &tuple{id: id, pos: nextpos, value: lists[id][nextpos]})
+		}
+	}
+	return result
+}


Test patch:
diff --git a/mergeKSortedLists/problem_test.go b/mergeKSortedLists/problem_test.go
new file mode 100644
index 0000000..19bd913
--- /dev/null
+++ b/mergeKSortedLists/problem_test.go
@@ -0,0 +1,67 @@
+package mergeklist
+
+import (
+	"reflect"
+	"testing"
+)
+
+var testcases = []struct {
+	input    [][]int
+	expected []int
+}{
+	{[][]int{
+		[]int{10, 15, 30},
+		[]int{12, 15, 20},
+		[]int{17, 20, 32}},
+		[]int{10, 12, 15, 15, 17, 20, 20, 30, 32}},
+	{[][]int{
+		[]int{1, 2, 3},
+		[]int{2, 4, 6},
+		[]int{1, 2, 3},
+		[]int{2, 5, 7}},
+		[]int{1, 1, 2, 2, 2, 2, 3, 3, 4, 5, 6, 7}},
+	{[][]int{
+		[]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
+		[]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
+		[]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
+		[]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
+		[]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
+		[]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
+		[]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
+		[]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
+		[]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
+		[]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}},
+		[]int{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10}},
+}
+
+func TestMergeKSortedLists(t *testing.T) {
+	for i, tc := range testcases {
+		if result := MergeKSortedLists(tc.input); !reflect.DeepEqual(result, tc.expected) {
+			t.Errorf("did not merge list correctly for testcase#%d, got %v", i, result)
+		}
+	}
+}
+
+func BenchmarkMergeKSortedLists(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MergeKSortedLists(tc.input)
+		}
+	}
+}
+
+func TestMergeKSortedListsUsingHeap(t *testing.T) {
+	for i, tc := range testcases {
+		if result := MergeKSortedListsUsingHeap(tc.input); !reflect.DeepEqual(result, tc.expected) {
+			t.Errorf("did not merge list correctly for testcase#%d, got %v", i, result)
+		}
+	}
+}
+
+func BenchmarkMergeKSortedListsUsingHeap(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MergeKSortedListsUsingHeap(tc.input)
+		}
+	}
+}