Реализуйте функцию, которая собирает ID всех друзей пользователя до глубины 3
(«три рукопожатия»), параллельно опрашивая внешний источник getFriends.
// CollectFriends собирает ID всех друзей до глубины 3, опрашивая getFriends.
// Ограничение: не более 10 одновременных вызовов getFriends.
// Защита от циклов (взаимные друзья). Сборка результата без гонок.
func CollectFriends(startID int, getFriends func(id int) ([]int, error)) ([]int, error)
Условия:
- Обход в ширину (BFS) по уровням: уровень 0 — друзья
startID, и так до
3-го уровня включительно.
- Не более 10 одновременных вызовов
getFriends (семафор).
- Граф содержит циклы (взаимные друзья) — нужна защита от повторной
обработки через множество
visited.
- Результат собирается без гонок; дубликаты исключены.
startID в результат не включается (если только он не достижим как чужой друг).
В тесте строится небольшой граф с циклами; getFriends имитирует сетевой вызов
(может «спать»). Проверяется, что возвращается ровно множество достижимых за 3
шага вершин (без учёта порядка), без дубликатов, и что число одновременных
вызовов getFriends никогда не превышало 10. Проверка идёт под детектором
гонок (-race).
На что смотрит интервьюер:
- BFS по уровням (0..3) с обработкой каждого уровня параллельно.
- Семафор (буферизированный канал размера 10), ограничивающий конкурентность.
visited под мьютексом — защита от циклов и дубликатов.- Сбор результата под мьютексом;
sync.WaitGroup для ожидания уровня.
- Корректная остановка на глубине 3 и отсутствие гонок под
-race.