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
