Life, the Universe and Technical Interviews

“There is a small satellite orbiting an unremarkable planet 50 light years from Earth. In spite of its tiny size, this floating cube of metal and silicon carries a load of paramount importance to the infrastructure of our galaxy. Inside its computer resides the Big Developer Matrix. As you can infer from its name it is fairly large, and it contains information about developers. More specifically software developers, because it was created by software developers. Each row of this matrix represents a company, and each column a developer. Every cell contains a binary value, which means either HIRE or DON’T HIRE.

The Big Matrix is rather sparse, and it is widely used by software managers across the Milky Way. In fact, it is the standard tool for hiring decisions pretty much everywhere. There are some fringe planets like Earth who rarely query the Big Matrix, and nobody is quite sure why. One of the maintainers of the software suspects it may have to do with a mismatch between the latency of communications and the average life spans of humans.”

— The author of this post, just now.

Unfortunately for us humans, we have little choice but to conduct technical interviews. We need an answer to the question of whether we want to hire someone or not, and we don’t have the time to really assess someone level of technical competence. Many try to approximate the Big Matrix with a series of progressive Bloom filters: techniques that tell you DON’T HIRE this person or INCONCLUSIVE. FizzBuzz is a good example of a Bloom filter question. I’ve never asked it to anyone and I don’t think I will; if you have to ask that question, you probably should rethink your pre-interview selection process.

One of the things I dislike about FizzBuzz is that it reminds me of customs forms with questions such as “have you ever been a member of the Communist party?” It’s almost insulting, and there is no way to show that you’re a good developer by coding FizzBuzz. There are questions that serve a similar purpose, while at the same time giving the candidate an opportunity to show off some skills. Here’s an example of a question that I like, even though I’ve never asked it:

Write some code that calculates how many numbers under a million (positive integers) have digits that add up to 42.

Why do I like this question? For one, it doesn’t require any specific knowledge besides basic programming techniques and math. Anybody who spent some time programming in some language should know enough to solve that in a few lines. Also, it has a mundane element that you normally encounter in real-life programming: one straightforward way of answering the question involves converting integers to strings and back. Furthermore, it lends itself to elegant functional solutions. Finally, getting the reference is an added bonus for personality fit 🙂

I asked this question on Twitter a couple of nights ago just for fun, and got some quick responses. The first one, in Haskell:

another one, in Python:

Clojure:

Ruby:

One of my favorites, in C and bash:

One I did in Clojure, without using strings and using recursion:

(count (filter #(= 42 %)
               (map (fn d [n]
                      (if (> 10 n)
                        n
                        (+ (mod n 10) (d (quot n 10)))))
                     (range 1e6))))

One in Forth by @technomancy:

s dup if 10 /mod recurse + then ; : f 0 1000000 0 do i s 42 = if 1 + then loop ;

I couldn’t fit a Java version into a tweet, but someone did it with Java 8:

class S{public static void main(String a[])
{int i=0,j=0;for(;i++<1e6;j+=(i+"").
chars().map(x->x-48).sum()==42?1:0);System.out.print(j);}}

@ejenk reduced the Haskell version to:

length . filter (== 42) . fmap sum . replicateM 6 $ [0..9]

There were a few other good solutions. The shortest were in languages like sed or Wolphram, which allowed the authors to “cheat” somewhat.

Conclusion

I will never get to ask the 42 question in an interview. If I did, I wouldn’t expect a candidate to show off code-colfing skills. I might ask about performance considerations for a larger space, and be pleasantly surprised if the candidate pondered solving the problem  mathematically for a second.

While this particular question may seem very easy in the comfort of your browser and favorite editor, it’s not trivial in the context of an interview. Always remember that technical interviews are very stressful; some of the best candidates I interviewed had sweaty palms upon entering the room. Even the best of us sometimes forget to bring a towel.

7 thoughts on “Life, the Universe and Technical Interviews

  1. First thing I do when I see code which resembles most of those tweets is refactoring. In almost all cases it’s not (easily) readable and in most cases it’s not efficient since they are working on strings. Instead of trying to be too cool for school with their one liners they should thing about all the unnecessary conversions they are doing.

    The problem with that question is that I don’t know, as the interviewer, would that person really write that at work or is he trying to show off his coding-fu. If the latter then he might still get the job, if it’s the former well it depends on his overall performance but he sure just scored a huge minus in my book.

    • Obviously you (I) would never ask anyone to do an one-liner in an interview. These are tweets, not production code. I personally know a few of the people who replied to me, and their production code is solid and readable.

  2. what about not taking the pure math approach or the functional approach, but taking an approach that would just be faster 🙂

    #!/usr/bin/env ruby
    require ‘benchmark’

    def sum(target, digits)
    return 0 if target < 0
    if digits == 1
    return 1 if target < 10
    return 0
    end
    partial = 0
    10.times do |c|
    partial += sum(target-c,digits-1)
    end
    return partial
    end

    puts "ruby version #{RUBY_VERSION}"
    direct = 0
    indirect = 0

    time = Benchmark.measure do
    direct = (1…1000000).select{|i| i.to_s.each_char.map(&:to_i).inject(:+) == 42}.size
    end

    puts "direct = #{direct}"
    puts time

    time2 = Benchmark.measure do
    indirect = sum(42,6)
    end

    puts "indirect = #{indirect}"
    puts time2

    =====================

    ruby version 1.9.3
    direct = 6062
    4.470000 0.000000 4.470000 ( 4.560090)
    indirect = 6062
    0.030000 0.000000 0.030000 ( 0.032660)

  3. I tend to ask what I think is a rather simpler question in most interviews: find the sum of the two largest (most positive) numbers in an array of integers. Consider the efficiency of your solution for very large arrays.

    It is amazing how many seemingly knowledgeable, intelligent people cannot do this. And the vast majority of those who do, do it by sorting the array, efficiency be damned.

    • For this example I would create a “highest” and a “next highest” variable, then loop through the array once. Each time test if the current number is equal or higher than the highest number. If it is, set the next highest value to the highest value and set then current value to the highest. Then just add the two variables when the array loop is finished.

    • Mathematical thinking in programming is becoming a more specialized skill which is partly why there are so many bad programmers out there (IMO).

      You can build a lot of applications by thinking logically and not mathematically and rely on libraries to take care of the “mathy” bits.
      A lot of developers get by on this with almost no understanding of basic algorithms and data structures.

      I operated in this way for years as a self taught developer, building CRUD apps and web apps. Almost none of my problems required me to make decisions on which data structures were more efficient for a particular problem. All of my “algorithms” were inefficient or pulled from a library and it didn’t matter because the data sets were never large enough to make a difference. This core part of my knowledge really centered around code organization, readability, state management, class hierarchies, design patterns etc.

      I think it’s where the so called “imposter syndrome” comes from.
      The more math I learn and the more I can think mathematically, the less I feel like an idiot at the keyboard, even if I’m not directly using mathematics.

Leave a Reply

Your email address will not be published. Required fields are marked *