Даны два набора чисел, отсортированных по возрастанию: основной pool и
список исключений cleared. Нужно вернуть pool без элементов, попавших в
cleared. Коллега написал решение, но оно возвращает пустой слайс. Найди и
исправь баг.
func Sieve(pool, cleared []int) []int {
clearedSet := make(map[int]bool, 100)
for _, v := range cleared {
clearedSet[v] = true
}
kept := make([]int, 0, len(pool))
for _, v := range pool {
if !clearedSet[v] {
kept := append(kept, v)
_ = kept
}
}
return kept
}
Требования
- Порядок
pool сохраняется, повторы в pool сохраняются (кроме исключённых
значений, они удаляются все).
pool не меняется. nil и пустые входы допустимы.
Пример
Sieve([]int{1, 2, 3, 4, 5}, []int{2, 4}) // [1 3 5]
Sieve([]int{3, 80, 123, 421, 936}, []int{80, 936}) // [3 123 421]
Входы отсортированы, а решение этим не пользуется.
func SieveSorted(pool, cleared []int) []int
- Тот же результат за O(len(pool) + len(cleared)), без
map.
- Память выделяется один раз — под результат.
Устно: почему компилятор не ругается на этот баг? Как его поймал бы
линтер? Зачем в исходном коде make(map[int]bool, 100) и что не так с этой
сотней?