what to expect:
- welcome: hello, small talk
- you will write on walls (if you can only write in the IDE, then you might not know the code as well)
How to crack the interview: Part #1:
- Listen (are there clues?)
- Don’t panic!
- Ask clarification questions (do you understand the problem, what is the expected output)
- Draw a picture and a sample input (pictures and diagrams can help visualize the problem)
- Define the scope (are there memory concerns, can I assume ASCII, is input well formed)
- Can I calculate a couple of expected results
Selecting a Strategy #2:
- Can you see an optimal solution (if you see it before, be honest)
- Can you see any solution? (your aim is to get something working, you can optimize it later)
- 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
Writing Code: Part #3:
- Tell me what you are going to do (tell the language you are going to code it in)
- 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
- Test it, test it, test it!
- walk through a quick sanity check
- just fix mistakes
Now REALLY test it #3:
- Run through your hand calculated example/diagram still on the board
- Think like a tester/hacker, and test again (select nasty test cases, Null/Empty, negative, stuck/looped forever)
- Tell me when you think you’re done (if I say “Are you sure that’s right?”, it’s probably not)
- Be prepared to answer questions on the code
- Know about time complexity, and space complexity (Is it O(n^2), O(nlogn), O(n))
Optimization #4:
- Can your current solution be optimized(“Are you sure that is optimal”, it probably isn’t)
- 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:
- can we modify the data in place
- does order need to be preserved
- Is it case sensitive? ASCII?
- is input well formed?
- if there are multiple solutions, are we looking for one solution, all solutions? If one, the largest? Smallest?
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:
- sort first
- return the last three elements, or first two and last element
Best idea:
- only pass through array once
- find thrid best
Example #5 Two Sum Problem
Naiive solution - O(n^2)
Better:
- sort into ascending order
- O(nLogn)
Example #6 Hash Version
- (6,6) is not a pair (they are the same)
- overflow in massive negative numbers
Example #7 Count number of negative elements
Naiive soltion:
O(n * m)
better:
- know numbers to the left are negative, once you reach one, go downwards
practice, practice, practice
cracking the coding interview
what we’re looking for:
- you can understand the problem
- suggest a good algorithm and solve it
- convert into clean, efficient, bug-free, code
- understand the time/space complexity of the solution
- describe/communicate the algorithm
- optimize your current solution
- know limitations of the solution