Before finding a solution

1) Make sure to understand the problem by listing:

2) Draw examples


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:

  1. a and b do not overlap
  2. a and b overlap, b ends after a
  3. a completely overlaps b
  4. a and b overlap, a ends after b
  5. b completely overlaps a
  6. a and b do no overlap
  7. a and b are equals


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

2 different ways:


Divide and conquer algorithm paradigm

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

Example with merge sort:

  1. Split the array into two halves
  2. Sort them (recursive call)
  3. Merge the two halves


How to name a matrix indexes

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


If stucked on a problem


In place definition

Mutates an input


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?


Solving optimization problems


Stable property

Preserve the original order of elements with equal key


What do to after having designed a solution

Testing on nominal cases then edge cases

Time and space complexity