Programming Praxis

The sequence of Hamming numbers 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, … (A051037) consists of all numbers of the form 2ⁱ·3^j·5^k where i, j and k are non-negative integers. Edsger Dijkstra introduced this sequence to computer science in his book A Discipline of Programming, and it has been a staple of beginning programming courses ever since. Dijkstra wrote a program based on three axioms:

Axiom 1: The value 1 is in the sequence.

Axiom 2: If x is in the sequence, so are 2 * x, 3 * x, and 5 * x.

Axiom 3: The sequence contains no other values other than those that belong to it on account of Axioms 1 and 2.

.

Your task is to write a program to compute the first thousand terms of the Hamming sequence. 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

Here is another from our collection of interview questions:

Given a list of elements and a block size k, return the list of elements with every block of k elements reversed, starting from the beginning of the list. For instance, given the list 1, 2, 3, 4, 5, 6 and the block size 2, the result is 2, 1, 4, 3, 6, 5.

Your task is to write a function to solve the sublist-reversal problem. 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 look today at a famous problem known as the knapsack problem. The task is to fill a knapsack that can carry objects of a known total weight—the capacity—with objects of a given set—each object having a given weight and value—in such a way as to maximize the sum of the values of the objects. Since any individual object is subject to a binary decision to either take it or leave it, this variant of the knapsack problem is known as the 0/1 knapsack.

The usual algorithm uses dynamic programming on the recurrence expression V[i,w] = max(V[i−1,w], v_i + V[i−1,w−w_i]), where V[i,w] is the maximum value of a knapsack of capacity w using the first i objects (which must be arranged by increasing weight), v_i is the value of the ith object, and w_i is the weight of the ith object. The program builds up the V matrix, starting from V[0,w] = 0, for all weights 0 ≤ w ≤ W and all sets of objects 1 ≤ i ≤ n, where n is the number of objects available. The answer is V[n,W].

Your task is to write a function that implements the knapsack 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

This question appears on several lists of interview questions:

Write a function that takes an input string and returns the first character from the string that is not repeated later in the string. For instance, the two letters “d” and “f” in the input string “aabcbcdeef” are non-repeating, and the function should return “d” since “f” appears later in the string. The function should return some indication if there are no non-repeating characters in the string.

Your task is to write the indicated 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

Today’s task comes to us from i has 1337 code:

Given a cyclic list with elements in sorted order, write a function to insert a new element into the cyclic list that maintains the sorted order of the cyclic list. Do not assume that the cyclic list is referenced by its minimal element.

Your task is to write the function described above. 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

Daniel Tunkelang posted this interview question to his blog:

Given an input string and a dictionary of words, segment the input string into a space-separated sequence of dictionary words if possible. For example, if the input string is “applepie” and dictionary contains a standard set of English words, then we would return the string “apple pie” as output.

He also gave a number of constraints: The dictionary provides a single operation, exact string lookup, and is a given to the task; you are not to consider how to implement the dictionary, nor or you to worry about stemming, spelling correction, or other aspects of the dictionary. The output may have more than two words, if there is more than one solution you only need to return one of them, and your function should indicate if there are no solutions.

Your task is to write a function that solves the “word break” problem. 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

Over at PrologSite, Werner Hett gives a list of Ninety-Nine Prolog Problems “to give you the opportunity to practice your skills in logic programming.” Today’s exercise is number 1.28 on the list. Hett gives the problem two stars, meaning that he expects a skilled Prolog programmer to spend thirty to ninety minutes to solve it. Here is Hett’s statement of the problem:

1.28 (**) Sorting a list of lists according to length of sublists
a) We suppose that a list (InList) contains elements that are lists themselves. The objective is to sort the elements of InList according to their length. E.g. short lists first, longer lists later, or vice versa.

Example:
?- lsort([[a,b,c],[d,e],[f,g,h],[d,e],[i,j,k,l],[m,n],[o]],L).
L = [[o], [d, e], [d, e], [m, n], [a, b, c], [f, g, h], [i, j, k, l]]

b) Again, we suppose that a list (InList) contains elements that are lists themselves. But this time the objective is to sort the elements of InList according to their length frequency; i.e. in the default, where sorting is done ascendingly, lists with rare lengths are placed first, others with a more frequent length come later.

Example:
?- lfsort([[a,b,c],[d,e],[f,g,h],[d,e],[i,j,k,l],[m,n],[o]],L).
L = [[i, j, k, l], [o], [a, b, c], [f, g, h], [d, e], [d, e], [m, n]]

Note that in the above example, the first two lists in the result L have length 4 and 1, both lengths appear just once. The third and forth list have length 3; there are two list of this length. And finally, the last three lists have length 2. This is the most frequent length.

Your task is to solve Hett’s problem 1.28; you need not use Prolog. Be sure to follow Hett’s advice:

Your goal should be to find the most elegant solution of the given problems. Efficiency is important, but logical clarity is even more crucial.

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’ve been working hard for the last few exercises, and it is Friday, so we’ll have a little bit of fun. You all know the song, right?

Your task is to write a program that prints the lyrics to the popular song “Ninety-Nine Bottles Of Beer;” if this program seems too simple for you, make your solution as outlandish as you can — I definitely want to see a solution in Intercal or Brainf*ck. 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 conclude the current series of exercises on the prime-counting function with this exercise on the inverse of the prime-counting function that returns the nth prime, denoted p_n. It is true for all positive integers n that π(p_n) = n.

Given Lehmer’s computation of the prime-counting function and Riemann’s approximation of the same function it is relatively easy to compute the nth prime: Use Riemann’s approximation to estimate the value. Apply Lehmer’s formula to the estimate and compute the exact value of π at the approximation. Count up or down as needed using either a sieve or a primality tester.

Your task is to write a function that computes the n prime, and to use it to compute the million’th prime. 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