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

Data Structures

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;
  • 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

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:

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:

Algorithms

Interview tips

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.