Skip to main content

Algo + DS

Algorithms​

  1. Union-Find Algorithm

    • Dynamic Connectivity

    • Quick Find

    • Quick Union

    • Improvements

      • Weighted Quick Union

      • Weighted Quick Union with Path Compression

  2. Analysis of algorithms

    • Scientific Method of Analysis

    • Empirical Method of Analysis

  3. Stacks and Queues

    • Stacks

    • Resizing Arrays

    • Queues

    • Deque

    • Randomized Queues

  4. Elementary Sort

    • Selection Sort

    • Insertion Sort

    • Shell Sort

    • Shuffling

      • Shuffle Sort

      • Knuth Shuffle

    • Convex Hull

  5. Merge Sort

    • Bottom up mergesort

  6. Quick Sort

    • Quick Select (Selection)

    • 3- way partition quicksort (Duplicate Keys)

    • System sorts

  7. Priority Queues

    • Binary heaps

    • Heap sort

  8. Elementary Symbol Tables

    • Elementary Implementations

Sorted array (Binary Search)

Unordered List (Sequential Search)

  1. Ordered Operations

  2. Binary Search Trees

  3. Ordered Operations in BSTs

  4. Deletion in BSTs

  5. Balanced Search Trees

    • 2-3 Search Trees

    • Red-Black Trees

    • B-Trees

  6. Geometric applications of BST

  • 1d Range Search

  • Line Segment Intersection

  • Kd-Trees

  • Interval Search Trees

  • Rectangle Intersection

  1. Hash Tables

  • Uniform Hashing Assumption

  • Separate Chaining

  • Linear Probing

  1. Symbol Table Applications

  • Sets

  • Dictionary Clients

  • Indexing Clients

  • Sparse Vectors

Data Structures​

  1. Undirected Graphs

    • Implementation

      • Adjacency Matrix

      • Adjacency List

    • DFS

    • BFS

    • Connected Components

  2. Directed Graphs

    • Topological Sort

      • Topological order of an acyclic digraph

    • Strongly Connected Components

      • Kosaraju-Sharir algorithm for computing strong components of a digraph

  3. Minimum Spanning Trees

    • Kruskal's Algorithm

    • Prim's Algorithm

  4. Shortest Path

    • Dijkstra's Algorithm

    • Bellman Ford Algorithm (Negative Weights)

  5. Maximum Flow and Minimum Cut

    • Ford-Fulkerson Algorithm

  6. Radix Sorts

    • Key-Indexed Counting

    • LSD Radix Sort

    • MSD Radix Sort

    • 3-way Radix Quicksort

    • Suffix Arrays

  7. Tries

    • R-way Tries

    • Ternary Search Tries

  8. Substring Search

    • KMP (Knuth-Morris-Pratt)

    • Boyer-Moore

    • Rabin-Karp

  9. Regular Expressions

    • DFA

    • NFA

  10. Data Compression

  • Run Length Encoding

  • Huffman Compression

  • LZW Compression

  • Burrows-Wheeler

  1. Reductions

  2. Linear Programming

  • Brewer's Problem

  • Simplex Algorithm

  1. Intractability

  • P

  • NP

  • NP-Complete

Strategies for algorithms​

  1. B.U.D. (Bottleneck, Unnecessary work, Duplicated work)

  2. Space / Time Tradeoffs

Resources​

  1. Coursera - Algorithms Part 1

  2. Coursera - Algorithms Part 2

https://www.toptal.com/algorithms/interview-questions

Most Important Algos / DS / Programming Concepts​

  1. Depth first search

  2. Breadth first search

  3. Matching parenthesis

  4. Hash Tables

  5. Variables / Pointer manipulations

  6. Reversing a linked list

  7. Sorting fundamentals

  8. Recursion

  9. Custom data structures (suffix tree)

  10. Binary search

BUD Optimization Strategy​

  • Bottlenecks
  • Unnecessary work
  • Duplicated work

https://4tee-learn.blogspot.com/2017/12/optimisation-technique-15-bud.html

Questions to asking when solving a coding interview questions​

  1. What is the data types of the inputs?

    • Can we assume the string is ASCII or Unicode?

  2. Do we have to worry about load factors?

  3. Do we have to validate inputs?

  4. Can we assume this fits in memory?

  5. Can we use additional data structures?

https://www.freecodecamp.org/news/learn-algorithms-and-data-structures-in-python

MIT 6.006 Introduction to Algorithms, Fall 2011

https://github.com/MisterBooo/LeetCodeAnimation