Data Structures & Algorithms in Python

What you will be able to do

• Implement the core structures
• Traverse trees and graphs
• Solve dynamic programming problems

What you will learn

1. 6.1Linked Lists6 lessons

   Build, traverse, insert, delete, reverse and merge linked lists, find a middle or a cycle, and solve the classic interview problems.

   1. The Node Class: Build and Traverse25 min
   2. Insert and Delete28 min
   3. Reverse, Middle and Cycle Detection30 min
   4. Merge Lists and Classic Interview Problems32 min
   5. Linked Lists Checkpoint28 min
   6. Must-do problems: Linked Lists120 min
2. 6.2Stacks & Queues7 lessons

   Stacks with a list, bracket matching and expression evaluation, monotonic stacks, deque queues, and design problems.

   1. Stacks with a List: Push, Pop and Peek22 min
   2. Valid Brackets and Expression Evaluation26 min
   3. Monotonic Stack: Next Greater Element and Largest Rectangle28 min
   4. Queues with deque, and Why Not list.pop(0)26 min
   5. Queue with Stacks and Other Design Problems28 min
   6. Stacks and Queues Checkpoint28 min
   7. Must-do problems: Stacks and Queues120 min
3. 6.3Hash Tables from Scratch6 lessons

   Build a hash map from buckets, handle collisions, understand resizing and dict and set, and design an LRU cache.

   1. Hash Functions, Buckets and a Small Map26 min
   2. Collisions, Chaining and Probing26 min
   3. Resizing, Average Cost and How dict and set Relate26 min
   4. Design Problems and the LRU Cache30 min
   5. Hash Tables from Scratch Checkpoint28 min
   6. Must-do problems: Hash Tables from Scratch120 min
4. 6.4Sorting Algorithms7 lessons

   The simple sorts, merge sort, quick sort and quickselect, counting and bucket sort, and which one to choose in Python.

   1. Bubble, Selection and Insertion Sort28 min
   2. Merge Sort and Counting Inversions30 min
   3. Quick Sort, Partitioning and Quickselect32 min
   4. Counting Sort and Bucket Sort28 min
   5. Timsort and Choosing a Sort in Python26 min
   6. Sorting Algorithms Checkpoint28 min
   7. Must-do problems: Sorting Algorithms120 min
5. 6.5Binary Trees7 lessons

   Tree terms and input, the three traversals, level order, height, diameter and balance, paths and lowest common ancestor.

   1. Binary Tree Terms, TreeNode and Level-Order Input22 min
   2. Preorder, Inorder and Postorder Traversals26 min
   3. Level-Order Traversal with deque24 min
   4. Height, Diameter and Balance26 min
   5. Paths, Lowest Common Ancestor and Building from Traversals28 min
   6. Binary Trees Checkpoint28 min
   7. Must-do problems: Binary Trees120 min
6. 6.6Binary Search Trees7 lessons

   Search, insert, delete and validate a BST, answer kth smallest, floor, ceiling and range queries, and know when to use bisect.

   1. The BST Rule, Search and Insert28 min
   2. Delete a Key from a BST28 min
   3. Validate a BST and Sorted Output with Inorder30 min
   4. Kth Smallest, Floor, Ceiling and Range Queries32 min
   5. Balance, and Sorted Collections in Python30 min
   6. Binary Search Trees Checkpoint28 min
   7. Must-do problems: Binary Search Trees110 min
7. 6.7Heaps & Tries7 lessons

   Build a heap by hand, keep the best k and a running median, then store and search words with a trie.

   1. How a Heap Works: Sift Up and Sift Down28 min
   2. Top K, Merging Sorted Lists and Max Heaps28 min
   3. Running Median with Two Heaps26 min
   4. Tries: Insert and Search26 min
   5. Prefix Search and Word Problems28 min
   6. Heaps and Tries Checkpoint28 min
   7. Must-do problems: Heaps and Tries120 min
8. 6.8Graphs: Basics & Traversal7 lessons

   Adjacency lists, BFS and DFS, shortest paths by edges, components, grid islands and cycles.

   1. Graph Terms and Adjacency Lists22 min
   2. BFS and Shortest Path by Number of Edges26 min
   3. DFS: Recursive and Iterative24 min
   4. Connected Components and Grid Problems26 min
   5. Cycle Detection: Undirected and Directed26 min
   6. Graphs Basics Checkpoint28 min
   7. Must-do problems: Graphs Basics and Traversal130 min
9. 6.9Graph Algorithms7 lessons

   Topological sort, Union-Find, Dijkstra, Bellman-Ford, Floyd-Warshall, Kruskal and Prim.

   1. Topological Sort: Kahn and DFS28 min
   2. Union-Find with Path Compression28 min
   3. Dijkstra: Shortest Paths with heapq30 min
   4. Bellman-Ford and Floyd-Warshall in Brief26 min
   5. Minimum Spanning Tree: Kruskal and Prim28 min
   6. Graph Algorithms Checkpoint30 min
   7. Must-do problems: Graph Algorithms150 min
10. 6.10Greedy & Intervals6 lessons

    Greedy choices and counterexamples, activity selection, job sequencing, merging intervals, meeting rooms and reach problems.

    1. What Makes a Problem Greedy, and When Greedy Fails26 min
    2. Activity Selection and Job Sequencing28 min
    3. Merge Intervals, Insert Interval and Meeting Rooms28 min
    4. Jump Game, Gas Station and Reach Problems28 min
    5. Greedy and Intervals Checkpoint28 min
    6. Must-do problems: Greedy and Intervals120 min
11. 6.11Dynamic Programming (1D)7 lessons

    Turn slow recursion into memoization and tables: stairs, house robber, coin change, LIS, word break and decode ways.

    1. From Recursion to Memoization to a Table26 min
    2. Climbing Stairs, House Robber and Min Cost26 min
    3. Coin Change and Counting Ways28 min
    4. Longest Increasing Subsequence with bisect28 min
    5. Word Break and Decode Ways28 min
    6. Dynamic Programming 1D Checkpoint30 min
    7. Must-do problems: Dynamic Programming (1D)150 min
12. 6.12Dynamic Programming (2D)7 lessons

    Fill grids and tables for paths, knapsack, strings, intervals and bitmasks.

    1. Grid Paths and Minimum Path Sum28 min
    2. 0/1 Knapsack and Subset Sum30 min
    3. Longest Common Subsequence and Edit Distance30 min
    4. Palindrome and Interval DP30 min
    5. Bitmask DP in Brief24 min
    6. 2D Dynamic Programming Checkpoint30 min
    7. Must-do problems: 2D Dynamic Programming150 min