Популярные задачи для собеседований бэкенд-разработчиков на Go и их решения

[elephantum]

Первая задача, утверждение «А можно выделить дополнительную память и решить за линейное время.» некорректно.

Описанное решение работает не за линейное, а за N*log(N)*M время. (составление словаря — это N*log(N))

[lair]

(составление словаря — это N*log(N)

В Go составление словаря имеет логарифмическую сложность? Я как-то привык считать, что хэш-таблицы имеют (амортизированную) константную сложность вставки, особенно если размер заранее известен.

[Videoman]

Даже если иметь в виду взвешенное бинарное дерево, то там сложность log(N). Откуда еще N не понятно.

[elephantum]

Потому что вставить нужно не один раз а N, по количеству элементов.

[Videoman]

Упс. Имелась в виду операция вставки конечно.

[mayorovp]

Бинарное дерево за логарифм никак не строится, хотя бы потому что ему нужна память Θ(N).

[elephantum]

Согласен, позабыл, что в удачном случае вставка в хешмап — O(1). (Но так же стоит не забывать, что в неудачном — O(N))

[lair]

Логарифму все равно взяться неоткуда. А когда вы вставляете множество, да еще и с заранее известным размером, вы как раз должны попадать в амортизированную оценку.

[elephantum]

Все верно. Логарифма нет, есть константа или линейная в зависимости от того на сколько нам повезло. Чаще всего везет и сложность O(1)

[Labutin]

В задаче "Слить N каналов в один" sync.WaitGroup не обязательно передавать как аргумент:

func joinChannels(chs ...<-chan int) <-chan int {
	mergedCh := make(chan int)

	go func() {
		wg := &sync.WaitGroup{}

		wg.Add(len(chs))

		for _, ch := range chs {
			go func(ch <-chan int) {
				defer wg.Done()
				for id := range ch {
					mergedCh <- id
				}
			}(ch)
		}
		wg.Wait()
		close(mergedCh)
	}()
	return mergedCh
}

[negasus]

Не стоит забывать о нулевых значениях в Go.

Вот этот код

if _, ok := counter[elem]; !ok {
    counter[elem] = 1
} else {
    counter[elem] += 1
}

можно записать как

counter[elem]++

[mejedi]

> Создаем канал, куда будем сливать все данные. Он будет небуферезированный, потому что мы не знаем, сколько данных придет из каналов.

Буфер нужен для того, чтобы уменьшить количество переключений между горутинами и позволить им работать параллельно. Вовсе не обязательно делать буфер достаточно большим, чтобы вместить все данные.

[andyN]

Вот последняя часть статьи и раскрывает в чем серьезный недостаток Go. Да, писать на нем легко и просто. Фан и всё такое. Отдых для уставших от бесконечных Java классов и логов. Но выбирать его как основной язык разработки — это большой риск. Потому что если проект разрастется (а это происходит почти всегда, в случае успеха) — без тех самых «надоедливых» фич из Java, C++, C# и прочих, становится очень неудобно и просто опасно. Не всё и не всегда можно разбить на мелкие микросервисы чисто с технической стороны, да и не всегда есть бюджеты и время чтобы это сделать.

[anton19286]

Задачу «написать генератор случайных чисел» я представлял иначе.

[paramtamtam]

Просто оставлю здесь вариант для первой задачи (поиска пересечения слайсов) что работает для неограниченного количества слайсов на входе:

Код функции

func intersection(in ...[]int) []int {
  var result = make([]int, 0)

  if len(in) < 2 {
    return result
  }

  var longestSliceIdx = 0

  for i := 0; i < len(in); i++ { // находим самый длинный слайс
    if len(in[i]) > len(in[longestSliceIdx]) {
      longestSliceIdx = i
    }
  }

  var m = make([]map[int]uint, len(in)-1) // слайс из мап для счётчиков значений

  for i, j := 0, 0; i < len(in); i++ { // "прогреваем" мапы по каждому полученному слайсу
    if i == longestSliceIdx { // кроме самого длинного
      continue
    }

    m[j] = make(map[int]uint)
    for _, k := range in[i] {
      m[j][k]++
    }

    j++
  }

valuesLoop:
  for _, value := range in[longestSliceIdx] { // проходимся по всем значениям из самого длинного слайса
    for _, mmap := range m { // пробегаемся по всем мапам, что хранят количество вхождений
      if count, ok := mmap[value]; ok { // и если в карте найдено значение из самого длинного слайса
        if count > 0 { // и оно больше нуля
          mmap[value]-- // то уменьшаем его счётчика и НЕ прерываем цикл
        } else {
          delete(mmap, value) // если значения есть и оно == 0, то удаляем его (прибираемся)

          continue valuesLoop // и переходим к следующему значению (не ищем во всех мапах)
        }
      } else {
        continue valuesLoop // если значения в мапе нет, то и в других мапах искать нет смысла
      }

      result = append(result, value)
    }
  }

  return result
}

[Urbansamurai]

func slicesIntersection(a, b []int) []int {

	buf := make(map[int]bool)
	res := make([]int, 0)

	for _, v := range a {
		if _, ok := buf[v]; !ok {
			buf[v] = false
		}
	}

	for _, v := range b {
		if _, ok := buf[v]; ok {
			res = append(res, v)
		}
	}

	return res

}

А такой вариант решения для первой задачи чем-то отличается?

[mayorovp]

Если на вход подать последовательности 1 1 и 1 1 1 — то решение автора выберет две единицы, а ваше — три.