## Steve Yegge’s Phone-Screen Coding Exercises

### June 30, 2009

All of these are easy, and very much shorter than the Java versions that Yegge provides:

1. Most Scheme systems provide a `string-reverse` function, although it is not required by the Standard. Here is a purely-Standard version:

```(define (string-reverse s)   (list->string (reverse (string->list s))))```

2. Yegge gives this function to compute fibonacci numbers:

```(define (fib n)   (if (<= n 1) n     (+ (fib (- n 1)) (fib (- n 2)))))```

That function takes exponential time to compute, due to the constant re-computation of previously-computed results. If Yegge gave me that function during a phone screen, he wouldn’t pass to the next stage of the hiring process. Here is a linear-time version of the fibonacci function:

```(define (fib n)   (let fib ((n n) (f1 1) (f2 0))     (if (zero? n) f2       (fib (- n 1) (+ f1 f2) f1))))```

3. Standard Scheme doesn’t provide formatted output, but most Scheme systems provide a version of Lisp’s `format` function, which provides a wealth of options:

```(define (times-table n)   (do ((i 1 (+ i 1))) ((> i n))     (do ((j 1 (+ j 1))) ((> j n) (newline))       (format #t "~4d" (* i j)))))```

4. `Read` gets the next object from the input; if the input consists of integers separated by newlines, each call to `read` will return the next number on the input:

```(define (sum-file file-name)   (with-input-from-file file-name     (lambda ()       (let loop ((n (read)) (sum 0))         (if (eof-object? n) sum           (loop (read) (+ n sum)))))))```

If you prefer, you can use the `fold-input` function from the Standard Prelude:

```(define (sum-file file-name)   (fold-input read + 0 file-name))```

5. Things don’t get much simpler than this:

```(define (print-odds)   (do ((i 1 (+ i 2))) ((> i 100))     (display i) (newline)))```

6. Well, maybe they do:

`(define (largest xs) (apply max xs))`

7. Standard Scheme provides `number->string`, which takes an optional radix argument but doesn’t write leading zeros, so we make our own `to-hex` function:

```(define (format-rgb r g b)   (define (to-hex n)     (string       (string-ref "0123456789ABCDEF" (quotient n 16))       (string-ref "0123456789ABCDEF" (modulo n 16))))   (string-append (to-hex r) (to-hex g) (to-hex b)))```

If you like `format`, it has an option to print hexadecimal numbers.

It’s hard to imagine that coding exercises like this would be a barrier for any practicing programmer, but apparently they are; Yegge got the fibonacci question wrong, and if you read the comments on his original article, he also got the `print-odds` program wrong initially (he since changed his article, claiming the mistake was due to a failed optimization), printing even numbers instead of odd numbers. Of course, that’s the reason this blog exists: to give savvy programmers a chance to practice their skills, so the don’t make dumb coding mistakes, either during a phone screening or in their working programs.

Pages: 1 2

### 10 Responses to “Steve Yegge’s Phone-Screen Coding Exercises”

1. [...] Praxis – Steve Yegge’s Phone-Screen Coding Exercises By Remco Niemeijer Today’s Programming Praxis problem is an easy one. In 2005, Steve Yegge posted an article about [...]

2. Remco Niemeijer said

```import Text.Printf
import Data.Word

reverse' :: String -> String
reverse' = foldr (:) []

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

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

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

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

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

toHex :: Word8 -> Word8 -> Word8 -> String
toHex = printf "%02x%02x%02x"
```
3. Scott Pedersen said

C# Solution

I couldn’t resist writing smartass responses for questions three and five to just return fixed strings. I also wrote more general answers that I thought were more in keeping with the spirit of the exercise.

The basic recursive implementation for Fibonacci numbers is a classic, but is terribly slow. It’s the answer I’d expect out of most interview candidates as a first pass since it is taught so regularly as an example of recursion. However, they’d be in trouble if they couldn’t quickly identify the problems with such an implementation. I wrote out a couple of alternatives that are a bit more efficient.

4. Remco Niemeijer said

Thanks to nonowarn for catching a bug:

The correct code for exercise 1 should be

```reverse' :: String -> String
reverse' = foldl (flip (:)) []
```
5. liesen said

I think you’ve got them all, Remco. My Haskell solutions are similar. Here is one simpler solution to #5:

printOdds = print [1,3..99]

There’s one more bug in Remco’s code, though: largest assumes positive integers, but it should read:

largest = foldl1 max

6. Remco Niemeijer said

Yeah, I noticed that one too, but didn’t get round to fixing it. However, if you treat Steve Yegge’s solution as the spec then the correct implementation is actually

largest = foldl max minBound

7. Connochaetes said
```def reverse(str)
# 1. Write a function to reverse a string.
len = str.length - 1
len.downto(0).collect {|n| str[n].chr}.to_s
end

def nth_fib(n)
# 2. Write a function to compute the Nth fibonacci number.
# NB. assumes fibonacci numbers are zero-indexed.
x,y = 0,1
n.times {x,y = y,x+y}
y
end

def multi_table
# 3. Print out the grade-school multiplication table up to 12 x 12.
size = 12
1.upto(size).each do |x|
1.upto(size).each do |y|
printf "%4d", x*y
end
printf "\n"
end
end

def sum_ints_from_file(filename)
# 4. Write a function that sums up integers from a text file, one per line.
sum = 0
File.open(filename).each {|line| sum += line.to_i}
sum
end

def print_odd_numbers
# 5. Write a function to print the odd numbers from 1 to 99.
(1..99).step(2).each {|n| puts n} ; nil
end

def find_largest_value(arr)
# 6. Find the largest int value in an int array.
arr.inject {|x,y| x > y ? x : y}
end

def format_RGB(r,g,b)
# 7. Format an RGB value (three 1-byte numbers) as a 6-digit hexadecimal string.
format "%02X%02X%02X", r,g,b
end

```
8. [...] for the exercise, I picked Steve Yegge’s Phone-Screen Coding Exercises, figuring seven different small problems might cover slightly more ground than one bigger [...]

9. Graham said

I’m never sure how much of a language’s built-in functionality we’re supposed to use for a question.
Python solution
Common Lisp solution

10. brooknovak said

For the RGB => Hex conversion you can always take advantage API knowledge (such as string formatting features), but its not as fun!

```public static string ConvertToHex(byte r, byte g, byte b) {
char[] buffer = new char[6];
int rgb = (r << 16) | (g << 8) | b;
for (int i = 0; i < 6; i++) {
int val = rgb & 15;
if (val <= 9)
buffer [5 - i] = (char)('0' + val);
else
buffer [5 - i] = (char)('A' + (val - 10));
rgb >>= 4;
}
return new string(buffer);
}
```