Up at 5AM: The 5AM Solutions Blog

Why I still ask Big-O questions during interviews

Posted on Tue, Sep 29, 2009 @ 12:48 PM

Every development interview inevitably includes some question about Big-O notation. How fast does the code you just wrote for us run? How much stack or heap space do you need? Or, what is the runtime of QuickSort? Here is what I expect from candidates, and what I am trying to get from asking these questions:

First, does the candidate know what I'm talking about? Big-O notation and analysis is core curriculum for an undergraduate CS degree. Candidates straight out of school should be familiar from their algorithms or discrete math classes, even if they've never needed to analyze an algorithm since then. Industry candidates may have forgotten the term, but shouldn't be lost after a quick explanation like "you know, order n, order n squared, n log n, that sort of thing." Candidates that haven't been introduced to the concept are a red flag for me. I expect every candidate will have been asked this before in an interview.

Generally, good candidates will have immediate recall for well known data structures or algorithms. I try to ask a recall question as part of a larger problem. Like knowing the concept, candidates that don't immediately say that sorting is generally an O(n log n) problem are a red flag. Mentioning QuickSort's expected vs. worst-case performance is only marginally interesting, and I generally stop any candidate from explaining parallel quicksort or attempting to tell me about the tail distribution bound for a randomized version. Knowing and mentioning these variations shows plenty of theoretical depth, and my motivation for the recall question isn't to see if someone has taken a graduate-level class. I want to see explanation of an entire solution's runtime, not delve deeply into the minutia.

These questions are more than CS101. I often ask candidates to trade off between time and space complexity by throwing in some oddball requirement like constant memory. Typically making the required changes requires mental flexibility in the interview, as this comes up after someone has already been successful at solving the problem. I want to see how the candidates reacts to "great, you did exactly what I asked... now change it." I'm looking for the candidate to understand the changed circumstances and develop a solution that meets the new need. Does the candidate get stuck on their prior solution? Are they upset by the change? Do they forget about their old solution and try to start over completely? Ideally none of these things happen, and none have much to do with programming skill.


Diagnostic Tests on the Map of Biomedicine


Download the ebook based on our popular blog series. This free, 50+ page edition features updated, expanded posts and redesigned, easier-to-read maps. 

FREE Biobanking Ebook

Biobanking Free Ebook
Get this 29 page PDF document on how data science can be used to advance biorepositories.

 Free NGS Whitepaper

NGS White Paper for Molecular Diagnostics

Learn about the applications, opportunities and challenges in this updated free white paper. 

Recent Posts