#7 – 100 Days of Coding Problems

Day 7

Photo by Glenn Carstens-Peters on Unsplash

The Problem

Given a linked list, uniformly shuffle the nodes. What if we want to prioritize space over time?
https://dailycodingproblem.com

The Thought Process

Given the problem’s instructions, it was assumed that the linked list was not circular, and therefore had an end element.

When trying to figure out the solution to this problem, I first searched the internet for ways to “uniformly” shuffle an array. I came across this stackoverflow question, which led me to the Fisher—Yates shuffle. This algorithm shuffles all the elements in-place, which makes it quite space-efficient.

— Option 1

Next, I considered the different ways in which the linked list could be optimized in order to take the least time. My first thought was that it would make the whole process quicker if I could get it out of the form of a linked list and into an object format to make fetching each node much faster. The algorithm might look something like this:

1. Turn the linked list into an object data structure (n operations)
2. Shuffle the linked list (n operations)
3. Turn the object back into a linked list (n operations)

The number of operations required would total to: 3n

— Option 2

The alternative option would be to go through the linked list each time. It might look something like this:

Picking a random number from the list (n operations to figure out how long the linked list is)
Taking a random element from the list and moving it to the end ([n(n+1)]/2 operations)

The number of operations required would total to: [n^2+3n]/2

Comparing the two options

To find out which option would be more efficient at different linked list lengths, I plugged the equations into desmos:

And found that when the list contained less than 3 nodes, option 2 was more efficient, but as soon as the number of nodes passed 3, the first option was more efficient. That being said, option 1 is much less space efficient.

In solving the problem, I plan on writing both algorithms so as to provide code samples of each one.

Shared Code

First, I wrote the code that would be shared between both options. This includes the “Link” class (since Node is reserved in TypeScript), a helper function constructList that constructs a linked list of a given length, and another helper function printList that prints the list values using arrows (for debug purposes).

class Link {
	val?: any
	next?: Link = null

	constructor(val: any) {
		this.val = val
	}
	
	setNext (node: Link) {
		this.next = node
		return this
	}
}

function constructList (length: number) {
	if (length < 1) {
		throw new Error('Length cannot be less than 1')
	} else if (length === 1 ) {
		return new Link(1)
	} else {
		return new Link(length).setNext(constructList(length - 1))
	}
}

function printList (list: Link, message = '') {
	if (list.next === null) {
		console.log(`${message}${list.val}`)
	} else {
		message += `${list.val} -> `
		printList(list.next, message)
	}
}

View Code

The Solutions

— Option 1 – Time Efficient

const list = constructList(100)

function listToArray (list: Link): Link[] {
	if (list.next === null) {
		return [list]
	} else {
		const currentLink = list
		const nextLink = currentLink.next
		currentLink.next = null
		return [currentLink].concat(listToArray(nextLink))
	}
}

function randomizeTimeEfficient (list: Link) {
	const arrayFormat = listToArray(list)
	return randomizeTimeEfficientRecursive(arrayFormat)
}

function randomizeTimeEfficientRecursive (list: Link[], current?: Link) {
	const length = list.length

	if (length === 0) {
		return current
	}
	
	const randomIndex = Math.round(Math.random() * length)
	const randomLink = list[randomIndex]
	// Construct a list without the randomIndex
	const nextList = list.slice(0, randomIndex).concat(list.slice(randomIndex + 1))
	
	if (current) {
		current.setNext(randomizeTimeEfficientRecursive(nextList, randomLink))
		return current
	} else {
		return randomizeTimeEfficientRecursive(nextList, randomLink)
	}
}