README.md

Algorithm

It helps you preparing and succeeding in algorithm & data structure interview.

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.

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 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
• x | 1s
• x | x
• XOR operations
• | operator
• ~ 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

• Dynamic programming concept
• Memoization vs tabulation

Encoding

• ASCII charset
• Difference encoding/charset
• Unicode charset

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

• Hash table complexity: search, insert, delete
• Hash table implementation

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

• Dequeue data structure
• Queue
• Queue implementations and insert/delete complexity

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

• Stack
• Stack implementations and insert/delete complexity

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