main

Вопросы на собеседовании по структурам данных

Наши соц. сети: instagram, fb, tg

Вопросы на собеседовании по структурам данных

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

Сегодня мы рассмотрим семь общих вопросов по структурам данных JavaScript, по одному для каждой из структур данных, которые мы обсуждали ранее. Каждый из них также обсудит свою временную сложность на основе теории обозначений BigO.

Массив: удалить все четные целые из массива

Постановка задачи: реализовать функцию removeEven(arr), которая принимает массив arr на вход и удаляет все четные элементы из данного массива.

Ввод: массив случайных чисел


[3, 2, 41, 3, 34]


Вывод: массив, содержащий только нечетные целые числа


[3, 41, 3]


Есть два способа решить эту проблему кодирования на собесе. Давай обсудим каждый.

Решение № 1: Делать это «вручную»

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

Решение № 2: Использование filter() и лямбда-функции

Это решение также начинается с первого элемента и проверяет, является ли оно четным. Если он четный, он отфильтровывает этот элемент. Если нет, переходит к следующему элементу, повторяя этот процесс, пока он не достигнет конца массива.

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

Стек: Проверьте наличие сбалансированных скобок, используя стек

Постановка задачи: Реализуйте функцию isBalanced(), чтобы получить строку, содержащую только фигурные скобки {}, квадратные [] и круглые ().
Функция должна сообщить нам, все ли скобки в строке сбалансированы. Это означает, что каждая открывающая скобка будет иметь закрывающую. Например, {[]} сбалансирован, а {[}] нет.
Входные данные: строка, состоящая исключительно из ( ) { } [ ]

exp = "{[({})]}"


Вывод: возвращает False, если выражение не имеет сбалансированных скобок. Если это так, функция возвращает True.

Чтобы решить эту проблему, мы можем просто использовать стек символов. Посмотри на код ниже, чтобы понять, как он работает.

Этот процесс будет перебирать строку по одному символу за раз. Мы можем определить, что строка не сбалансирована, основываясь на двух факторах:

1. Стек пуст.

2. Верхний элемент в стеке неправильного типа.

Если любое из этих условий выполняется, мы возвращаем False.
Если скобка является открывающей скобкой, она помещается в стек. Если к концу все сбалансированы, стек будет пустым. Если стек не пуст, мы возвращаем False. Поскольку мы пересекаем строку exp только один раз, временная сложность составляет O (n).

Очередь: генерировать двоичные числа от 1 до n

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

n = 3


Вывод: возвращает двоичные числа в виде строк от 1 до n

result = ["1","10","11"]


Самый простой способ решить эту проблему - использовать очередь для генерации новых номеров из предыдущих номеров. Давай разберемся с этим.

Ключ должен генерировать последовательные двоичные числа, добавляя 0 и 1 к предыдущим двоичным числам. Чтобы уточнить:
10 и 11 могут быть сгенерированы, если 0 и 1 добавлены к 1.
100 и 101 генерируются, если 0 и 1 добавляются к 10.
Как только мы сгенерируем двоичное число, оно помещается в очередь, так что новые двоичные числа могут быть сгенерированы, если мы добавим 0 и 1, когда это число будет поставлено в очередь. Поскольку очередь это First-In First-Out, двоичные числа, помещенные в очередь, удаляются из очереди, так что результирующий массив математически корректен.
Посмотри на код выше. В строке 7 1 ставится в очередь. Чтобы сгенерировать последовательность двоичных чисел, число удаляется из очереди и сохраняется в массиве результата. В строках 11-12 мы добавляем 0 и 1 для получения следующих чисел. Эти новые номера также ставятся в очередь в строках 14-15. Очередь будет принимать целочисленные значения, поэтому она преобразует строку в целое число при постановке в очередь.
Временная сложность этого решения заключается в O (n) O (n), поскольку операции с постоянным временем выполняются n раз.

Связанный список: отменить связанный список

Постановка задачи: Напишите функцию обратного просмотра, чтобы взять односвязный список и развернуть его на месте.

Вход: односвязный список


LinkedList = 0->1->2->3-4


Вывод: обратный связанный список


LinkedList = 4->3->2->1->0


Самый простой способ решить эту проблему - использовать итеративные манипуляции с указателями. Давай посмотрим!

Мы используем цикл для перебора списка ввода. Для current узла его связь с previous узлом обратная. Затем next сохраняет следующий узел в списке. Давай разберем это по строкам.
Строка 11 - сохранить current элемент nextElement в next
Строка 12 - установить nextElement current узла на previous
Строка 13 - сделать current узел новым previous для следующей итерации
Строка 14 - Используйте next, чтобы перейти к следующему узлу
Строка 18 - мы сбрасываем указатель head, чтобы он указывал на последний узел
Поскольку список просматривается только один раз, алгоритм работает в O (n).

Дерево: Найти минимальное значение в бинарном дереве поиска

Постановка проблемы: Используйте функцию findMin (root), чтобы найти минимальное значение в бинарном дереве поиска.

Вход: корневой узел для двоичного дерева поиска


bst = {

6 -> 4,9

4 -> 2,5

9 -> 8,12

12 -> 10,14

}

where parent -> leftChild,rightChild


Вывод: наименьшее целочисленное значение из этого двоичного дерева поиска


2


Давай посмотрим на простое решение этой проблемы.

Решение: итеративный findMin( )
Это решение начинается с проверки, является ли корень null. Возвращает null, если так. Затем он перемещается в левое поддерево и продолжает работу с левым дочерним узлом каждого узла, пока не будет достигнут самый левый дочерний узел.

Граф: удалить вершину

Постановка проблемы: Реализуйте функцию removeEdge, чтобы взять входные данные и назначение в качестве аргументов. Он должен определить, существует ли грань между ними.

Входные данные: график, источник и пункт назначения

first

Вывод: график с удаленной гранью между источником и пунктом назначения.


removeEdge(graph, 2, 3)


second

Решение этой проблемы довольно простое: мы используем индексирование и удаление. Посмотрим…

Поскольку наши вершины хранятся в массиве, мы можем получить доступ к source по связанному списку. Затем мы вызываем функцию delete для связанных списков. Временная сложность для этого решения составляет O (E), поскольку нам, возможно, придется пересечь E ребра.

Хеш-таблица: конвертировать Max-Heap в Min-Heap

Постановка задачи: Реализуйте функцию convertMax(maxHeap) для преобразования двоичной max-heap в двоичную min-heap. maxHeap должен быть массивом в формате maxHeap, т.е. родительский элемент больше, чем его дочерние элементы.
Вход: Max-Heap

maxHeap = [9,4,7,1,-2,6,5]


Выход: возвращает преобразованный массив


result = [-2,1,5,9,4,6,7]


Чтобы решить эту проблему, мы должны минимально heap-икнуть всех родительских узлов. Посмотрим…

Мы считаем maxHeap регулярным массивом и переупорядочиваем его для точного представления минимальной кучи. Ты можешь увидеть это в коде выше. Затем функция convertMax() восстанавливает свойство heap на всех узлах самого нижнего родительского узла, вызывая функцию minHeapify(). Что касается времени, это решение занимает O(nlog(n))O(nlog(n)) время.