software engineering

Wikipedia has this entry for Benford’s Law, which deals with the distribution of leading digits of a collection of samples.

Idly looking up a coding problem got me to investigate Dyck Languages, which led me to update my binary tree Go package.

There’s one more item I discovered during my mergesort investigation that bothers me. I wrote code that finishes with a low-to-high data value list. Starting with a “reverse sorted” (high-to-low data values) list with Wikipedia’s bottom up algorithm does not show the abrupt performance drops that a randomly-chosen data values initial list does, but has bumps in comparison count at lists of 2^N+1 lengths.

Why is this?

I wrote a Go program this morning. I thought of a super clever way to find the median of a sorted slice of float64 types. This clever way to do medians worked in the little program I wrote first, because I strictly follow Gall’s Law.

I read an article about Term Frequency-Inverse Document Frequency on John D. Cook Consulting’s blog.

When you write Go code, you use os.Stdout and os.Stderr instead of our old C friends, stdout and stderr from stdio.h. os.Stdin, os.Stdout and os.Stderr have type *os.File. This Go type encapsulates encapsulates Linux file descriptors (small integer values representing open files).

Here’s the problem:

---

Read a file of text, determine the n most frequently used words, and print out a sorted list of those words along with their frequencies.

Another puzzle courtesy the Daily Coding Problem email list.

Daily Coding Problem: Problem #1578 [Hard]

This problem was asked by Facebook.

Given an array of numbers of length N, find both the minimum and maximum using less than 2 * (N - 2) comparisons.

---

Github repo for my solution.

This is from the Daily Coding Problem email list. The owners of that list haven’t sent out a problem that caught my imagination in quite a while.

Daily Coding Problem: Problem #1553 [Hard]

This problem was asked by Airbnb.

You come across a dictionary of sorted words in a language you’ve never seen before. Write a program that returns the correct order of letters in this language.

For example, given ['xww', 'wxyz', 'wxyw', 'ywx', 'ywz'], you should return ['x', 'z', 'w', 'y'].

---

Github repo for my solution. Feel free to look it over, try it and email me (bediger8@gmail.com) if you notice anything.

I ran across an engineering aphorism or principle called “Gall’s Law”:

A complex system that works is invariably found to have evolved from a simple system that worked. The inverse proposition also appears to be true: A complex system designed from scratch never works and cannot be made to work. You have to start over, beginning with a working simple system.