⚙️ Алгоритмы  ·  20 вопросов  ·  ~40 мин  ·  ⏱ Таймер 40:00  ·  Средний  · 

Хеш-таблицы

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

Отвечено: 0 из 20
⏱ --:--
0%
💡 Инструкция: Выбери один ответ из четырёх. В тесте 20 вопросов и 40 минут. После завершения откроются общий процент, четыре тематические шкалы, правильные ответы и пояснения.
Вопрос 1 из 20
В какую корзину попадёт строка при данной функции?
h_{i+1}=(31h_i+code_i)\bmod 11
Python
def h(s, m):
    value = 0
    for ch in s:
        value = (value * 31 + ord(ch)) % m
    return value

print(h("cab", 11))
Вопрос 2 из 20
Почему эта функция особенно неудачна для ключей вида "user_1001", "user_1002" и так далее?
Python
def weak_hash(s, m):
    return ord(s[0]) % m
Вопрос 3 из 20
Какое требование обязательно для ключей пользовательского класса в хеш-таблице?
Вопрос 4 из 20
Сколько непустых корзин получится?
Python
keys = [12, 19, 26, 5, 16]
m = 7
buckets = [[] for _ in range(m)]
for x in keys:
    buckets[x % m].append(x)
print(sum(bool(b) for b in buckets))
Вопрос 5 из 20
Какая строка корректно обновляет полиномиальный хеш слева направо с основанием p и модулем m?
Вопрос 6 из 20
Как будут выглядеть цепочки после вставки?
Python
m = 5
buckets = [[] for _ in range(m)]
for x in [7, 12, 4, 17, 9]:
    buckets[x % m].append(x)
print(buckets[2], buckets[4])
Вопрос 7 из 20
В какой позиции окажется ключ 24 при линейном пробировании?
Python
table = [None] * 7
for key in [10, 17, 24]:
    i = key % len(table)
    while table[i] is not None:
        i = (i + 1) % len(table)
    table[i] = key
print(table.index(24))
Вопрос 8 из 20
Почему при открытой адресации удалённую ячейку часто помечают специальным маркером, а не превращают в обычную пустую?
Вопрос 9 из 20
Что напечатает вызов find(24) и в чём состоит ошибка поиска?
Python
EMPTY = None
DELETED = object()
table = [EMPTY] * 7
table[3] = 10
table[4] = DELETED
table[5] = 24

def find(key):
    i = key % len(table)
    while table[i] is not EMPTY:
        if table[i] is DELETED:
            return False
        if table[i] == key:
            return True
        i = (i + 1) % len(table)
    return False

print(find(24))
Вопрос 10 из 20
Когда операции хеш-таблицы могут деградировать до O(n)?
T_{worst}(n)=O(n)
Вопрос 11 из 20
Какой останется вместимость capacity после проверки порога перед шестой вставкой?
Python
capacity = 8
size = 5
threshold = 0.75
if (size + 1) / capacity > threshold:
    capacity *= 2
print(capacity)
Вопрос 12 из 20
В таблице 18 элементов и 24 корзины. Чему равен коэффициент заполнения?
\alpha=\frac{18}{24}=0.75
Вопрос 13 из 20
Почему расширение таблицы до нового размера требует перехешировать элементы, а не просто скопировать массив ячеек?
Вопрос 14 из 20
Какие значения old_index и new_index будут напечатаны для ключа 14?
Python
key = 14
old_index = key % 5
new_index = key % 11
print(old_index, new_index)
Вопрос 15 из 20
Что обычно происходит при слишком высоком коэффициенте заполнения в открытой адресации?
Вопрос 16 из 20
Какое значение будет выведено?
Python
seen = set()
answer = None
for x in [4, 2, 7, 2, 4]:
    if x in seen:
        answer = x
        break
    seen.add(x)
print(answer)
Вопрос 17 из 20
Какую пару индексов вернёт алгоритм?
Python
a = [8, 3, 11, 5, 7]
target = 12
pos = {}
answer = None
for i, x in enumerate(a):
    need = target - x
    if need in pos:
        answer = (pos[need], i)
        break
    pos[x] = i
print(answer)
Вопрос 18 из 20
Как наиболее надёжно проверить, являются ли две строки анаграммами, если важны все символы и их кратности?
Вопрос 19 из 20
Сколько подмассивов с суммой 3 найдёт программа?
Python
a = [1, 2, 1, 2]
target = 3
counts = {0: 1}
prefix = 0
answer = 0
for x in a:
    prefix += x
    answer += counts.get(prefix - target, 0)
    counts[prefix] = counts.get(prefix, 0) + 1
print(answer)
Вопрос 20 из 20
В какой задаче обычная хеш-таблица недостаточна без дополнительной структуры?

Ответьте на все 20 вопросов, чтобы получить результат

🔗 Встроить тест на свой сайт (iframe) ▼

Скопируйте код и вставьте в любое место на вашем сайте:

Также доступна прямая ссылка на embed-страницу