Home

Daily Coding Problem #6 - Xor Linked List

February 23, 2019

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.

Thoughts

In order to work with memory addresses directly in Go, I’ll have to use the unsafe package, which is usually a big NO NO in a production app. But I guess solving whiteboard problem can be counted as an exception 😂.

Solution

6_xor_linked_list.go

package daily_coding_problem_in_go

import (
	"unsafe"
)

type XorNode struct {
	Val int
	Npx uintptr
}

// NewXorLinkedList returns a root node
func NewXorLinkedList(val int) *XorNode {
	return &XorNode{val, 0}
}

// Insert insert a value and return pointer to the new head node
func (head *XorNode) Insert(val int) *XorNode {
	newHeadNode := &XorNode{Val: val}
	ptr := unsafe.Pointer(head)

	newHeadNode.Npx = 0 ^ uintptr(ptr)
	newNodePtr := unsafe.Pointer(newHeadNode)

	head.Npx = uintptr(newNodePtr) ^ uintptr(head.Npx)

	return newHeadNode
}

func (head *XorNode) ToSlice() []int {
	var result []int
	prev := uintptr(0)
	this := unsafe.Pointer(head)
	result = append(result, head.Val)
	for prev^head.Npx != 0 {
		prev, this = uintptr(this), unsafe.Pointer(prev^head.Npx)
		head = (*XorNode)(this)
		result = append(result, head.Val)
	}
	return result
}

6_xor_linked_list_test.go

package daily_coding_problem_in_go

import (
	"testing"
)

var xorLinkedListTests = [][]int{
	{1, 2, 3, 4, 5},
	{5, 4, 3, 2, 1},
}

func TestXorLinkedList(t *testing.T) {
	for _, tc := range xorLinkedListTests {
		a := NewXorLinkedList(tc[0])
		for _, e := range tc[1:] {
			a = a.Insert(e)
		}
		if actual, expected := a.ToSlice(), Reverse(tc); !Equal(actual, expected) {
			t.Errorf("expecting %v, got %v", expected, actual)
		}
	}
}