/cheat-sheet

Data structures & algorithms cheat sheet

cheat-sheet

Warning: Copying and pasting code from this cheat sheet for a programming competition will cause you to fail the plagiarism detector.

This cheat sheet contains concise implementations of common data structures and algorithms (DS&As) in Python. Its purpose is to give you a short list of DS&As that are worth memorizing because they are frequently used, yet most people struggle with them. I have excluded DS&As that most computer science graduates can implement with very little thought, such as tree traversals.

Table of Contents

  • Quickselect
  • Radix Sort
  • Index of First True
  • All Nearest Smaller Values
  • String Parsing

Bit Manipulation

  • Single Number
  • Longest Common Subsequence
  • Knapsack Problem
  • Best Time to Buy and Sell Stock
  • Matrix Chain Multiplication
  • Djikstra's Algorithm
  • Bellman-Ford Algorithm
  • Floyd-Warshall Algorithm

Competitive Programming Hacks

  • Fast O(n) Tricks
  • 2-Line Memoization