Coding-Interview-101

Author: @xianzhez

Last updated: 2020.11.26

Remark:

For data structures and algorithms in this document

• in bold: you must know the concept and complexity, and can implement in real code.
• normal: you should know the concept and complexity, but pseudo-code is fine.
• in italic: you should know the general idea. If you encounter such a question in an interview for entry-level position, that company might not be hiring actively.

Preface

This post is summarizing the data structure and algorithm fundamentals you might need in a coding interview and the corresponding implementations in different languages (Currently Python, Java, and C++).

You may or may not know some of them. It's totally fine. You could easily find videos, blogs, and source code about these data structures and algorithms online.

I tried to make it accurate and correct. But I might be still missing something important or writing something wrong. If you find any mistake or have good advice, you are welcome to contact me. If you find it useful, welcome to star, fork, and share this repo. Please also provide the reference if you are going to refer to this repo.

Coding classic algorithms may not represent your actual ability and specialization. Don't feel discouraged if you cannot solve it in limited time or fail an interview. It takes some time!

I will keep updating this doc and make it more helpful. I hope everyone could land a dream job eventually. Keep coding!

Prerequisite

1. Learn a programming language;
2. Learn data structures and APIs;
3. Understand the underlying implementation of data structures;
4. Understand complexity analysis;
5. Learn classical algorithms and advanced data structures;

Language

• C++: cplusplus.com - The C++ Resources Network
• Python: Python Tutorial
• Java: Java Documentation

Data Structures

• Cheatsheet(ALGS4)(Java): Algorithms and Data Structures Cheatsheet
• Big-O Algorithm Complexity

Python: Data Structures — Python 3.8.6 documentation, Common Python Data Structures (Guide) – Real Python
Java: Lesson: Interfaces (The Java™ Tutorials > Collections)
C++: Containers - C++ Reference

Basic

• Array:

Python: list
Java: ArrayList
C++: std::vector

• LinkedList:

Python: list or customized
Java: LinkedList
C++: std::list

• HashTable:

Python: dict(), collections.defaultdict()
Java: HashMap
C++: std::unordered_map

• HashSet

Python: set()
Java: HashSet()
C++: std::unordered_set

Advanced

• Tree
• Graph
• Stack

Python: list, deque
Java: Stack
C++: std::stack

• Deque

Python: collections.deque()
Java: LinkedList, ArrayDeque
C++: std::deque

• PriorityQueue (heap)

Python: heapq, collections.PriorityQueue (thread safe)
Java: PriorityQueue
C++: std::priority_queue

• BinarySearchTree (map)

Python: None (try to use bisect, but big O is different)
Java: TreeMap
C++: std::map

• BinarySearchTree (set)

Python: None (try to use bisect], but big O is different)
Java: TreeSet
C++: std::set

• Trie: a map of key, map pairs;

• T = lambda: collections.defaultdict(T)
• Implement Trie (Prefix Tree) - LeetCode

• UnionFind

You can implement by yourself in an interview, here is a very concise and brilliant template (path compression has been included):

uf = {i:i for i in range(len(M))}
def find(p):
  if uf[p] != p:
      uf[p] = find(uf[p])
  return uf[p]

def union(p1, p2):
  a1, a2 = find(p1), find(p2)
  uf[a2] = a1

WARNING: this implementation has some limitation, such as you need to traverse the uf by calling find for every element with a set to count the number of unions, this operation is O(n) since the length of the path for every element will be no more than 2.

Time complexity for union find is a little bit tricky, the union and find operation will take log*n time. Please check this wiki to get a better understanding.

Ultimate

• Red-black tree
• KD-Tree
• B-tree
• Segment Tree

Algorithms

Cheatsheet(ALGS4) (Java): Algorithms and Data Structures Cheatsheet

Basics

• DFS
• BFS
• BackTracking
• Binary Search
• Two pointers
• Fast and slow pointers
• (Thinking from Reverse Order)

Advanced

• Topological sort
• Greedy: e.g. Huffman coding
• Divide and Conquer
• UnionFind
• Cycle detection in undirected graph
• Cycle detection in directed graph
• Find SCC in directed Graph
• Lowest Common Ancestor
  • Lowest Common Ancestor of a Binary Tree - LeetCodeLowest Common Ancestor Binary Tree - YouTube
• Dijkstra: single source shortest path, O(nlogn + m )
• Bellman-Floyd: single source with negative weights, O(mn)
• Floyd-Warshall: all pairs shortest path; O(n^3)
• Reservoir Sampling
• KMP Implement strStr() - LeetCode
• Manacher
• Morris

Ultimate

• Minimum Spanning Tree: Prim’s, Kruskal
• minimum s-t cut: Ford-Fulkerson
• global min cut: Karger’s, Karger Stein

Dynamic Progamming

Recipe for DP:

1. Identify optimal substructure
2. Find a recursive formulation for the optimal solution
3. Use dynamic programming to find optimal solution
4. If needed, keep track of some additional info so that the algorithm from step 3 can find the actual solution

Classical Problems:

• LCS: longest common subsequence Longest Common Subsequence - LeetCode
• unbounded knapsack
• 0/1 knapsack

LeetCode LC322M: Coin Change - LeetCode

Complexity: reduce time complexity from exponential with brutal force to polynomial.

Resources

Blogs and Repos

1. GitHub - Tech-Interview-Cheat-Sheet: An interview cheatsheet.
2. Data Structures - GeeksforGeeks: data structure basics
3. fucking-algorithm: algorithms (available in both English and Chinese)
4. fuck-coding-interviews: data structure and algorithms implementation, as well as solutions for leetcode questions sorted by categories.

Videos

These videos and Youtuber might be helpful.

You can also take some online courses or watch some famous courses online to learn data structures and algorithms systematically if you have enough time. This might be time consuming but useful. Such as CS106B@Stanford, CS161@Stanford, 6.006@MIT, etc.

Some textbooks you can refer to but not required:

• Introduction to Algorithms
• Algorithms

Algorithms

• @Tushar Roy - Coding Made Simple

  • Graph Algorithms @ Tushar Roy - Coding Made Simple: I found these videos very useful to understand and implement graph algorithms. Tushar also provide the source code.

  • Dynamic Programming @ Tushar Roy - Coding Made Simple

• @Abdul Bari

  • Algorithms: most of algorithms mentioned in this blog are covered.

Interview tips

• @Clément Mihailescu

  • Google Coding Interview With A College Student
  • Google Coding Interview With A High School Student

• @TechLead

  • How to solve coding interview problems ("Let's leetcode") @ TechLead

Takeaway

Before the interview

• Practice on some platforms such as LeetCode, Google KickStart, HackerRank;
  • LeetCode Premium is very useful, especially you can filter questions with tags and companies, and sort problems by frequency.
  • Participating in the weekly contest on LeetCode is also a good way to practice interivew.
• Find someone to do mock interview.

In the interview

• Correctness matters, find a workable solutions at least.
• Time matters, spending too much on a simple solution you have known is not a good option.
• Communication matters, think loud and let the interviewer know what you are thinking about. Then the interviewer can know how to give you hints.
• Handle edge cases, you can skip some parts handling edge cases and complete them later, but you must let the interviewer know that you have noticed these edge cases. You can add some TODOs or move it to a function to implement later.
• Time complexity and space complexity are necessary. Even the interviewer forgets to ask you about the complexity analysis, you should address them. Because it is an important part of the feedback the interviewer will submit.