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 😀
An XOR linked list is a more memory efficient than a doubly linked list. Instead of each node holding
prevfields, 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
dereference_pointerfunctions that converts between nodes and memory addresses.