The second part on my quick revision on data structures and algorithms, this one focuses on algorithms.

### Design techniques

Based off of 1:

- Examplify: write specific examples of the problem and derive a general rule from them.
- Some times it helps to start with an intermediate state of the problem e.g. 3.6 in 1. Don't forget to check the edge cases (i=0 and i=n) at the end anyway.

- Pattern matching: is it a variation of a known algo? or can you use the same technique?
**Simplify**and generalize: change a constraint to make the problem easier, solve and then generalize- E.g. in 18.7 of 1 assume a word can be created by 2 words and not n

- Base case and build: start from a base case (e.g. n = 1) and build next solutions from it. 2 variants here: top down or bottom up.
- Brainstorm: with data structures
- Bonus: Brainstorm with complexities: if you know already the desired complexity of the solution, think of an algo that has the same complexity

#### Tips

- Pre-processing: instead of doing everything in one go (which could be n^2), consider pre-processing first, e.g.
- sorting input first
- construct an "efficient" data structure (depending on the problem e.g. heap/tree/hashmap etc) and then act on it with lookups/insertions etc.
- Split in 2 or more tasks that are running sequentially: the total complexity will the worst of the 2.
- e.g. generate sequences and then evaluate them e.g. in Palantir interview.

- Time vs space tradeoff: you can improve time by using up more space and vice versa. Usually we care more about time but check with the interviewer.
- Runner up pointer technique: "offset" the second pointer by a certain amount or have it move twice (or as much as needed) as fast
`fast = fast.next.next;`

, for example used in palindromes, rotated lists, segregating arrays

### Recursion vs DP vs divide and conquer

Note: the terms are usually used ambiguously.

- Recursion is simply the act of calling the same function.
- I find it's more bottom-up than top-down e.g. in trees although you start from the root, it's when you reach a leaf (where the answer is trivial) that you start bubbling up the answer.
- Every recursive solution (if) can be coded as an iteration (for/while), which might be more space efficient - see part I for a note on tail optimization.
- When writing recursive functions note the ending conditional and the base calculation (besides what is being returned and the input like with any method)
- A limitation (with Java at least) is that you can't return multiple values (unless with a wrapper object or static "globals")

- Dynamic programming is solving problems with overlapping subproblems by solving each sub-problem only
**once**. 5 - If a problem can be solved by combining optimal solutions to non-overlapping sub-problems, the strategy is called "divide and conquer" instead. This is why merge sort and quick sort are not classified as dynamic programming problems. 6

TODO: gather also from chapter 11 of Algorithms in a nutshell

## Types of problems

- Check if a condition exists
- Output is true or false. Examples:
- Return
**an**example or all:- Return the pair in the k-Sum example or all pairs.
- Return all sequences.

- Optimization problem: longest/shortest subarray
- Usually DP

- Duplicates/uniques
- rotations: 1.8, 11.3
- palindromes: 1 2.7,
- anagrams (or permutations for strings): 1 1.3,11.2
- permutations/combinations: detect them, find where they occur, compute all etc

### Specific to data-structures

- Strings
- On string problems (e.g. longest palindrome Leet 5) order usually matters (so you can't pre-sort for example)
- Think of precomputed dicts (e.g. unique characters of string 1.1 in Ctci)
- Lookup many (small) strings in one: build a suffix tree 18.8 in Ctci
- Lookup a String in a big text? Rabin-karp 6.13 in Epi

- Arrays:
- k-sum with variations (k-diff, using 2, 3, 4 numbers), detect if there is a pair, return the pairs. Array can be sorted or not. Youtube from Google, CTci 17.12
- 2 pointers technique e.g. Dutch flag

- LinkedList
- 2 pointers technique: 2.2 k-th, 2.6 loop, 2.7 palindrome check.
- Recursive algorithms, almost the same as in Trees/Graphs that are represented by objects and pointers.
- Check: Singly or doubly linked? Do we know the size?

## Resources

- Algorithms in a nutshell, Edition 1 and 2nd in PDF, Github repo, check Java/Python code folders
- Clevercoder and here
- Toptal
- Interviewbit
- Programcreek
- Codility
- Algorithms in a nutshell version 2: https://doc.lagout.org/science/0_Computer%20Science/2_Algorithms/Algorithms%20in%20a%20Nutshell%20%282nd%20ed.%29%20%5BHeineman%2C%20Pollice%20%26%20Selkow%202015-11-25%5D%20%28draft%29.pdf