- Define public APIs to be implemented:
- Things to define - Input type
- Things to define - Number of input arguments
- Things to define - Output type
- boolean: Whether solutions exist or not
- int: the number of solutions
- List<?> : solutions themselves
- List<?>: solutions without duplicates
- List<?>: solutions with specific order
- Clarify ambiguous problem statements / Gather all requirements
- Solution existence: "What if no solution exists? How should I handle that?"
- Solution uniqueness: "Whether there are multiple solutions?"
- Input emptiness: "How should I handle null pointers and input of size zero?"
- Input validity: "Could I assume input is always invalid?"
- Input types:
- Typical scenarios
- In most cases, one single public API
- Multiple public APIs inside a class
- Two associated APIs, like serialize and deserialize
- Input - Field types
- Integer or double
- Positive or negative, non-positive or non-negative
- Input - Array
- Sorted or unsorted, sorted increasingly or decreasingly
- Given two arrays, which one's size is bigger
- Whether could modify entries inside array
- Input - String
- Whether the string contains space
- How are tokens separated, using comma, slash or something else
- Alphabetic characters(lower/upper case), ascii characters, or unicode characters
- Input - LinkedList
- Doubly or singly linkedlist
- Input - Tree
- Binary tree
- Binary search tree
- Complete tree
- Input - Graph
- Directed or undirected
- Weighted or not
- Connected or not
- Typical scenarios
- Problem types:
- Sort
- Stable or not
- External or internal
- Input almost sorted or not
- Input range
- Increasing/Decreasing order
- Search
- Whether duplicate entries exist
- Sort
- Edge cases: "If input is like this, then what should I output?"
- As of today, a single 2GHz CPU could process 2*10^9 OPS/second
- When the following factors are considered, a single 2GHz CPU could perform 10^6-10^7 ops/sec.
- Overhead of memory access
- Overhead of branching
- Large constant factors
- The input size could give an intuition on the best algorithm's type.
Sample Problem Type |
Algorithm complexity |
Applicable input size |
Calculation using upper bound |
|---|---|---|---|
Permutation |
O(n!) | 1-10 | 10! = 3628800 |
Combination |
O(2^n) | 1-20 | 2^20 = 10^6 |
All pairs, dense graph / DP |
O(n^4) | 10-50 | 50^4 = 6.25*10^6 |
All pairs, shortest path / DP |
O(n^3) | 10-100 | 100^3 = 10^6 |
DP |
O(n^2) | 100-1000 | 1000 ^ 2 = 10^6 |
Sorting based(Greedy) / heap / divide & conquer |
O(nlogn) | 1000-10^6 | 10^6 * log(10^6) = 10^6 |
DP, graph traversal / topological sort (V+E) / tree traversal |
O(n) | 1000-10^6 | 10^6 |
Prime, square sum |
O(sqrt(n)) | 10^4-10^9 | 10^6 |
Binary search |
O(log(n)) | 10^5-10^9 | 10^6 |
Math |
O(1) | 10^6-10^9 | 10^6 |
- Usually a size of 4~5 is enough.
- Synchronize with interviewer "Let's come up with a brute force solution first."
- Unstuck strategy:
- The most straightforward way to list all possible solutions
- Whether I could decompose the problem into subproblems and solve them individually
- Divide and conquer "The problem could be decomposed into X subproblems."
- Brainstorm DS/Algo which might be used / Give it a try
- Give it a try: "Let's try a graph-based solution"
- Talk about the data structures to be used.
- Talk about the algorithm to be used.
- Calc time/space complexity: "The time complexity of the algorithm is O(XXX) and space complexity is O(XXX)"
- Synchronize with interviewer "The time/space complexity of the brute force solution is too high and will be impractical."
- Consider the typical optimizing patterns below:
- Where the bottleneck is: "The bottleneck of the algorithm lies in this section of code"
- What the time complexity upper bound is: "Theoretically, the best time complexity I could achieve is O(n) because I need to look through all items."
- Whether space complexity is acceptable or not: "algo with linear space complexity is usually acceptable."
- Repetitive computation: "We solve a lot of repetitive problems. If we could cache the solutions, it will be much more efficient."
- Additional rounds of iterating input: "We iterate through input twice. If we could reduce it to once, it will boost performance twice."
- Synchronize with interviewer "The reason we could do better is XXX."
- Ask for help when being stuck
- Show interviewer all the approaches you tried and difficulties. ""
- Be keen to what interviewer is saying: Every word the interviewer is saying has its meanings. ""
- Synchronize with interviewer "Do you have any concerns for the proposed algorithm? Should we write code for this."
- In general, the following types of test cases should be considered
- The normal case: e.g. array length of even or odd in sorting algo
- The extremes: e.g. empty array, one element array, extremely large one array
- Nulls and "illegal" input: e.g. input is negative when positive is expected
- Strange input: an array already sorted
- Typical test cases for different input types
- Integer
- Integer.MAX_VALUE, Integer.MIN_VALUE
- 0
- Positive/negative numbers
- String
- NULL
- Single character
- Two characters
- Contains duplicated characters
- Contains space, tab or other separators
- Array/List <?> list
- NULL
- One element List/Array
- List/Array entry is NULL
- List/Array of even length
- List/Array of odd length
- Integer
- Synchronize with interviewer "There are XXX steps in this algorithm. The first is XXX. The second...."
- Check input validity (already discussed thoroughly before)
- Use // or empty line to separate different steps and a place to synchronize with interviewer.
- Just get the general algorithm down first and avoid getting caught up in trivialities
- When forget some language-specific trivial
- "I do not remember exactly how the interface looks like, but I'd guess it has an API like this."
- When need implement a large code block, or nested for/while loop, or repeated needed util methods, consider using a subroutine
- "I am going to use a subroutine with the following interface. I will implement later".
- When need double check trivials (like +1 or plus two, loop termination conditions ):
- "Not sure whether my loop should have "<" or "<=". Write a checkmark to remind yourself to figure out the details at the end.""
- When forget some language-specific trivial
- Synchronize with interviewer: "Then I would usually check my code against tests"
- Check the code by myself
- Check steps:
- Look for typos
- Look for unused variables, counters, unnecessary edge case checkings, boundaries index overflow/underflow
- Look for unhandled problem assumptions
- Use small test cases to test different logical branches of the code
- When there is a bug: do not rush to change. Identify the root cause first.
- "Give me a moment, I feel there is a bug here. Let's have a double check."
- "The root cause of the problem is XXX."
- Check steps:
- Explain shortcuts I have taken: Talk about sections which could be refactored/improved, but was done in a certain way in an interview setting
- Bad smells for refactoring and optimization
- Code/function length > 100
- Too many if statement checking for boundary cases
- Code do not generalize well. Only work for current problem. e.g. merge 2 sorted list -> merge k sorted List
- Nested while loops ( really error prone )
- Global variables
- Bad smells for refactoring and optimization
- Synchronize with interviewer: "I think I am done with the problem".
- Typical follow-up questions
- No duplicates -> duplicates exist
- Whether result exist -> return all results
- One dimension -> two dimension
- How to avoid global variables
- How to improve performance
- Evaluation criteria
- Can s/he explain technical solutions well?
- Does s/he understand basic concepts well?
- Does s/he has a good grasp of past project experiences?
- How is his/her attitude?
- Is s/he a good coder? (proficiency in leetcode and whether error-prone)
- What are interviewers really asking
| What they ask | Wrong response | What they really want |
|---|---|---|
| Tell me what you did for this project | Describe the process in chronological order Recites what's on their resume |
What are you able to do after completing this project4 How did you overcome obstacles Details that are not on your resume |
| Tell me what you did for this job | Describe major projects Describe daily tasks |
Were you able to learn quickly Did you add enough value at your previous job to prove that you can add value for me |
| Compare data structure A and B | Explain what A and B are respectively List 1 difference between them |
Does your explanation show that you have actually used them in a real project Explain real situations where you would use A vs B. |
| Write code to solve problem | Jumps into writing code Awkward silence |
Would I want to work with them everyday Have they actually written production grade code What do they do when stuck |
| Maybe you could try this ... | Take advice without serious thinking | Do they think independently How fast can they absord new information Do they take advice/directions well Do they learn quickly and run with it |
- Do not just give "yes" or "no" answers. Limit initial explanation to short summaries and allow the interviewer to ask follow up questions.
- Your tone of voice and word choice. Interviewers use voice to judge how believable you are. Posture really have impact on your mind.
- Eye contact and shake hands. Say thanks to interviewers at last.
- Test the online coding environment.
- Make sure your cellphone has enough battery.
- Have a copy of resume in front of you.
- Take notes and write a follow up thank you email with details from the discussion.
- Show up 15 minutes early and have the interviewer's phone number for last minute changes.
- Things to bring with you
- Identity card.
- Bring extra copies of your resume with you - for the interviewer and your own reference.
- Notes on the detailed schedule. Put interviewers' names and interview topic on a sticker and bring it with me.
- Tea/Coffee.
- Whiteboard pen and erasers.
- A piece of pen and paper. Take notes when an interviewer speaks to help yourself focus and ask more specific questions.
- Computers for last minute warm-up.