what to expect:

How to crack the interview: Part #1:

  1. Listen (are there clues?)
  2. Don’t panic!
  3. Ask clarification questions (do you understand the problem, what is the expected output)
  4. Draw a picture and a sample input (pictures and diagrams can help visualize the problem)
  5. Define the scope (are there memory concerns, can I assume ASCII, is input well formed)
  6. Can I calculate a couple of expected results

Selecting a Strategy #2:

  1. Can you see an optimal solution (if you see it before, be honest)
  2. Can you see any solution? (your aim is to get something working, you can optimize it later)
  3. If you really can’t see a solution (what tools can you apply from your bag of tricks, apply all computer science tools) -> hash table, linked list, tree, attack with recursion
    • pseudo/flowchart

Writing Code: Part #3:

  1. Tell me what you are going to do (tell the language you are going to code it in)
  2. Start to write code
    tip 1: start near the top of the walls
    tip 2: use sensible variable names
    tip 3: it’s okay to use helper functions
    tip 4: it’s hard to copy-paste on a white board
    tip 5: if you start off neat, you will probably stay neat, if it starts messy, it will probably be messy
  3. Test it, test it, test it!
    • walk through a quick sanity check
    • just fix mistakes

Now REALLY test it #3:

  1. Run through your hand calculated example/diagram still on the board
  2. Think like a tester/hacker, and test again (select nasty test cases, Null/Empty, negative, stuck/looped forever)
  3. Tell me when you think you’re done (if I say “Are you sure that’s right?”, it’s probably not)
  4. Be prepared to answer questions on the code
  5. Know about time complexity, and space complexity (Is it O(n^2), O(nlogn), O(n))

Optimization #4:

  1. Can your current solution be optimized(“Are you sure that is optimal”, it probably isn’t)
  2. Is there a totally different algorithm that might work better (possible ways to solve the problem in a different way, talk through pros/cons, I may ask you to implement a more optimal strategy)

Questions to consider:

Are there any clues in the question?

“Array of numbers”
“Array of integers”
“Array of unsigned 8-bit integers”
“Array of sorted integers”
“Array of sorted, positive, integers”
“Array of unsorted array of integer, some positive, some negative”
“Array of distinct integers”
“Array of sorted,distinct integers”

Examples

Example #1 Magic array

M[i] == i

Given an array of sorted distinct integers, find out if there is a magic number

Naiive solution: brute force,

better == binary search

Example #3 Sum of Digits

Naiive solution: helper function

Write a function to return the large of two numbers

bail based on sigfigs what should you return if both are equal

Possible Follow up Questions

add two long string numbers together

Example #4 Max Product Triplet

Naiive Solution: brute force O(n^3)

Better:

Best idea:

Example #5 Two Sum Problem

Naiive solution - O(n^2)

Better:

Example #6 Hash Version

Example #7 Count number of negative elements

Naiive soltion: O(n * m)

better:

practice, practice, practice cracking the coding interview

what we’re looking for:

Facebook Cracking the Coding Interview | Home