Daily Coding Problem: Problem #6

Photo by Emil Priver on Unsplash

Problem

This problem was asked by Google.

An XOR linked list is a more memory efficient doubly linked list. Instead of each node holding next and prev fields, it holds a field named both, which is an XOR of the next node and the previous node. Implement an XOR linked list; it has an add(element) which adds the element to the end, and a get(index) which returns the node at index.

If using a language that has no pointers (such as Python), you can assume you have access to get_pointer and dereference_pointer functions that converts between nodes and memory addresses.

Solution

Let’s understand the problem. Instead of using our traditional next and prev variables to store the next and previous node’s address, we will use a both pointer which stores the XOR of the next and previous node’s address. Might be a little confusing, let’s visualize with an example

A ←→ B ←→ C ←→ D

A.both contains B
B.both contains A^C
C.both contains B^D
D.both contains C

Now how do iterate through the list or how do we find the address of the next node since the current node’s both contains the XOR or previous and the next node. It turns out that it is quite simple. If we do XOR of the previous node’s both with the current node, we get the pointer to the next node. We can initialize the previous to be 0 . And XOR or anything with 0 is itself.

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'

Time Complexity for add : O(1)

Time Complexity for get : O(n)

I hope you guys enjoyed this post.

If you find it helpful, please share and claps are much appreciated! 😄

Feel to ask your queries in the comments section!.

bumblebee211196/DailyCodingProblems