Programming Praxis

This question appears on several lists of interview questions:

Write a function that takes an input string and returns the first character from the string that is not repeated later in the string. For instance, the two letters “d” and “f” in the input string “aabcbcdeef” are non-repeating, and the function should return “d” since “f” appears later in the string. The function should return some indication if there are no non-repeating characters in the string.

Your task is to write the indicated function. 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 task comes to us from i has 1337 code:

Given a cyclic list with elements in sorted order, write a function to insert a new element into the cyclic list that maintains the sorted order of the cyclic list. Do not assume that the cyclic list is referenced by its minimal element.

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

Daniel Tunkelang posted this interview question to his blog:

Given an input string and a dictionary of words, segment the input string into a space-separated sequence of dictionary words if possible. For example, if the input string is “applepie” and dictionary contains a standard set of English words, then we would return the string “apple pie” as output.

He also gave a number of constraints: The dictionary provides a single operation, exact string lookup, and is a given to the task; you are not to consider how to implement the dictionary, nor or you to worry about stemming, spelling correction, or other aspects of the dictionary. The output may have more than two words, if there is more than one solution you only need to return one of them, and your function should indicate if there are no solutions.

Your task is to write a function that solves the “word break” problem. 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

Over at PrologSite, Werner Hett gives a list of Ninety-Nine Prolog Problems “to give you the opportunity to practice your skills in logic programming.” Today’s exercise is number 1.28 on the list. Hett gives the problem two stars, meaning that he expects a skilled Prolog programmer to spend thirty to ninety minutes to solve it. Here is Hett’s statement of the problem:

1.28 (**) Sorting a list of lists according to length of sublists
a) We suppose that a list (InList) contains elements that are lists themselves. The objective is to sort the elements of InList according to their length. E.g. short lists first, longer lists later, or vice versa.

Example:
?- lsort([[a,b,c],[d,e],[f,g,h],[d,e],[i,j,k,l],[m,n],[o]],L).
L = [[o], [d, e], [d, e], [m, n], [a, b, c], [f, g, h], [i, j, k, l]]

b) Again, we suppose that a list (InList) contains elements that are lists themselves. But this time the objective is to sort the elements of InList according to their length frequency; i.e. in the default, where sorting is done ascendingly, lists with rare lengths are placed first, others with a more frequent length come later.

Example:
?- lfsort([[a,b,c],[d,e],[f,g,h],[d,e],[i,j,k,l],[m,n],[o]],L).
L = [[i, j, k, l], [o], [a, b, c], [f, g, h], [d, e], [d, e], [m, n]]

Note that in the above example, the first two lists in the result L have length 4 and 1, both lengths appear just once. The third and forth list have length 3; there are two list of this length. And finally, the last three lists have length 2. This is the most frequent length.

Your task is to solve Hett’s problem 1.28; you need not use Prolog. Be sure to follow Hett’s advice:

Your goal should be to find the most elegant solution of the given problems. Efficiency is important, but logical clarity is even more crucial.

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’ve been working hard for the last few exercises, and it is Friday, so we’ll have a little bit of fun. You all know the song, right?

Your task is to write a program that prints the lyrics to the popular song “Ninety-Nine Bottles Of Beer;” if this program seems too simple for you, make your solution as outlandish as you can — I definitely want to see a solution in Intercal or Brainf*ck. 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 conclude the current series of exercises on the prime-counting function with this exercise on the inverse of the prime-counting function that returns the nth prime, denoted p_n. It is true for all positive integers n that π(p_n) = n.

Given Lehmer’s computation of the prime-counting function and Riemann’s approximation of the same function it is relatively easy to compute the nth prime: Use Riemann’s approximation to estimate the value. Apply Lehmer’s formula to the estimate and compute the exact value of π at the approximation. Count up or down as needed using either a sieve or a primality tester.

Your task is to write a function that computes the n prime, and to use it to compute the million’th prime. 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 the two previous exercises we have seen three different methods for computing the prime-counting function π(n), all based on a formula of Legendre. We have also seen the difficulty of the calculation, as three eminent mathematicians got their sums wrong, and the difficulty continues even today with the use of computers, as Xavier Gourdon had to stop an attempt to compute π(10²³) because of an error. Given the difficulty of calculation, in some cases it might make sense to calculate an approximate value of π, instead of an exact value. In today’s exercise we look at two methods for approximating the prime-counting function.

The first method dates to the German mathematician Carl Friedrich Gauss, who gives an estimate π(x) ∼ Li(x), the logarithmic integral—this is the celebrated prime number theorem, which Gauss figured out when he was fifteen years old! The logarithmic integral can be calculated by expanding the infinite series

to the desired degree of accuracy; somewhere around a hundred terms ought to be sufficient for arguments up to 10¹². Beware the singularity at x=0.

In 1859, Bernhard Riemann, whose hypothesis about the prime numbers is one of the greatest open questions in mathematics, described a different, and much more accurate, approximation to the prime counting function:

where μ(n) is the Möbius function that takes the value 1 when n is 1, 0 when the factorization of n contains a duplicated factor, and (−1)^k, where k is the number of factors in the factorization of n, otherwise. There is no better way to compute the Möbius function than to compute the factors of n. As with the logarithmic integral, about a hundred terms of the infinite series ought to be sufficient to get a good approximation for arguments up to 10¹².

Your task is to write functions to compute the logarithmic integral, the Möbius function, and Riemann’s R function, and to compare the results to the values you calculated for the prime-counting function in the previous exercise. 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 the previous exercise we studied Legendre’s prime-counting function. In today’s exercise we will look at two more prime-counting functions, one from Ernst Meissel in the late 1800s and the other from Derrick Lehmer in the mid 1990s.

Both formulas are based on Legendre’s original formula; in both cases, they simply rearrange the terms of Legendre’s formula to eliminate some work. We won’t try to give derivations, as they are complex and chock-full of Greek letters; if you are interested, Hans Riesel’s book Prime Numbers and Computer Methods for Factorization was the source for all three formulas.

Meissel: , where and

Lehmer: , where , , , and for .

Your task is to implement the prime-counting functions of Meissel and Lehmer, then compare timings with Legendre's prime-counting function of the previous exercise. 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

The prime-counting function π(n) computes the number of primes not greater than n, and has been a matter of fascination to mathematicians for centuries. The Prime Number Theorem tells us that π(n) is approximately n / log(n); Carl Fredrich Gauss proposed the prime number theorem in 1792 when he was only fifteen years old, and Jacques Hadamard and Charles-Jean de la Valle Poussin both proved it, independently, in 1896. The first person to make a serious attempt at the calculation, except for trivial attempts that simply enumerated the primes and counted them, was the French mathematician Adrien-Marie Legendre at the end of the eighteenth century; his formula was correct, but he erroneously reported that π(10⁶) = 78526, whereas the correct value is 78498. We will recreate Legendre’s calculation in today’s exercise.

Legendre’s formula works in two parts. First, he defined a function φ(x, a) that counts all the numbers from 1 to x inclusive that are not stricken by sieving with the first a primes. For instance φ(50, 3) = 14, because the numbers 1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 and 49 less than or equal to 50 are not divisible by the first three primes 2, 3, or 5. The φ function can be computed by the recurrence equation φ(x, a) = φ(x, a−1) − φ(x/p_a, a−1), where φ(x, 1) is the number of odd integers less than or equal to x and p_a is the ath prime number. The second part of Legendre’s formula uses the φ function to compute the value of π recursively: π(x) = φ(x, a) + a − 1, where a = π(⌊√x⌋).

Your task is to write φ and π functions and recreate Legendre’s calculation of π(1000000). 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 exercise in our on-going series of interview questions:

Write a program that takes a list of integers and a target number and determines if any two integers in the list sum to the target number. If so, return the two numbers. If not, return an indication that no such integers exist.

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.

Pages: 1 2