На сегодняшнем конкурентном рынке труда, особенно в области разработки программного обеспечения в ведущих технологических гигантах, таких как Meta, очень важно быть готовым. Одной из часто затрагиваемых тем в таких интервью является структура данных LinkedList.
Ознакомьтесь с курсом Coderust: Hacking the Coding Interview для интервью по программированию в Facebook и Google.
Углубившись в это, мы составили список из десяти самых популярных вопросов LinkedList, которые часто задают в интервью по разработке программного обеспечения Meta, в комплекте с решениями Python.
1. Обратный LinkedList
Учитывая односвязный список, напишите функцию для его обращения. Эта задача проверяет понимание обхода LinkedList и манипулирования указателями.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseLinkedList(head):
prev = None
current = head
while current:
next_node = current.next
current.next = prev
prev = current
current = next_node
return prev
2. Обнаружение цикла в LinkedList
Используя алгоритм поиска цикла Флойда, определите, есть ли в данном LinkedList цикл или нет. Задача здесь состоит в том, чтобы обнаружить циклы, не используя дополнительное пространство.
def hasCycle(head):
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
Получите более высокую зарплату с помощью Grokking Comp Negotiation in Tech.
3. Найдите средний элемент
Не зная длины LinkedList, придумайте способ найти его средний элемент. Этот вопрос часто включает подход «черепаха и заяц».
def findMiddle(head):
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
