Два канала отдают числа по неубыванию. Нужно вернуть канал, из которого все
числа читаются тоже по неубыванию — как шаг слияния в merge sort, только на
потоках.
func MergeOrdered(left, right <-chan int) <-chan int
Требования
- На выходе каждое число из обоих входов ровно один раз, по неубыванию.
Дубликаты сохраняются.
- Входы могут быть разной длины, в том числе пустыми. Когда один вход
закончился, остаток другого идёт на выход как есть.
- Выход закрывается, когда оба входа закрыты и вычитаны.
- Входы — обычные каналы: значения приходят с задержками, ничего заранее
«вычитать в слайс и отсортировать» нельзя. Функция возвращает канал сразу.
- После того как выход дочитан, горутин не остаётся. Код проходит
go test -race.
Пример
left, right := make(chan int), make(chan int)
go func() { defer close(left); left <- -2; left <- 3; left <- 6 }()
go func() { defer close(right); right <- 0; right <- 3; right <- 5 }()
for v := range MergeOrdered(left, right) {
fmt.Print(v, " ") // -2 0 3 3 5 6
}
func MergeK(chans ...<-chan int) <-chan int
- То же для произвольного числа отсортированных входов (в том числе нуля:
тогда выход сразу закрыт).
- При K входах на каждое число — O(log K) работы, а не O(K).
Устно: что будет с горутиной MergeOrdered, если потребитель перестал
читать выход? Как это починить?
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.