Programming Praxis

We have today another exercise from our never-ending supply of interview questions:

Given a string, find the first character that appears only once in the string. For instance, given the string “aabbcddd”, the first character that appears only once is the “c” found at the 4th character in the string, counting from 0. Be sure that your program properly handles the case that all characters appear more than once.

Your task is to write a program that finds the first unrepeated character in a string, and its index in the string. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

My solution to the previous exercise has a horrible performance bug. Because of its use of shuffle, the function takes time proportional to the length of the dictionary instead of the length of the passphrase. For a four-word passphrase and the 3097-word dictionary used in the solution, that’s a three-order-of-magnitude performance bug. Ouch!

Your task is to fix your solution if you got it wrong like I did. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

In his 936th xkcd comic strip, Randall Munro described what is wrong with common passwords and suggested a method of passphrase generation that is simpler to use and provides greater security. Unfortunately, I know of no popular websites that permit xkcd-style passphrases. I do still recall, however, the xkcd-style passphrase that CompuServe assigned me about twenty-five years ago (does anyone else remember upgrading from a 1200 baud modem to 9600 baud?)

Your task is to write an xkcd-style passphrase generator. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

We filled in a missing piece of the Standard Prelude in the previous exercise. In today’s exercise we fill in another missing piece, the integer root function: iroot(k, n) returns the largest integer x such that x^k does not exceed n, assuming k and n are both positive integers. For example, iroot(3, 125) equals 5, because 5³ equals 125; likewise, iroot(3, 126) equals 5, but iroot(3, 124) is 4, because 5³ is greater than 124.

Your task is to write the integer root function. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

In many programming languages, dates have a kind of “second class” relationship to data types such as integers, characters, strings and arrays; functions related to dates, such as finding the number of days between two dates, may be relegated to libraries or omitted entirely. Our Standard Prelude provides a few simple date functions, but missing is a function to neatly format a date.

Your task is to write a function that takes a date and returns a neatly-formatted string representing the input date; your function may be as simple or as elaborate as you wish. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

One of the pleasures of writing a blog like mine is that I get to learn from my readers just as they learn from me. In a comment on the previous exercise on cyclic equality, reader Maurits pointed to Booth’s algorithm, which I had never previously heard of. Note that Booth’s algorithm is somewhat different than the one we gave in the previous exercise, since Booth’s algorithm relies on an ordering predicate between elements of the cycle while our algorithm relies only on an equality predicate.

Booth’s algorithm creates a canonical rotation of a cycle by putting it in the least possible lexicographic order out of all possible rotations. This is done by a variant of the Knuth-Morris-Pratt string search algorithm. We won’t give the algorithm here, as Wikipedia does a fine job; Booth’s original paper, referenced at Wikipedia, is behind a paywall. Here is Wikipedia’s explanation:

The algorithm uses a modified preprocessing function from the Knuth-Morris-Pratt string search algorithm. The failure function for the string is computed as normal, but the string is rotated during the computation so some indices must be computed more than once as they wrap around. Once all indices of the failure function have been successfully computed without the string rotating again, the minimal lexicographical rotation is known to be found and its starting index is returned. The correctness of the algorithm is somewhat difficult to understand, but it is easy to implement.

Your task is to implement the cyclic equality test of the prior exercise using Booth’s linear-time algorithm. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Two cyclic lists are equal if they have the same number of elements in the same order. For instance, the cyclic lists (1 2 3 4 5) and (3 4 5 1 2) are equal. So are the cyclic lists (1 1 2 2) and (2 1 1 2), and also the cyclic lists (1 1 1 1) and (1 1 1 1). The two cyclic lists (1 2 3 4) and (1 2 3 5) are not equal because they have different elements, and the cyclic lists (1 1 1) and (1 1 1 1) are not equal because they have different lengths.

Your task is to write a function that takes two cyclic lists and determines if they are equal. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Today’s exercise appears from time to time on beginning-programmer message boards:

Write a program that, given n, returns the last non-zero digit of n! (factorial). For instance, 7! = 1 * 2 * 3 * 4 * 5 * 6 * 7 = 5040, and its last non-zero digit is 4.

Your task is to write a program to find the last non-zero digit of a factorial. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

We implemented a very basic quadratic sieve in a previous exercise. In today’s exercise we will implement three improvements to the sieving phase of the algorithm.

The first improvement comes from the world of code tuning: we will segment the sieve instead of employing a single monolithic sieve. This allows us to tune the memory footprint of the sieve and keep everything in cache memory, which makes the entire process much faster. The second improvement also comes from the world of code tuning: we will use logarithms base 2 instead of base e, because they keep the entire calculation within the realm of integer arithmetic instead of floating-point arithmetic, and we will define an error factor on the sum of the logarithms based on the size of n.

The third improvement is algorithmic. Sometimes when checking a possible smooth number, a number is found that is almost smooth, with a single large prime factor between f and f²; such relations are called partial relations. If the large primes of two partial relations are equal, they can be multiplied together to form a match, which can then be treated like any other relation in the exponent vector. By the birthday paradox, matches are more common than you might think. Thus, sieving produces two lists, a list of relations and a list of partials, then the partials are sorted on their leading prime and a simple scan through the list of partials identifies the matches. The effect is to find more usable relations with the same amount of sieving.

Your task is to modify the quadratic sieve of the previous exercise to incorporate these changes. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2