Coding Interview

Algorithms study cheatsheets

Basics

• Array
• String
• Hash table
• Recursion
• Sorting and searching

Data structures

• Matrix
• Linked list
• Queue
• Stack
• Interval

Advanced data structures

• Tree
• Graph
• Heap
• Trie

Additional

• Dynamic programming
• Binary
• Math
• Geometry

General interview tips

Clarify any assumptions you made subconsciously. Many questions are under-specified on purpose.

Always validate input first. Check for invalid/empty/negative/different type input. Never assume you are given the valid parameters. Alternatively, clarify with the interviewer whether you can assume valid input (usually yes), which can save you time from writing code that does input validation.

Are there any time/space complexity requirements/constraints?

Check for off-by-one errors.

In languages where there are no automatic type coercion, check that concatenation of values are of the same type: int/str/list.

After finishing your code, use a few example inputs to test your solution.

Is the algorithm meant to be run multiple times, for example in a web server? If yes, the input is likely to be preprocess-able to improve the efficiency in each call.

Use a mix of functional and imperative programming paradigms:

• Write pure functions as much as possible.
• Pure functions are easier to reason about and can help to reduce bugs in your implementation.
• Avoid mutating the parameters passed into your function especially if they are passed by reference unless you are sure of what you are doing.
• However, functional programming is usually expensive in terms of space complexity because of non-mutation and the repeated allocation of new objects. On the other hand, imperative code is faster because you operate on existing objects. Hence you will need to achieve a balance between accuracy vs efficiency, by using the right amount of functional and imperative code where appropriate.
• Avoid relying on and mutating global variables. Global variables introduce state.
• If you have to rely on global variables, make sure that you do not mutate it by accident.

Generally, to improve the speed of a program, we can either: (1) choose a more appropriate data structure/algorithm; or (2) use more memory. The latter demonstrates a classic space vs. time tradeoff, but it is not necessarily the case that you can only achieve better speed at the expense of space. Also, note that there is often a theoretical limit to how fast your program can run (in terms of time complexity). For instance, a question that requires you to find the smallest/largest element in an unsorted array cannot run faster than O(N).

Data structures are your weapons. Choosing the right weapon for the right battle is the key to victory. Be very familiar about the strengths of each data structure and the time complexities for its various operations.

Data structures can be augmented to achieve efficient time complexities across different operations. For example, a hash map can be used together with a doubly-linked list to achieve O(1) time complexity for both the get and put operation in an LRU cache.

Hash table is probably the most commonly used data structure for algorithm questions. If you are stuck on a question, your last resort can be to enumerate through the common possible data structures (thankfully there aren't that many of them) and consider whether each of them can be applied to the problem. This has worked for me sometimes.

If you are cutting corners in your code, state that out loud to your interviewer and say what you would do in a non-interview setting (no time constraints). E.g., I would write a regex to parse this string rather than using split() which may not cover all cases.

Study and practice plan

Week 1 - 4: Topical study + practice

Week 1

Topic	Priority	Time required
Array	High	2 hours
String	High	3 hours
Hash table	Mid	3 hours
Recursion	Mid	3 hours

Week 2

Topic	Priority	Time required
Sorting and searching	High	3 hours
Matrix	High	1 hour
Linked list	Mid	3 hours
Queue	Mid	2 hours
Stack	Mid	2 hours

Week 3

Topic	Priority	Time required
Tree	High	4 hours
Graph	High	4 hours
Heap	Mid	3 hours
Trie	Mid	3 hours

Week 4

Topic	Priority	Time required
Interval	Mid	2 hours
Dynamic programming	Low	4 hours
Binary	Low	2 hours
Math	Low	1 hour
Geometry	Low	1 hour

Week 5 - 12: In-depth practice

To track progress: Grind 75

Week 5

Problem	Difficulty	Duration
Two Sum	Easy	15 mins
Valid Parentheses	Easy	20 mins
Merge Two Sorted Lists	Easy	20 mins
Best Time to Buy and Sell Stock	Easy	20 mins
Valid Palindrome	Easy	15 mins
Invert Binary Tree	Easy	15 mins
Valid Anagram	Easy	15 mins
Binary Search	Easy	15 mins
Flood Fill	Easy	20 mins
Lowest Common Ancestor of a Binary Search Tree	Easy	20 mins
Balanced Binary Tree	Easy	15 mins
Linked List Cycle	Easy	20 mins

Week 6

Problem	Difficulty	Duration
Implement Queue using Stacks	Easy	20 mins
First Bad Version	Easy	20 mins
Ransom Note	Easy	15 mins
Climbing Stairs	Easy	20 mins
Longest Palindrome	Easy	20 mins
Reverse Linked List	Easy	20 mins
Majority Element	Easy	20 mins
Add Binary	Easy	15 mins
Diameter of Binary Tree	Easy	30 mins
Middle of the Linked List	Easy	20 mins
Maximum Depth of Binary Tree	Easy	15 mins
Contains Duplicate	Easy	15 mins

Week 7

Problem	Difficulty	Duration
Min Stack	Medium	20 mins
Maximum Subarray	Medium	20 mins
Insert Interval	Medium	25 mins
01 Matrix	Medium	30 mins
K Closest Points to Origin	Medium	30 mins
Longest Substring Without Repeating Characters	Medium	30 mins
3Sum	Medium	30 mins
Binary Tree Level Order Traversal	Medium	20 mins
Clone Graph	Medium	25 mins
Evaluate Reverse Polish Notation	Medium	30 mins

Week 8

Problem	Difficulty	Duration
Course Schedule	Medium	30 mins
Implement Trie (Prefix Tree)	Medium	35 mins
Coin Change	Medium	25 mins
Product of Array Except Self	Medium	30 mins
Validate Binary Search Tree	Medium	20 mins
Number of Islands	Medium	25 mins
Rotting Oranges	Medium	30 mins
Search in Rotated Sorted Array	Medium	30 mins

Week 9

Problem	Difficulty	Duration
Combination Sum	Medium	30 mins
Permutations	Medium	30 mins
Merge Intervals	Medium	30 mins
Lowest Common Ancestor of a Binary Tree	Medium	25 mins
Time Based Key-Value Store	Medium	35 mins
Accounts Merge	Medium	30 mins
Sort Colors	Medium	25 mins
Word Break	Medium	30 mins

Week 10

Problem	Difficulty	Duration
Partition Equal Subset Sum	Medium	30 mins
String to Integer (atoi)	Medium	25 mins
Spiral Matrix	Medium	25 mins
Subsets	Medium	30 mins
Binary Tree Right Side View	Medium	20 mins
Longest Palindromic Substring	Medium	25 mins
Unique Paths	Medium	20 mins
Construct Binary Tree from Preorder and Inorder Traversal	Medium	25 mins
Container With Most Water	Medium	35 mins

Week 11

Problem	Difficulty	Duration
Letter Combinations of a Phone Number	Medium	30 mins
Word Search	Medium	30 mins
Find All Anagrams in a String	Medium	30 mins
Minimum Height Trees	Medium	30 mins
Task Scheduler	Medium	35 mins
LRU Cache	Medium	30 mins
Kth Smallest Element in a BST	Medium	25 mins
Minimum Window Substring	Hard	30 mins

Week 12

Problem	Difficulty	Duration
Serialize and Deserialize Binary Tree	Hard	40 mins
Trapping Rain Water	Hard	35 mins
Find Median from Data Stream	Hard	30 mins
Word Ladder	Hard	45 mins
Basic Calculator	Hard	40 mins
Maximum Profit in Job Scheduling	Hard	45 mins
Merge k Sorted Lists	Hard	30 mins
Largest Rectangle in Histogram	Hard	35 mins

License

Copyright (c) 2017-Present Yangshun Tay