List of Algorithms

All programs are categorized in level 1 to 4 (1 being easiest)

Sorting

• Bubble sort (Python): Implement bubble sort in Python | O(n^2) | Level 2.
• Bubble sort (Go): Implement bubble sort in Golang | O(n^2) | Level 2.
• Selection sort (Python): Implement selection sort in Python | O(n^2) | Level 2.
• Selection sort (Go): Implement selection sort in Golang | O(n^2) | Level 2.
• Insertion sort (Python): Implement insertion sort in Python | O(n^2) | Level 2.
• Insertion sort (Go): Implement insertion sort in Golang | O(n^2) | Level 2.
• Heap sort using max heap (C): Build a max heap and sort array in ascending order in C | Level 3.
• Heap sort using max heap (Python): Build a max heap and sort array in ascending order in Python | Level 3.
• Heap sort using max heap (Go): Build a max heap and sort array in ascending order in Golang | Level 3.
• Heap sort using min heap (C): Build a min heap and sort array in descending order in C | Level 3.
• Heap sort using min heap (Python): Build a min heap and sort array in descending order in Python | Level 3.
• Heap sort using min heap (Go): Build a min heap and sort array in descending order in Golang | Level 3.
• Merge sort: Implement merge sort | O(nlogn) | Level 3.
• Merge sort - python: Implement merge sort in python | O(nlogn) | Level 3.
• Quick sort: Implement quick sort(C) for array of random numbers | O(nlogn) | Level 3.
• Quick sort - python: Implement quick sort(python) for array of random numbers | O(nlogn) | Level 3.
• Counting sort: Implement count sort | O(n + k) | Level 2.
• Counting sort - python: Implement count sort in python | O(n + k) | Level 2.
• Radix sort: Implement radix sort | O(digits * (n + base)) | Level 4.

Trie

• Trie implementation: Implement trie and perform insert, search and delete operations | O(L) | Level 3.
• Trie autocomplete: Implement word autocomplete feature using trie | O(ALPHABET_SIZE * N * L) | Level 3.
• Trie, sorted strings: Print all words in trie, in sorted order | O(ALPHABET_SIZE * N * L) | Level 2.
• Trie, longest prefix matching: Given a string, find a word from trie which matches longest prefix | O(n) | Level 2.
• Pattern matching using suffix tries: Implement suffix tries for pattern matching | O(m) | Level 3.

Graphs

• DFS traversal: Create a directed graph and performs depth first search(DFS) traversal | O(V + E) | Level 2.
• BFS traversal: Breadth first search(BFS) traversal of directed graph | O(V + E) | Level 2.
• Connected components: Find all connected components in a graph | O(V + E) | Level 2.
• Shortest path in unweighted graph: Find shortest path from src to dst in an unweighted graph | O(V + E) | Level 2.
• Cycle in graph: Check if there is cycle in a directed graph, uses DFS | O(V + E) | Level 3.
• Topological sort: Topological order of directed acyclic graph (DAG) using DFS | O(V + E) | Level 3.
• Topological sort (Kahn's algo): Topological order of directed acyclic graph (DAG) using Kahn's algorithm | O(V + E) | Level 3.
• Shortest path of DAG: Find shortest in a directed acyclic graph from a source vertex to all reachable vertex | O(V + E) | Level 3.
• Dijkstras shortest path: Implement Dijkstras shortest path algo | O(E * log(V)) | Level 3.
• Bellman ford: Bellman ford algo to find shortest path in a graph | O(VE) | Level 3.
• Triagles in graph: Given a graph(directed or undirected), count the number of triagles present | O(N^3) | Level 2.

Union find(disjoint sets)

• Implement disjoint sets (Python): Implement union find data structure with path compression and rank in Python | O(1) | Level 2.
• Implement disjoint sets (Go): Implement union find data structure with path compression and rank in Go | O(1) | Level 2.
• Undirected graph cycle detection: Check if undirected graph has cycle or not using union find | O(V + E) | Level 2.
• Kruskals algo - MST: Kruskals algorithm to find minimum spanning tree(MST) of undirected graph | O(ElogE) | Level 3.
• Job sequencing problem: Given set of jobs with deadline and profit, find seq for max profit | O(N) | Level 4.

Square root decomposition

• Square root decomposition - Python: Implement square root decomposition method for range sum query in Python | O(sqrt(n)) | Level 2.
• Square root decomposition - Go: Implement square root decomposition method for range sum query in Go | O(sqrt(n)) | Level 2.

Segment tree

• Segment Tree - Python: Implement segment tree (iterative approach) in Python | O(logn) | Level 3.
• Segment Tree - Go: Implement segment tree (iterative approach) in Golang | O(logn) | Level 3.

Binary indexed (Fenwick) tree

• Binary indexed (Fenwick) tree: Implement BIT (fenwick tree) | O(n) | Level 3.

Cracking the coding interview(6th edition)

1. Arrays and strings

• Check strings has unique characters: Check if a string has all unique characters or not | Level 1.
• 2 strings are permutations: Check if 2 strings are permutations of each other or not | Level 2.
• Update input string: Update(in-place) input string to have space replaced with %20 | O(n) | Level 2.
• Is permutation palindrome: Check if any permutation of given string is palindrome or not | Level 2.
• Check 2 strings, one edit away: Check if 2 strings are max one edit away or not | O(n) | Level 2.
• String compression: Compress string, show count for consecutive repeating characters | O(n) | Level 2.
• Rotate square matrix: Rotate square matrix clockwise by 90 degrees | O(n) | Level 3.
• Clear row and column if 0 found: If an element in a matrix is 0, its entire row and column are set to 0 | O(MxN) | Level 3.
• 2 strings are rotations: Check if 2 strings are rotations of each other or not | O(n) | Level 2.

2. Linked list

• Remove duplicates from linked list: Remove duplicates from a linked list | O(n) time and space | Level 2.
• kth from last in linked list: Find kth element from last of a singly linked list | O(n) | Level 3.
• Delete node from linked list: Given only reference to an arbitary node of a linked list, delete that node | O(1) | Level 2.
• Partition linked list: Partition a linked lists with respect to a given value | O(n) | Level 2.
• Sum digits of 2 linked list, digits in reverse order: Add 2 numbers stored in linked list in reverse order(12 is 2->1) | O(n) | Level 2.
• Sum digits of 2 linked list, digits in forward order: Add 2 numbers stored in linked list in forward order(12 is 1->2) | O(n) | Level 3.
• Is linked list palindrome: Check if linked list is palindrome or not | O(n) | Level 2.
• Linked list intersection: Find if two linked list intersect each other | O(m + n) | Level 2.
• Starting node of loop in linked list: Detect loop in linked list and find starting node of loop | O(n) | Level 4.

3. Stacks and queues

• Skipped code, mostly theoritical/design questions

4. Trees and graphs

• Route between 2 nodes: Given a directed graph, check if there is a route b/w 2 nodes | O(V + E) | Level 2.
• Sorted array to BST: Given a sorted array, create binary search tree(BST) with minimal height | O(N) | Level 3.
• List of depths: Binary tree to linked list for each level | O(N) | Level 2.
• Is tree balanced: Check if a binary tree is balanced | O(N) | Level 2.
• Is BST valid: Check if a tree is valid BST or not | O(N) | Level 3.
• BST inorder successor: Find inorder successor of a node in binary search tree | O(h) | Level 2.
• Project build order: Given projects and there dependent projects, find build order. Graph topological sort problem | O(P + D) | Level 2.
• [