## String Re-ordering

### March 27, 2015

Today’s exercise is a fun little interview question:

You are given a string

Othat specifies the desired ordering of letters in a target stringT. For example, given stringO= “eloh” the target stringT= “hello” would be re-ordered “elloh” and the target stringT= “help” would be re-ordered “pelh” (letters not in the order string are moved to the beginning of the output in some unspecified order).

Your task is to write a program that produces the requested string re-ordering. 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.

## Excellent Numbers

### March 24, 2015

Today’s exercise channels our inner Project Euler:

An

excellentnumbernhas an even number of digits and, if you split the number into the front halfaand the back halfb, thenb^{2}−a^{2}=n. For example, 3468 = 68^{2}− 34^{2}= 4624 − 1156 = 3468, so 3468 is an excellent number. The only two-digit excellent number is 48 and the only four-digit excellent number is 3468. There are eight six-digit excellent numbers, 140400, 190476, 216513, 300625, 334668, 416768, 484848, and 530901, and their sum is 2615199. What is the sum of the 10-digit excellent numbers?

Your task is to compute the sum of the 10-digit excellent numbers; in the spirit of Project Euler, your solution should take no more than one minute of computation time. 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.

## Matrix Transpose

### March 20, 2015

Transposing a matrix turns rows into columns and columns into rows; for instance the transpose of the matrix below left is the matrix below right:

11 12 13 14 11 21 31

21 22 23 24 12 22 32

31 32 33 34 13 23 33

14 24 34

That’s easy enough to do when everything fits in memory, but when the matrix is stored in a file and is too big to fit in memory, things get rather harder.

Your task is to write a program that transposes a matrix to large to fit in memory. 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.

## Common Elements Of Three Arrays

### March 17, 2015

We have another interview question today. There are several different ways to approach this task, so it makes for an interesting exercise:

Given three arrays of integers in non-decreasing order, find all integers common to all three arrays. For instance, given arrays [1,5,10,20,40,80], [6,7,10,20,80,100] and [3,4,15,20,30,70,80,120] the two common integers are 20 and 80. If an integer appears multiple times in each of the arrays, it should appear multiple times in the output, so with input arrays [1,5,5,5], [3,4,5,5,10] and [5,5,10,20] the correct output is [5,5].

Your task is to write a program to solve the interview question. 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.

## Prime Power Predicate

### March 13, 2015

In today’s exercise we write a function that determines if a number *n* can be written as *p ^{k}* with

*p*prime and

*k*> 0 an integer. We looked at this function in a previous exercise where we tested each prime exponent up to the base-2 logarithm of

*n*.

Henri Cohen describes a better way to make that determination in Algorithm 1.7.5 of his book *A Course in Computational Algebraic Number Theory*. He exploits Fermat’s Little Theorem and the witness to the compositeness of *n* that is found by the Miller-Rabin primality tester. Cohen proves that if *a* is a witness to the compositeness of *n*, in the sense of the Miller-Rabin test, then gcd(*a ^{n}* −

*a*,

*n*) is a non-trivial divisor of

*n*(that is, it is between 1 and

*n*).

Your task is to write a program that determines if a number can be written as a prime power and, if so, returns both the prime and 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.

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