coding problems

I found a set of linked list coding problems I’d never seen before.

The document is titled Linked List Problems, written and copyright by Nick Parlante, dated 2002. Apparently Linked List Problems is part of the Stanford CS Education Library, which looks to date to around the end of the 20th Century.

• Problem statement and some experimentation
• Explanation of the algorithm I came up with in 2021.
• Recursive merge sort algorithm to have something to compare
• Re-using linked lists while benchmarking
• Effect of address-ordered linked lists
• Traversing linked lists does not exhibit weird performance drops at specific list lengths
• Effect of size of linked list nodes tests whether virtual memory is somehow involved. It is not.
• Bottom-up implementation with linked lists from Wikipedia, has the same performance drops as my July 2021 algorithm
• Memory access effects: incrementing .Data values, or arbitrarily changing .Next pointers does not cause the performance drops, and looking for other anomalies
• Effect of garbage collection before preparing a new, unsorted, linked list
• The memory access patterns of recursive and wikipedia bottom up algorithms are identical, for linked lists that are powers-of-2 long. For other length linked lists, the memory access patterns are not.
• I wrote an iterative, explicit stack frame variation of recursive mergesort to try to get the same abrupt performance drops as the wikipedia bottom up algorithm. No joy.
• Recursive mergesort variations that explore specific differences between iterative and recursive algorithms do not impart any revelations.
• Counts of comparison operations finally reveals the cause of the performance drops.
• More counts of comparison operations, this time featuring pre-sorted and reverse-sorted initial linked lists

What happens if you compare the number of comparisons made by recursive and wikipedia bottom up algorithms if the initial list is pre-sorted (low data value to high data value) or reverse sorted (high data value to low).

My recursive mergesort algorithm, and the wikipedia bottom-up) algorithm read and write the same list nodes in the same order, for list lengths that are powers of two. Something other than mere data reading and pointer writing causes abrupt performance drops at linked list lengths of 2^N+1 nodes.

I decided to count the number of comparisons used in merging lists. I had to write a different program so as to use an unsorted list with data in the same randomly chosen order for each of the three algorithms.

I tried several minor variations of recursive mergesort to try to understand the abrupt performance drops that my iterative mergesort code exhibits at some linked list lengths.

I wrote variants of recursive mergesort that simulate function call recurision by iteration with an explicit stack of activation records. This is an effort to try to understand the abrupt performance drops that the wikipedia bottom up algorithm exhibits at some linked list lengths.

Incidentally, these two algorithms both satisfy the Daily Coding Problem problem statement. Their simulated call stack could potentially overflow for extremely long lists, but those stacks wouldn’t have to be much bigger to accomodate those long lists.

I finally looked at the addresses of linked list nodes that my recursive and wikipedia bottom-up) algorithms read and write.

Daily Coding Problem: Problem #1790 [Easy]

Implement the function fib(n), which returns the n^th number in the Fibonacci sequence, using only O(1) space.

Problem Statement

Given a list of words, find all pairs of unique indices such that the concatenation of the two words is a palindrome.

For example, given the list [“code”, “edoc”, “da”, “d”], return [(0, 1), (1, 0), (2, 3)].