React Frontend Developer

Question 1

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

Accepted Answer

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

Question 2

Как уменьшить сложность с O(n²) до O(n)?

Accepted Answer

Чтобы уменьшить сложность с O(n²) до O(n), нужно заменить вложенные циклы на более эффективные структуры данных, например, хеш-таблицы. Вместо перебора всех пар элементов можно использовать один проход с записью данных в словарь. Это позволяет находить нужные элементы за константное время. Такой подход часто применяется в задачах поиска пар, подсчёта частот или проверки дубликатов.

Question 3

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

Accepted Answer

Линейная сложность O(n) означает, что время выполнения алгоритма растет прямо пропорционально размеру входных данных n. Например, если на входе 10 элементов, алгоритм делает 10 операций, а на 100 элементах — 100 операций. Это типично для простого перебора массива в поиске значения.

Question 4

Как реализовать удаление дубликатов из массива объектов за линейное время O(n) без использования Set (например, через объект-хэш)?

Accepted Answer

Для удаления дубликатов за O(n) используйте объект как хэш-таблицу. Создайте пустой объект, затем пройдите по массиву, используя уникальное свойство объекта как ключ. Если ключ уже существует, пропустите элемент, иначе добавьте его в результат и запишите ключ в объект. Это позволяет проверять уникальность за константное время.

Вопросы React Frontend Developer