Cracking the Algorithm & Coding Interview - Gayle McDowell - Push yourself!

http://www.slideshare.net/gayle2/cracking-the-algorithm-coding-interview-svcc
Strong CS fundamentals
Analytical skills
Make tradeoffs
Push through hard problems
Communication
How you think

Preparation
Implement DS/Algorithms
MASTER Big O
Practice with interview questions
Code on paper/whiteboard
Mock interviews

Expectations & Evaluation
What is not expected:
To know the answers
To solve immediately
To code perfectly

Be excited about hard problems
More than just “correct”
Drive!
Keep trying when stuck
Write real code
Show me how you think!

RELATIVE
Not a “metric” / timer
No one is perfect!

step 1:
Listen (for clues)
What’s the clue?
Anagram server
Ex: rates -> aster, stare, taser, tears

Clue: why is it on a server?

Step 2:
Draw an Example
Big Enough + General Purpose

Ex: Intersection of Two Sorted Arrays
Most people draw something like this:
[1, 12, 15, 19]
[2, 12, 13, 20]

Too small
Too special-case-y
same size, one common element, same index

Better:
  [1, 12, 15, 19, 20, 21]
  [2, 15, 17, 19, 21, 25, 27]

Big
No special cases

Step 3:
Brute Force / Naive
Stupid & terrible is okay!

Step 4:
Optimize
Walk through brute force
Look for optimizations

Techniques to Develop Algorithms
Optimize
BUD
Space/time
Do it yourself

Solve
Recursion
Solve “incorrectly”
Other data structures

(A) Look for BUD
Bottlenecks
Unnecessary work
Duplicated work

What’s the bottleneck?
Ex: counting the intersection
  [1, 12, 15, 19, 20, 21]
  [2, 15, 17, 19, 21, 25, 27]
Bottleneck: searching

What’s unnecessary?
Ex: a3 + b3 = c3 + d3    (1 <= a, b, c, d <= 1000
Unnecessary: looking for d

What’s duplicated?

Duplicated: c, d pairs

(B) Space/Time Tradeoffs
Hash tables & other data structures
Precomputing

Space/Time Tradeoffs  Hash tables
Find # pairs with sum
  INPUT: array = [5, 15, 8, 9, 3, 2, -1, 4]
              sum = 7
  OUTPUT: 3
    pairs = (5, 2), (8, -1), (3, 4)
Put items into hash table

Space/Time Tradeoffs  Precomputing
Find rectangle at origin w biggest sum

Find permutations of s within b
s = abbc
b = babcabbacaabcbabcacbb

Find them!
… now how did you actually do it?

(D) Recursion / Base Case & Build
Subsets of a set
{}  {}
{a}  {}, {a}
{a, b}  {}, {a}, {b}, {a, b}
{a, b, c}  …
Subsets of {S1…Sn-1} + Sn to each

(E) Solve “incorrectly”
Develop incorrect solution
Identify why precisely it’s incorrect
Repair
(& Repeat)

Random node in BST
Try: flip coin
Coin = Heads
 Branch Left
Coin = Tails
 Branch Right

Try: pick random # 0 through n-1
R = 0
 Return root
1 <= R <= left.size
 Branch left
R > left.size
 Branch right

(F) Other Data Structures
Giving out phone numbers
“I want any available number”
“I want this number”
Try: sorted array? Sorted linked list? Hash table? BST?

step 5:
Walk Through
Know the variables
and when they change

How to Write Whiteboard Code
Modularized
Error cases / TODOs
Good variables

Write straight
Top-left corner
Use arrows if needed

step 7 - Testing

FIRST Analyze

What’s it doing? Why?

Anything that looks weird?

Error hot spots

THEN use test cases

Small test cases

Edge cases

Bigger test cases

Final Thoughts

Be a great teammate.

Be a great engineer.

http://www.slideshare.net/gayle2/cracking-the-coding-interview-40140660
The Perfect Candidate
How to become a more perfect dev candidate
Coursera
Bootcamps
Read lots.
Write lots.

Hackathons
Diversity languages.
Independent projects.

Length:
1 – 2  pages.
1 – 2 lines per bullet.
3 – 6 bullets per company.
Projects.
Clear accomplishments.
Technical…
But not overwhelming.

Knowledge Questions
Know your stuff.
Be cautious about what you list.
If you don’t know, admit it.
Derive it if possible.

“Design Google Maps”
Strong foundation in CS
Analytic skills/intelligence.
Ability to make tradeoffs.
Discussion/teamwork ability.
How you think about a problem.

7. Testing
Conceptual - does it make sense?
Weird stuff (x = len – 2)
Hot spots (end of list)