Day #6: XOR Doubly Linked List

Hello. Today is the Day 6 of the #100DaysOfCodeChallenge. Received a problem previously asked by Google with a hard tag to it.

The Question On Day #6:

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.

Doing it on C++, since pointer implementation on Python is messy and not efficient.

Algorithm

The main logic behind the question is to understand the properties of XOR.
Refer wiki.

C++ Code

https://gist.github.com/nmreddy1911/28584d0667a1f920bcb580970ab3b25b

Output

Nodes: 
40 30 20 10

Explanation

Not getting much into the details of the logic, the wikipedia reference speaks it all.

You can look into the visualiser to understand the BTS of the logic here.

Feel free to reach out for any query clearance.

Thanks and cheers:)

Day #6: XOR Doubly Linked List

Comments

100 Days Of Code

Day #7: Number of possible decodable messages

More from this blog

DIY Portfolio: Unleashing Your Professional Story Online

Building Code Runner - Part #2 : Node.js Backend With Express Server and JDoodle API

Building Code Runner - Part #1 : Creating An Overview And MERN Project Setup With PNPM and Vite

Building Code Runner - Part #0

Day #8: Number Of Unival Trees Using Python

The Question On Day #6:

Algorithm

C++ Code

Explanation

Command Palette

Comments

100 Days Of Code

Day #7: Number of possible decodable messages

More from this blog

The Question On Day #6:

Algorithm

C++ Code

Explanation