🧠 Редкая задача для Go-разработчиков
Версия: Go 1.23+
Именно в Go 1.23 появился range по функциям-итераторам и пакет iter.
Нужно реализовать:
func MergeSorted(a, b iter.Seq[int]) iter.Seq[int]
Функция получает два ленивых отсортированных итератора и возвращает один общий поток в отсортированном порядке.
Пример:
a := Seq(1, 4, 7, 10)
b := Seq(2, 3, 8, 9)
for v := range MergeSorted(a, b) {
fmt.Println(v)
}
Результат:
1 2 3 4 7 8 9 10
Но есть условия:
* нельзя превращать входы в []int;
* нельзя использовать горутины и каналы;
* память должна быть O(1);
* если внешний цикл сделал break, оба исходных итератора должны прекратить работу;
* каждый элемент исходного iterator можно получить только один раз.
🔥 Дополнительный уровень: сделать generic-версию:
func MergeSorted[T cmp.Ordered](
a, b iter.Seq[T],
) iter.Seq[T]
На первый взгляд обычный merge. На практике придётся хорошо понять, как устроены push/pull iterators, `yield` и раннее завершение `range` в Go 1.23.
Версия: Go 1.23+
Именно в Go 1.23 появился range по функциям-итераторам и пакет iter.
Нужно реализовать:
func MergeSorted(a, b iter.Seq[int]) iter.Seq[int]
Функция получает два ленивых отсортированных итератора и возвращает один общий поток в отсортированном порядке.
Пример:
a := Seq(1, 4, 7, 10)
b := Seq(2, 3, 8, 9)
for v := range MergeSorted(a, b) {
fmt.Println(v)
}
Результат:
1 2 3 4 7 8 9 10
Но есть условия:
* нельзя превращать входы в []int;
* нельзя использовать горутины и каналы;
* память должна быть O(1);
* если внешний цикл сделал break, оба исходных итератора должны прекратить работу;
* каждый элемент исходного iterator можно получить только один раз.
🔥 Дополнительный уровень: сделать generic-версию:
func MergeSorted[T cmp.Ordered](
a, b iter.Seq[T],
) iter.Seq[T]
На первый взгляд обычный merge. На практике придётся хорошо понять, как устроены push/pull iterators, `yield` и раннее завершение `range` в Go 1.23.