К треку

Алгоритмы и структуры данных100Слияние двух отсортированных слайсов

Войти

Задачи курса

Прогресс0/166

01Массивы и слайсы

02Основы Go: типы, строки, структуры, generics

03Ошибки, defer, panic/recover

04Map

05Каналы и select

06Синхронизация: sync, atomic, data race

07Context

08Алгоритмы и структуры данных

09Паттерны конкурентности и лайвкодинг

10NoSQL и кеширование

11Архитектура, ООП, SOLID, паттерны

12Брокеры сообщений: Kafka, RabbitMQ, NATS

13Сеть и API: HTTP, gRPC, REST

Тренажёр166 задач⌘↵

Перейти к редактору ↓

Слияние двух отсортированных слайсов

Даны два слайса целых чисел, каждый отсортирован по неубыванию. Верните новый отсортированный слайс, в котором есть все элементы обоих (дубли сохраняются).

// MergeSorted сливает отсортированные a и b в новый отсортированный слайс.
func MergeSorted(a, b []int) []int

Требования

Время O(n + m), где n и m — длины входов.
Входы не изменяются, результат не разделяет с ними память: изменение результата не должно менять a или b (в том числе когда один из входов пуст).
Ровно одна аллокация — под результат. Для двух пустых входов вернуть пустой слайс (nil тоже подходит).

Примеры

MergeSorted([]int{2, 6, 10, 14}, []int{2, 10, 14, 18})
// [2 2 6 10 10 14 14 18]
MergeSorted([]int{2, 4, 6, 8, 10}, []int{8, 10, 12, 14, 16})
// [2 4 6 8 8 10 10 12 14 16]
MergeSorted([]int{3, 6, 9}, []int{12, 15, 18, 21, 24})
// [3 6 9 12 15 18 21 24]
MergeSorted([]int{2, 10, 12, 36, 198}, []int{4, 8, 18, 22})
// [2 4 8 10 12 18 22 36 198]

Устно: почему append(a, b...) и sort.Ints — плохой ответ? Как распараллелить слияние двух очень больших массивов?

Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.

Подсказки0/3

Сначала попробуй сам — подсказки не дают готовый ответ.

go test -race

solution.go

Загрузка редактора…

go test -race ./...Готов к запуску

Запусти тесты, чтобы увидеть вывод

Запусти тесты, чтобы увидеть вывод · ⌘↵

График