algodeck
Note: I also released the system design version: https://github.com/teivah/designdeck, an open-source collection of 230+ flash cards.
Overview
Algo Deck is an open-source collection of 200+ algorithmic flash cards.
It helps you preparing and succeeding in your algorithm & data structure interview. The code examples are in Java.
The topics covered are the following:
- Array: reversing an array, finding a pivot, handling a dynamic array, etc.
- Bit: operators, bit manipulation, etc.
- Complexity: algorithm & data structures complexity
- Dynamic Programming: dynamic programming concept
- Encoding: encoding theory
- General: general knowledge including how to approach a problem or testing a first solution
- Graph: A*, Dijkstra, BFS vs DFS, cycles detection, topological sort, etc.
- Greedy: greedy algorithms concepts
- Hash Table: hashtable data structure
- Heap: heap data structure including min-heap/max heap, binary heap use cases, etc.
- Linked List: linked list data structure, how to get the middle element, iterate over two lists, doubly linked list, etc.
- Math: discrete math
- Queue: queue data structure
- Recursion: recursion concepts
- Sort: sort algorithms including concepts, complexity, use cases, etc.
- Stack: stack data structure
- String: string permutation, rotation, rabin-karp substring search, etc.
- Technique: most important techniques to master to solve algorithmic problems including greedy techniques, runner, sliding window, etc.
- Tree: binary tree use cases, binary search tree, 2-3 tree, red-black tree, use cases, etc.
Anki Deck
Anki is a free software (Windows/Mac/Linux/iPhone/Android) which makes remembering things easy. It utilizes spaced repetition which is a proven technique to increase the rate of memorization:
Spaced Repetition: The most powerful study technique on YouTube
The single biggest change that Anki brings about is that it means memory is no longer a haphazard event, to be left to chance. Rather, it guarantees I will remember something, with minimal effort. That is, Anki makes memory a choice.
Michael A. Nielsen, “Augmenting Long-term Memory”
Using Anki is a great way to prepare your algorithm & data structure interview. Here is a flashcard example:
The Anki version (a clone of the +200 flashcards from this repo) is available via a one-time GitHub sponsorship tier for $19: ❤️ Sponsor, One-time tab, Access to the latest Anki deck version of Algo Deck tier.
Cards Index
Array
- Algorithm to reverse an array
- Array complexity: access, search, insert, delete
- Binary search in a sorted array algorithm
- Find an element in a rotated sorted array
- Given an array, move all the 0 to the left while maintaining the order of the other elements
- How to detect if an element is a pivot in a rotated sorted array
- How to find a pivot element in a rotated array
- How to find the duplicates in an array
- How to manage a dynamic array
- How to test if the array is sorted in ascending or descending order
- Rotate an array by n elements (n can be negative)
Bit
- & operator
- « operator
- » operator
- »> operator
- [^ operator](/bit.html)
- Bit vector structure
- Check exactly one bit is set
- Clear bits from i to 0
- Clear bits from most significant one to i
- Clear ith bit
- Flip ith bit
- Get ith bit
- How to flip one bit
- How to represent signed integers
- Set ith bit
- Update a bit from a given value
- x & 0s
- x & 1s
- x & x
- x ^ 0s
- x ^ 1s
- x ^ x
-
[x 0s](/bit.html) -
[x 1s](/bit.html) -
[x x](/bit.html) - XOR operations
-
[ operator](/bit.html) - ~ operator
Complexity
- 0/1 Knapsack brute force complexity
- 0/1 Knapsack memoization complexity
- 0/1 Knapsack tabulation complexity
- Amortized complexity definition
- Array complexity: access, search, insert, delete
- B-tree complexity: access, insert, delete
- BFS and DFS graph traversal time and space complexity
- BFS and DFS tree traversal time and space complexity
- Big O
- Big Omega
- Big Theta
- Binary heap (min-heap or max-heap) complexity: insert, get min (max), delete min (max)
- BST complexity: access, insert, delete
- BST delete algo and complexity
- Bubble sort complexity and stability
- Complexity of a function making multiple recursive subcalls
- Complexity to create a trie
- Complexity to insert a key in a trie
- Complexity to search for a key in a trie
- Counting sort complexity, stability, use case
- Doubly linked list complexity: access, insert, delete
- Hash table complexity: search, insert, delete
- Heapsort complexity, stability, use case
- Insertion sort complexity, stability, use case
- Linked list complexity: access, insert, delete
- Mergesort complexity, stability, use case
- Quicksort complexity, stability, use case
- Radix sort complexity, stability, use case
- Recursivity impacts on algorithm complexity
- Red-black tree complexity: access, insert, delete
- Selection sort complexity
- Stack implementations and insert/delete complexity
- Time complexity to build a binary heap
- Topological sort complexity
Dynamic Programming
Encoding
General
- Before finding a solution
- Comparator implementation to order two integers
- Different ways for two intervals to relate to each other
- Different ways for two intervals to relate to each other if ordered by start then end
- Divide and conquer algorithm paradigm
- How to name a matrix indexes
- If stucked on a problem
- In place definition
- P vs NP problems
- Solving optimization problems
- Stable property
- What do to after having designed a solution
Graph
- A* algorithm
- Backedge definition
- Best-first search algorithm
- BFS & DFS graph traversal use cases
- BFS and DFS graph traversal time and space complexity
- Bidirectional search
- Connected graph definition
- Difference Best-first search and A* algorithms
- Dijkstra algorithm
- Dynamic connectivity problem
- Dynamic connectivity problem - Quick-find solution
- Dynamic connectivity problem - Quick-union solution
- Dynamic connectivity problem - Weighted Quick-union solution
- Given n tasks from 0 to n-1 and a list of relations so that a -> b means a must be scheduled before b, how to know if it is possible to schedule all the tasks (no cycle)
- Graph definition
- Graph traversal: BFS
- Graph traversal: DFS
- How to compute the shortest path between two nodes in an unweighted graph
- How to detect a cycle in a directed graph
- How to detect a cycle in an undirected graph
- How to name a graph with directed edges and without cycle
- How to name a graph with few edges and with many edges
- How to name the number of edges
- How to represent the edges of a graph (structure and complexity)
- Topological sort complexity
- Topological sort technique
- Travelling salesman problem
- Two types of graphs
Greedy
- Best-first search algorithm
- Greedy algorithm
- Greedy algorithm: structure
- Greedy technique
- Technique - Optimization problems requiring a min or max
Hash Table
Heap
- Binary heap (min-heap or max-heap) complexity: insert, get min (max), delete min (max)
- Binary heap (min-heap or max-heap) data structure used for the implementation
- Binary heap (min-heap or max-heap) definition
- Binary heap (min-heap or max-heap) delete min
- Binary heap (min-heap or max-heap) insert algorithm
- Binary heap (min-heap or max-heap) use-cases
- Comparator implementation to order two integers
- Convert an array into a binary heap in place
- Find the median of a stream of numbers, 2 methods insert(int) and int findMedian()
- Given an unsorted array of numbers, find the K largest numbers in it
- Heapsort algorithm
- Is binary heap stable?
- Time complexity to build a binary heap
- Two heaps technique
- Why binary heap over BST for priority queue?
Linked List
- Algorithm to reverse a linked list
- Doubly linked list
- Doubly linked list complexity: access, insert, delete
- Get the middle of a linked list
- Iterate over two linked lists
- Linked list complexity: access, insert, delete
- Linked list questions prerequisite
- Queue implementations and insert/delete complexity
- Ring buffer (or circular buffer) structure
- What if we need to iterate backwards on a singly linked list in constant space without mutating the input?
Math
- a = a property
- If a = b and b = c then a = c property
- If a = b then b = a property
- Logarithm definition
- Median of a sorted array
- n-choose-k problems
- Probability: P(a ∩ b) // inter
- Probability: P(a ∪ b) // union
- Probability: Pb(a) // probability of a knowing b
Queue
Recursion
- How to handle a recursive function that need to return a list
- How to handle a recursive function that need to return a maximum value
- Loop inside of a recursive function?
Sort
- Bubble sort algorithm
- Bubble sort complexity and stability
- Counting sort complexity, stability, use case
- Counting sort algorithm
- Heapsort algorithm
- Heapsort complexity, stability, use case
- Insertion sort algorithm
- Insertion sort complexity, stability, use case
- Mergesort algorithm
- Mergesort complexity, stability, use case
- Quicksort algorithm
- Quicksort complexity, stability, use case
- Radix sort algorithm
- Radix sort complexity, stability, use case
- Selection sort algorithm
- Selection sort complexity
- Shuffling an array
Stack
String
- First check to test if two strings are a permutation or a rotation of each other
- How to print all the possible permutations of a string
- Rabin-Karp substring search
- String permutation vs rotation
- String questions prerequisite
Technique
- 0/1 Knapsack brute force technique
- 0/1 Knapsack memoization technique
- 0/1 Knapsack tabulation technique
- Backtracking technique
- Cyclic sort technique
- Greedy technique
- K-way merge technique
- Runner technique
- Simplification technique
- Sliding window technique
- Subsets technique
- Technique - Dealing with cycles in a linked list or an array
- Technique - Find all the permutations or combinations
- Technique - Find an element in a sorted array or linked list
- Technique - Find or calculate something among all the contiguous subarrays of a given size
- Technique - Find the longest/shortest substring or subarray
- Technique - Find the smallest/largest/median element of a set
- Technique - Finding a certain element in a linked list (e.g. middle)
- Technique - Given a sorted array, find a set of elements that fullfill certain conditions
- Technique - Given an array of size n containing integer from 1 to n (e.g. with one duplicate)
- Technique - Given time intervals
- Technique - How to get the K biggest/smallest/frequent elements
- Technique - Optimization problems requiring a min or max
- Technique - Problems featuring a list of sorted arrays (merge or find the smallest element)
- Technique - Scheduling problem with n tasks where each task can have constraints to be completed before others
- Technique - Situations like priority queue or scheduling
- Top K elements technique (biggest and smallest)
- Topological sort technique
- Traversal technique
- Two heaps technique
- Two pointers technique
- What if we need to iterate backwards on a singly linked list in constant space without mutating the input?
Tree
- 2-3 tree
- AVL tree
- B-tree complexity: access, insert, delete
- B-tree: definition and use case
- Balanced binary tree definition
- Balanced BST use case: B-tree, Red-black tree, AVL tree
- BFS and DFS tree traversal time and space complexity
- Binary tree BFS traversal
- Binary tree definition
- Binary tree DFS traversal: in-order, pre-order and post-order
- Binary tree: complete
- Binary tree: full
- Binary tree: perfect
- BST complexity: access, insert, delete
- BST definition
- BST delete algo and complexity
- BST insert algo
- BST questions prerequisite
- Complexity to create a trie
- Complexity to insert a key in a trie
- Complexity to search for a key in a trie
- Given a binary tree, algorithm to populate an array to represent its level-by-level traversal
- How to calculate the path number of a node while traversing using DFS?
- Min (or max) value in a BST
- Red-Black tree
- Red-black tree complexity: access, insert, delete
- Reverse a binary tree algo
- Trie definition, implementation and use case
- Why to use BST over hash table