## Count All Matches

### March 10, 2015

Count All Matches

Today’s exercise is an interview question from Google, as reported at Career Cup:

Given two strings, find the number of times the first string occurs in the second, whether continuous or discontinuous. For instance, the string CAT appears in the string CATAPULT three times, as CATapult, CAtapulT, and CatApulT.

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

## 357 Numbers

### March 6, 2015

This question arose at a job-interview site:

Find all numbers divisible only by 3, 5 and 7. For instance, 35 = 5 × 7 is included in the set, but 30 = 2 × 3 × 5 is not because of the factor of 2.

Your task is to write the requested program and determine how many numbers in the set are less than a million. When you are finished, you are welcome to read or run a suggest solution, or to post your own solution or discuss the exercise in the comments below.

## Three Powering Algorithms

### March 3, 2015

In mathematics, the powering operation multiplies a number by itself a given number of times. For instance, the powering operation `pow(2,3)`

multiplies 2 × 2 × 2 = 8.

Your task is to write three functions that implement the powering operation, with time complexities O(*n*), O(log *n*) and O(1) in the exponent. 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.

## Currency Exchange

### February 27, 2015

There is much data available on the internet, and it is often convenient to query that data in a specific way, repeatedly. In that case, the best thing to do is to write a program to automate the request. Today’s exercise is specifically about currency exchange, but anything is fair game, from weather reports to baseball standings.

Your task is to write a program that takes a “from” currency, a “to” currency, and an amount specified in the “from” currency, and returns the equivalent amount in the “to” currency. When you are finished, you are welcome to read a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Coin Flips

### February 24, 2015

I decided over the weekend to perform a simple test over several random number generators at my disposal; the test counts the number of “heads” that appear in a million flips. Here’s the test:

`(do ((n 1000000 (- n 1)))`

(h 0 (if (< (rand 1.0) 0.5) (+ h 1) h)))

((zero? n) h))

Applied to the random number generator built-in to Chez Scheme, I get these five results: 500017, 500035, 499968, 499977, and 500009. That’s pretty close to perfect. The random number generator in the Standard Prelude isn’t as good: 499987, 500503, 500422, 499808, and 500264. And the simple linear-congruential random number generator (69069 x + 1234567) % 2^{32} gives these results: 500301, 499445, 500232, 500047, and 498341.

None of those results are unusual (well, maybe the Chez result is *too* close to perfection), but that’s not what interests us today. What we want to do is assume that the random number generator is biased but still use it to make an unbiased coin flip. Say you have a coin that returns 40% heads and 60% tails. To get an unbiased coin result, flip the coin twice; if you get two heads or two tails, flip twice more, but if you get opposite results, return the first.

Your task is to write a program that delivers unbiased coin flips from a biased coin. 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.

## Morris Counting

### February 20, 2015

We have today an algorithm from the early days of computing that is still relevant today: counting a large number of events using only a small amount of memory. The technique was invented by Robert Morris (early unix researcher and NSA cryptographer, father of the RTM of “internet worm” fame) and described in his 1978 paper

“Counting Large Numbers of Events in Small Registers.”

The basic idea is to count logarithms instead of discrete events. Assuming base-2 logarithms, the algorithm is simple:

Initialize a counter C to 0.

When an event occurs, increment the counter with probability 2

^{−C}.When asked for the count, return 2

^{C}− 1.

It probably seems like a trivial saving to record a count in a single byte instead of, say, a 4-byte integer. But the savings multiply quickly if you need to count a large number of distinct events; the difference between 1-megabyte and 4-megabytes of counters could be significant in a large program where counting is only a small part of the whole.

Your task is to write a program that does Morris counting. 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.

## Invoice

### February 17, 2015

Today’s exercise comes from a text for a first-level programming course.

` Praxis Grocery Store`

17 Feb 2015

```
```

`1 2% Milk 2 3.30 6.60`

2 93% Ground Beef 1 5.98 5.98

3 Clam Chowder 2 1.78 3.56

4 Honey 1 4.42 4.42

5 6 Eggs 1 1.18 1.18

Subtotal 21.74

Tax 5.25% 1.14

Total 22.88

Your task is to write a program that prompts the user to enter item descriptions, quantities and amounts and produces an invoice as shown 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.

## Closest Pair, Part 2

### February 13, 2015

In a previous exercise we studied the brute-force method for finding the closest pair of points in a set of points by forming all pairs, computing the distance between each of them, and choosing the smallest. That algorithm has time complexity O(*n*^{2}). Today we will look at a divide-and-conquer algorithm that has time complexity O(*n* log *n*.

The divide-and-conquer algorithm sorts the pairs along their *x*-coordinates, splits the list of pairs in two, recursively finds the closest pair in the two halves, then compares all points for the closest pair that crosses the dividing line between the two sets of points, taking the minimum of the three possibilities. The third possibility is the tricky one. It won’t do to consider all possible pairs. Instead, we consider only those points less than *d* distance from the dividing line, where *d* is the minimum of the distances of the two recursive calls. It can be proved, though we won’t do so here, that the third step takes only linear time, so the entire algorithm is O(*n* log *n*).

Your task is to write a program that computes the closest pair of points in an input set using the divide-and-conquer 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.

## Project Euler Problem 1

### February 10, 2015

Project Euler is a collection of math problems intended for computer solution, and is one of the inspirations for Programming Praxis. The first problem on Project Euler, which also regularly appears on lists of phone interview questions, asks you to:

Find the sum of all the multiples of 3 or 5 below 1000.

Your task is to write a program that solves Problem 1 for arbitrary *n*; since the problem is simple, you must provide at least three fundamentally different solutions. 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.

## Two Stream Selection Questions

### February 6, 2015

Today’s exercise provides two questions involving selection from a stream. Both require a solution that takes O(*n*) time and O(1) space.

First: Given a stream of unknown length, select a random item from the stream, with all items selected with equal probability. For instance, given the stream {A, D, F, A, G} the selection would return A with probability 40% and D, F or G with probability 20%.

Second: Given a stream of unknown length, each item in the stream paired with a weight, select a random item from the stream with all items selected with probability according to their weights. For instance, given the stream {1 A, 2 D, 5 F, 3 A, 9 G} the selection would return A with probability 20%, D with probability 10%, F with probability 25%, and G with probability 45%.

Your task is to write the two programs that select items from streams. 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.