The second part on my quick revision on data structures and algorithms, this one focuses on algorithms.
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
- 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
- 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
- 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
- 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
- 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?
- Algorithms in a nutshell, Edition 1 and 2nd in PDF, Github repo, check Java/Python code folders
- Clevercoder and here
- 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