Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 367
Good morning! Here's your coding interview problem for today.

This problem was asked by Two Sigma.

Given two sorted iterators, merge it into one iterator.

For example, given these two iterators:

```
foo = iter([5, 10, 15])
bar = iter([3, 8, 9])
```

You should be able to do:

```
for num in merge_iterators(foo, bar):
    print(num)

# 3
# 5
# 8
# 9
# 10
# 15
```

Bonus: Make it work without pulling in the contents of the iterators in memory.

Pull request:
Day367
Resolves #740.

Patch:
diff --git a/README.md b/README.md
index 4e00b5e..6bd4abf 100644
--- a/README.md
+++ b/README.md
@@ -361,4 +361,6 @@ problems from
 * [Day 363](https://github.com/vaskoz/dailycodingproblem-go/issues/716)
 * [Day 364](https://github.com/vaskoz/dailycodingproblem-go/issues/718)
 * [Day 365](https://github.com/vaskoz/dailycodingproblem-go/issues/720)
+* I thought it was done at day 365. Apparently not.
+* [Day 367](https://github.com/vaskoz/dailycodingproblem-go/issues/740)
 
diff --git a/day367/problem.go b/day367/problem.go
new file mode 100644
index 0000000..3f77b28
--- /dev/null
+++ b/day367/problem.go
@@ -0,0 +1,108 @@
+package day367
+
+import "sort"
+
+// LessThanEqual returns true if the first argument is less or equal to the second.
+// False otherwise.
+type LessThanEqual func(a, b interface{}) bool
+
+// SortedIterator is an iterator with sorted elements.
+type SortedIterator interface {
+	// Empty is true if there are no more elements in the iterator.
+	Empty() bool
+
+	// Peek returns the next value without advancing the iterator.
+	Peek() interface{}
+
+	// Next returns the next sorted iterator element.
+	// Returns nil if Empty() is true.
+	Next() interface{}
+}
+
+type singleSourceSortedIterator struct {
+	sortedData []interface{}
+	nextIndex  int
+}
+
+func (sssi *singleSourceSortedIterator) Empty() bool {
+	return sssi.nextIndex == len(sssi.sortedData)
+}
+
+func (sssi *singleSourceSortedIterator) Peek() interface{} {
+	if sssi.nextIndex == len(sssi.sortedData) {
+		return nil
+	}
+
+	return sssi.sortedData[sssi.nextIndex]
+}
+
+func (sssi *singleSourceSortedIterator) Next() interface{} {
+	if sssi.nextIndex == len(sssi.sortedData) {
+		return nil
+	}
+	sssi.nextIndex++
+
+	return sssi.sortedData[sssi.nextIndex-1]
+}
+
+// NewSortedIterator returns a new SortedIterator given a slice and a lessThan
+// function.
+// "lessThan" should answer consistently if 'a' is less than 'b' then true, else false.
+func NewSortedIterator(vals []interface{}, lessThan LessThanEqual) SortedIterator {
+	copied := make([]interface{}, len(vals))
+	copy(copied, vals)
+	sort.Slice(copied, func(i, j int) bool {
+		return lessThan(copied[i], copied[j])
+	})
+
+	return &singleSourceSortedIterator{sortedData: copied, nextIndex: 0}
+}
+
+type multipleSourceSortedIterator struct {
+	a, b     SortedIterator
+	lessThan func(a, b interface{}) bool
+}
+
+func (mssi *multipleSourceSortedIterator) Empty() bool {
+	return mssi.a.Empty() && mssi.b.Empty()
+}
+
+func (mssi *multipleSourceSortedIterator) Peek() interface{} {
+	switch {
+	case mssi.Empty():
+		return nil
+	case mssi.a.Empty():
+		return mssi.b.Peek()
+	case mssi.b.Empty():
+		return mssi.a.Peek()
+	default:
+		if mssi.lessThan(mssi.a.Peek(), mssi.b.Peek()) {
+			return mssi.a.Peek()
+		}
+
+		return mssi.b.Peek()
+	}
+}
+
+func (mssi *multipleSourceSortedIterator) Next() interface{} {
+	switch {
+	case mssi.Empty():
+		return nil
+	case mssi.a.Empty():
+		return mssi.b.Next()
+	case mssi.b.Empty():
+		return mssi.a.Next()
+	default:
+		if mssi.lessThan(mssi.a.Peek(), mssi.b.Peek()) {
+			return mssi.a.Next()
+		}
+
+		return mssi.b.Next()
+	}
+}
+
+// MergeSortedIterators returns a SortedIterator that is the result
+// of merging two other SortedIterator's.
+func MergeSortedIterators(a, b SortedIterator, lessThan LessThanEqual) SortedIterator {
+	return &multipleSourceSortedIterator{a, b, lessThan}
+}


Test patch:
diff --git a/day367/problem_test.go b/day367/problem_test.go
new file mode 100644
index 0000000..c82035d
--- /dev/null
+++ b/day367/problem_test.go
@@ -0,0 +1,186 @@
+package day367
+
+import "testing"
+
+// nolint
+var (
+	intLessThanEqual LessThanEqual = func(a, b interface{}) bool {
+		aI := a.(int)
+		bI := b.(int)
+		return aI <= bI
+	}
+	stringLessThanEqual LessThanEqual = func(a, b interface{}) bool {
+		aS := a.(string)
+		bS := b.(string)
+		return aS <= bS
+	}
+)
+
+// nolint
+var testcases = []struct {
+	a                 []interface{}
+	aLessThanEqual    LessThanEqual
+	b                 []interface{}
+	bLessThanEqual    LessThanEqual
+	combLessThanEqual LessThanEqual
+
+	expected []interface{}
+}{
+	{
+		[]interface{}{5, 10, 15},
+		intLessThanEqual,
+		[]interface{}{3, 8, 9},
+		intLessThanEqual,
+		intLessThanEqual,
+		[]interface{}{3, 5, 8, 9, 10, 15},
+	},
+	{
+		[]interface{}{3, 8, 9},
+		intLessThanEqual,
+		[]interface{}{5, 10, 15},
+		intLessThanEqual,
+		intLessThanEqual,
+		[]interface{}{3, 5, 8, 9, 10, 15},
+	},
+	{
+		[]interface{}{9, 3, 8, 1, 9},
+		intLessThanEqual,
+		[]interface{}{25, 2, 100, 10, 15},
+		intLessThanEqual,
+		intLessThanEqual,
+		[]interface{}{1, 2, 3, 8, 9, 9, 10, 15, 25, 100},
+	},
+	{
+		[]interface{}{"o", "a", "k", "s", "v"},
+		stringLessThanEqual,
+		[]interface{}{"w", "e", "l", "c", "o", "m", "e"},
+		stringLessThanEqual,
+		stringLessThanEqual,
+		[]interface{}{"a", "c", "e", "e", "k", "l", "m", "o", "o", "s", "v", "w"},
+	},
+	{
+		[]interface{}{10, 8, 9, 7, 5, 6, 4, 2, 3, 1, 0},
+		intLessThanEqual,
+		[]interface{}{"a", "c", "k", "b", "d", "f", "e", "h", "g", "i", "j"},
+		stringLessThanEqual,
+		func(a, b interface{}) bool {
+			if av, ok := a.(string); ok {
+				if bv, ok := b.(string); ok {
+					return stringLessThanEqual(av, bv)
+				} else {
+					avr := int(av[0]) - 'a'
+					bv := b.(int)
+					return avr <= bv
+				}
+			} else {
+				av := a.(int)
+				if bv, ok := b.(string); ok {
+					bvr := int(bv[0]) - 'a'
+					return av <= bvr
+				} else {
+					bv := b.(int)
+					return intLessThanEqual(av, bv)
+				}
+			}
+		},
+		[]interface{}{0, "a", 1, "b", 2, "c", 3, "d", 4, "e", 5, "f", 6, "g", 7, "h",
+			8, "i", 9, "j", 10, "k"},
+	},
+}
+
+func TestMergeSortedIterators(t *testing.T) {
+	t.Parallel()
+
+	for _, tc := range testcases {
+		a := NewSortedIterator(tc.a, tc.aLessThanEqual)
+		b := NewSortedIterator(tc.b, tc.bLessThanEqual)
+		c := MergeSortedIterators(a, b, tc.combLessThanEqual)
+
+		for index, v := range tc.expected {
+			if peek := c.Peek(); v != peek {
+				t.Errorf("Expected element index %d equal to %v, got %v", index, v, peek)
+			} else if got := c.Next(); peek != got {
+				t.Errorf("peek and got do not match index %d peek=%v got=%v", index, peek, got)
+			}
+		}
+
+		if !c.Empty() {
+			t.Errorf("Expected an empty merged iterator, but it's not")
+		}
+
+		if c.Peek() != nil || c.Next() != nil {
+			t.Errorf("once empty, all peek and next should be nil")
+		}
+	}
+}
+
+func BenchmarkMergeSortedIterators(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			a := NewSortedIterator(tc.a, tc.aLessThanEqual)
+			b := NewSortedIterator(tc.b, tc.bLessThanEqual)
+			c := MergeSortedIterators(a, b, tc.combLessThanEqual)
+
+			for !c.Empty() {
+				c.Next()
+			}
+		}
+	}
+}
+
+func TestSingleSortedIterators(t *testing.T) {
+	t.Parallel()
+
+	for _, tc := range testcases {
+		a := NewSortedIterator(tc.a, tc.aLessThanEqual)
+
+		first := a.Next()
+
+		for !a.Empty() {
+			next := a.Next()
+			if !tc.aLessThanEqual(first, next) {
+				t.Errorf("a not sorted %v should be less than %v", first, next)
+			}
+
+			first = next
+		}
+
+		if a.Peek() != nil || a.Next() != nil || !a.Empty() {
+			t.Errorf("expected empty with nils")
+		}
+
+		b := NewSortedIterator(tc.b, tc.bLessThanEqual)
+
+		first = b.Next()
+
+		for !b.Empty() {
+			next := b.Next()
+			if !tc.bLessThanEqual(first, next) {
+				t.Errorf("b not sorted")
+			}
+
+			first = next
+		}
+
+		if a.Peek() != nil || a.Next() != nil || !a.Empty() {
+			t.Errorf("expected empty with nils")
+		}
+	}
+}
+
+func BenchmarkSingleSortedIterators(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			a := NewSortedIterator(tc.a, tc.aLessThanEqual)
+			b := NewSortedIterator(tc.b, tc.bLessThanEqual)
+
+			for !a.Empty() {
+				a.Next()
+			}
+
+			for !b.Empty() {
+				b.Next()
+			}
+		}
+	}
+}