Post #104

Самый популярный follow-up вопрос на интервью в Meta и Amazon Всем привет! Прорабатываем сейчас с менти тему алгоритмов и структур данных (DSA), и я понял, что могут быть трудности с ответом на самый популярный follow-up вопрос на интервью в Meta и Amazon. ❓Итак, вы написали решение алгоритмической задачи, проверили решение. И интервьюер вас спрашивает: 'Какая у вас time & space complexity?' Для ответа на вопрос про time complexity для любого алгоритма, можно использовать такой подход, который хорошо работает для меня: 1) определить переменную для размера входных данных, ту самую 'n' (размер массива, количество вершин графа и т.п.) 2) понять, сколько шагов в алгоритме 3) дать 'цену' для каждого шага (постоянная работа - константа, цикл - число повторений, известные операции типа сортировки - n log n, бинарный поиск log n) 4) просуммировать 'цены' всех шагов, беря в расчет только 'порядок' роста (константа + константа = константа, n + n = n, n + n^2 = n ^2) 5) Сказать это словами как O(n) ('Big O of n') С этим подходом, зная 'цену' (сложность) стандартных операций вроде поиска в хеш-таблице (константа, ищется за постоянное время, оно же О(1)), можно без зубрежки уверенно отвечать на этот главный follow-up интервьюеров. Для space complexity еще проще - нужно оценить объем памяти для дополнительных структур данных, которые вы используете. Выразить это в привязке к длине входных данных. Например, на входе массив из n элементов и вы его копируете в другой массив такого же размера у вас в коде - space complexity будет O(n). Тонкий момент касается рекурсий - вы вроде как в явном виде не создаете новых структур данных, но при рекурсии в памяти создается стек вызова и ваша space complexity будет равна размеру этого стека. ⚠️ Важное уточнение: говоря о такой сложности, нужно различать среднюю и worst-case сложности. Для worst-case сложности вам надо сначала сформулировать, что это такое: Например, искомый элемент в массиве находится в самом конце и при поиске сначала мы его найдем, только просмотрев все n -1 остальных элементов. Или дерево, у которого у каждого узла всегда по 1-му потомку - тогда оно превращается в линейный список и поиск в глубину (DFS) для поиска числа в конечном листе этого дерева, должен будет пройти все n узлов. Подготовка к ответу на этот вопрос поможет вам и в ежедневной работе, вы начнете видеть ненужные линейные поиски, вложенные циклы, лишние вспомогательные структуры, которые занимают память. 👉@faangiscalling -------------------------------- Было интересно? Подпишитесь и поделитесь с друзьями!👋 Telegram — YouTube