Skip to content

Latest commit

 

History

History
397 lines (372 loc) · 45 KB

README.md

File metadata and controls

397 lines (372 loc) · 45 KB

List of Algorithms

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

Sorting

Trie

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)

Square root decomposition

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

Cracking the coding interview(6th edition)

1. Arrays and strings

2. Linked list

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.
  • LCA in binary tree: Find lowest common ancestor in binary tree | O(n) | Level 3.
  • LCA in BST: Find lowest common ancestor in binary search tree | O(logn) | Level 2.
  • BST sequence: Skipped, not clear
  • Check subtree: Given 2 trees, check if one tree is exact subtree of another | O(n + km) | Level 2.
  • Check subtree - using preorder: Given 2 trees, check if one tree is exact subtree of another | O(n + m) | Level 2.
  • Get random node: Skipped, not clear
  • Paths with sum: Count number of paths in binary tree having given sum | O(nlogn) | Level 3.

5. Bit manipulation

6. Math and logic puzzles

  • Skipped, puzzles and mathematical questions

7. Object oriented design

  • LLD questions

8. Recursion and dynamic programming

9. System design and scalability

  • System design questions

10. Sorting and searching

11. Testing

  • Skipped

12. C and C++

  • Skipped

13. Java

  • Skipped

14. Databases

  • General DB concepts and questions

15. Threads and locks

  • Questions on thread and concurrency issues

16. Moderate

  • Swap 2 numbers: Swap 2 numbers, inplace | O(1) | Level 1.
  • Word frequency: Find frequency of words in list of words | O(N) | Level 2.
  • Intersection: Skipped, mathematical
  • Tic tac win: Skipped code, design
  • Factorial zeros: Compute number of trailing 0s in n factorial | log(n) | Level 2.
  • Smallest difference: Find smallest difference b/w pair of elements from 2 arrays | O(Alog(A) + Blog(B)) | Level 2.
  • Number max: Skipped, do in C language
  • English int: Skipped code
  • Arithmetic operations: Skipped code
  • Year with max population: Given birth and death years, find year with max population | O(Y + P) | Level 3.
  • Diving board: Find number of lengths possible using 2 lengths k times | O(2^k) | Level 2.
  • Diving board - optimized: Find number of lengths possible using 2 lengths k times | O(k) | Level 3.
  • XML encoding: Skipped, uses some predefined methods - refer random/practice/xml_encoding.py
  • Bisect squares: Skipped, not clear
  • Best line: Skipped code
  • Master mind: Given solution and guess for 4 slots of RGBY string, find hits and pseudo hits | O(n) | Level 2.
  • Sub sort: Find indices of array which needs to be sorted to make whole array sorted | O(N) | Level 3.
  • Largest sum of subarray: Given an unsorted array(+ve and -ve numbers), find max sum possible of a subarray | Kadane's algo | O(N) | Level 3.
  • Pattern matching: Skipped, not clear
  • Pond sizes: Given matrix having water(0) and land, find the size of ponds | O(MN) | Level 2.
  • T9 number to string: Skipped code
  • Sum swap: Find pair of elements from 2 given array to make sum of 2 arrays same | O(A + B) | Level 3.
  • Langton's Ant: Skipped code
  • Rand7 from rand5: Implement rand7 using rand5 | Level 3.
  • Pairs having given sum: Given an array and required sum, find pairs in array that sums to required sum | O(n) time and space | Level 2.
  • Pairs with sum - python: Find all pairs of integers with an array which sum to specified sum | O(N) | Level 2.
  • LRU cache impelementation: Put and Get operations implemented in LRU cache | Level 3.
  • Evaluate expression: Evaluate arithmetic expression(without parentheses) | O(N) | Level 3.

17. Hard

  • Add 2 numbers: Add 2 numbers without arithmatic operations | OlogN) | Level 2.
  • Shuffle cards: Given deck of cards, shuffle it | O(N) | Level 2.
  • Random set: Generate random set having m elements from an array having n elements | O(N) | Level 2.
  • Missing number: Skipped, not clear
  • Letters and numbers: Find longest subarry having same number of letters and numbers | O(N) | Level 3.
  • Count 2's: Skipped, not clear
  • Baby names: Get count of synonym names | O(B + P) | Level 3.
  • Circus tower: Given list of pair of words, find longest increasing sequence | O(nlogn) | Level 3.
  • Kth multiple - 3, 5 and 7: Find kth number such that the only factors are 3, 5 and 7 | O(k) | Level 3.
  • Majority element from array: Find majority(more than n/2 times) element from an array | Moore's voting algo | O(N) | Level 2.
  • Majority element from array - python: Find majority(more than n/2 times) element from an array | Moore's voting algo | O(N) | Level 2.
  • Word distance: Given list of words, find shortest distance b/w 2 given words | O(A + B) | Level 2.
  • Binary tree to doubly linked list: Convert a binary tree to doubly linked list | O(N) | Level 3.
  • Re-space: Add spaces in sentence to have min unrecognized chars | O(N^2) | Level 4.
  • Smallest K numbers: Given unsorted array find k smallest numbers | O(N) | Level 3.
  • Longest word: Given list of words, find longest word that can be found using other words | O(nlogn + L^2) | Level 3.
  • The masseuse: Given list of meetings, find max meeting minutes without taking any adjacent meetings | O(N) | Level 2.
  • The masseuse - space optimized: Given list of meetings, find max meeting minutes without taking any adjacent meetings | O(N) | Level 3.
  • Multi search: Given a string and list of smaller strings, search all smaller strings in bigger string - trie using dict | O(b^2 + kt) | Level 3.
  • Multi search - optimal: Given a string and list of smaller strings, search all smaller strings in bigger string | O(kt + bk) | Level 3.
  • Shortest supersequence: Find smallest subarray of bigger array having all elements of smaller array | O(SB^2) | Level 2.
  • Missing number: Given an array having numbers from 1 to N but one missing, find missing | O(N) | Level 2.
  • Missing 2 numbers: Given an array having numbers from 1 to N but 2 numbers missing, find missing numbers | O(N) | Level 2.
  • Track median, stream of numbers: Keep track of median from stream of numbers | O(logn) track and O(1) get median | Level 4.
  • Volume of histogram: Given set of histogram bars, find max water logged | O(N) | Level 3.
  • Word transform: Skipped, not clear
  • Max black square: Skipped, not clear
  • Max submatrix: Given NxN matrix having +ve and -ve numbers, find submtrix having max sum | O(N^6) | Level 2.
  • Word rectangle: Skipped code
  • Sparse similarity: Given list of documents, find similarity b/w pairs | O(D^2 * W) | Level 2.

Uncategorised

Other problems