# General

## Before finding a solution

1) Make sure to understand the problem by listing:

- Inputs
- Outputs (what do we search)
- Constraints

2) Draw examples

#general

## Comparator implementation to order two integers

Ordering, min-heap: (a, b) -> a - b

Reverse ordering, max-heap: (a, b) -> b - a

#general #heap

## Different ways for two intervals to relate to each other

7 ways:

- a and b do not overlap
- a and b overlap, b ends after a
- a completely overlaps b
- a and b overlap, a ends after b
- b completely overlaps a
- a and b do no overlap
- a and b are equals

#general

## Different ways for two intervals to relate to each other if ordered by start then end

2 different ways:

- No overlap
- Overlap // Merge intervals (start of the first interval, max of the two ends)

#general

## Divide and conquer algorithm paradigm

- Divide: break a given problem into subproblems of same type
- Conquer: recursively solve these subproblems
- Combine: combine the answers to solve the initial problem

Example with merge sort:

- Split the array into two halves
- Sort them (recursive call)
- Merge the two halves

#general

## How to name a matrix indexes

Use m[row][col] instead of m[y][x]

#general

## If stucked on a problem

- Start with the smallest and easiest problem (e.g. 2 elements) and build a solution for that. Then, add elements and see if we can find a common pattern
- Greedy method
- Traversal technique

#general

## In place definition

Mutates an input

#general

## P vs NP problems

P (polynomial): set of problems that can be solved reasonably fast (example: multiplication, sorting, etc.)

Complexity is not exponential

NP (non-deterministic polynomial): set of problems where given a solution, we can test is it is a correct one in a reasonable amount of time but finding the solution is not fast (example: a 1M*1M sudoku grid, traveling salesman problem, etc)

NP-complete: hardest problems in the NP set

There are other sets of problems that are not P nor NP as an answer is really hard to prove (example: best move in a chess game)

P = NP means does being able to quickly recognize correct answers means thereâ€™s also a quick way to find them?

#general

## Solving optimization problems

- Greedy method
- Dynamic programming (memoization or tabulation)
- Branch and bound (minimization problem only)

#general

## Stable property

Preserve the original order of elements with equal key

#general

## What do to after having designed a solution

Testing on nominal cases then edge cases

Time and space complexity

#general