Welcome to another coding interview challenge. In this series of blog posts, we ask you sample coding interview questions asked by top tech companies in Silicon Valley. Today we are turning up the heat by asking you to implement an XOR linked list. As always, share your answers by linking to a pastebin or gist in the comments below. Happy Coding ūüėÄ

Difficulty: HARD

An XOR linked list is a more memory efficient than a 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_pointerfunctions that converts between nodes and memory addresses.