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.
| Topic | Priority | Time required |
|---|---|---|
| Array | High | 2 hours |
| String | High | 3 hours |
| Hash table | Mid | 3 hours |
| Recursion | Mid | 3 hours |
| 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 |
| Topic | Priority | Time required |
|---|---|---|
| Tree | High | 4 hours |
| Graph | High | 4 hours |
| Heap | Mid | 3 hours |
| Trie | Mid | 3 hours |
| 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 |
To track progress: Grind 75
| 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 |
| 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 |
| 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 |
| 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 |
| 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 |
| 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 |
| 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 |
| 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 |
Copyright (c) 2017-Present Yangshun Tay