Programming Praxis

We have three simple interview questions today:

1) Verify that a binary tree is a binary search tree. In a binary search tree, all nodes to the left of the current node have values less than the value of the current node, all nodes to the right of the current node have values greater than the value of the current node, and those two rules hold for all nodes in the tree.

2) Remove duplicates from a list.

3) A girl counts on her fingers by counting 1 on her thumb, 2 on her index finger, 3 on her middle finge, 4 on her ring finger, and 5 on her pinkie. Then she continues the other way, counting 6 on her ring finger, 7 on her middle finger, 8 on her index finger, and 9 on her thumb. Then she continues the other other way, counting 10 on her index finger, 11 on her middle finger, 12 on her ring finger, and 13 on her pinkie. She continues in this way indefinitely. Write a program that, given n, determines which finger she will be on when her count reaches n.

Your task is to write programs that solve the three interview questions given 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 studied three bit hacks in a previous exercise. In today’s exercise we look at three more:

1) Compute the minimum (or maximum) of two integers without branching.

2) Determine if an integer is a power of two.

3) Swap the values of two variables without using any extra space.

Your task is to write bit hacks for the three tasks noted above; you may want to find multiple solutions for some of them. 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’m not sure of the original source of this fun little puzzle:

There is a monkey which can walk around on a planar grid. The monkey can move one space at a time left, right, up or down. That is, from (x, y) the monkey can go to (x+1, y), (x-1, y), (x, y+1), and (x, y-1). Points where the sum of the digits of the absolute value of the x coordinate plus the sum of the digits of the absolute value of the y coordinate are lesser than or equal to 19 are accessible to the monkey. For example, the point (59, 79) is inaccessible because 5 + 9 + 7 + 9 = 30, which is greater than 19. Another example: the point (-5, -7) is accessible because abs(-5) + abs(-7) = 5 + 7 = 12, which is less than 19. How many points can the monkey access if it starts at (0, 0), including (0, 0) itself?

Your task is to write a program that counts the number of available points. 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 was written by guest author Robert Fisher. Having worked on shrinkwrapped consumer software, e-commerce web apps, embedded systems, and insurance OLTP systems, Robert currently writes C/C++ and Javascript for HP Tippingpoint and writes Scheme whenever he can. Suggestions for exercises are always welcome, or you may wish to contribute your own exercise; feel free to contact me if you are interested. ]

Under Unix, files are identified by paths. These are strings of directory names separated by slash characters followed by the name of the file. Paths starting with a slash are absolute, but paths that don’t start with a slash are relative to the current directory. Relative paths may include “..” elements. These represent a parent directory. Likewise, “../..” would represent a grandparent directory. For example, if the current directory is “/home/bob” then “praxis/prelude.scm” represents the file “/home/bob/praxis/prelude.scm” and “../tom/bin/scheme” represents “/home/tom/bin/scheme”.

Your task is to write a function that takes the current directory path and a target path and returns an absolute and minimal path equivalent to the target path. 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 time-honored tradition among programmers is to hack a program to reduce the number of operations it takes, and a major component of that effort goes in to bit hacks, which we can define as dealing with data structures smaller than a single byte. Embedded systems programmers use bit hacks all of the time, as do game programmers and many others. We have three tasks today:

1) Determine the sign of an integer.

2) Determine if two integers have the same sign.

3) Determine the absolute value of an integer without branching.

Your task is to write bit hacks for the three tasks noted above; you may want to find multiple solutions for some of them. 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 prime number p is a Sophie Germain prime if 2p+1 is also prime. The list of Sophie Germain primes begins 2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, (A005384); it is not known if the list is infinite. Sophie Germain primes are named after the French mathematician Marie-Sophie Germain, who in 1825 proved Fermat’s last theorem for such primes; thus, if p is a Sophie Germain prime, then there do not exist integers x, y and z not equal to zero and not a multiple of p such that x^p + y^p = z^p.

One way to find Sophie Germain primes is to enumerate the primes p and check the primality of each 2p+1. That works fine for relatively small p. For larger p, amateur mathematician Harvey Dubner developed a sieve that speeds finding Sophie Germain primes:

Define the three polynomials f_p(c) = c * 3003 * 10^b – 1, f_q(c) = 2 f_p(c) + 1, and f_r(c) = (f_p(c) – 1) / 2. Choose b which is the approximate number of digits for the range of Sophie Germain primes you are searching.

Sieve each of the polynomials over the range 1 ≤ c ≤ m for some suitable m. Use as sieving primes the primes greater than 13 but less than some suitable f which is conveniently large but much less than the square root of f_p(1). All three polynomials are sieved over the same sieving array. Sieving is done in a similar manner to sieving the polynomials in the multiple polynomial quadratic sieve.

After sieving is complete, apply a primality test to each f_p(c) that survived all three sievings. If it is prime, check both f_q(c) and f_r(c) for primality. If f_q(c) is prime, then f_p(c) is a Sophie Germain prime. If f_r(c), then f_r(c) is a Sophie Germain prime.

Your task is to write a sieve that finds Sophie Germain primes as 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

In a normal hash table, a key is hashed then linear search is performed in the bucket where the key will be found if it exists in the hash table. A successful search terminates as soon as the key is found, on average half-way through the bucket, but an unsuccessful search requires that every item in the bucket be examined.

Donald Knuth proposed that instead of keeping keys in a bucket in random order they be kept in increasing order, so that a search can stop as soon as the search passes the value of the key. That means inserts take longer; you have to find the right place in the bucket to put the key instead of just putting it at the beginning of the bucket. But lookups are quicker, as an unsuccessful search can terminate half-way through the bucket, on average. This change also means that the data type of the hash table changes, as now the comparison function is less-than rather than equal-to.

Your task is to write a small library of ordered hash tables; you should provide lookup, insert and delete functions, at least. 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

There was a big buzz on Stack Overflow recently when a question about buying croissants was asked:

At my office someone buys croissants for everybody every Friday. Sometimes we have problems arranging a suitable schedule because of absences — illness, vacation, training, customer meetings — so we’re looking for an algorithm that randomly chooses the person who should bring croissants so that everyone buys and consumes about as many croissants as everyone else.

The question caused a big ruckus at Stack Overflow, and is currently locked while the community decides if the question is appropriate; I personally think that it is, and further, that the question is both fun and practical.

Your task is to devise a suitable algorithm for deciding who should buy croissants, and demonstrate by simulation that your algorithms is fair. 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 today another of our unlimited supply of interview questions: this one supposedly comes from Amazon:

Given an array X[0..n-1] of integers sorted into ascending order with no duplicates, find an array item that is also its index, so that X[i] = i.

For example, X[3] = 3 in the array shown below:

i     0 1 2 3 4 5
x[i] -3 0 1 3 5 7

Your task is to write a program that finds i. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exericse in the comments below.

Pages: 1 2

In the early days of Unix, Mike Lesk wrote a directory-assistance program that allowed users to input a name using the numeric keypad on a telephone and get a telephone number in return. The program worked by “signing” each name with its telephonic equivalent, then storing the signatures in a database. This scheme makes collisions possible, but in practice collisions are rare, and when they do happen the user is prompted for additional information.

Your task is to write a program that takes a name and returns a telephone number; a database is provided on the next page. 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