Cracking the Coding Interview (Part 1, 2 of 2)

January 14, 2016

Take notes about the video 

Cracking the Coding Interview (Part 1 of 2)

software programmer

Coding, problem solving, analytical skills and intelligent. 

Look for your aptitude, but not just your knowledge, for those top companies. 

Entrepreneur: start a marathon training group

The valuation of technical questions are relative to other candidates. 

How You Are Judged
How did you do RELATIVE to other candidates on the SAME question? 

More detail, coding questions, how fast you come out solution, how good your algorithm, how clean your code, how buggy your code. 

PM Roles (program manager, project manager)
. Communication Skills
. User-Focused Thinking
. Passion for Technology 
. Analytical Skills
. Technical Skills ( position dependent )

How We Review Resumes
1. Pull resume out of giant stack
2. Spot-check: company names, positions, projects, schools. 
3. Skim bullets to see if you've written real code
      reject   interview
4. Go to next resume & whine about how many more you have left. 

"Glanced at," not read, 15-30 seconds

Behavior questions:
Communication Goals
. Answer the question. 
. Deliver a *good* answer. ()
. Communicate well. 

Preparing for Behavioral Qs
. Create Preparation Grid for Projects
                                  OS Project           Amazon Intern
Enjoyed
Hated
Most Challenging
Hardest Bug 

Behavior Grid [for PM & less tech. roles]

Two structures:
1. First words is the answer. 
2. Situation, Action, Result   S. A. R. 

Technical questions:
Coding algorithms - study very well 
Out-of-schools 

They are not testing your knowledge. 

Practice solving questions. 
- Don't memorize!
- See: CtCI & CareerCup.com
. Push yourself!

Data strucutres
How to implement 
When to use (pros / cons)
Linked Lists         Stacks   Queues
Trees                   Tries      Graphs
Vectors                Heap      Hashtables

Algorithms
Implementation
Space vs. Time complexity 

Quick Sort                                 Merge Sort 
Tree Insert / Find                       Binary Search 
Breadth-First  Search                Depth-First Search 

Concepts 

Not just a concept - know how to code!

Threading   System Design & Scalability         Memory Management 

Recursion   Probability + Combinatorics           Bit Manipulation

Big O time 

How to learn CS Fundamentals:
Necessary for "elite" tech companies 
MIT Open Courseware
Freshman / sophomore level DS & Algo courses
Books 
- CLRS (Algorithms)


Part 2 of 2  - probably here? 

Types of "Serious" Questions
1. Product Design Questions
2. Estimation Questions
3. Software Engineering Questions
- Coding & Algorithms
- Object Oriented Design 
- Scalability 
- Factual / Trivia / Language-Based

Problem Design Qs: Approach 
1. Ask questions to resolve ambiguity
2. Understand the user
3. Structure the problem
4. Solve piece by piece

Estimation Questions:

It is not important to know the answers. About two things, problem solving and basic quantity skills. 

How much Gmail business revenue annually? 

The way to approach questions, 
Ask questions, gmail or gmail.com
Revenue or net sales 

Find structures: 
1. How many gmail acount users?
2. Estimate how much dollar value per click
3. How many clicks

If I can guess 3 numbers we have, I can multiply them and get answer for you. 

How do you figure out how many Gmail account users? 
Break down, make some assumptions, 

Estimation Qs: How to Approach
1. Ask questions to resolve ambiguity
- Don't make assumptions (yet)
2. Outline / Structure Your Approach 
3. Break down the components
- Assume numbers when necessary
- State assumptions explicitly 
- Round numbers to make your math easier

How many population? 80% uses gmail
Make reasonable guess

Take notes when you do it

Coding algorithms:
Ask questions - what the people are looking for
Talk aloud - 

How to Solve Tough Problems (7:53 /22:56 - ? )

1. Ask Questions!
- Questions are more ambiguous than they appear

2. Talk out loud
- Show us how you think 

3. Think critically 
- Does your algorithm really work? What's the space and time complexity? 

4. Code slowly and methodically
- It's not a race. 

Make too many mistakes, take too long, don't try to race it. 
If your code is done, test your code; make sure that it really works

Find the bug, do not just fix the value; find what is wrong. 

What does mean to write a good code? 

What does a "good coder" do? 
. Code in top-left of whiteboards
. Pseudo code first (if necessary)
. Be methodical. Don't try to rush. 
. Reasonably Bug Free
- Thorough testing (and careful fixing)
- Check for error conditions
. Clean coding
- Use other functions
- Good use of data structure (define own if useful)
- Concise and readable 

Algorithm Qs: Pattern Matching (13:10/22:56)

Q: Write code to reverse the order of words in a sentence. 
"dogs are cute"
"cute are dogs"

Similar to: reverse characters in a string. 
"dogs are cute"
"etuc era sgod"

A: Reverse full string, then reverse each word. 

Another approach: Simplify and generalize

Q: Design algorithm to figure out if you can build a ransom note (array of strings) from a magazine ( array of strings). 

Simplify: what if we used characters instead of strings? 
  -> Build array of characters frequencies. 

Generalize: how we can extend answer to words? 

A: Build hashtable from word to frequency. 

Next Approach: Base case & Build 
Q: Design algorithm to print subsets of set
{a, b, c} -> {}, {a}, {b}, {c}, {a,b}, {a,c}, {b, c}, {a, b, c}

S({}) -> {}
S({a}) ->{}, {a}
S({a,b}) -> {}, {a}, {b}, {a,b}
S({a,b,c}) -> ?

A. Build S(n) by cloning S(n-1) and add n to the cloned sets. 

Final approach, data structure brain storm

Q: There are 10^10 possible phone #s. Explain how you could efficiently implement 
assignSpecificNum(num) and assignAnyAvailableNum(). 

Array (sorted)? Too slow to remove num. 
Linked list? Too slow to find specific num. 
Hash table? Can't iterate through free nums. 
Tree? Ah-ha!  Binary search tree

Evaluation is relative. 

Top 10% - always get A, does not matter how hard the problem is. 

. Write real code - 
. Don't rush