Programming Praxis

I saw this question on Stack Overflow a few days ago; it’s a well-known problem in number theory:

For a given number n, how many numbers less than n have exactly 3 divisors?

Your task is to write a program that counts the numbers less than n that have exactly 3 divisors, and use it to find the result when n is one billion. 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 problem appeared on a beginning-programmers discussion list:

How can I determine if a number n is a power of 3?

Your task is to write a program to determine if a number is a power of 3. 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

A sexy prime is a prime number p for which p + 6 is also prime. Such primes are called sexy because the Latin word for six is sex.

Your task is to write a program that counts the sexy primes between one billion and two billion. 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 an interview question today:

In a list of integers, find the sum of the integers that appear only once. For instance, in the list [4 2 3 1 7 4 2 7 1 7 5], the integers 1, 2, 4 and 7 appear more than once, so they are excluded from the sum, and the correct anser is 3 + 5 = 8.

Your task is to write a program to find the sum of the distinct integers in a list. 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 a fun task for a lazy summer Friday:

Given a circular array X of positive integers and a starting index k of the array, delete the element at k and jump X[k] steps in the circular array. Repeat until only a single element remains. Find the last remaining element.

For example, with array 6 2 3 1 4 7 5 and k = 3, the last man standing is 3, computed as shown below, with the item to be deleted at each step marked with brackets and the list rotated at each step to bring the new head of the list to the front:

6 2 3 [1] 4 7 5
4 [7] 5 6 2 3
5 6 [2] 3 4
3 4 [5] 6
6 3 [4]
[6] 3
3

Your task is to write a program to find the last remaining element. 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 morning when I drive to work the highway signs display commute information: 7 minutes to Manchester Road, 11 minutes to Olive Blvd, speed ahead 55 mph. That’s little comfort when I’m sitting still on the highway. The “speed ahead” calculation is always rounded to the nearest 5 mph; the Department of Transportation takes a bunch of speed readings from sensors buried in the pavement and averages them.

Your task is to take a list of speed readings and average them to the nearest 5 mph. 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

Consider the triangle:

1
1 2
1 2 3
1 2 3 4
1 2 3 4 5
...

When the triangle is flattened, it produces the sequence (1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 …).

Your task is to write a program to generate the flattened sequence, and a second program to calculate the nth item in the 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 writing a lot of Awk code at work lately; Awk is an acceptable language where I work, Scheme is not. One of my Awk programs got big enough that I needed a cross-referencer, so I pulled out the one on the next page from my dusty archives. It’s thirty years old, and still works! I was amazed. Though I guess I’ll have to update the list of keywords, because Gawk, which we use where I work, has many more keywords than Awk did thirty years ago.

Your task is to write a cross-referencer for your favorite language. 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 wish I thought of this:

I came up with a single pass O(n) sort algorithm I call StalinSort. You iterate down the list of elements checking if they’re in order. Any element which is out of order is eliminated. At the end you have a sorted list.

Your task is to implement StalinSort. 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