interview_checklist
interview_checklist
Typical whiteboard coding workflow
Clarify question
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
Problem types:
Sort
Stable or not
External or internal
Input almost sorted or not
Input range
Increasing/Decreasing order
Search
Whether duplicate entries exist
Edge cases: "If input is like this, then what should I output?"
Clarify the input size
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.
|
|
|
|
| O(n!) | 1-10 | 10! = 3628800 |
| O(2^n) | 1-20 | 2^20 = 10^6 |
| O(n^4) | 10-50 | 50^4 = 6.25*10^6 |
| O(n^3) | 10-100 | 100^3 = 10^6 |
| O(n^2) | 100-1000 | 1000 ^ 2 = 10^6 |
| O(nlogn) | 1000-10^6 | 10^6 * log(10^6) = 10^6 |
| O(n) | 1000-10^6 | 10^6 |
| O(sqrt(n)) | 10^4-10^9 | 10^6 |
| O(log(n)) | 10^5-10^9 | 10^6 |
| O(1) | 10^6-10^9 | 10^6 |
Give a small but general enough example for discussing algo/DS
Usually a size of 4~5 is enough.
Come up with a brute force algorithm
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)"
Optimize the brute force solution
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."
Write test cases
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
Write code
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.""
Walk through test cases
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."
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
Synchronize with interviewer: "I think I am done with the problem".
Solve follow up questions
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
Interview mindset
Understanding what interviewers really wants
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 |
Checklist
Things to be careful.
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.
Phone interviews
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.
Onsite interviews
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.
Last updated