Programming Praxis

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

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

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.

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

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

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

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

Every so often I get it in mind to start solving the daily cryptogram in the newspaper. For instance:

[Category: Literature] V MVXEGC NK V RGIIZH HYZ IGXDK PZQ YNK QLMCGIIV HYGX AYG KQX NK KYNXNXO VXD HZXAK NA MVUE AYG LNXQAG NA MGONXK AZ CVNX. — LVCE AHVNX

The first word is either A or I, and the repeated two-letter words NK, NK, NA and NA suggest words like IF, IS, IT or OF, ON, OR. Further, the digraph NK also appears as YNK. So we guess that NK is IS, YNK is HIS, and V is A. Now the author LVCE AHVNK is _A__ __AI_, which rather strongly suggests MARK TWAIN. Now we have the phrase WH_N TH_ S_N IS SHININ_, which is almost certainly WHEN THE SUN IS SHINING, and the rest of the cryptogram is easy: A BANKER IS A FELLOW WHO LENDS YOU HIS UMBRELLA WHEN THE SUN IS SHINING AND WANTS IT BACK THE MINUTE IT BEGINS TO RAIN. — MARK TWAIN.

We’ve written a program to solve cryptograms, a long time ago, using a dictionary attack, but sometimes it’s still fun to solve them by hand. One way a computer can help is by creating frequency tables of single letters, digraphs, and trigraphs; in the puzzle shown above, a table of digraphs leads quickly to NX, which appears six times, along with NK (three times) and NA (two times), which quickly limits the possibilities for the letter N. We didn’t use it in the analysis above, but AYG is the most common trigram, and both times it appears it is a word by itself, so it is almost certainly THE or AND. Thus, frequency tables quickly lead to a solution.

Your task is to write a program that generates frequency tables, including single characters, digraphs, trigraphs, and other lengths. 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 studied maximal prime gaps in a recent exercise. In today’s exercise we will look at minimal prime gaps — the smallest gap of a given size. For instance, the minimal prime gap of 2 is the gap from 3 to 5, the minimal prime gap of 4 is the gap from 7 to 11, the minimal prime gap of 6 is the gap from 13 to 19, and so on.

Your task is to write a program that finds minimal prime gaps. 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