## Two Boys And A Canoe

### March 11, 2016

We have today an interview question from Google:

A group of Boy Scouts is taking a trip by canoe and needs to determine how many canoes to rent. A canoe can hold one or two boys and a total of 150 pounds. Given a list of boys’ weights, how many canoes are needed?

Your task is to write a program that determines how may canoes are needed. 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

## String Prefixes

### March 8, 2016

Two strings have a common prefix that consists of the longest prefix of the strings that is the same. For instance, the strings “I love cats” and “I love dogs” have the common prefix “I love ” (including a trailing space at the end of love, which doesn’t appear properly in some browsers).

Your task is to write a program that finds the common prefix of a list of strings (possibly more than two strings). 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

## Wave Sorting

### March 4, 2016

A list of integers is sorted in “wave” order if alternate items are greater than their immediate neighbors (thus the other alternate items are less than their immediate neighbors). Thus, the list [4 1 7 5 6 2 3] is in wave order because 4 > 1, then 1 < 7, then 7 > 5, then 5 < 6, then 6 > 2, and finally 2 < 3. Note that the two alternate streams [4 7 6 3] and [1 5 2] need not themselves be sorted. It doesn’t matter if the first item is the high wave or the low trough between waves, though starting with a wave is traditional.

Your task is to write a program that takes a list of unique integers and sorts it into wave order. 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

## Powers Of 3

### March 1, 2016

The powers of 3 are 30 = 1, 31 = 3, 32 = 9, 33 = 27, and so on.

Your task is to write a program that determines if a number is a power of 3; you must give more than one solution. 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 Amazon Interview Questions

### February 26, 2016

In the previous exercise I wrote a solution that doesn’t work, so I guess I have to try again with two more Amazon interview questions:

Create a set data structure that provides the following operations, which must all operate in constant time: insert, delete, member?, and random. The random operation should return a random element from the set.

and

Given an array, find the first element that appears an even number of times.

Your task is to answer the two interview questions. 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

## Arithmetic Sequence

### February 23, 2016

Today’s exercise is an interview question from Amazon:

Determine if a list of integers forms an arithmetic sequence. For instance, the integers 1, 2, 3, 4, 5 form an arithmetic sequence because the differences between them are all the same, but the integers 1, 2, 4,8, 16 do not form an arithmetic sequence because the differences betweent them are not all the same. The input need not be sorted, so the integers 3, 2, 5, 1, 4 also form an arithmetic sequence.

Your task is to write a function that determines if a list of integers forms an arithmetic 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

## Hacked

### February 19, 2016

I’ve been without internet connectivity for three days following a potential hacking attack against my home network:

1. The light on my router flashes continuously, indicating data transfer, even when I’m not using my computer.
2. I noticed file with extension .bin being downloaded to my Android tablet; I had not requested any such file, nor was I notified of any downloads.
3. There are numerous “connection requests” on my router log; I am not running a publicly available server, and there is no reason for anyone to be requesting a connection to my network.

I called my service provider and spoke to a supervisor. He suspects a hardware problem in the router, and is shipping a new one, which will arrive in a few days. In the meantime, I have shut down the old router. I can see how a new router might fix the first item, but not the other two.

I’ll let you know how I get on. In the meantime, I’ll appreciate any suggestions anyone has. I don’t even know if I’ve actually been hacked.

I haven’t had time to write an exercise, nor do I have a way to upload it; I’m writing this note at my office. I’ll be sure to have one next Tuesday.

## Finding God

### February 16, 2016

The first three verses of the Bible are shown below. Pick any word in the first verse, count its letters, and move forward that many words in the text. Then repeat until you reach the third verse. You will always end with God.

1 In the beginning God created the heaven and the earth.

2 And the earth was without form, and void; and darkness was upon the face of the deep. And the Spirit of God moved upon the face of the waters.

3 And God said, Let there be light: and there was light.

For instance, if you start at beginning, count nine letters and move forward to the first the in the second verse. Then count forward three words to without, count forward seven words to upon, then count forward three words to the, count forward three words to another the, count forward three words to God, count forward three words to the, count forward three words to yet another the, and finally count forward three words to God. This trick was discovered by Martin Gardner.

Your task is to write a program that reads a text and checks if the trick works; you might look at the first paragraph of Alice in Wonderland, where starting within the first ten words always leads to sister, or the words of Twinkle, Twinkle Little Star, where starting anywhere within the first two lines always leads to you in the last line. 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 3

## Three String Exercises

### February 12, 2016

We have three simple exercises on strings today:

1. Write a function that determines the length of a string.
2. Write a function that finds the index of the first occurrence of a character in a string, optionally starting at a given index.
3. Write a function that creates a new string as a substring of an input string, from a given starting index to a given ending index.

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

## Counting Primes

### February 9, 2016

We have studied functions for counting the prime numbers less than a given number in two previous exercises. All of them were based on Legendre’s phi function that counts the numbers less than x not stricken by sieving with the first a primes.

Today we look at a rather different method of counting the primes that is due to G. H. Hardy and Edward M. Wright. Their method is based on factorials, and their formula is

$\pi(n) = -1 + \sum_{j=3}^{n} \left( (j-2)! - j\lfloor \frac{(j-2)!}{j} \rfloor \right)$

for n > 3, where ⌊n⌋ is the greatest integer less than n. The expression inside the big parentheses is 1 when n is prime and 0 when n is composite, by Wilson’s Theorem, which states that an integer n > 1 is prime if and only if (n − 1)! ≡ −1 (mod n); the theorem was first stated by Ibn al-Haytham (c. 1000AD), but is named for John Wilson, who first published it in 1770, and it was first proved by Lagrange in 1771.

Your task is to write a program that counts primes by the Hardy-Wright method. 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