docs.md

Algorithms and Data Structures

Tree

Tree traversal (important)

• DFS, what is inorder, preorder, postorder traversal
• BFS
• DFS vs BFS
• DFS iteratively

Binary search tree (important)

• search and insertion
• read about deletion, other optional
• binary_search_trees (optional)

B-tree

• B-tree
• optional

2-3 tree

• general info, no code

AVL tree

• general info, no code
• optional

Red-Black tree

• Robert Sedgewick Princeton Algorithms Course 10 2 Red Black BSTs. Read 2-3 before!!! All other links are optional if you watch this video
• info
• link
• TreeMap
• Reb-Black tree implementation

Trie (or Prefix Tree) (important)

• info
• trie implementation

Suffix Tree (optional)

• decr
• wiki

Segment Tree or interval tree (optional)

• segment-tree-set

Binary indexed tree or fenwick tree (optional)

• fenwick-tree

Graph

General information (important)

• graph types
• graph representation

Graph Traversal (important)

• DFS in directed graph
• BFS in directed graph
• iterative DFS
• NonrecursiveDFS

Detect Cycle (important)

• detedct cycle with DFS + recStack
• DFS in directed graph with colors, same idea like in recStack above
• DFS in undirected graph

Topological Sorting (important)

• general info
• Khan algorithm
• DFS

Dijkstra Algorithm to find shortest path (important)

• good description
• implementation similar to Sedgewick’s
• Sedgewick implementation (optional)
• optional, Bellman-Ford shortest path algorithm

Eulerian path, Eulerian circuit (optional)

• euler_path
• eulerian-path-and-circuit
• other

Weighted graph

-EdgeWeightedGraph

Minimum Spanning Tree

• https://algs4.cs.princeton.edu/43mst/
• Prim’s algorithm
• Kruskal’s algorithm

Geo Index (optional)

• https://en.wikipedia.org/wiki/Spatial_database
• https://docs.mongodb.com/manual/geospatial-queries/
• https://en.wikipedia.org/wiki/R-tree

K-D Tree (optional)

• Robert Sedgewick course
• k-dimensional-tree

Union-Find

• http://algs4.cs.princeton.edu/15uf/
• https://algs4.cs.princeton.edu/15uf/WeightedQuickUnionUF.java.html
• http://www.geeksforgeeks.org/union-find/
• http://www.geeksforgeeks.org/union-find-algorithm-set-2-union-by-rank/

Hash Table

• https://algs4.cs.princeton.edu/34hash/
• https://algs4.cs.princeton.edu/34hash/SeparateChainingHashST.java.html

Heap

• https://habrahabr.ru/post/112222/

Strings

Minimum Edit distance (Levenshtein Distance)

• https://en.wikipedia.org/wiki/Edit_distance
• https://web.stanford.edu/class/cs124/lec/med.pdf
• https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance
• https://people.cs.pitt.edu/~kirk/cs1501/Pruhs/Spring2006/assignments/editdistance/Levenshtein%20Distance.htm
• https://www.youtube.com/watch?v=We3YDTzNXEk

Maze

• Diff approaches
• Sedgewick
• implementation

Arrays

Dutch flag problem

• http://www.geeksforgeeks.org/sort-an-array-of-0s-1s-and-2s/
• https://en.wikipedia.org/wiki/Dutch_national_flag_problem

Quick Selection

• https://en.wikipedia.org/wiki/Quickselect

Quick Sort

• http://www.geeksforgeeks.org/quick-sort/
• https://algs4.cs.princeton.edu/23quicksort/
• https://github.com/Semaserg/LeetCodeProblems/blob/master/design/QuickSort/QuickSort.java

Merge sort

• http://www.geeksforgeeks.org/merge-sort/

Insertion sort

• http://www.geeksforgeeks.org/insertion-sort/

Dynamic Programming

Increasing subsequence

• https://habrahabr.ru/post/113108/

Knapsack problem

• https://neerc.ifmo.ru/wiki/index.php? - title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D1%80%D1%8E%D0%BA%D0%B7%D0%B0%D0%BA%D0%B5
• http://www.geeksforgeeks.org/knapsack-problem/
• https://www.youtube.com/watch?v=8LusJS5-AGo&list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr

Math

Permutation vs combination

• https://www.mathplanet.com/education/algebra-2/discrete-mathematics-and-probability/permutations-and-combinations
• https://discuss.leetcode.com/topic/46162/a-general-approach-to-backtracking-questions-in-java-subsets-permutations-combination-sum-palindrome-partioning

Concurrency(Java)

• http://docs.oracle.com/javase/tutorial/essential/concurrency/procthread.html
• https://stackoverflow.com/questions/18202388/how-to-use-invokeall-to-let-all-thread-pool-do-their-task
• http://www.baeldung.com/java-executor-service-tutorial
• https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ConcurrentHashMap.html
• https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/atomic/package-summary.html
• https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/atomic/AtomicInteger.html

Future, ExecutorService, Callable

• http://winterbe.com/posts/2015/04/07/java8-concurrency-tutorial-thread-executor-examples/
• https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/Future.html
• https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/Callable.html

Links

• LeetCodeProblems
• google-interview