Programming Praxis – Steve Yegge’s Phone-Screen Coding Exercises

Today’s Programming Praxis problem is an easy one. In 2005, Steve Yegge posted an article about interviewing programmers that listed 7 simple programming exercises for phone screening. These assignments are a perfect example of ‘Bonsai code’, since they require so little code. The scheme solution clocks in at 22 lines, or just over 3 lines per function on average. Let’s see how Haskell does.

Our imports (the latter one is only to ensure type safety in exercise 7):

import Text.Printf
import Data.Word

1. Write a function to reverse a string

Normally you would just use the reverse function from the Prelude (like the Scheme solution does), but I consider that cheating, since the assignment says to write our own. Fortunately, the full solution is not much longer:

reverse' :: String -> String
reverse' = foldl (flip (:)) []

2. Write a function to compute the Nth fibonacci number

The function to produce an infinite list of Fibonacci numbers is a well-known example of Haskell’s brevity. All we need to fulfill the assignment is to get the correct one:

fib :: (Num a) => Int -> a
fib n = fibs !! n where fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

3. Print out the grade-school multiplication table up to 12 x 12

The only non-one-liner of the bunch, but still very trivial.

timesTable :: IO ()
timesTable = mapM_ putStrLn [concat
    [printf "%4d" (a * b) | a <- [1..12]] | b <- [1..12 :: Int]]

4. Write a function that sums up integers from a text file, one per line.

Aside from the map read bit it’s almost plain English.

sumFile :: FilePath -> IO ()
sumFile path = print . sum . map read . lines =<< readFile path

5. Write a function to print the odd numbers from 1 to 99.

And another one that almost anyone should be able to understand.

printOdds :: IO ()
printOdds = print $ filter odd [1..99]

6. Find the largest int value in an int array.

As with the reverse assignment, we would normally just use the built-in maximum function here. But since that’s cheating, we use another simple fold:

largest :: [Int] -> Int
largest = foldl max minBound

7. Format an RGB value (three 1-byte numbers) as a 6-digit hexadecimal string.

Printf to the resque. As mentioned in the imports, we could just use Ints and get rid of one of our imports, but this way we guarantee that only 1-byte numbers can be passed in.

toHex :: Word8 -> Word8 -> Word8 -> String
toHex = printf "%02x%02x%02x"

And that brings us to 10 lines of code in total, which is less than half the Scheme solution size. I just love one-liners :)

About these ads

Tags: , , , , , , , , ,

6 Responses to “Programming Praxis – Steve Yegge’s Phone-Screen Coding Exercises”

  1. Mark Says:

    printOdds = print $ [1,3..99]

    — but this is getting golfy :)

  2. Mark Says:

    printOdds = print [1,3..99]

    — but this is getting golfy :)

  3. nonowarn Says:

    > reverse’ = foldr (:) []

    Did you mean
    reverse’ = foldl (flip (:)) []

    ?

  4. Remco Niemeijer Says:

    The foldl version is the one used in the Prelude if USE_REPORT_PRELUDE is true, yes. The foldr version will produce the same output though, and since it’s a bit shorter that’s the one I decided to use. After reading your comment, I figured I’d do a little benchmark to see which one is faster. It turns out that on a string with 5 million characters the foldr version is 30% faster than foldl when interpreted, and about 4 times faster when compiled.
    I guess there must be some reason why they’re using the foldl version in the Prelude, but to be honest I don’t see it. If anyone happens to know the answer I’d love to hear it.

  5. nonowarn Says:

    Your reverse’ function does not seem work, that’s why I commented here. It’s acting like id function for String.

    Prelude> let reverse’ = foldr (:) “”
    Prelude> reverse’ “foobar”
    “foobar”

    I guess you didn’t test the function enough or have some mistakes.

  6. Remco Niemeijer Says:

    D’oh. Apparently I forgot to test again after replacing the foldl with the foldr version. The lesson here: just because it typechecks doesn’t automatically mean that it’s correct :) Thanks, fixed.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: