## 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:

- 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)))) - 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)))) - 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))))) `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))- Things don’t get much simpler than this:
`(define (print-odds)`

(do ((i 1 (+ i 2))) ((> i 100))

(display i) (newline))) - Well, maybe they do:
`(define (largest xs) (apply max xs))`

- 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.

[…] 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 […]

My Haskell solution (see http://bonsaicode.wordpress.com/2009/06/30/programming-praxis-steve-yegge%E2%80%99s-phone-screen-coding-exercises/ for a version with comments):

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.

Thanks to nonowarn for catching a bug:

The correct code for exercise 1 should be

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

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

[…] 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 […]

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

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