/algoPrep

Solving some odd problems in style.

Primary LanguageC++

algoPrep

DS Algo

List of solved problems.

Resource

1. Sliding window

The Sliding Window pattern is used to perform a required operation on a specific window size of a given array or linked list. Sliding Windows start from the 1st element and keep shifting right by one element and adjust the length of the window according to the problem that you are solving. In some cases, the window size remains constant and in other cases the sizes grows or shrinks.

Used when: The problem input is a linear data structure such as a linked list, array, or string You’re asked to find the longest/shortest substring, subarray, or a desired value Common problems you use the sliding window pattern with:

  1. Maximum sum subarray of size ‘K’ (easy)
  2. Longest substring with ‘K’ distinct characters (medium)
  3. String anagrams (hard)

2. Two pointer

Two Pointers is a pattern where two pointers iterate through the data structure in tandem until one or both of the pointers hit a certain condition.Two Pointers is often useful when searching pairs in a sorted array or linked list

Used when: It will feature problems where you deal with sorted arrays (or Linked Lists) and need to find a set of elements that fulfill certain constraints The set of elements in the array is a pair, a triplet, or even a subarray Here are some problems that feature the Two Pointer pattern:

  1. Squaring a sorted array (easy)
  2. Triplets that sum to zero (medium)
  3. Comparing strings that contain backspaces (medium)

3. Modified Binary Search

Whenever you are given a sorted array, linked list, or matrix, and are asked to find a certain element, the best algorithm you can use is the Binary Search. This pattern describes an efficient way to handle all problems involving Binary Search.

Used when:

4. Dynamic Programming

About 25% of all SRM problems have the "Dynamic Programming" category tag. The DP problems are popular among problemsetters because each DP problem is original in some sense and you have to think hard to invent the solution for it. Since dynamic programming is so popular, it is perhaps the most important method to master in algorithm competitions.

Goal is to fix the overlapping problem of not recalculating states.

  1. Memoization (Top Down): The memoized program for a problem is similar to the recursive version with a small modification that looks into a lookup table before computing solutions. We initialize a lookup array with all initial values as NIL. Whenever we need the solution to a subproblem, we first look into the lookup table. If the precomputed value is there then we return that value, otherwise, we calculate the value and put the result in the lookup table so that it can be reused later.
  2. Tabulation (Bottom Up): The tabulated program for a given problem builds a table in bottom-up fashion and returns the last entry from the table. For example, for the same Fibonacci number, we first calculate fib(0) then fib(1) then fib(2) then fib(3), and so on. So literally, we are building the solutions of subproblems bottom-up.

Optimal Substructure: A given problems has Optimal Substructure Property if optimal solution of the given problem can be obtained by using optimal solutions of its subproblems.

5. Uses of DS.

- ## Map
  - To count occurences of elements
  - To count if element is repeated in given length string. mp.size and string length compare

6. Code snippet of implementations