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:

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:

• 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?

• keywords

“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