Реализуйте функцию, которая собирает ID всех друзей пользователя на расстоянии до
трёх рукопожатий. Друзей отдаёт медленный внешний источник getFriends, поэтому
обход должен быть параллельным.
// CollectFriends собирает ID всех друзей до глубины 3, опрашивая getFriends.
// Не более 10 одновременных вызовов getFriends. Граф может содержать циклы.
func CollectFriends(startID int, getFriends func(id int) ([]int, error)) ([]int, error)
Дружба в графе направленная: getFriends(id) возвращает тех, кого указал id.
1 -> 2, 3
2 -> 1, 4
3 -> 4, 5
4 -> 6
5 -> 7
6 -> 8
7 -> 9
ids, err := CollectFriends(1, getFriends)
sort.Ints(ids)
fmt.Println(ids, err) // [1 2 3 4 5 6 7] <nil>
Разберём по уровням:
- Расстояние 1:
2 и 3 (друзья 1).
- Расстояние 2:
1, 4, 5 (друзья 2 и 3).
- Расстояние 3:
6 и 7 (друзья 4 и 5).
- Вершины
8 и 9 лежат на расстоянии 4 и в ответ не попадают.
Обратите внимание на 1 в ответе. Стартовый ID не добавляется сам, но если он
оказался чьим-то другом (как 1 у 2), то в результат входит. Повторно спрашивать
у getFriends про него при этом не нужно.
- Обход в ширину, по уровням. Вершину опрашивают не более одного раза.
- Не более 10 одновременных вызовов
getFriends.
- Циклы (взаимные друзья) не приводят к бесконечному обходу.
- В результате нет дубликатов, порядок любой.
- Если
getFriends вернул ошибку, CollectFriends возвращает nil и ошибку.
- Если друзей нет, результат пуст, ошибки нет.
- Всё идёт под детектором гонок (
-race).
- Граф с циклами: после сортировки результат равен
[1 2 3 4 5 6 7], без дубликатов.
- Широкий граф (вершина с 100 друзьями, у каждого свой друг):
getFriends считает
одновременные вызовы, максимум не больше 10 и не меньше 2, то есть параллелизм
реально используется.
- Граф
1 -> 2, 2 -> 1, 3, 3 -> 2, 1 не зацикливает обход, результат [1 2 3]
(таймаут теста 10 секунд).
- Пустой список друзей даёт пустой результат без ошибки.
- Каждая вершина (и стартовая тоже) опрашивается ровно один раз, вершины глубже
третьего уровня не опрашиваются вовсе.
- Ошибка
getFriends на первом, втором или третьем уровне даёт nil и именно эту
ошибку (проверка через errors.Is).
На что смотрит интервьюер: разбиение на уровни и барьер между ними, семафор на
буферизованном канале, visited и результат под мьютексом, корректная граница
глубины (не на уровень больше или меньше).