coding_patterns_brief

Question 1

Sliding Window

Answer 1

Handle input data in a specific window size

Question 2

Islands (Matrix Traversal) /Matrices

Answer 2

Matrix Traversing (2D Array)

Question 3

Two Pointers

Answer 3

iterate input data , pointers move in opposite direction

Question 4

Fast & Slow Pointers

Answer 4

Two Pointers to traverse the input data at different speeds

Question 5

Merge Intervals

Answer 5

Overlaping Intervals

Question 6

Cyclic Sort

Answer 6

Solve array problems where the input datra lies within a fixed range

Question 7

In-place Reversal of a LinkedList

Answer 7

reverse a linkedlist without using extra memory

Question 8

Tree Breadth-First Search

Answer 8

traverse a tree, each level fully

Question 9

Tree Depth First Search

Answer 9

traverse a tree, going down child nodes until the end and then go back up

Question 10

Two Heaps

Answer 10

In many problems, we are given a set of elements that can be divided into two parts. We are interested in knowing the smallest element in one part and the biggest element in the other part. Uses a Min-Heap to find the smallest element and a Max Heap to find the biggest element

Question 11

Subsets

Answer 11

Permutations or Combinations of a set elements

Question 12

Modified Binary Search

Answer 12

Search a sorted set of elements efficiently

Question 13

Bitwise XOR / Bitwise Manipulation

Answer 13

Bit manipulations

Question 14

Top ‘K’ Elements

Answer 14

Find the top/smallest/frequent ‘K’ elements in a set

Question 15

K-way Merge

Answer 15

Solve problems that involve a list of sorted array

Question 16

Topological Sort

Answer 16

Find a linear ordering of elements that have dependencies on each other

Question 17

0/1 Knapsack

Answer 17

Used to solve optimization problems. Use this technique to select elements that give maximum profit from a given set with limitation on capacity and that each element can only be picked once

Question 18

Fibonacci Numbers

Answer 18

Solve problems that follow the fibonacci numbers

Question 19

Palindromic Subsequence

Answer 19

This techniew is used to solve optimization problems related to palindromic sequences or strings

Question 20

Longest Common Substring

Answer 20

Use this technique to find the optimal part of a string/sequence or set of strings/sequences

Question 21

Stacks

Answer 21

Use this technique if you want to get elements out in the reverse order in which you inserted them (LIFO)

Question 22

Hash Maps

Answer 22

Use this when repeated fast access to data during the exection of algorithm. If you need to store the releationship between two sets of data in order to compute the required result. This is achieved through the mechanism of a key-value pair, where we stored the hashed version of the key to enable fast look-ups.

Question 23

Knowing What To Track

Answer 23

problem seems hard with a naive approach of at least
O(n2) time complexity, if not worse. Yet, on careful inspection, we realize that there are certain key characteristics of the input data that, if tracked, allow us to solve the problem far more efficiently

Generally speaking, this approach is worth trying when we are required to choose from a fixed set of possibilities: Yes / No, True / False, Valid / Invalid, Player 1 / Player 2.

Key characteristics could include the frequency of characters in a string, the pattern of generation of a sequence of permutations, or the implications of a given move in a game like tic-tac-toe or chess.

Question 24

Greedy Techniques

Answer 24

if selecting a series of local optima allows us to construct or identify the globally optimum solution.

Question 25

Graphs

Answer 25

There is a network of interconnected objects with some relationship between them; that is, the data can be represented as a graph.

Question 26

Custom Data Structures

Answer 26

The problem requires customizing an existing data structure, that is, adding a feature to it or modifying an existing feature. Examples include min stack and maximum frequency stack.

The problem requires combining one or more data structures to solve the problem efficiently. An example would be implementing an LRU cache.

Question 27

Backtracking

Answer 27

While constructing any single candidate solution, all paths must be explored. This means that if exploring a certain path results in a dead end, we need to move back one level and explore all the other paths in the solution space.
Example: Determine whether an undirected graph can be colored using no more than
n colors in such a way that no two adjacent vertices share the same color.

The problem requires us to consider all feasible solutions in order to select the best one. While solving such a problem, not a single feasible solution may be ignored. In certain problems, even if some feasible solutions are eventually discarded, we still need to find and evaluate them.
Example: Select elements from an array of strings and concatenate them, such that the concatenated string is of the maximum possible length and contains unique characters.

The problem requires us to compile a list of all feasible solutions.
Example: Partition a given string into substrings so that each substring is a palindrome. We need to determine all possible ways in which the partitioning can be done to obtain palindromic substrings.

Question 28

Trie

Answer 28

We need to compare two strings to detect partial matches, based on the initial characters of one or both strings.

We wish to optimize the space used to store a dictionary of words. Storing shared prefixes once allows for significant savings

Question 29

Dynamic Programming

Answer 29

Overlapping subproblems, that is, we can use the results of one subproblem when solving another, possibly larger subproblem.

Optimal substructure, that is, if the final solution can be constructed from the optimal solutions to its subproblems.

Question 30

Union Find

Answer 30

The problem requires arranging elements with a certain property into groups, or, to use graph terminology, into connected components.

We have been given a problem that contains elements represented as separate sets initially where we have to combine pairs of sets or find whether two elements belong to the same set or not.

The problem data is best organized in the form of a graph, yet the data has not been provided in the form of an adjacency list/matrix.