React Frontend Developer

Question 1

Какую сложность будет иметь решение с объектом-словарём

Accepted Answer

Операции доступа к объекту-словарю (Object или Map) обычно имеют O(1). Это связано с использованием хеш-таблиц. Однако в худшем случае сложность может деградировать до O(n) из-за коллизий. На практике для большинства задач доступ считается константным.

Question 2

Как организовать очередь в JavaScript без использования структуры данных с O(1) shift, и стоит ли использовать Array.prototype.shift() при высокой нагрузке?

Accepted Answer

Метод Array.prototype.shift() имеет сложность O(n), так как при удалении первого элемента все остальные сдвигаются. Для очереди с высокой нагрузкой лучше использовать связный список или реализацию с двумя указателями (head/tail) на объекте. Также можно применять кольцевой буфер или библиотеки вроде 'denque'.

Question 3

Что такое хеш-функция и как она обеспечивает доступ к элементу HashMap за O(1)?

Accepted Answer

Хеш-функция преобразует ключ в целое число (хеш-код), которое затем используется для определения индекса в массиве (bucket). Благодаря прямому доступу по индексу, поиск элемента занимает O(1) в среднем. Коллизии (когда разные ключи дают одинаковый хеш) решаются с помощью цепочек или открытой адресации, что может ухудшить производительность до O(n) в худшем случае.

Question 4

Что такое константная сложность? Чему соответствует O(1)?

Accepted Answer

Константная сложность O(1) означает, что время выполнения алгоритма не зависит от размера входных данных. Алгоритм всегда выполняется за одно и то же количество операций, независимо от того, насколько велики входные данные. Примеры: доступ к элементу массива по индексу, вставка в начало хеш-таблицы (в среднем), проверка чётности числа.

Вопросы React Frontend Developer