Common_DS_Algo_Tasks
Common Tasks in Data Structures & Algorithms Problems
In Data Structures and Algorithms (DS&A) problems, especially in programming interviews or competitive programming, there are several common tasks or patterns that you can expect to encounter. Here's a list of some of the most common ones:
Hashmap Usage
- Description: Leveraging hashmaps (or dictionaries) for fast lookups, counting, or mapping relationships between elements.
- Example: Finding the frequency of elements in an array.
Two Pointers Technique
- Description: Using two pointers to traverse an array or linked list to find a pair of elements that meet certain criteria.
- Example: Finding a pair of numbers that sum up to a target value.
2D Array Iteration
- Description: Iterating over two-dimensional arrays (matrices), which can involve variations like row-wise, column-wise, or diagonal traversal.
- Example: Rotating a matrix, traversing a grid to find a path.
Binary Search
- Description: Applying binary search on sorted arrays or using it as a technique to optimize solutions related to searching or optimization.
- Example: Finding the first or last position of an element in a sorted array.
Depth-First Search (DFS) and Breadth-First Search (BFS)
- Description: Traversing trees or graphs using DFS or BFS to explore nodes or find paths.
- Example: Checking if a path exists between two nodes in a graph.
Dynamic Programming
- Description: Solving problems by breaking them down into overlapping subproblems, storing the results of subproblems to avoid redundant computations.
- Example: Finding the longest common subsequence, solving the knapsack problem.
Recursion
- Description: Solving problems where a function calls itself as a subroutine, often used in divide and conquer algorithms.
- Example: Implementing quicksort or mergesort, solving puzzles like the Tower of Hanoi.
Sliding Window
- Description: Using a window that slides over the data to consider subsets of data at a time, often used in array/string problems.
- Example: Finding the longest substring with unique characters.
Greedy Algorithms
- Description: Building up a solution piece by piece, always choosing the next piece that offers the most immediate benefit.
- Example: Coin change problem, activity selection.
Backtracking
- Description: An algorithmic-technique for solving recursive problems by trying to build a solution incrementally and removing solutions that fail to satisfy the constraints of the problem at any point of time.
- Example: Solving the N-Queens problem, finding all permutations of a string.
Understanding these tasks and patterns is key to solving DS&A problems efficiently.