Coding Problems

I stumbled across a blog post about finding the median of a list of numbers as a job interview question.

John D. Cook Consulting seems to do the manner of work that regular programmers like me only dream of doing, and their blog entries are uniformly interesting, educational and somehow esoteric. I’m amazed by them.

John D. Cook Consulting’s blog published a post Fitting a regular expression to a list of words where (apparently!) John Cook himself shows how to use a Python library to combine several strings into a regular expression that, when interpreted by a program like grep, will match all those strings.

The Go Blog has a post titled Allocating on the Stack. The post makes the claim that programs compiled with Go v1.26 compiler, and using the v1.26 runtime can allocate backing store of slices on the stack under some circumstances.

A long time ago, I worked at a company that has since merged with another large company. Back in the day, my employers kept a technical reference library that included back issues of a magazine, Software: Experience and Practice. A few of the earliest issues of that magazine had a “Computer Recreations” column. Volume 2, pages 397-400 had a column on self reproducing programs.

I came across an article by Brian Kernighan. The article is about a piece of C code written by Rob Pike, apparently for a book Pike and Kernighan wrote together, The Practice of Programming.

The old Daily Coding Problem email list gave us this problem around 2020:

Daily Coding Problem: Problem #237 [Easy]

A tree is symmetric if its data and shape remain unchanged when it is reflected about the root node. The following tree is an example:

        4
      / | \
    3   5   3
  /           \
 9             9

Given a k-ary tree, determine whether it is symmetric.

This problem is less well described than I thought when I worked on it in 2020.

There’s an older programming job interview question:

Given a string of round, curly, and square open and closing brackets, return whether the brackets are balanced (well-formed).

For example, given the string “([])”, you should return true.

Given the string “([)]” or “((()”, you should return false.

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. I looked for other anomalies, too.
• 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
• Try to understand if merge algorithm choices affects mergesort performance.
• Examine effects of worst case initial data affects mergesort comparison counts.

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