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
- pseudo/flowchart

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?

- 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”

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

Naiive solution: helper function

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

add two long string numbers together

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

Naiive solution - O(n^2)

Better:

- sort into ascending order
- O(nLogn)

- (6,6) is not a pair (they are the same)
- overflow in massive negative numbers

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