Питання на співбесіді: зв’язані списки із петлями
Зв’язані списки
Зв’язані списки одні із найбільш відомих структур даних і найбільш цікаві програмісти вивчають їх із самого початку. Але для повноти, давайте розглянемо їх коротко. Зв’язаний список являє собою послідовність вузлів. Кожен вузол містить фрагмент даних , а також посилання на наступний вузол в списку. Графічно це виглядає наступним чином
Зв’язаний список із петлею (циклом)
Можливо так, що вузол у зв’язаному списку може вказувати на попередній елемент у списку. Це погано з багатьох причин, не останньою з яких є те, що будь-який цикл, який перебирає всі вузли в списку через доступ до наступного вузлу ніколи не закінчиться. Таким чином, потрібно визначати, чи цикл має петлі. Ось ілюстрація того, як може виклядати список із петлею:
Легке рішення
Просте рішення полягає в тому, щоб відслідковувати кожен вузол, який було пройдено до цього і перевірити , якщо поточний вузол є у цьому списку. Ось дуже простий зв’язаний список, реалізований на Ruby.class Node attr_accessor :data, :next def initialize(data = nil) @data = data @next = nil end end
def has_loop?(node) seen = [] until node.next.nil? do return true if seen.include? node seen << node node = node.next end false end
Черепаха і заєць
Краще рішення вимагає трохи математичного мислення. Якщо є цикл, то це означає, що будь-який ітератор, незалежно від того скільки кроків приходиться на одну ітерацію, повинен досягти вузол-”порушник”. Таким чином, якщо у нас є два ітератора, один з яких має довжину, яка є кратною іншій, вони коли небуть опиняться на одному й тому ж вузлі. Звичайне рішення полягає у створенні одного ітератора на один крок (“черепаха”), а другий – на 2 кроки (“заєць”). Це алгоритм виглядає наступним чиномdef has_loop?(node) slow = node fast = node until slow.next.nil? or fast.next.nil? do slow = slow.next fast = fast.next.next return true if (slow == fast) end false end
Додаткові питання
Вважаючи, що відповідь на поставлені вище питання, отримана правильно і швидко, інтерв’юер, ймовірно, почне задавати додаткові питання. Як виправити зв’язаний список, коли ви виявляєте цикл? Що, коли він містить декілька петель? Як визначити розмір петлі?Я залишу вас замислитися над цими питаннями.
Оригінал: http://20bits.com/articles/interview-questions-loops-in-linked-lists/

![Як почати проект автоматизації тестування (переклад) [Image]](http://lh3.ggpht.com/_N74PyctBgQU/TFbNdbt_aJI/AAAAAAAAAWs/TEuCkX8h4Mo/Automation%20Project%20Start.png)
My LinkedIn Account
Останні коментарі