Рубрики
Без рубрики

10 Обязательных Вопросов Для Интервью Со Связанным Списком

Связанный список Вопросов и ответов для интервью, чтобы подготовиться к собеседованию по структурам данных и алгоритмам. 10 Лучших Вопросов Из Связанного Списка.

Автор оригинала: Pankaj Kumar.

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

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

В этом уроке мы рассмотрим 10 основных вопросов из Связанных списков, которые вы должны знать, прежде чем пройти техническое собеседование.

1. Что такое Связанный список?

Связанный список-это структура данных, в которой хранятся коллекции данных. Он обладает следующими свойствами:

  • Последовательные элементы соединены указателями.
  • Последний элемент указывает на нуль ( для некруглого LL).
  • Может быть сделано столько, сколько потребуется, и может увеличиваться/уменьшаться во время выполнения программы.

2. Чем связанный список отличается от массива?

Массивы также хранят коллекции данных, однако в массиве элементы доступны через их индекс. Адрес каждого блока в массиве может быть вычислен с использованием адреса нулевого элемента. Находясь в Связанном списке, адрес блока сохраняется в блоке перед ним.

3. Каковы преимущества и недостатки массива по сравнению со связанным списком?

Преимущества:

  • Массивы просты и удобны в использовании.
  • Массивы обеспечивают более быстрый доступ к элементам.

Недостатки:

  • Поскольку массив предварительно выделяет необходимую память, это часто приводит к потере памяти, если блоки остаются пустыми. В то время как в Связанном списке блок или узел создается только тогда, когда это необходимо.
  • Массивы имеют фиксированный размер.
  • Вставка элемента в заданное положение требует перемещения элементов, что является вычислительно неэффективным.

4. Каковы преимущества и недостатки связанного списка по сравнению с массивом?

Преимущества:

  • Связанный список может быть расширен в течение постоянного времени.

Недостатки:

  • Время доступа к элементу в Связанном списке равно не O(1).

5. Сравните связанный список и массив с точки зрения времени их вставки/удаления.

Параметр Связанный список Массив
Вставка/удаление в начале O(1) O(n)
Удаление в конце O(n) O(1)
Вставка в конце O(n) O(1)
Вставка посередине O(n) O(n)
Удаление в середине O(n) O(n)

Чтобы узнать больше о сравнении массива и связанного списка, прочитайте это руководство . В нем очень подробно рассматривается сравнение и реализация этих двух методов.

6. Что такое Круговой связанный список?

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

Если вы продолжите обходить круговой связанный список, ища “null”, чтобы завершить обход, вы застрянете в бесконечном цикле.

7. Как вы определите длину данного Связанного списка?

Существует два способа определения длины связанного списка.

  • Повторяющийся
  • Рекурсивный

Итеративный подход заключается в следующем:

  • Заголовок Указывает на Первый Узел Списка.
  • Инициализируйте переменную count значением 0
  • Инициализируйте переменную temp с помощью Head
  • Пройдите через LL, используя temp.
  • По мере доступа к каждому узлу значение переменной count увеличивается на 1.
  • Остановите процесс, когда мы достигнем нуля.
  • количество возвратов.

Рекурсивный подход заключается в следующем:

Для рекурсии нам нужен базовый случай и рекурсивное уравнение.

Базовый Случай:

  • Последний узел указывает на нулевое значение
  • Верните 0 и выйдите.

Рекурсивный Случай:

  • На каждом шаге обновляйте значение текущего узла до следующего узла
  • Вызов= 1+веселье(далее)

Чтобы ознакомиться с кодом для обоих методов, прочитайте учебник о том, как найти длину связанного списка?

8. Как вы можете обнаружить цикл в Связанном списке?

Наиболее оптимальным способом обнаружения цикла в Связанном списке является использование алгоритма поиска циклов Флойда.

Алгоритм использует два указателя, которые движутся с разной скоростью. Если есть цикл, оба указателя будут указывать на одно и то же значение в какой-то момент в будущем.

Обычно эти два указателя работают медленно и быстро. Самый быстрый движется с удвоенной скоростью. Если они встретятся в какой-то момент, то наступит цикл. Если цикла нет, то быстрый указатель пройдет через весь связанный список и дойдет до конца. В случае цикла в связанном списке не будет конца. Следовательно, эти два указателя обязательно встретятся.

Чтобы ознакомиться с реализацией Алгоритма поиска циклов Флойда , ознакомьтесь с его учебным пособием.

9. Как вы можете отменить связанный список?

Чтобы отменить связанный список, существует два метода:

  • Повторяющийся
  • Рекурсивный

Вот учебное пособие, в котором подробно рассматривается эта тема вместе с реализацией.

10. Как распечатать связанный список в обратном порядке?

Основная идея здесь состоит в том, чтобы рекурсивно пройти до конца связанного списка. Затем, возвращаясь, начните печатать элементы.

Псевдокод выглядит следующим образом:

function printListFronEnd(List head){
if(head==null)
return;
printListFronEnd(head.next); // recursive call to the next 
print(head.data); // print when coming back after making all
                  //the recursive calls 

Вывод

Это были некоторые из важных вопросов в Связанном списке с точки зрения технического интервью. Чтобы узнать больше о связанных списках и других темах, связанных с техническими собеседованиями, перейдите в раздел “Вопросы для интервью” на нашем веб-сайте.