Mock Google Coding Interview with a Meta Intern

15 ноября 2022 г. · 5 мин. чтения

Сегодня мы разберем процесс проведения тренировочного собеседования на позицию разработчика, где кандидат с опытом стажировки в Meta демонстрирует свои навыки решения алгоритмических задач в условиях, приближенных к реальному интервью в Google. В ходе сессии обсуждается задача проектирования структуры данных с поддержкой операций вставки, удаления и получения случайного элемента, а также анализируются компромиссы между различными подходами к реализации.

Вопрос 1. Разработайте структуру данных, поддерживающую три операции: вставку значения (без дубликатов), удаление значения и получение случайного значения с равной вероятностью среди всех вставленных значений.

Таймкод: 00:01:51

Ответ собеседника: правильный. Кандидат использует комбинацию массива (list) и хеш-словаря (dict). Вставка: проверка на дубликат через словарь O(1), добавление в конец массива O(1), сохранение индекса в словаре O(1). Удаление: нахождение индекса через словарь O(1), обмен удаляемого элемента с последним в массиве O(1), обновление словаря для перемещённого элемента O(1), удаление последнего элемента чер pop O(1), удаление записи из словаря O(1). Получение случайного значения: random.choice по массиву O(1). Все три операции работают за O(1). Кандидат также корректно адаптировал решение для поддержки дубликатов, заменив хранение одиночного индекса на множество (set) индексов в словаре. При обсуждении потокобезопасности кандидат верно указал на необходимость использования блокировок (locks) для операций вставки, удаления и получения случайного значения.

Правильный ответ:

Данная задача — классическая задача проектирования структуры данных (LeetCode 380. Insert Delete GetRandom O(1)). Ключевая идея — комбинация динамического массива и хеш-таблицы, что позволяет достичь амортизированного O(1) для всех трёх операций.

Базовая структура (без дубликатов)

Используем два контейнера:

slice (динамический массив) — хранит сами значения, обеспечивает O(1) доступ по индексу и O(1) добавление в конец
map[value]index — хранит отображение значения в его индекс в массиве, обеспечивает O(1) поиск

package main

import (
	"fmt"
	"math/rand"
	"time"
)

// RandomizedSet поддерживает insert, remove и getRandom за O(1)
type RandomizedSet struct {
	data []int
	idx  map[int]int
	rng  *rand.Rand
}

func NewRandomizedSet() *RandomizedSet {
	return &RandomizedSet{
		data: make([]int, 0),
		idx:  make(map[int]int),
		rng:  rand.New(rand.NewSource(time.Now().UnixNano())),
	}
}

// Insert добавляет значение, возвращает true если элемент был добавлен
func (rs *RandomizedSet) Insert(val int) bool {
	if _, exists := rs.idx[val]; exists {
		return false
	}
	rs.idx[val] = len(rs.data)
	rs.data = append(rs.data, val)
	return true
}

// Remove удаляет значение, возвращает true если элемент был найден и удалён
func (rs *RandomizedSet) Remove(val int) bool {
	index, exists := rs.idx[val]
	if !exists {
		return false
	}

	lastIndex := len(rs.data) - 1
	lastVal := rs.data[lastIndex]

	// Перемещаем последний элемент на место удаляемого
	rs.data[index] = lastVal
	rs.idx[lastVal] = index

	// Удаляем последний элемент из массива
	rs.data = rs.data[:lastIndex]

	// Удаляем запись из словаря
	delete(rs.idx, val)

	return true
}

// GetRandom возвращает случайный элемент с равной вероятностью
func (rs *RandomizedSet) GetRandom() (int, error) {
	if len(rs.data) == 0 {
		return 0, fmt.Errorf("set is empty")
	}
	return rs.data[rs.rng.Intn(len(rs.data))], nil
}

func main() {
	rs := NewRandomizedSet()

	fmt.Println(rs.Insert(1))    // true
	fmt.Println(rs.Insert(2))    // true
	fmt.Println(rs.Insert(1))    // false (дубликат)
	fmt.Println(rs.Remove(1))    // true
	fmt.Println(rs.Remove(1))    // false (уже удалён)

	val, _ := rs.GetRandom()
	fmt.Println("Random:", val)  // 2
}

Ключевой приём при удалении

При удалении элемента из середины массива наивный подход потребовал бы O(n) для сдвига всех последующих элементов. Вместо этого мы:

Находим индекс удаляемого элемента через хеш-таблицу — O(1)
Копируем последний элемент массива на позицию удаляемого — O(1)
Обновляем индекс перемещённого элемента в хеш-таблице — O(1)
Усекаем массив на один элемент с конца — O(1)
Удаляем запись из хеш-таблицы — O(1)

Это сохраняет непрерывность массива без дорогостоящего сдвига.

Адаптация для поддержки дубликатов (LeetCode 381)

Когда дубликаты разрешены, вместо хранения одного индекса в хеш-таблице храним множество индексов:

import "math/rand"

type RandomizedCollection struct {
	data []int
	idx  map[int]map[int]struct{} // val -> set of indices
	rng  *rand.Rand
}

func NewRandomizedCollection() *RandomizedCollection {
	return &RandomizedCollection{
		data: make([]int, 0),
		idx:  make(map[int]map[int]struct{}),
		rng:  rand.New(rand.NewSource(time.Now().UnixNano())),
	}
}

func (rc *RandomizedCollection) Insert(val int) bool {
	indices, exists := rc.idx[val]
	if !exists {
		indices = make(map[int]struct{})
		rc.idx[val] = indices
	}
	indices[len(rc.data)] = struct{}{}
	rc.data = append(rc.data, val)
	return !exists
}

func (rc *RandomizedCollection) Remove(val int) bool {
	indices, exists := rc.idx[val]
	if !exists || len(indices) == 0 {
		return false
	}

	// Берём произвольный индекс удаляемого элемента
	var removeIdx int
	for idx := range indices {
		removeIdx = idx
		break
	}

	lastIdx := len(rc.data) - 1
	lastVal := rc.data[lastIdx]

	if removeIdx == lastIdx {
		// Удаляемый элемент уже последний
		delete(indices, removeIdx)
	} else {
		// Перемещаем последний элемент на место удаляемого
		rc.data[removeIdx] = lastVal

		// Обновляем индексы для последнего элемента
		lastIndices := rc.idx[lastVal]
		delete(lastIndices, lastIdx)
		lastIndices[removeIdx] = struct{}{}

		// Удаляем индекс удаляемого элемента
		delete(indices, removeIdx)
	}

	rc.data = rc.data[:lastIdx]

	if len(indices) == 0 {
		delete(rc.idx, val)
	}

	return true
}

func (rc *RandomizedCollection) GetRandom() (int, error) {
	if len(rc.data) == 0 {
		return 0, fmt.Errorf("collection is empty")
	}
	return rc.data[rc.rng.Intn(len(rc.data))], nil
}

Потокобезопасность

В многопоточной среде Go все три операции должны быть защищены мьютексом, поскольку они выполняют несколько неделимых шагов над обоими контейнерами:

import "sync"

type SafeRandomizedSet struct {
	mu   sync.RWMutex
	data []int
	idx  map[int]int
	rng  *rand.Rand
}

func (s *SafeRandomizedSet) Insert(val int) bool {
	s.mu.Lock()
	defer s.mu.Unlock()
	// ... логика вставки
}

func (s *SafeRandomizedSet) Remove(val int) bool {
	s.mu.Lock()
	defer s.mu.Unlock()
	// ... логика удаления
}

func (s *SafeRandomizedSet) GetRandom() (int, error) {
	s.mu.RLock()
	defer s.mu.RUnlock()
	// ... логика получения случайного элемента
}

Для GetRandom используется RLock, поскольку операция чтения не модифицирует данные. Для Insert и Remove — исключительный Lock.

Альтернативные подходы и их недостатки

Только хеш-таблица (map): не позволяет получить случайный элемент за O(1), так как итерация по map в Go не гарантирует равномерное распределение при выборе случайного ключа
Только массив: удаление и проверка на дубликат работают за O(n)
Связный список + хеш-таблица: не позволяет получить случайный элемент за O(1), так как нет произвольного доступа по индексу

Сложность

Операция	Время	Память
Insert	O(1) амортизированно	O(n)
Remove	O(1) амортизированно	O(n)
GetRandom	O(1)	O(n)