Algorithms And Data Structures In Python (Interview Q&A)

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

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
This course is about data structures, algorithms and graphs. We are going to implement the problems in Python programming language. I highly recommend typing out these data structures and algorithms several times on your own in order to get a good grasp of it.So what are you going to learn in this course?Section 1:setting up the environmentdifferences between data structures and abstract data typesSection 2 - Arrays:what is an array data structurearrays related interview questionsSection 3 - Linked Lists:linked list data structure and its implementationdoubly linked listslinked lists related interview questionsSection 4 - Stacks and Queues:stacks and queuesstack memory and heap memoryhow the stack memory works exactly?stacks and queues related interview questionsSection 5 - Binary Search Trees:what are binary search treespractical applications of binary search treesproblems with binary treesSection 6 - Balanced Binary Trees (AVL Trees and Red-Black Trees):why to use balanced binary search treesAVL treesred-black treesSection 7 - Priority Queues and Heaps:what are priority queueswhat are heapsheapsort algorithm overviewSection 8 - Hashing and Dictionaries:associative arrays and dictionarieshow to achieve O(1) constant running time with hashingSection 9 - Graph Traversal:basic graph algorithmsbreadth-firstdepth-first searchstack memory visualization for DFSSection 10 - Shortest Path problems (Dijkstra's and Bellman-Ford Algorithms):shortest path algorithmsDijkstra's algorithmBellman-Ford algorithmhow to detect arbitrage opportunities on the FOREX?Section 11 - Spanning Trees (Kruskal's and Prim's Approaches):what are spanning treeswhat is the union-find data structure and how to use itKruskal's algorithm theory and implementation as wellPrim's algorithmSection 12 - Substring Search Algorithmswhat are substring search algorithms and why are they important in real world softwaresbrute-force substring search algorithmhashing and Rabin-Karp methodKnuth-Morris-Pratt substring search algorithmZ substring search algorithm (Z algorithm)implementations in PythonSection 13 - Hamiltonian Cycles (Travelling Salesman Problem)Hamiltonian cycles in graphswhat is the travelling salesman problem?how to use backtracking to solve the problemmeta-heuristic approaches to boost algorithmsSection 14 - Sorting Algorithmssorting algorithmsbubble sort, selection sort and insertion sortquicksort and merge sortnon-comparison based sorting algorithmscounting sort and radix sortSection 15 - Algorithms Analysishow to measure the running time of algorithmsrunning time analysis with big O (ordo), big Ω (omega) and big θ (theta) notationscomplexity classespolynomial (P) and non-deterministic polynomial (NP) algorithmsO(1), O(logN), O(N) and several other running time complexitiesIn the first part of the course we are going to learn about basic data structures such as linked lists, stacks, queues, binary search trees, heaps and some advanced ones such as AVL trees and red-black trees.. The second part will be about graph algorithms such as spanning trees, shortest path algorithms and graph traversing. We will try to optimize each data structure as much as possible.In each chapter I am going to talk about the theoretical background of each algorithm or data structure, then we are going to write the code step by step in Python.Most of the advanced algorithms relies heavily on these topics so it is definitely worth understanding the basics. These principles can be used in several fields: in investment banking, artificial intelligence or electronic trading algorithms on the stock market. Research institutes use Python as a programming language in the main: there are a lot of library available for the public from machine learning to complex networks.Thanks for joining the course, let's get started!

Overview

Section 1: Introduction

Lecture 1 Introduction

Lecture 2 Complexity theory basics

Section 2: Installation and Environment Setup

Lecture 3 Installing Python and PyCharm on Windows

Lecture 4 Installing Python and PyCharm on Mac

Section 3: ### DATA STRUCTURES ###

Lecture 5 Why do we need data structures?

Lecture 6 Data structures and abstract data types

Section 4: Data Structures - Arrays

Lecture 7 What are array data structures?

Lecture 8 Arrays introduction - operations

Lecture 9 Arrays in Python

Lecture 10 What are real arrays in Python?

Section 5: Interview Questions - (Arrays)

Lecture 11 Reversing an array in-place overview

Lecture 12 Reversing an array in-place solution

Lecture 13 Palindrome problem overview

Lecture 14 Palindrome problem solution

Lecture 15 Integer reversion problem overview

Lecture 16 Integer reversion problem solution

Lecture 17 Anagram problem overview

Lecture 18 Anagram problem solution

Lecture 19 Dutch national flag problem overview

Lecture 20 Dutch national flag problem theory

Lecture 21 Dutch national flag problem solution

Lecture 22 Trapping rain water problem overview

Lecture 23 Trapping rain water problem theory

Lecture 24 Trapping rain water problem solution

Section 6: Data Structures - Linked Lists

Lecture 25 What are linked lists?

Lecture 26 Linked list introduction - operations

Lecture 27 Linked list implementation I

Lecture 28 Linked list implementation II

Lecture 29 Linked list implementation III

Lecture 30 Revisiting remove operation

Lecture 31 Comparing linked lists and arrays

Lecture 32 Practical (real-world) applications of linked lists

Section 7: Data Structures - Doubly Linked Lists

Lecture 33 What are doubly linked lists?

Lecture 34 Doubly linked list implementation

Lecture 35 Running time comparison: linked lists and arrays

Section 8: Interview Questions (Linked Lists)

Lecture 36 Finding the middle node in a linked list overview

Lecture 37 Finding the middle node in a linked list solution

Lecture 38 Reverse a linked list in-place overview

Lecture 39 Reverse a linked list in-place solution

Section 9: Data Structures - Stacks

Lecture 40 What are stacks?

Lecture 41 Stacks in memory management (stacks and heaps)

Lecture 42 Stack memory visualization

Lecture 43 Stack implementation

Lecture 44 Practical (real-world) applications of stacks

Section 10: Data Structures - Queues

Lecture 45 What are queues?

Lecture 46 Queue implementation

Section 11: Interview Questions (Stacks and Queues)

Lecture 47 Max in a stack problem overview

Lecture 48 Max in a stack problem solution

Lecture 49 Queue with stack problem

Lecture 50 Queue with stack problem solution

Lecture 51 Queue with stack problem solution - recursion

Section 12: Data Structures - Binary Search Trees

Lecture 52 What are binary search trees?

Lecture 53 Binary search trees theory - search, insert

Lecture 54 Binary search trees theory - delete

Lecture 55 Binary search trees theory - in-order traversal

Lecture 56 Binary search trees theory - running times

Lecture 57 Binary search tree implementation I

Lecture 58 Binary search tree implementation II

Lecture 59 Stack memory visualization - finding max (min) items

Lecture 60 Stack memory visualization - tree traversal

Lecture 61 Binary search tree implementation III - remove operation

Lecture 62 Practical (real-world) applications of trees

Section 13: Interview Questions (Binary Search Trees)

Lecture 63 Compare binary trees overview

Lecture 64 Compare binary trees solution

Section 14: Data Structures - AVL Trees

Lecture 65 Motivation behind balanced binary search trees

Lecture 66 What are AVL trees?

Lecture 67 AVL trees introduction - height

Lecture 68 AVL trees introduction - rotations

Lecture 69 AVL trees introduction - illustration

Lecture 70 AVL tree implementation I

Lecture 71 AVL tree implementation II

Lecture 72 AVL tree implementation III

Lecture 73 AVL tree implementation IV

Lecture 74 AVL tree implementation V

Lecture 75 Practical (real-world) applications of balanced binary search trees

Section 15: Data Structures - Red-Black Trees

Lecture 76 What are red-black trees?

Lecture 77 The logic behind red-black trees

Lecture 78 Red-black trees - recoloring and rotation cases

Lecture 79 Red-black tree illustrations

Lecture 80 Red-black tree implementation I

Lecture 81 Red-black tree implementation II

Lecture 82 Red-black tree implementation III

Lecture 83 Red-black tree implementation IV

Lecture 84 Differences between red-black tree and AVL trees

Section 16: Data Structures - Heaps

Lecture 85 What are priority queues?

Lecture 86 Heap introduction - basics

Lecture 87 Heap introduction - array representation

Lecture 88 Heap introduction - remove operation

Lecture 89 Using heap data structure to sort (heapsort)

Lecture 90 Heap introduction - operations complexities

Lecture 91 Binomial and Fibonacci heaps

Lecture 92 Heap implementation I

Lecture 93 Heap implementation II

Lecture 94 Heap implementation III

Lecture 95 Heaps in Python

Section 17: Interview Questions (Heaps)

Lecture 96 Interview question #1 - checking heap properties

Lecture 97 Interview question #1 - solution

Lecture 98 Interview question #2 - max heap to a min heap

Lecture 99 Interview question #2 - solution

Section 18: Data Structures - Associative Arrays (Dictionaries)

Lecture 100 What are associative arrays?

Lecture 101 Hashtable introduction - basics

Lecture 102 Hashtable introduction - collisions

Lecture 103 Hashtable introduction - dynamic resizing

Lecture 104 Linear probing implementation I

Lecture 105 Linear probing implementation II

Lecture 106 Linear probing implementation III

Lecture 107 Dictionaires in Python

Lecture 108 Why to use prime numbers in hashing?

Lecture 109 Practical (real-world) applications of hashing

Section 19: ### GRAPH ALGORITHMS ###

Lecture 110 Graph theory overview

Lecture 111 Adjacency matrix and adjacency list

Lecture 112 Applications of graphs

Section 20: Graph Algorithms - Graph Traversal Algorithms

Lecture 113 Breadth-first search introduction

Lecture 114 Breadth-first search implementation

Lecture 115 What are WebCrawlers (core of search engines)?

Lecture 116 WebCrawler basic implementation

Lecture 117 Depth-first search introduction

Lecture 118 Depth-first search implementation

Lecture 119 Depth-first search implementation II

Lecture 120 Memory management: BFS vs DFS

Section 21: Interview Questions (Graph Traversal)

Lecture 121 Interview question #1 - implement DFS with recursion

Lecture 122 Interview question #1 - solution

Lecture 123 Depth-first search and stack memory visualisation

Lecture 124 Interview question #2 - using BFS to find way out of maze

Lecture 125 Interview question #2 - solution

Section 22: Graph Algorithms - Shortest Paths with Dijkstra's Algorithm

Lecture 126 What is the shortest path problem?

Lecture 127 Dijkstra algorithm visualization

Lecture 128 Dijkstra algorithm implementation I - Edge, Node

Lecture 129 Dijkstra algorithm implementation II - algorithm

Lecture 130 Dijkstra algorithm implementation III - testing

Lecture 131 Dijktsra's algorithm with adjacency matrix representation

Lecture 132 Adjacency matrix representation implementation

Lecture 133 Shortest path algorithms applications

Lecture 134 What is the critical path method (CPM)?

Section 23: Graph Algorithms - Shortest Paths with Bellman-Ford Algorithm

Lecture 135 What is the Bellman-Ford algorithm?

Lecture 136 Bellman-Ford algorithm visualization

Lecture 137 Bellman-Ford algorithm implementation I - Node, Edge

Lecture 138 Bellman-Ford algorithm implementation II - the algorithm

Lecture 139 Bellman-Ford algorithm implementation III - testing

Lecture 140 Greedy algorithm or dynamic programming approach?

Section 24: Interview Questions (Shortest Paths)

Lecture 141 Interview question #1 - detecting negative cycles on the FOREX

Lecture 142 How to use Bellman-Ford algorithm on the FOREX?

Lecture 143 Interview question #1 - solution

Section 25: Graph Algorithms - Spanning Trees with Kruskal Algorithm

Lecture 144 What is the disjoint set data structure?

Lecture 145 Disjoint sets visualization

Lecture 146 Kruskal's algorithm introduction

Lecture 147 Kruskal algorithm implementation I - basic classes

Lecture 148 Kruskal algorithm implementation II - disjoint set

Lecture 149 Kruskal algorithm implementation III - algorithm

Lecture 150 Kruskal algorithm implementation VI - testing

Section 26: Graph Algorithms - Spanning Trees with Prims Algorithm

Lecture 151 What is the Prim-Jarnik algorithm?

Lecture 152 Prims-Jarnik algorithm implementation I

Lecture 153 Prims-Jarnik algorithm implementation II

Lecture 154 Comparing the spanning tree approaches

Lecture 155 Applications of spanning trees

Section 27: Hamiltonian Cycles - Travelling Salesman Problem

Lecture 156 What are Hamiltonian cycles?

Lecture 157 The travelling salesman problem

Lecture 158 Travelling salesman problem implementation

Lecture 159 TSP and stack memory visualization

Lecture 160 Why to use meta-heuristics?

Section 28: ### SUBSTRING SEARCH ALGORITHMS ###

Lecture 161 Brute-force search introduction

Lecture 162 Brute-force substring search algorithm implementation

Lecture 163 Rabin-Karp algorithm introduction

Lecture 164 Rabin-Karp algorithm implementation

Lecture 165 Knuth-Morris-Pratt algorithm introduction

Lecture 166 Constructing the partial match table - visualization

Lecture 167 Knuth-Morris-Pratt algorithm implementation

Lecture 168 Z algorithm introduction

Lecture 169 Z algorithm illustration

Lecture 170 Z algorithm implementation

Lecture 171 Substring search algorithms comparison

Lecture 172 Applications of substring search

Section 29: ### SORTING ALGORITHMS ###

Lecture 173 Sorting introduction

Lecture 174 What is stability in sorting?

Lecture 175 What is adaptive sorting?

Lecture 176 Bogo sort introduction

Lecture 177 Bogo sort implementation

Lecture 178 Bubble sort introduction

Lecture 179 Bubble sort implementation

Lecture 180 Selection sort introduction

Lecture 181 Selection sort implementation

Lecture 182 Insertion sort introduction

Lecture 183 Insertion sort implementation

Lecture 184 Exercise - sorting custom objects with insertion sort

Lecture 185 Solution - sorting custom objects with insertion sort

Lecture 186 Shell sort introduction

Lecture 187 Shell sort implementation

Lecture 188 Quicksort introduction

Lecture 189 Quicksort introduction - example

Lecture 190 Quicksort implementation

Lecture 191 Hoare's partitioning and Lomuto's partitioning

Lecture 192 What is the worst-case scenario for quicksort?

Lecture 193 Merge sort introduction

Lecture 194 Merge sort implementation

Lecture 195 Stack memory and merge sort visualization

Lecture 196 Hybrid algorithms introduction

Lecture 197 Non-comparison based algorithms

Lecture 198 Counting sort introduction

Lecture 199 Counting sort implementation

Lecture 200 Radix sort introduction

Lecture 201 Radix sort implementation

Lecture 202 Measure running time differences

Section 30: Interview Questions (Sorting)

Lecture 203 Interview question #1 - implementing TimSort algorithm

Lecture 204 Interview question #1 - solution

Lecture 205 Interview question #2 - implement quicksort with iteration

Lecture 206 Interview question #2 - solution

Lecture 207 Interview question #3 - implementing selection sort with recursion

Lecture 208 Interview question #3 - solution

Section 31: ### APPENDIX - COMPLEXITY THEORY CRASH COURSE ###

Lecture 209 How to measure the running times of algorithms?

Lecture 210 Complexity theory illustration

Lecture 211 Complexity notations - big (O) ordo

Lecture 212 Complexity notations - big Ω (omega)

Lecture 213 Complexity notations - big (θ) theta

Lecture 214 Algorithm running times

Lecture 215 Complexity classes

Lecture 216 Analysis of algorithms - loops

Section 32: Next Steps

Lecture 217 Next steps

Section 33: Course Materials (DOWNLOADS)

Lecture 218 Download course materials (slides and source code)

Beginner Python developers curious about graphs, algorithms and data structures