Ежедневная проблема кодирования: проблема № 6

Проблема

Эта проблема была задана Google.

Связанный список XOR — это двусвязный список с более эффективным использованием памяти. Вместо того, чтобы каждый узел содержал поля next и prev, он содержит поле с именем both, которое является XOR следующего узла и предыдущего узла. Реализовать связанный список XOR; у него есть add(element), который добавляет элемент в конец, и get(index), который возвращает узел по индексу.

Если вы используете язык без указателей (например, Python), вы можете предположить, что у вас есть доступ к функциям get_pointer и dereference_pointer, которые выполняют преобразование между узлами и адресами памяти.

Решение

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

A ←→ B ←→ C ←→ D

A.both содержит B
B.both содержит A^C
C.both содержит B^D
D.both содержит C

Теперь, как выполнить итерацию по списку или как найти адрес следующего узла, поскольку текущий узел содержит XOR или предыдущий и следующий узлы. Оказывается, это совсем просто. Если мы делаем XOR предыдущего узла с текущим узлом, мы получаем указатель на следующий узел. Мы можем инициализировать предыдущий как 0 . И XOR или что-нибудь с 0 само по себе.

import ctypes


def _get_obj(id):
    return ctypes.cast(id, ctypes.py_object).value


class Node:

    def __init__(self, val):
        self.val = val
        self.both = 0


class XORLinkedList:

    def __init__(self):
        self.head = self.tail = None
        self.__nodes = []

    def add(self, element):
        node = Node(element)
        if self.head is None:
            self.head = self.tail = node
        else:
            node.both = id(self.tail)
            self.tail.both = id(node) ^ self.tail.both
            self.tail = node

    def get(self, index):
        head = self.head
        prev = 0
        for i in range(index):
            next = head.both ^ prev
            if next:
                prev = id(head)
                head = _get_obj(next)
        return head.val


xor_ll = XORLinkedList()
xor_ll.add('1')
xor_ll.add('2')
xor_ll.add('3')

assert xor_ll.get(0) == '1'
assert xor_ll.get(1) == '2'
assert xor_ll.get(2) == '3'

Временная сложность для add: O(1)

Временная сложность для get: O(n)

Надеюсь, вам понравился этот пост.

Если вы найдете это полезным, пожалуйста, поделитесь, и хлопки очень ценятся! 😄

Не стесняйтесь задавать свои вопросы в разделе комментариев!.