Coding Problems

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)].

Previously, in July 2021, I had tried to remove garbage collection from the possible variables affecting my iterative mergesort. I transliterated the Go code to a plain C version that could not have any garbage collection. The C code benchmarked very similarly to the Go code.

As a way to see if merely accessing the linked list node’s memory causes the mergesort performance drops, I wrote two non-sorting functions and benchmarked them to try to distinguish

• accessing the nodes’ data
• modifying .Next pointers

Problem statement

This problem was asked by Cisco.

Given an unsigned 8-bit integer, swap its even and odd bits. The 1st and 2nd bit should be swapped, the 3rd and 4th bit should be swapped, and so on.

For example, 10101010 should be 01010101. 11100010 should be 11010001.

Bonus: Can you do this in one line?

I thought that since the purely recursive implementation of mergesort didn’t show weird, abrupt performance drops, traversing linked lists (no matter what order the nodes appeared in memory) also did not show abrupt performance drops, and that node size in memory caused different performance oddities, that the iterative implementation’s memory access patterns might be the cause.

I checked the effect of list element size on my implementation of mergesort of a linked list.

It occurred to me that benchmarking traversing very long linked lists end-to-end might provide some clues.