thesarfo

Reference

Pattern Recognition Cheatsheet

Common hints in problem statements that point toward specific algorithms or data structures.

views 0

Common hints in problem statements that often indicate the potential use of specific algorithms:

  1. “Find the shortest path”: This often points towards graph algorithms like Dijkstra’s algorithm for weighted graphs or Breadth-First Search (BFS) for unweighted graphs.
  2. “Traverse all the nodes/vertices”: This hints at graph traversal algorithms such as Depth-First Search (DFS) or Breadth-First Search (BFS).
  3. “Maximum/minimum”: These keywords can suggest the use of dynamic programming or algorithms like Kadane’s algorithm for finding the maximum subarray sum.
  4. “Permutation/combination”: Problems involving permutations or combinations might be solved using backtracking or recursion.
  5. “Sort the array”: This implies sorting algorithms like QuickSort, MergeSort, or even the built-in sorting functions in the language being used.
  6. “Subset/Subsequence”: Problems that deal with subsets or subsequences often involve dynamic programming or backtracking approaches.
  7. “Tree-related operations”: Keywords like “Binary Tree,” “BST,” or “Heap” often hint towards tree-based algorithms such as tree traversal (in-order, pre-order, post-order), balancing, or heap operations (heapify, heap sort).
  8. “Pattern matching” or “String matching”: These problems might involve algorithms like KMP (Knuth-Morris-Pratt), Rabin-Karp, or regular expressions.
  9. “Optimization” or “Maximize/Minimize”: These can suggest the use of greedy algorithms, dynamic programming, or linear programming techniques.
  10. “Connected components” or “Strongly connected components”: These terms often lead to graph-related algorithms like Tarjan’s algorithm or Kosaraju’s algorithm.
  11. “Find the intersection”: This term suggests the use of the set data structure.
  12. Counting, Occurrences: These terms can be solved with Hashing.
  13. “Solve with O(log n) runtime”: Binary search.
  14. “Sorted Array”: Two pointers.
  15. “Subarray/Substring”: Sliding Window.
  16. “Detect cycle”: Fast and Slow pointers.
  17. If you notice a pattern where the answer is valid until a certain point and invalid after a certain point, you can use a binary search on answers.