1 of 17

Big O Stuff

Cracking the Coding Interview

Gayle Laakmann McDowell

2 of 17

Thanks for playing! �Write down your answers.

Check them at go.gayle.com/bigoquiz

3 of 17

  1. MIN

​

​

​

4 of 17

02. MIN AND MAX

​

​

​

5 of 17

03. NESTED WITH TWO ARRAYS

​

​

​

6 of 17

04. NESTED WITH J STARTING AT I

​

​

​

7 of 17

05. MAX POPULATION

​

​

​

Q5: Given list of people with birth years and death years (so population changes over time), find highest population.

​

  1. Get last death year.
  2. Create histogram from 0 → last death year (this will end up giving us population at each year).
    1. Walks through all people
      1. For each person, increment histogram for each year they were alive.
  3. Walk through histogram to get highest population.

8 of 17

06. VALIDATE

​

​

​

9 of 17

07. RECURSION

​

​

​

10 of 17

08. MEMOIZATION

​

​

​

11 of 17

Thanks for playing! �Write down your answers.

Check them at go.gayle.com/bigoquiz

12 of 17

Statistics

(from the first ~350) people

13 of 17

methodology

  • I converted answers to their canonical form, so that O(N^2) and O(N*N) would be treated the same. Answers were not “wrong” because they express them differently.
  • I excluded anyone who got Question 1 incorrect. If you don’t know this, you don’t know Big O enough to answer the rest.
  • I gathered responses mainly on Facebook from the Cracking the Coding Interview Official group and the Hackathon Hackers group.

14 of 17

conclusions

  • Typical person got about half wrong.
  • Almost no one got everything correct.
  • Most people made the same mistake repeatedly: carelessness with what a variable means in big O. For example, nested for loops are not inherently O(N^2); they might be O(A*B) or something else.

15 of 17

% People Who Got Exactly ___ Correct

​

​

​

Remember! Everyone got Q1 right (by definition). If you didn’t, your responses were excluded.

16 of 17

% People Who Got a Score of At Least ____

Remember! Everyone got Q1 right (by definition). If you didn’t, your responses were excluded.

17 of 17

% People Who Got Question ___ Correct / Incorrect / Blank

Remember! Everyone got Q1 right (by definition). If you didn’t, your responses were excluded.