classic-algo

A collection of the classic algorithms and data structures implemented on java

• Binary Search Algorithm, tests.

  • exactIndex, the first occurrence of a target in an array, if it is present. If the target is not present, it returns the position where the value can be inserted.
  • indexRightMost, the last occurrence of a target (right most index) in an array, if it is present. If the target is not present, it returns the previous position where the value should be inserted.
  • indexIfFound, the first occurrence of the target (left most index) in the array, if it is present. If the target is not present, it returns -1;

• Binary Search Tree (BST).

• Binary tree traversals:

  • Recursive
    • inorder
    • preorder
    • postorder
  • Iterative
    • inorder
    • preorder
    • postorder
      • 2 stacks
      • 1 stack
    • bfs using queue
    • bfs by levels using queue

• Binary Indexed Tree (BIT, Fenwick Tree) for calculating prefix/range cumulative operations in O(logn) time complexity (tests).

• Graph represented by a 2d array (tests):

  • Iterative BFS that returns a parent array for finding paths from any node to the starting point (root).
  • Getting path to a root
  • Shortest path
  • Connected components
  • Recursive DFS

• Topological Sort

  • Topological Sort
  • All possible topological sort sequences using backtracking

• Max-Heap

• Partitioning:

  • QuickSelect is a selection algorithm to find the kth smallest element in an unordered list. It is related to the quicksort sorting algorithm.
  • QuickSort
  • Three Way Partitioning (Dutch national flag problem).

• Segment Tree (updating and querying the data in log(n) time, tests):

  • build
  • query
  • update
  • query range

• Trie (Prefix Tree) with the insert, search, and startsWith methods, tests.

• Backtracking (for generating subsets, permutations, solving sudoku, etc.).

• CycleSort and searching all cycles (groups) in a permutation findCycles and tests

• 0/1 Knapsack and tests

• Intervals:

  • Insert and merge an interval into a sorted list of the non-overlapping intervals, tests.
  • Find all free slots between (overlapping) intervals, tests.
  • Merge overlapped intervals, tests

Other code templates, see here.