Algorithms And Data Structures In Python

A guide to implement data structures, graph algorithms and sorting algorithms from scratch with interview questions!

Last updated 2022-01-10 | 4.5

- Understand arrays and linked lists
- Understand stacks and queues
- Understand tree like data structures (binary search trees)

What you'll learn

Understand arrays and linked lists
Understand stacks and queues
Understand tree like data structures (binary search trees)
Understand balances trees (AVL trees and red-black trees)
Understand heap data structures
Understand hashing
hash tables and dictionaries
Understand the differences between data structures and abstract data types
Understand graph traversing (BFS and DFS)
Understand shortest path algorithms such as Dijkstra's approach or Bellman-Ford method
Understand minimum spanning trees (Prims's algorithm)
Understand sorting algorithms
Be able to develop your own algorithms
Have a good grasp of algorithmic thinking
Be able to detect and correct inefficient code snippets

* Requirements

* Python basics
* Some theoretical background ( big O notation )

Description

  • Understand arrays and linked lists
  • Understand stacks and queues
  • Understand tree like data structures (binary search trees)
  • Understand balances trees (AVL trees and red-black trees)
  • Understand heap data structures
  • Understand hashing, hash tables and dictionaries
  • Understand the differences between data structures and abstract data types
  • Understand graph traversing (BFS and DFS)
  • Understand shortest path algorithms such as Dijkstra's approach or Bellman-Ford method
  • Understand minimum spanning trees (Prims's algorithm)
  • Understand sorting algorithms
  • Be able to develop your own algorithms
  • Have a good grasp of algorithmic thinking
  • Be able to detect and correct inefficient code snippets

Course content

30 sections • 216 lectures

Why to use data structures Preview 04:49

Data structures and abstract data types Preview 03:33

Data Structures and Abstract Data Types Quiz

Installing Python and PyCharm on Windows Preview 00:23

Installing Python and PyCharm on Mac Preview 00:20

What are array data structures? Preview 06:55

Arrays introduction - operations Preview 06:56

Arrays in Python Preview 08:04

What are real arrays in Python? Preview 03:55

Arrays Quiz

Reversing an array in-place overview Preview 00:11

Reversing an array in-place solution Preview 04:34

Palindrome problem overview Preview 00:08

Palindrome problem solution Preview 06:31

Integer reversion problem overview Preview 00:07

Integer reversion problem solution Preview 09:57

Anagram problem overview Preview 00:11

Anagram problem solution Preview 06:06

Dutch national flag problem overview Preview 00:10

Dutch national flag problem theory Preview 08:03

Dutch national flag problem solution Preview 04:40

Trapping rain water problem overview Preview 00:14

Trapping rain water problem theory Preview 13:34

Trapping rain water problem solution Preview 06:46

What are linked lists? Preview 04:53

Linked list introduction - operations Preview 11:03

Linked list implementation I Preview 07:45

Linked list implementation II Preview 04:20

Linked list implementation III Preview 08:27

Comparing linked lists and arrays Preview 06:26

Practical (real-world) applications of linked lists Preview 05:17

Linked Lists Quiz

What are doubly linked lists? Preview 06:59

Doubly linked list implementation Preview 08:11

Running time comparison: linked lists and arrays Preview 03:57

Doubly Linked Lists Quiz

Finding the middle node in a linked list overview Preview 00:05

Finding the middle node in a linked list solution Preview 05:28

Reverse a linked list in-place overview Preview 00:02

Reverse a linked list in-place solution Preview 06:52

What are stacks? Preview 04:35

Stacks in memory management (stacks and heaps ) Preview 03:44

Stack memory visualization Preview 06:19

Stack implementation Preview 08:41

Practical (real-world) applications of stacks Preview 03:56

Stack Quiz

What are queues? Preview 04:15

Queue implementation Preview 08:36

Queues Quiz

Max in a stack problem overview Preview 00:09

Max in a stack problem solution Preview 07:05

Queue with stack problem Preview 00:04

Queue with stack problem solution Preview 06:04

Queue with stack problem solution - recursion Preview 03:46

What are binary search trees? Preview 14:38

Binary search trees theory - search, insert Preview 07:55

Binary search trees theory - delete Preview 06:12

Binary search trees theory - in-order traversal Preview 05:28

Binary search trees theory - running times Preview 04:35

Binary search tree implementation I Preview 07:56

Binary Search Tree implementation II Preview 10:29

Stack memory visualization - finding max (min) items Preview 04:40

Stack memory visualization - tree traversal Preview 06:00

Binary Search Tree implementation III Preview 13:52

Practical (real-world) applications of trees Preview 03:06

Binary Search Trees Quiz

Compare binary trees overview Preview 00:08

Compare binary trees solution Preview 07:58

Motivation behind balanced binary search trees Preview 03:26

What are AVL trees? Preview 06:47

AVL trees introduction - height Preview 12:38

AVL trees introduction - rotations Preview 09:05

AVL trees introduction - illustration Preview 05:17

AVL tree implementation I Preview 09:47

AVL tree implementation II Preview 08:16

AVL tree implementation III Preview 12:05

AVL tree implementation IV Preview 07:51

AVL tree implementation V Preview 02:20

Practical (real-world) applications of balanced binary search trees Preview 03:40

AVL Trees Quiz

What are red-black trees? Preview 10:48

The logic behind red-black trees Preview 05:24

Red-black trees - recoloring and rotation cases Preview 09:25

Red-black tree illustrations Preview 07:33

Red-black tree implementation I Preview 06:51

Red-black tree implementation II Preview 05:33

Red-black tree implementation III Preview 09:57

Red-black tree implementation IV Preview 02:10

Differences between red-black tree and AVL trees Preview 02:46

Red-Black Trees Quiz

What are priority queues? Preview 04:31

Heap introduction - basics Preview 10:14

Heap introduction - array representation Preview 09:36

Heap introduction - remove operation Preview 07:12

Using heap data structure to sort (heapsort) Preview 06:25

Heap introduction - operations complexities Preview 05:05

Binomial and Fibonacci heaps Preview 04:17

Heap implementation I Preview 05:11

Heap implementation II Preview 10:18

Heap implementation III Preview 04:31

Heaps in Python Preview 03:56

Heaps Quiz

Interview question #1 - checking heap properties Preview 00:14

Interview question #1 - solution Preview 06:46

Interview question #2 - max heap to a min heap Preview 00:03

Interview question #2 - solution Preview 06:57

What are associative arrays? Preview 05:51

Hashtable introduction - basics Preview 11:25

Hashtable introduction - collisions Preview 11:19

Hashtable introduction - dynamic resizing Preview 07:08

Linear probing implementation I Preview 06:03

Linear probing implementation II Preview 06:27

Linear probing implementation III Preview 02:14

Dictionaires in Python Preview 03:40

Practical (real-world) applications of hashing Preview 06:31

Dictionaries Quiz

Graph theory overview Preview 06:45

Adjacency matrix and adjacency list Preview 07:58

Applications of graphs Preview 03:37

Graph Algorithms Overview Quiz

Breadth-first search introduction Preview 09:31

Breadth-first search implementation Preview 08:00

What are WebCrawlers (core of search engines)? Preview 05:49

WebCrawler basic implementation Preview 09:42

Depth-first search introduction Preview 10:22

Depth-first search implementation Preview 05:58

Depth-first search implementation II Preview 00:37

Memory management: BFS vs DFS Preview 05:23

Graph traversal quiz

Interview question #1 - implement DFS with recursion Preview 00:09

Interview question #1 - solution Preview 02:54

Depth-first search and stack memory visualisation Preview 06:01

Interview question #2 - using BFS to find way out of maze Preview 00:25

Interview question #2 - solution Preview 16:14

What is the shortest path problem? Preview 04:50

Dijkstra algorithm visualization Preview 11:04

Dijkstra algorithm implementation I - Edge, Node Preview 10:34

Dijkstra algorithm implementation II - algorithm Preview 13:58

Dijkstra algorithm implementation III - testing Preview 03:55

Dijktsra's algorithm with adjacency matrix representation Preview 12:10

Adjacency matrix representation implementation Preview 12:46

Shortest path algorithms applications Preview 05:08

What is the critical path method (CPM)? Preview 04:10

Dijkstra's Algorithm Quiz

What is the Bellman-Ford algorithm? Preview 13:41

Bellman-Ford algorithm visualization Preview 05:20

Bellman-Ford algorithm implementation I - Node, Edge Preview 01:38

Bellman-Ford algorithm implementation II - the algorithm Preview 07:46

Bellman-Ford algorithm implementation III - testing Preview 03:21

Greedy algorithm or dynamic programming approach? Preview 05:45

Bellman-Ford Algorithm Quiz

Interview question #1 - detecting negative cycles on the FOREX Preview 00:13

How to use Bellman-Ford algorithm on the FOREX? Preview 06:29

Interview question #1 - solution Preview 03:57

What is the disjoint set data structure? Preview 14:13

Disjoint sets visualization Preview 05:53

Kruskal's algorithm introduction Preview 10:08

Kruskal algorithm implementation I - basic classes Preview 06:28

Kruskal algorithm implementation II - disjoint set Preview 13:02

Kruskal algorithm implementation III - algorithm Preview 05:15

Kruskal algorithm implementation VI - testing Preview 03:25

Kruskal's Algorithm Quiz

What is the Prim-Jarnik algorithm? Preview 09:36

Prims-Jarnik algorithm implementation I Preview 10:26

Prims-Jarnik algorithm implementation II Preview 03:14

Comparing the spanning tree approaches Preview 02:08

Applications of spanning trees Preview 06:10

Prim's Algorithm Quiz

Sorting introduction Preview 07:36

Here is the article on the running time complexities of comparison based sorting algorithms:

http://people.seas.harvard.edu/~cs125/fall14/lec1.pdf

What is stability in sorting? Preview 06:09

What is adaptive sorting? Preview 03:14

Sorting Algorithms Basics Quiz

Bogo sort introduction Preview 03:14

Bogo sort implementation Preview 07:53

Bogo Sort Quiz

Bubble sort introduction Preview 05:27

Bubble sort implementation Preview 05:31

Selection sort introduction Preview 05:14

Selection sort implementation Preview 05:30

Selection Sort Quiz

Insertion sort introduction Preview 08:35

Insertion sort implementation Preview 05:23

Exercise - sorting custom objects with insertion sort Preview 00:10

Solution - sorting custom objects with insertion sort Preview 00:32

Insertion Sort Quiz

Shell sort introduction Preview 06:18

Shell sort implementation Preview 06:27

Shell Sort Quiz

Quicksort introduction Preview 12:15

Quicksort introduction - example Preview 07:41

Quicksort implementation Preview 11:36

Hoare's partitioning and Lomuto's partitioning Preview 00:44

What is the worst-case scenario for quicksort? Preview 07:20

QuickSort Quiz

Merge sort introduction Preview 08:17

Merge sort implementation Preview 08:22

Stack memory and merge sort visualization Preview 07:49

Merge Sort Quiz

Hybrid algorithms introduction Preview 06:09

Non-comparison based algorithms Preview 02:13

Counting sort introduction Preview 10:17

Counting sort implementation Preview 09:48

Radix sort introduction Preview 13:03

Radix sort implementation Preview 13:37

Measure running time differences Preview 00:35

Non-Comparison Based Sorting Quiz

Interview question #1 - implementing TimSort algorithm Preview 00:19

Interview question #1 - solution Preview 00:53

Interview question #2 - implement quicksort with iteration Preview 00:22

Interview question #2 - solution Preview 00:35

Interview question #3 - implementing selection sort with recursion Preview 00:09

Interview question #3 - solution Preview 00:55

Download course materials (slides and source code) Preview 00:00