Learn Data Structures and Algorithms in Python with Visualizations

#Data Structures #Algorithms #Python #Big O Notation #Recursion #Interview Prep #Programming
💬 Chat with this Video
Ask anything about this video…
Learn data structures and algorithms in Python in this beginner's course. It covers arrays, linked lists, stacks, queues, hash tables, trees, heaps, and graphs, plus recursion, searching, sorting, and interview prep. Each topic is explained with custom animations and visualizations alongside Python code examples. >> This is a complete course on data structures and algorithms in Python. We go step by step and we start from zero. Why this course? Because many people learn algorithms by memorizing code and then they forget it after a week. Here we do it differently. Every idea is animated, so you can see the memory, the pointers, the calls, and every step of every algorithm. I made this course visual so you can really understand it and not only memorize it. And every number that you hear in this course comes from code that I really run, so you can run it too and get the same result. And why Python? Because Python is clean and it's less as focus on the idea and not on the syntax. But we will not stay on the surface. We will look inside the Python list, the dictionary, and the set, and we will see how they really work. We will first build the structures ourselves and then we will use the tools that [snorts] Python already has. What will you learn? We start with big O, the language that we use the measure to speed of a program. Then we study arrays and linked list and we see how data really lives in memory. After that, stacks and queues and hash tables, which make searching very fast. Then trees, heaps, and graphs and structures behind maps, schedules, and social networks. Then searching and sorting. And at the end, the patterns that interviews ask again and again and how to sing in a coding interview. What do you need? Only the basics of Python, variables, loops, functions and lists. You don't need a computer science degree. You don't need to be good at math. My advice is simple. Watch a video, then pause and type the code yourself. Do a little every day. This is better than a lot in one day. If a topic is hard, watch it again. Everybody needs a second time for recursion and graphs and that is normal. By the end of this course, you will understand how the most important data structures work inside and you will know when to use each one. So open your editor and let's begin. Big O part one. How to measure a program? Here's a simple question. You have two programs and both give the correct answer. Which one is better? Maybe you will say the faster one. But faster on which computer? And with how much data? A program can be fast on my laptop and slow on your phone. So we need a way to measure a program that doesn't depend on the computer. The way is to count the steps and to ask one question. When the input grows, how do the steps grow? This is big O. It doesn't give us seconds. It give us the shape of the grows. Let's let's see the first three shapes from the best one. The first shape is constant time written O of one. The number of steps doesn't depend on the input. The basic example is the index of a list. When you write of 500,000, Python goes directly to that place in memory. It doesn't matter if the list has 10 elements or 1 million. It's always one step. The second shape is linear time, written O n. The steps grow together with the input. Let's search for a number in a list with a loop. In the worst case, the number is at the end and we check array element. I counted the steps. For 10 elements, 10 steps. For 1,000 elements, 1,000 steps. For 1 million elements, 1 million steps. 10 times more data, 10 times more steps. On a graph, this is a straight line. The search shape is a beautiful one, logarithmic time, written O log n. Think about a paper dictionary. You open it in the middle and you throw away half of the book. Then half of the rest and half again. This is binary search and it works only a sorted list. I counted the steps in the worst case. For 10 elements, four steps. For 1,000 elements, 10 steps. For 1 million elements, only 20 steps. 1 million elements and only 20 steps. On a graph, the line is almost flat. Every time the data becomes two times bigger, we add only one step. So now we know three shapes, constant, logarithmic, and linear. All three are good and we are happy to see them. In the next video, we will meet the dangerous shapes. Big O part two, the dangerous shapes and the rules. Welcome back. In the last video, we met the three good shapes, constant, logarithmic, and linear. Now let's meet the other three and then we will learn the rules. The fourth shape is O n log n. This is the cost of a good sorting algorithm. For 1,000 elements, it's about 10,000 steps. It is a little more than linear and much less than the next shape. You will see it again in the sorting section. The fifth shape is a dangerous one, quadratic time, written of and squared. It happens when we have a loop inside the loop. For every element we visit all the elements. Let's look at the code. We have a list and the outer loop takes one element at a time. For each one the inner loops go through the whole list again. I counted the steps for 10 elements 100 steps, for 100 elements 10,000 steps, for 1,000 elements 1 million steps, 10 times more data and 100 times more steps. On a graph the line goes up like a wall. So when you see a loop inside a loop you should stop and ask, do I really need this? The sixth shape is worst, exponential time, written of two to the n. Every new element doubles the work. A good example is the recursive Fibonacci that we will meet in the recursive recursion section. I counted the function calls for the number 10 177 calls, for 20 21,891 calls, for 32 million 692,537 calls. Only 30 and almost 3 million calls. Another example is all the subsets of a set. With 20 elements there are 1 million 48,576 subsets. With 30 elements more than 1 billion. With this shape even a small input is too big. Now we have all six shapes from the best to the worst, constant, logarithmic, linear, n log n, quadratic, and exponential. If you remember only one thing remember this order. Let's compare them with the same input, 1,000 elements. Constant one step, logarithmic 10 steps, linear one step 1,000 steps, N log N, about 10,000 steps. Quadratic, 1 million steps. Exponential and number with more than 300 digits. can feel the difference. the rules. practice, don't count every step exactly. simplify and there are three rules. Rule number one, we drop the constants. If a loop makes two steps for every element, we have two N steps. But for big O, two N is just O of N. Why? Because when the data grows, the shape is the same, a straight line. [snorts] Also three loops one after another are three N and this is still O of N. But be careful, a loop inside loop is not the same. Loops one after another we add. Loops inside each other we multiply. Rule two. We keep only the biggest part. Imagine a function with a nested loop and after it a simply loop. The steps are N squared plus N. For 1,000 elements this is 1 million plus 1,000. The small part is only a tiny piece of the total. So so write we write O of N squared and we forget the rest. Rule three. We think about the worst case. When we search for a number, maybe we are lucky in the and we find it in the worst first step. But big O asks, what is the worst that can happen? It is the case when the number is at the end or not there at all. This is a promise that we can trust. Let's repeat the rule rules. One, drop the constants. Two, keep the biggest part. Three, think about the worst case. And let's try one example. A function has a simple loop over the list and after it a loop inside the loop. The first part is a N steps. The second part is a N squared steps. Together N plus N squared. We keep the biggest part and the answer is O n squared. That's all. With these trailer rules, you can look at almost any code and say it's big O in a few seconds. And this is the language that we will use in every section of this course. Now you can measure a program and you are ready for the first data structures. It's the array and it is the next. Arrays, part one. How data lives in memory. Section two, arrays. Before we study arrays, we need to see where the data really lives. The memory of your computer is a long row of small cells. Every cell has its own number and this number is called the address. Our program uses three addresses to find the data. An array is the simplest idea in this world. It is a group of elements and they are stored one next to the other with no gaps. Imagine that our array starts at the address 1,000. If every element takes four bytes, the first element lives at 1,000. The second lives at 1,004. The third lives at 1,008. You can see the pattern. To find the address of any element, we use one simple formula. The start address plus the index times the size of one element. Now think about what this means. We want the element with the index 500,000. We don't walk through the list. We don't count the elements. We make one multiplication, one addition, and we jump directly to that place. It takes the same time for the index zero and for the index 500,000. This is why reading by index of n of one. And this is the superpower of an array. Now a small and important detail about Python. A Python list is an array, but there is one difference. A list doesn't keep the values inside the cells. It keeps the references. And every reference is a pointer to the real object. I checked the size in Python and empty empty list takes 56 bytes. A list with 10 elements takes 136 bytes. The difference is 80 bytes and this is 80 bytes for every element. 8 bytes is exactly the same size of one pointer on a modern computer. So the cells of a Python list have the same size and the formula still works. This is why lists can keep a number, a string, and another list together. Every cell is just a pointer of the same same size. Let's remember three things. First, an array is a row of elements in memory one next to the other. Second, we find any any elements with a simple formula. So reading by index or of one. Third, a Python list keeps pointer and every pointer takes 8 bytes. In the next video, we will see what happens when we add and remove elements and why one operation is cheap and another one is expensive. Arrays part two, adding, removing, and searching. Welcome back. In the last video, we saw that reading by index is fast. Now let's see what happens when we change the list. We start with the most common operation, append, adding an element at the end. Imagine a list with four elements. The memory has free space after the last element. So Python just writes the new one there. One step, so append is cheap. But what happens when there is no free space? Python asks the computer for a bigger block of memory and moves the element there. Then it's add the new element. Let's watch this in real code. I create an empty list and I add elements one by one. After each append I checked how many cells in the last list has reserved. This number is called the capacity. The empty list has zero cells. After the first append the capacity jumps to four. After the fifth element it becomes eight. After the ninth 16. After the 17th 24. Then 32 40 50 52 64 and 76. Do you see the idea? Python doesn't ask for a new block every time. It reserves extra space and the list grows a little more each time. So how many times did the list resize? For 1,000 appends only 29 times. For 1 million appends only 87 times. That's why we say that append is of one on average. Most of appends are cheap and the expensive ones are rare. [snorts] Now the second operation, inserting at the beginning. We have a list with five elements and we want to put a new element at the index zero. But the index zero is already taken. So every element must move one place to the right. First the last one. Then the one before it and so on until we make a free place. Only then we write the new element. For five elements five moves. For 1,000 elements 1,000 moves. The number of moves grows together with the size of the list. So this is of n. The same happens in the middle of the list. We move only the elements that are after the place. But in the worst case this is still of n. Now the opposite operation, removing. The method pop without argument removes the last element. Nothing needs to move. So it is of one. But pop of zero removes the first element and now all the other elements must move one place to the left to close the gap. This is again O N. So the position matter a lot. The end of the list is cheap. The beginning is expensive. If you need to remove elements from the beginning many times, a list is not the best choice. We will see a better structure for this in the quiz sections. Next, searching. Python gives us the word in and the method index. But inside they do the same thing as our loop from the first video. They check the elements one by one. In the worst case the element is at the end or it is not there and we check all of them. So searching in a normal list is O N. If the list is sorted we can do better and we will use binary search in the searching section. Now slicing. When we write X from two to five, Python creates a new list. It copies the elements. So the time is proportional to the size of the slice. The original list doesn't change. But be careful with a simple assignment. If I write Y equals X, there is no copy. Both names point to the same list. I added an element to Y and when I when I printed X the element was there too. It is the same list with the two names. If you need a real copy use a slice or the method copy. And the last trap which is classic one, a list of lists. Let's create a grid with three rows and three columns with the code list of zero times three and then times three again. Now let's change the first cell of the first row. I printed the grid and look, the first cell changed every row. Why? Because the outer multiplication doesn' create three lists. It copies the same pointer three times. All three rows are the same list. The correct way is a loop inside the brackets, a list comprehension, which creates a new row every time. I run it and now only the first row change as we wanted. Let's summarize the cost. Reading by index O of one. Append and pop at the end O of one on average. Insert and remove at the beginning or in the middle of n. Searching in an unsorted list of n. An array is perfect when we read a lot and add at the end. But when we insert in the middle again and again, we pay a high price. Can we find a structure where inserting is cheap? Yes, and this is the linked list, the topic of the next section. Linked list part one, the node and the pointer. Section three, linked list. In the last section, we saw the problem of the array. All the elements live in one block, one next to the other. So when we insert at the beginning, everything must move. Now let's imagine a different idea. What if the elements don't need to live next to each other? What if every element can live in any place of the memory? But then how do we find the next one? The answer is simple. Every element keeps the address of the next element. This small package is called a node. A node has two parts. The first part is a value, for example, the number 10. The second part is the pointer to the next node. Let's write this in Python. We create a class node. In the constructor, we save the value and we create the field next, which is none at the start. None means there is nothing after me. Now let's create three nodes, 10, 20, and 30. Each one lives alone in its own place in memory. Then we connect them. The next of the first node points to the second. The next of the second node points to the third. The third node keeps known because it's in the last one. Now we have a chain, but where does the chain start? We need one more variable and we call it head. The head points to the first node. If we lose the head, we lose the whole list. So the head is the only door in the list. How do we read all the elements? So we start from the head and we write a loop. While the current node is not known, we print its value and we move to the next node. I ran this code. The output is 10, 20, 30, and the loop made three steps. Now think about the array. In the array, the index 500,000 is one formula. Here is the no formula. We cannot We cannot jump into the middle because we don't not know the address. We must start from the head and follow the arrows one by one. I create a list with 1 million nodes and I counted the hops to the node with the index 500,000. It took exactly 500,000 hops. So reading by index in linked list is O of N. This is the price of this structure. But what do we get for this price? In the next video, we will see the superpower of the linked list, inserting and removing without moving anything. Linked list part two, insert, remove, and the doubly linked list. Welcome back. In the last video, we built a chain of nodes and we solved the price. Reading by Reading by index is O of N. Now let's see what we get for this price. Imagine a list with three nodes, 10, 20, and 30. We want to insert 15 between 10 and 20. In a in an array, we will move everything to the right. Here, we do not move anything. First, we create a new node with the value 15. Second, the next of the new node points to 20. Third, the next of 10 points to the new node. That's all. Two pointers change and no element moved. I run this code and the list became 10, 15, 20, 30. The order is important. If we change the next of 10 first, we lose the address of 20 and the rest of the list is gone. So, first we connect the new node to the future and only then we connect the past to the new node. Now the most interesting case, insert at the beginning. We create a new node, its next point to the old head, and the head now points to the new node. Two steps. I create a list with 1 million nodes and I inserted a new element at the beginning. It took it took two pointer change. The array has to move 1 million elements for the same operation. So in the insert at the head is of one. Now remove. We want to delete 15. We stand on the node before it, which is 10. We say the next of 10 is now the next of 15. The arrow jumps over 15 and nobody points to the to it anymore. Python sees this and cleans the memory by itself. I run this code and the list is is again 10, 20, 30. Again, one pointer change and nothing moved. But wait. There is a catch. To stand one the node before, we must find it and finding means walking from the head. I created a list with 1 million nodes and I walked to the last one. It took exactly 1 million hops. So insert at the end is also of n because we must walk to the end. How do we how do we fix this? We keep one more variable and we call it tail. The tail always points to the last one, last node. Now insert at the end is simple. The next of the tail points to the new node and the tail moves to the new node one step so of one. Let's summarize. If we already stand on the right node insert and remove cost of one. If you must find the node first the walking cost of n. So the real superpower is not the insert itself but the fact that nothing moves. Now there is another problem. In the list we have now we can move only forward. If we stand on a node we cannot go back and to remove a node we need the node before it. The solution is a double linked list. Here every node has two pointers next and also prev the previous node. Now we can walk in the both directions and if we have a node we can remove it right away because the node itself knows its its neighbors. The previous node points to the next one and the next next one points back to the previous one. The pointers on each side but still of one. This is why real system like it so much but everything has a price. I measured the memory for 1 million elements. The array of integer took about 40 megabytes. The linked list with the same number took about 120 megabytes, three times more. Every node is a separate object with a pointer plus all this overhead. And the double linked list took about 128 megabytes because of the second pointer. Also the node live in different place of the memory so the processor love them less than the array where everything is next to each other. So when do we use which one? If we read by index often, we use an array. If we insert and remove at the beginning or in the middle and we already know the place, we use the linked list. Reading by index, the array is O of one. The linked list is O of n. Insert at the beginning, the array is O of n. The linked list is O of one. Search by value, both are O of n. Remember these tables because the interviewers love to ask about it. In the next section, we will use this idea to build a very simple but very powerful structure, the stack. Stacks, part one. The last one in is the first one out. Section four, stacks. In the last section, we built chains of nodes and we inserted and removed at the beginning in one step. Now we will use this idea to build a very simple structure and you already know it from your life. Imagine a pile of plates in the kitchen. You put a new plate on the top and when you need a plate, you take it from the top. You never take a plate from the bottom because the whole pile will fall. This is exactly a a stack. A stack is a collection where we add and remove elements only at one end and this end is called the top. The the last element we put is in is the first element we take out. The rule has a name, LIFO, which means last in, first out. A stack has only three main operation. The first operation is push. We put a new element on the top. The second operation is pop. We remove the element from the top and we get it back. The third operation is pick. We only look at the top element and we do not remove it. Let's see this in Python. We don't need a new class because the Python list is already very good stack. We create an empty list and we call it stack. Push is the method append. We push 10 then 20 then 30. I run this code and the stack is 10 20 30 and the top is 30. Pick is the last element with the index minus one. The result is 30. Pop is the method pop. I call it uh it return 30 and the stack became 10 20. The next two pops return 20 and 10 and now the stack is empty. What if we pop from an empty stack? Python raise an error index error. Pop from empty list. So in real programs we first check that the stack is not empty. Now the most important question how fast is it? We never touch the element in the middle and we never move anything. Push pop and pick are all O of one. This is why the stack is so popular. It's very simple and it's very fast. In the next video we'll see where a stack lives in the real world and we will solve the classic problem with them. Stacks part two. Where stacks live and the balanced brackets. Welcome back. In the last video we learned the stacks push pop and pick all in one O of one. Now let's see where stack leave in the real world. The first example is the undo button. You type some text and every change goes on the top of stack. When you press undo the program pops the last change and cancel it. The last action is the first one to be canceled exactly like LIFO. Last in first out. The second example is the back back button in your browser. Every page you open goes on the stack. When you press back the browser pops the current page and shows the [snorts] one under it. The third example is is the most important one and you use it in every program, the call stack. When a function calls another function, Python puts a new frame on the top of stack. This frame keeps the variable of that calls and the place where to return. When the function finishes, Python pops the frame and goes back to the previous one. So the function that started last is always the first one to finish. Now, what happens if a function calls itself forever? The stack grows and grows and the memory is not infinite. So Python has a limit and I checked it, 1,000 frames. I wrote a function that calls itself without stopping. Python stopped it with an error, recursion error, maximum recursion depth exceeded. This is a stack overflow and now you know why it happens. We will come back to this in section about recursion. Now let's solve a classic problem with the stack. We have a text with bracket round round squared and curly. We must check that the bracket are balanced. Every opening bracket must have a closing bracket of the same type and in the right order. For example, round round square closing closing square curly closing curly closing round, this is correct. But round square closing round closing square, this is wrong because the round bracket close before the square one. How can a stack help us? The last the last bracket we open must be the first one to close and this is exactly LIFO. So here's the idea. We go through the text character by character. If the character is an opening bracket, we push it on the stack. If the character is a closing bracket, we pop the top of the stack and we check that it is the same type. If it is not the same the text is wrong. At the end, the stack must be empty. Let's write this in Python. We create an empty list and a small dictionary. For every closing bracket, it keeps the opening bracket that fits. Then we write a loop over the characters. If the character is an opening bracket, we we use append. If it's a closing bracket, first we check that the stack is not empty because a closing bracket without an opening one is already a mistake. Then we pop and we compare it with the dictionary. If it is different, we return false. After the loop, we return true only if the stack is empty. I ran this code on four texts. The text round square closing square curly closing curly closing round gave true. The next round square closing round closing square gave false. The text with two opening round bracket gave false because the stack was not empty at the end. And the text with two closing round bracket gave false because the stack was empty too early. Let's watch the stack in the first example. Round goes in. The stack has one bracket. Square goes in. Now there are two. Closing square comes. We pop the square and it fits. Curly goes in. Then closing curly takes it out. The last one is the closing round. We pop the round bracket and the stack is empty. How fast is it? We visit every character one time and every push and pop is O of one. So the wall check is O of n. Let's remember three things. Firstly, a stack is LIFO and push pop and pick are O of one. Second stacks leaving the undo button in the back button and in the call stack of every program. Third, when you see a problem about nested or matching things, think about the stack. In the next section we will see the cousin of the stack where the first one in is the first one out, the queue. Queues, the first one in is the first one out. Section five queues. In the last section we learn the stack. The last element in is the first element out. Now let's see its cousin and the rule here is the opposite. Imagine a line in a coffee shop. The first person who came is the first person who gets the coffee. New people join the line at the back and the service happen at the front. This is a queue. The rule has a name FIFO, which means first in, first out. A queue has three main operations. The first one is en queue. We add a new element at the back. The second one is de queue. We remove the element from the front and we get it back. The third one is peek. We only look at the front element. Now let's see this in Python. Here we have a trap. A Python list can work is a queue. Append adds at the back and pop is the index zero removes from the front. I run this code and it works. The first element came out first. But remember the section about arrays. When we remove the first element, all other elements must move one step to the left. I create a list with 1 million elements and I removed 1,000 elements from the front. On my computer is took about four tenths of a seconds. So de queue from a list is of one of n. And this is bad. Python has a better tool and it lives in the module collection. It is called deque. Deque is a double ended queue and it is built for fast work and both ends. We create it and we add elements with append. We remove from the front with the method pop left. I added 10, 20 and 30 then I called pop left and I got 10 and the queue became 20 30. Now the same test, 1 million elements and 1,000 removals from the front. For the deque it took less than a tens of milliseconds, thousand of times faster than the list. So enqueue and dequeue in the deque are both O of one. The rule is simple. When you need a queue in Python do don't use a list, use a deque. Now let's see where a queue queues live in the real world. The first example is a printer. 10 people send documents to their printer and the printer prints them in the same order. So the first document is printed first. The second example is the support line. When you write to the support your ticket goes to the back of the line and the agent takes the tickets from the front. The third example is a big one, message queues in the backend. One program puts a task in the queue, for example send an email. Another program takes the task from the front and dot them one by one. So the first program doesn't wait and the second program doesn't lose any task. And the operating system also uses queues to decide which program will use the processor next. Everywhere where [clears throat] fairness is important you will find a queue. Now let's solve a classic problem with a queue, the way out of maze. I made a small maze 5 by 5 cells. The letter C, the letter S is the start and it is in the top left corner. The letter E is the exit and it is in the bottom right corner. Some cells are walls and we cannot go through them. We want to find the shortest way from S to E. Here is the idea and it is called breadth first search. We start this queue and we put the start cell inside. Then we repeat one simple step. We take the first cell from the front of the queue. We look at its neighbors, up, down, left, and right. If neighbor is not a wall and we didn't visit it before, we mark it as visited and we put it at the back of the queue. Now think about what happens. First we visit visit the start, then all the cells at the distance one. Then all the cells at the distance two, then three and so on. It looks like a wave on the water. The waves goes from the start in all direction one ring at a time. The queue keeps this order for us because the cell that were added earlier are closer to the start and they leave the queue earlier. So the first time we reach the exit, we are sure this is the shortest way. Let's write this in Python. We import deque from collections. We create a queue and we put a pair in it, the start cell and the distance zero. We also create a set and we call it seen to remember the visited cells. Then while the queue is not empty, we take the first element with pop left. If the cell is the exit, we return the distance. Otherwise we go through four directions. For [snorts] every neighbor we check three things. It is inside the maze, it is not a wall and it's not in the set seen. If all is good, we add the neighbor to the set and we put it in the queue with the distance plus one. I ran this code on our maze. It returned eight. The shortest way from S to E is eight steps. And to find it, the program took 14 cells out of the queue. Why do we need this this set scene? Without it, the program would visit the same cell again and again, and it can run forever. How fast is it? Every cell enters the queue only one time. And for every cell, we check for neighbors. So the time is O of N, where is N is the number of cells. And this idea is much bigger than the maze. The same code finds the shortest way in a map, the shortest chain of friends in a social network, and the shortest way between two words. We will use it again in the section about graphs. Let's remember three things. First, a queue is a FIFO, and in Python we use deque because enQueue and deQueue are O one. Second, queues live in printers, in sub lines, and in message queues of big systems. Third, a queue and the breadth-first search find the shortest way ring by ring. In the next section, we will meet the structure that is the most important one in programming, the hash table. Hash tables, the fastest search in programming. Six Section Six, hash tables. In the last section, we used a queue and every operation was O one. Now let's meet the structure that is maybe the most useful one in all programming. Let's start with a problem. We have a list with 1 million number, and we want to know is the number 999,999 inside? In a list, we have no choice. We start from the beginning and we check the elements one by one. In the worst case, we make 1 million checks, so the search is O of O of N. I measured this in Python. The check with the word in a in on the list took about 10 milliseconds. 10 milliseconds is not a lot, but imagine that your program does this thousand of times per second. Now imagine a phone book. You don't read the whole book to find the name Smith. You open the book on the letters S and you are almost there. The name tells you where to look. This is a big idea of a hash table. The key itself tell us the address. Remember the array from the second section. If you know the index, we find the element in one step. So we need a way to turn a key, for example, a word into an an index. This this tool is called a hash function. A hash function takes a key and it returns a number. Then we take the remainder of the division by the size of our array and we get an index. Let's make the simplest hash function that we can imagine. We take a word, we add the codes of all its letters, and we take the remainder of the division by eight. I can run this in Python for the word Apple. The sum of the letter codes is 530 and the remainder is two. So Apple goes to the cell number two. The word Banana gives 609 and the remainder is one. The word Cherry gives 653 and the remainder remainder is five. The word Grape gives 527 and the remainder is seven. Now to find Apple, we don't know search. We run the hash function, we get two, we open the cell number two, and the value is there. It doesn't matter if the hash if the table has 10 elements or 1 million, it is always the same few steps. So the search, the insert, and the delete are all O O of one. But there's a problem. The array has only eight cells and the number of possible words is huge. So sooner or later two different keys will give the same index. This is called a collision. Look at the words melon and lemon. They have the same letters, so the sum is 539 for both and the index is three for both. Where do we put the second one? There are two classic solutions. The first solution is called chaining. Every cell of the array doesn't doesn't keep one element, but a small list. When two keys come to the same cell, we just add both to the list. To find a key, we go to the cell and we look through the small list. The second solution is called an open addressing. If the cell is busy, we look at the next cell and the next one until we find a free place. Python dictionaries use a smart version of this second idea. So let's see open addressing in only a small example. With the same hash function and the same eight cells, the word apple goes to the cell two and the cell is free, so it stays there. The word mango also wants to the cell two, but it is busy. So mango moves one step to the right and it lands in the cell three. The word banana goes to the cell one and it is free. The word peach also wants to wants the cell one, but the cells one, two, and three are all busy. So a peach makes three steps and it lands in the cell four. I ran this code and the table look like this. Empty, banana, apple, mango, peach, and three empty cells. To find peach, we do the same. We start from the cell one and we move to the right until we find peach or until we meet an empty cell. There is one sub one subtle thing about deleting. If you just empty the cell of apple, the search for mango will stop too early because it will meet an empty cell. So real tables mark a deleted cell with a special sign and the search goes through it. Let's build our own hash table with chaining. We create a class and in the constructor we make a list of empty list, one small list for every cell. The method for the index takes a key, adds the codes of its letters, and returns the remainder of the division by the size. The method put goes to the cell and it looks through the small list. If the key is already there, we replace the value. If it's not there, we add a new pair of key and value to the end of the small list. The method get goes to the same cell and it looks through the small list for the key. If it finds the key, it returns the value and if not, it returns none. I put eight words into this table. Apple, banana, cherry, grape, melon, lemon, peach, and mango. The word apple and the word apple and mango landed in the same cell. Banana and peach landed in the same cell and melon and and melon and lemon landed in the same cell. But the method get still found the number eight for mango and it returned none for kiwi, which was never added. So the collision are not a problem if we handle them, but a table with a very long small list is slow. If all the keys land in one cell, the table becomes a simple list and the search becomes O of N. So two things are important. A good hash function that spreads the keys evenly and a table that is not too full. How full the table is we measure with the load factor. The load factor is the number of element divided by the number of cells. When the load factor becomes bigger than zero point 0.75 we make the table twice bigger and we put all the elements again into the new table. This is called resize and it is exactly the same idea as the same as the capacity of Python list from the section about arrays. In my test the table started with four cells and after eight elements it had 16 cells. It grew two times. A resize is expensive, but it happens rarely. So on average every put is still O of one. Now the good news. In Python we don't need to build all this by ourselves. The dictionary and the set are hash tables and they are written in C and they are very fast. I created list with one million number and dictionary with the same keys. Then I searched for the last number. The list needed about 10 milliseconds and the dictionary need less than a microsecond. In my test the dictionary was about 30,000 times faster. This is the power of O of one. The set is the same, but it keeps only keys without values. There is one rule. A key must be hashable. Numbers, strings are tuples are hashable. A list is not. When I try to use a list as a key, Python raise an error, type error and hashable type list. The reason is simple. If key can change, then its hash can change and we will look in the wrong cell. And one more thing, since Python 3.7 a dictionary [clears throat] remembers the order in which we added the keys. But a set doesn't remember the order and for strings. Python change the hash value every time you start the program. So never write a program that depends on the order of the elements in its set. Now let's solve three classic problem with the hash tables. The first problem is counting. You have a text and we want to know how many times every letters appears. We go through the text and and for every letter we add one to its counter in the dictionary. Python has a ready tool for this in the module collection. It is called counter. I run it on the word Mississippi. The letters I and S appear four times each. The letter P appears two time and the letter letter M appears one time. The method most common gives the top result top result in one line. The second problem is duplicates. We have a list and we want to know if some number repeats. We put all the number into a set. If the set is smaller than the list, there are duplicates. I run this on a list with five numbers and the set had only three. So there are duplicates. The third problem is the most famous one, the numbers with a given sum. We have a list of numbers, for example, 2, 7, 11 and 15 and the target is nine. We must find two numbers that give nine together. The slow way is to check all pairs and it's O and square. The fast way use a dictionary. We go through the list and for every number we ask is the number that we need already in the dictionary? The number that we need is the target minus the current number. If yes, we are done. If not, we save the current number in the dictionary with its index. I run this in our list. At the number seven, the program need two and two was already in the dictionary. The answer was the indexes zero and one. We went through the list only once, so the whole solution is O of n. Notice [clears throat] the pattern. We paid with memory and we got speed. [clears throat] Now one more classic problem, grouping anagrams. Anagrams are words made from the same letters. For example, listen, silent and enlist. How can we put them in groups? The trick is to find a key that is the same for all the words in a group. If we sort the letters of a word, then all the anagram give the same result. So we use the sorted letters as a key and a list of words as a value. I run this on seven words. The words melon and lemon went to one group with the key e [clears throat] l m and o. The word listen, silent and enlist went to the second group and apple and pleb went to the third group. We went through the words only once, so for n words and short words this is O of n. Here we see again a good key turn the hard problem into an easy one. And the last small problem, the first letter that doesn't repeat. For the for the word Swiss, we count the letters with counter and then we go through the word again. [cough and clears throat] Excuse me. And we take the first letter with the counter one. I run this and the answer was the letter W on the index one. This trade is one of the most important ideas in programming. Let's remember three things. First, a hash table turns a key into a an index with a hash function, so search, insert, and delete are O of one on average. Excuse me. Second, collisions are normal and we solve them with the chaining or open addressing and resize keep the table fast. [clears throat] Third, in Python use a dictionary and the set and when you see a problem about searching, counting, or duplicates, think about the hash table first. In the next section, we will go from the flat structure to a structure with branches, the tree. Trees, data with branches. Section seven, trees. In the last section, all our structures were flat, a row of elements, a chain, a line. But a lot of data in the in the real world is not flat. Think about the folders on your computer. A folder keeps other folders and everyone of them keeps more folders and files. Think about a web page. The page keeps a body. The body keeps a menu and a text and the menu keeps links. Think about a family tree or the structure of a company. All of these are trees. A trees is a structure of nodes where every node can have children. The node at the very top is called the root. Every other node has exactly one parent, the node above it. A node without children is called a leaf. The The with the same parent are called siblings. An node and all the nodes below it make a subtree. The the depth of a node is the number of steps from the root to this node. The the height of tree is the number of levels from the top to the deepest leaf. Now the most popular type is the binary tree. And in a binary tree, every node has at most two children, the left child and the right child. Let's write this in Python. We already know the node from the linked list. We create a class node and in the constructor we save the value and two fields, left and right, both known at the start. So it's the same idea as before, but now every node has a two pointers. Let's build a small tree. The root has the value one. Its left child is two and its right child is three. The node two has its own children, four on the left and five on the right. So our tree has five nodes and three levels. How do we visit all these all these nodes? This called is traversal. And for trees we have four classic ways. The first three use recursion, a function that calls itself for the left and the right child. We will study recursion in detail in a later section, but here the idea is simple. A tree is a node and two smaller trees under it. So to process a tree, we process the node and we ask the same function to process the left left tree and the right tree. When the node is none, we stop because there is nothing to do. The first way is called pre-order. First the node, then the left tree, then the right tree. I ran this on our tree and the order was 1 2 4 5 three. The second way is called in order. First the left tree, then the node, then the right tree. The result was 4 2 5 1 3. The third way is called post order. First the left tree, then the right tree, then the node. The result was 4 5 2 3 1. Post order is useful when we must process the children before the parent. For example, when we delete a folder together with everything inside. The fourth the fourth way is the level order. And it goes level by level from the top to the bottom. Do you remember the queue from the last section? We put the root in a queue. And we repeat. [clears throat] We take a node from the front, we visit it, and we put its children at the back. This is exactly the breadth first search, and I ran it, and the result was 1 2 3 4 5. All the four traversal visit every node one time, so they are O of n. Let's use the same idea for two small function. The height of the node is none. The height is zero. Otherwise it is one plus the bigger height of the two children. And the count of nodes. If the node is none, the count is zero. Otherwise it is one plus the count of the left tree plus the count of the right tree. For our tree, I got the height three and the count five. Now let's make the tree useful for search. A binary search tree has one extra rule. For every every node, all the values in the left subtree are smaller, and all the values in the right subtree are bigger. This rule gives us a superpower. Let' search for the number 60 in a tree. We start as the root and the root is 50. 60 is bigger, so we go right and we ignore the whole left side. The next node is 70 and 60 is smaller, so we go left. The next node is 60 and we found it. Three steps for a tree with seven nodes. Every step cuts away half of the remaining tree just like in the binary search from the section about big O. To insert a new value, we do the same walk and we put the new node in the place where the search ended. In code, the insert is a small recursive function. If the node is none, we create and return a new node. If the value is smaller than the value of the node, the left child becomes the result of the same insert on the left tree. If the value is bigger, the right child becomes the result of the same insert and on the right tree. And we return the node. I create a tree with the values 50, 30, 70, 20, 40, 60 and 80 in this order. Then I run the in-order traversal and the result was 20, 30, 40, 50, 60, 70, 80. Look, it's sorted. This is a very nice property. The in-order traversal of a binary search tree will always give the sorted order. I also search for 65 which is not in the tree and the search needed this three steps and said not found. So the search and the insert take as many steps as the height of the tree. [cough and clears throat] If the tree is balanced, the height is about log of n and the operation are O log n. But there is a danger. What if we insert the number in sorted order? 1 2 3 4 5 6 7. Every new number is bigger than all the previous one. So it always goes to the right. The tree becomes a chain like a linked list. I ran this and the height was seven. And to find the number seven, I needed seven steps. I repeated this test with 1,000 sorted numbers and the height was 1,000. So in the worst case, the operation are O O n. Now the same test with 1,000 random numbers. The height was 21. And for a perfect tree, it will be 10. And for 100,000 random numbers, the height was 39. And the perfect tree would need 17. So random data gives a tree that is not perfect, but it is still very good. A search in a tree with 100,000 nodes needs about 40 40 steps, not 100,000. To protect from the bad case, real system use self-balancing trees. After every insert, the tree check itself and if one side become too heavy, it rotates some nodes to keep them height small. Famous examples are the AVL tree and the red-black tree. Database and file system is a close relative. The B-tree which keeps many keys in one node. With a balanced tree, even 1 million nodes need only about 20 levels. Let's also see how to delete a node from a binary search tree because here we have three three cases. The The first case, the node is a leaf and we just remove it. I I 20 and the in order result was 30, 40, 50, 60, 70, 80. The second case the node has one child and we replace the node with its child. The third case is the interesting one. The node has two children. We cannot just remove it because the subtrees would lose their parent. So we find the next bigger value. It is the smallest value in the right subtree and we call it the successor. We copy the value of the successor into our node and then we delete the successor from the right subtree. I deleted 30 and its successor was 40 and the result was 20, 40, 50, 60, 70, 80. Still sorted and still a correct tree. I also deleted the root 50 and the new root became 60. Before the real world, we solved three classic problems with tree. The first problem the in order traversal without recursion. Do you remember the call stack from the section about stack? Recursion uses the stack and we can use our own stack instead. We start at the root and we go left as far as we can and every node on the way goes into the stack. When there is no left child anymore, we pop a node from the stack we visited and we move it to its right child. Then we repeat. I ran this in our search trees and the result was 20, 30, 40, 50, 60, 70, 80. The same as the recursive version. This is useful when a tree is very deep because the stack of our our own does not doesn't have the limit of 1,000 calls. The second problem is this tree a correct binary search tree? The first idea is to check every node with its two children. The left child must be and the right child must be bigger. But this idea is wrong. Imagine a tree with a root 10. Its left child is five and its right child is 20. Now the node five has a right child with a value 15. Locally everything is correct. 15 is bigger than five, but 15 is in the left subtree of 10. So it must be smaller than 10 and it's not. I ran both check on this tree. The local check said yes and it was wrong. [snorts] The right way is to carry a range down the down the tree. At the root any values is allowed. When we go left the upper limit becomes the value of the parent. When we go right the lower limit becomes the value of the parent. If any node is outside of its range the tree is wrong. My function with a my function with a range say true for our correct tree and false for the broken one. We visit every node once, so this is O of N. The third problem, invert a binary tree. We want to swap the left and the right children in every node. The recursive idea is very short. For a node we invert the right tree and the left tree and we put them in the opposite place. I ran the preorder before the inversion and the result was 50, 30, 20, 40, 70, 60, 80. After the inversion it was 50, 70, 80, 60, 30, 40, 20. The whole tree become a mirror. Notice how every one of these problems has the same shape, a base case for node and one step for the node and then the same function for the child for the children. This is the shape of almost every tree problem and and the bonus the lowest common ancestor in in the search tree. This is the lowest node that is above to given nodes. We start at the root and if both values are smaller we go left. If both are bigger we go right. Otherwise this node is the answer because the values are on the different size. For 20 and 40 the answer was 30. For 20 and 80 the answer is answer was 50. For 60 and 80 the answer was 70. This is a loop of at most the height of the tree. So it is O log n for a balanced tree. Now where are trees used? The folders of your computer and the document of every web page are trees. Database keep indexes in trees to find a record without reading the whole table. Autocomplete in your phone uses a special tree for words where every level is one letter and the compiler turns your code into a tree before it runs it. Python has no built in binary search tree in the standard library. If you need a sorted collection you can use a sorted list with a model bisect which we will meet in the section about searching. But you need to know trees because they are everywhere and because they are the basis for the next structure. Let's remember three things. First a tree is nodes with children and a binary tree has at most two children for every node. Second the traversals are preorder, in order, post order, and level order and they are O of n. Third a binary search tree keeps the smaller values on the left and the bigger on the right. So the search is O log n if the trees is balanced and O n if the tree is a chain. In the next section we will meet a special tree and that always give us the smallest element in one step, the heap. Heaps always the smallest one first. Section eight, heaps. In the last section we learned the trees and the binary search tree. [clears throat] Now let's meet a special tree that solves one problem very well. They give us the smallest element in one step. Let's start with a story. Imagine a hospital emergency room. The patient don't go in the order of their arrival. The most urgent patients go first, even if he came the last. This is a priority queue. In a normal queue the first element in is the first out. In a priority queue the element with the highest priority is the first out. How can we build it? The [clears throat] simplest idea is a list and the search for the smallest element every time. But the search in a list is O n. The second idea is a sorted list, but then every insert is O n because we must move the elements. We need something better and this is the heap. A heap is a binary tree with two rules. The first rule is the shape. The tree is complete, which means that all the levels are full except maybe the last one and the last level is filled from the left to the right. The second rule is the order. Every parent is smaller than or equal to its children. This is called a min heap. If every parent is bigger than its children it is a max heap. Look at what the second rule gives us. The smallest element is always at the top, in the root. We don' search for it, we just take it and this is open. Notice that the rules is not as strict as in this search tree. The left and the right children are not sorted between them. A heap only guarantees that the parent is smaller than its children. And here's a beautiful trick. Because the tree is complete, we don't we don't need nodes and pointers. We can keep the whole heap in a simple list. We write the root first, then the then the next level from the left to the right, then the next level and so on. Let's take the the list one tree [clears throat] 1 3 2 5 9 and 8. The root is the number one at the index zero. The children of the root are three and two uh at the indexes one and two. The children of the number three are five and nine at the indexes three and four. The number two has only one child, eight at the index five. And now the magic formulas. For a node at the index I, the left child is at two time I plus one. And the right child is at two time I plus two. And the parent is at I minus one divided by two with the integer divisions. For example, the number nine is at the index four and its parent is at the index four minus one divided by two which is one, the number three. It is correct because three is smaller than nine. So an array and two formulas replace the whole tree and it uses less memory. And [clears throat] it is friendly to the processor, not the operations. The first operation is push. To add a new element, we put the new element at the end of the list, which is which is the first free place of the last level. But now the order rule can be broken because the new element can be smaller than its parent. So we compare it with its parent and if it's smaller, we swap them. Then we compare it with the new parent and so on until the order is correct or until we reach the root. This this movement up is called sift up. Let's see an example. I I took our heap 1 3 2 5 9 8 and I added the number 0. 0 went to the end to the index 6 and its parent was the number 2 so they swapped. Then the parent was the number 1 so they swap again and 0 became the root. The result was 0 3 1 5 9 8 2. How how many steps can it take? At most one for every level of the tree. The tree is always complete so its height is about log of n and the push is O O log of log n. The second operation is pop to take the smallest element. The smallest element is the root but we can't just remove it because we will get a hole. So we do a trick. We take the last element of the list and we put it in the root. Now the order is probably broken because a big element sits at the top. So we compare it with its two children. We we choose the smaller child and if the child is smaller than our element, we swap. We repeat this going down until the order is correct. This movement down is called sift down. I ran this on the heap 1 3 2 5 9 1 The pop returned one. The number eight moved to the root and then it's swapped with the smaller child which which was two. The [snorts] result was 2 3 8 5 9. Again we make at most one step for every level so the pop is O of log n. So the heap give us the smallest element in O of one. The push in O of log n and the pop in O of log n. [clears throat] Python has a ready heap in the module heap q. It's a min heap and the heap is simply a normal list. The function heap push adds an element and the function heap pop removes and returns the smallest. I pushed the number 5 3 8 1 9 and 2 1 by 1 and the list after the last push was 1 3 2 5 9 8. Then I called heap pop and I got one. And when I called heap pop again and again I got the number in this order 2 3 5 8 9. The elements came out sorted. This is an idea for a sorting algorithm and it's called the heap sort. We push everything into a heap and then we pop everything out. Its time is O of n log n. If you already have a list there is a faster way to make a heap from it. The function heapify. It rear- rearranges the list in place and surprisingly it takes only O of n not O of n log n. I ran it on the list 9 4 7 1 8 2 and I got 1 4 2 9 8 7. For 1 million random numbers, heapq took about 700 of of a second and 1 million pushes took about 1,100. Now let's compare the heap with the list in a real test. I made a list with 1 million numbers and heap with the same numbers. I took the smallest element 1,000 times from the heap with heap pop. It took about 4 milliseconds. From the sorted list with pop at the index zero, it took about 370 milliseconds. The heap was about 90 times faster on my computer. There is one more thing. Python has only a min heap. If you need a max heap, the trick is to put the number with a minus sign. The smallest of the negative numbers is the biggest of the original ones. I tried this on the numbers 7 2 9 4 1 8 and 3 and I got the number 9 after changing the sign back. And if you need priorities, you can push a tuple. The priority first and the stack second. Python compares tuples from the left, so the priority decides. I push three task, write a report with the priority two, fix a bug with the priority one and launch with the priority three. The first task that came out was fix a bug. Where do we use heaps? An operating system uses a heap to choose the next task. A game uses a heap for the events that must happen at a given time. The algorithms for the shortest way, which we will see in the section about graphs, use a heap in every step. And a very common problem is the top K elements. Let's solve it. We have a stream of numbers and we want to keep the K biggest ones. The idea is surprising. We use a min heap of the size K. For every new number, we push it and if the heap has more than K elements, we pop the smallest one. At the end, the heap keeps exactly the K biggest numbers and the smallest of them sits in the root. So the root is the K biggest number. I ran this for the list 3 2 1 5 6 4 with K equal to 2 and the answer was 5, the second biggest number. And for 7 2 9 4 1 8 3 with K equal to 3, the answer was 7. The time is O of N log K and the memory is only K. Python even has this inside. The function enlarges and in smallest. I asked I asked for the three biggest numbers from 1 million and enlargest needed about 300 of a second. Sorting the whole list need almost half a second, about 17 times more. Remember, when you need only the best few, do not sort everything. Let's remember three things. First, a heap is a complete binary tree where every parent is is smaller than its children. So the smallest element is always in the root. Second, we keep it in a list and the push and the pop are O of log N and the smallest element is O of 1. Third, in Python we use the module heap queue and for the max heap we change the sign. In the next section we will meet the most flexible structure of all the graph. Graphs, everything is connected. Section nine, graphs. In the last section we learned the heap. Now we come to the most flexible structure in the whole course, [snorts] the graph. A tree is a special graph and the graph is a tree without the rules. Let's start with examples. A map of roads, the cities are connected by roads. A social network, the people are connected by friendship. The internet, the pages are connected by links. A subway map, a flight schedule, the dependencies between the files of a program. All of this is a graphs. A graph is a very simple, it's has vertices and it has edges. A vertex is a point, for example a city or a person. An edge is a line between two vertices, for example a road of or a friendship. Two vertices connected by an edge are called neighbors. The edges can have a direction and then the graph is called directed. A page A can link to a page B and the page B doesn't link back. If the edges have no direction, the graph is undirected like a friendship. If I am your friend, you are my friend. The edges can also have a weight, a number, for example the length of a road or the price of a flight. Now the main question, how do we keep a graph in the memory? There are two classic ways. The first way is is the adjacency matrix. We make a table where the rows and the columns are the vertices. If there is an edge between two vertices, we write one in the cell and if not we write zero. The good things to check if two vertices are connected, we look at one cell and it's of one. The bad things, is the table has n times n cells even if there are only a few edges. I made a graph with seven vertices and six edges. The matrix had 49 cells and only 12 of them were ones. Every edge is written two times because the graph is undirected. Imagine a social network with a million people. The table would have a trillion cells and almost all of them are zero. So the second way is much more popular, the adjacency list. For everywhere everywhere vertex, we keep a list of its neighbors. In Python, this is a dictionary. The key is a vertex and the value is a list of its neighbors. Our small graph looks like this. The vertex A has the neighbors B and C. The vertex B has the neighbor A and D. The vertex C has the neighbor A and D. The vertex D has the neighbor B, C, and E. The vertex E has one neighbor, it's D. And two more vertices, F and G, are connected only to each other and they are not connected to the first five. The memory of the adjacency list is of V plus E, the number of vertices plus the number of edges. For 1,000 vertices and 3,000 edges, the matrix needs 1 million cells. And the list need and the list needs only 6,000 entries. So for most real graphs, we use the adjacency list and I will use it in all examples. Now the main question, how do we visit all the vertices of a graph? There are two classic ways and you already know both of them. The first way is the breadth-first search and we already use it for the maze. We take a vertex and we visit all its neighbors, then the neighbors of the neighbors and so on, ring by ring. We need a queue and a set of the visited vertices. I run it from the vertex A and the order was A B C D E. First A itself, then both neighbors B and C and then D and then E. The vertices F and G were not visited because we can't reach them from A. The second way is a deep first deep first search. Here we go as deep as possible. We take a neighbor, then then a neighbor of this neighbor and so on until we are in a dead end. Then we go back and we try the next neighbor. For this we need a stack and the easiest way is recursion because the call stack is already a stack. The function visits a vertex, marks it as visited and then calls itself for every neighbor that is not visited yet. I ran from the vertex A and the order was A B D C E. First A then B, then from B we go to D. Then from D we go back to C and then to E. Compare it with the breadth first search. The vertices are the same but the order is different. We can also do the depth first search without recursion. With our own stack we push the start vertex and while the stack is not empty we pop a vertex and if it's new we visit it and we push its neighbors. I ran this and the order was the same A B D C E. Both searches visit every vertex one time and every edge one or more times so both are of V plus E. So when do we use which one? If we need the shortest way, we use a breadth first search because it goes ring by ring. I run the distance from A to E and the answer was three edges. And the distance from A to F was known because there is no way. If we need to explore all the possibilities or to check the connection, we use the depth first search because it's simple and it needs little memory. Let's solve some classic problem. The first the first problem, the number of connected components. A component is a group of vertices that can reach each other. We go through all the vertices and if a vertex is not visited, we start a new search from it and we add one to the counter. In our graph, I got two components. One with A, B, C, D and E and another one with F and G. The second problem. Does the graph have a cycle? A cycle is a way that comes back to the start without repeating edges. In the depth first search, we remember the parent of every vertex. If we meet a visited vertex that is not our parent, then we found a cycle. I run this on our graph and it said true. The path A, B, D, C goes back to A. Then I run it on a chain of three vertices, A, B and C and the answer was false. By the way, a tree is exactly a graph without cycle and with one component. The third problem, the order of the task which is called the topological sort. [gasps] Imagine the courses at a university. You must learn math before physics and math before computer science and computer science before algorithms. This is the is directed graph and we want an ordering which every courses comes after its requirements. The idea is simple. We count for every vertex how many edges come into it. The vertices with zero incoming edges can go first. We put them in a queue and we take them one by one and after every vertex we reduce the counters of its neighbors. When a counter becomes zero the vertex goes into the queue. I ran this on our courses and the order was math, physics, computer science, algorithms. If the if the graph has a cycle the order doesn't exist and some vertices will never get to to the queue. Before that let's see two more things that are very common. The first thing is a directed graph. Imagine a small website. The home page links to the blog and to the shop. The blog links back to the home page and to the first post. The shop links to the cart. The post and the cart have no links at all. In in the dictionary every page keeps on the page that it links to. I counted the links that go into every page and the links that go out. The home page has two outgoing links and the post has zero. Every page here has exactly one incoming link. These two numbers have names, the out degree and the in degree and search engines use the in degree as one of the sign of a popular page. The second thing is a surprise. A graph can be hidden inside a grid. Imagine a map of four rows where one means land and zero means water. The first two rows start with the two cells of land and they make a block. The third row has one separate cells of land in the middle. The last row has two cells and of land on the right. How many island do we have? The cell of the grid are the vertices and the neighbors up, down, left, and right are the edges. So the number of island is the number of connected component and we already know how to count them. We go through all the cells and when we meet a land cell that is not visited we start the depth first search which which marks the whole island and we add one to the other counter. I ran this and the answer was three island with the size four and two one and two. We visit every cell one time. So for a grid with n cells this is O of n. When you see a grid in a problem you can almost always think about it's a graph. Now the last and the most interesting problem. The shortest way in a graph is weights. The breadth first search counts the edges but now every edge has its price. The famous solution is the largest Dijkstra and it's a breadth first search with one change. Instead of a normal queue it uses a heap. We keep the best known distance to every vertex and we start from the start vertex with a distance zero. Every time we take from the heap the vertex with the smallest distance and we try to improve the distance of its neighbors. If we found the shortest way shortest way we update the distance and we push the neighbor into the heap. Let's see an example with four vertices. From A to B the road is four and from A to C it's one. From C to B it is two and from B to D it's one and from C to D is five. I ran algorithm from A and the result was is A0 C1 B3 D4. Look the Look Look the direct road from the A to B costs four, but the way through C costs only one plus two, which is three. And to reach D, the best way is A C B D is a total price of four. The algorithm works only if all the weights are not negative. It's a time is O for V plus E of log of V because every push and pop of the heap costs O log N. Dijkstra is the idea behind the navigation in your phone. Let's remember three things. First, the graph is vertices and edges in a Python we keep it as a dictionary of lists which needs O V plus E of memory. Second, the breadth-first search uses a queue and find the shortest way by the number of edges and the depth-first search uses a stack or recursion and goes deep first. Third, for the for the weights we use Dijkstra with a heap. In the next section we will look closer at the idea that we use many times in this course, the recursion. Recursion, a function that calls itself. Section 10 recursion. In the last section we already used recursion many times in the trees and in the depth-first search. Now it's a time to look at it closely. Recursion is a simple idea, a function that calls itself. Imagine two mirrors, one against the other. You see a mirror in a mirror in a mirror and it looks infinite. Or imagine a Russian doll. You open it and inside there is a smaller doll, and inside is a smaller one until the last tiny doll. Recursive functions solve a big problem in a very special way. It makes the problem a little bit smaller, and it gives the smaller problem to itself. There are two parts, and you must have both. The first part is a base case, the problem that is so small, and we know the answer without any work. It is the last tiny doll. The second part is a recursive case. [gasps] We make the problem smaller, and we call the same function. If there is no base case, the function will call itself forever, and the program will crash. This is the classic example, the factorial. The factorial of five is 5 * 4 * 3 * 2 * 1. Notice that the factorial of five is five times the factorial of four. So the factorial of n is n times the factorial of n - 1. And the base case, the factorial of one is one. In Python, this is three lines. If n is smaller or equal to one, we return one. Otherwise, we return n times the factorial of n - one. I ran this, and the factorial of five was 120, the factorial of 10 was 3,628,800. And the factorial of 20 was two quintillion 432 quadrillion and some more digits. How does it works inside? Remember the cell stack from the section about stacks. When we call the factorial of five, Python puts a frame on the stack, and this frame is waiting for the answer of the factorial of four. So the factorial of four goes on stack and it waits for the factorial of three and so on until the factorial of one. The factorial of one returns one desired any new calls. It is the base case. Now the frame leaves the stack one by one from the top. The factorial of two returns two. The factorial of three returns six. [gasps] The factorial of four returns 24 and the factorial of five returns 120. So the stack grows down to the base case and then the answers go go back up. So this is a key picture of recursion and you should keep it in your head. Let's try the second example, the sum of a list. The sum of an empty list is zero. This is a base case. The sum of a list is the first element plus the sum of the rest. I ran this on the list one two three four and I got them 10. Here every call makes the list one element shorter. So the list shrinks to the base case. The third example reverses string. An empty string or a string with one letter is already reversed. Otherwise we reverse the rest of the string and we put the first letter at the end. I ran this on the word hello and I got olleh. And one more, the palindrome. A word is a palindrome is the first and the last letter are the same and the middle part is also a palindrome. I checked the word level and the answer was true and for the word hello it was false. Now the most famous example, the Fibonacci numbers. Every Fibonacci number is the sum of the two previous ones, zero one one two three five eight and so on. The recursive code is beautiful. If n is smaller than 2, we return n. Otherwise, we return the Fibonacci of n - 1 + the Fibonacci of n - 2. But here's the trap. I counted how many times the function was called. For the Fibonacci of 10, which is 55, the function was called 177 times. For the Fibonacci of 30, which is 8 832,040, the function was called 37 times. 2 million calls to compute one number. Why? Because every call makes two new calls, and the same values are computed again and again. The Fibonacci of 30 calls the Fibonacci of 29 and 28. The Fibonacci of 29 calls 28 and 27. So the Fibonacci of 28 [clears throat] is computed twice already, and the number of repeats grow like a tree. The the time of this solution is exponential. And the fix is very simple. Memoization. We save every answer in a dictionary, and before the real work, we check, maybe we already know this answer. I ran the same Fibonacci of 30 with a dictionary, and the function was called only 50 59 times instead of 2 million. The result was the same, 832,040. Python had has a ready tool for this, a decorator called LRU Cache from the module functools. You write it above the function, and Python does the memoization for you. With it, I computed the Fibonacci of 100 and it was a number with 21 digits instantly. The time became of n because every value is computed only one time. This idea to remember the answers of small problems is called dynamic programming and it is a very big topic, but you just saw its first step. Now let's talk about the limit. Every call takes a frame on the stack and the memory is not infinite. Python protect us with a limit and by default it's 1,000 frames. I wrote a function that counts down by one and I called it with 5,000. Python raised an error, recursion error, and the factorial of 900 worked fine, but the factorial of 1,000 failed because it needed more than 1,000 frames. You can change the limit with a function set recursions limit, but be be careful. If you make it too big, the whole program can crash. So when the dips can be large, there are two option to use a loop instead or to use our our own stack. Every recursion can be rewritten as a loop. For the factorial, the loop is simple. We start with a one and we multiply by the number from two up to n. I checked [clears throat] and the result was the same. Then why do we need recursion? Because for some problems the recursive code is much shorter and clearer than a loop, especially for trees and for problems where we try many options. Let's see one such problem, the Tower of Hanoi. We have three rods and n disks of different size on the first rod. The biggest at the bottom. We must move all the disks to the third rod, but we can move only one disk at a time and we can never put a bigger disk on a smaller one. The recursive idea is very short. To move n disks from a to c, first we move n - 1 disks from a to b. Then we move the biggest disk from a to c, and then we move n - 1 disks from b to c. The base case is zero disk. There is nothing to do. [clears throat] I counted the moves. For three disks, I got seven moves. For 10 disks, 1,023 moves. For 20 disks from for 20 disks, more than 1 million moves, exactly 1,048,575. The rule is to [clears throat] 2 to the power of n - 1. Every new disk doubles the work, so the time is exponential, and no computer can solve it for 50 disks, no matter how smart the code is. Recursion is also great when we can cut the problem in half. Let's compute 2 to the power of 100. The slow way is to multiply by 2 100 times. The smart way is this. The power of n is the power of n divided by 2 multiplied by itself, and if n is odd, we multiply by one more one by one more 2. The base case is a power zero, which is one. Every call cuts the exponent in half, so we need only about log of n calls, and the time is of log n. I ran this for 2 to the power of 10, and I got the I got 1,024, and for 2 to the power of 100, the result was the same as the Python operator. And one more nice example in nested list where list are inside of list. We want to make it flat. We go through the element. If an element is a list, we flatten it with the same function. And if it's And if it's a number, we just take it. I ran this in on one. Then a list with a two and list with a three and four and the five. And I got one, two, three, four, five. A loop would need a lot of work here because we don't know how deep the list are. Next, a very common technique that use recursion backtracking. We build the solution step by step and at every step we try all the options. And if one options leads to a dead end, we go back and we try another one. The simplest example all the subsets of a list. For every elements we have two choices to take it or not to take it. For the list one, two, three I got eight subsets, empty one, then three, two, two and three, one, one and three, one and two and one, two, three. For a list of four elements there are 16 subsets, two to the power of four. The second example, all the permutation which means all the orders of the elements. We choose the first element in all possible ways. And for the rest we call the same function. For the list one, two, three I got six permutation. And for four elements 24. The number The number of permutation is a factorial of n and grows even faster than two to the power of n. How do we write recursive code without getting lost? Here Here are the three rules. First, write the base case first, so you don't forget it. Second, trust the function. Imagine that the call for the smaller problem already works and think only about one step. check that every call really moves towards the base case. Let's remember the three things. First, a recursion has a base case and a recursive case. And the calls go down to the base case and the answer come back back up the stack. Second, if if the same small problems repeat, use memoization and a slow exponential solution becomes of n. Third, Python has a limit of 1,000 frames. So for a very deep recursion, use a loop or your own stack. In the next section, we will go back to a simple but very important task, how to find an element quickly. Searching, finding a needle fast. Section 11, searching. Searching is one of the most common tasks in programming. We have a collection and we want to find an element or to know that it's not there. In this section, we will see two ways and the difference between them is huge. The the first way is a linear search and you already know it. We start from begin from the beginning and we check the elements one by one until we find the target. In Python, this is a for loop is a simple check. It works for any list, sorted or not. I run it on a list with 10 numbers and I looked for the number 23 which was on the index five and the program made six checks. But for a list with 1 million numbers and a target in the last place, it needs 1 million checks. So the linear search is O of n. The second way is a binary search. And it needs one condition. The list must be sorted. Think about the game. I think about a number from one to 100 and you must guess it. And I only say bigger or smaller. What's your first guess? Not one, not two, you say 50. If I say bigger, you say 75. And you cut away half a game. This is a binary search. Let's write it. We keep the board two borders, left and right. At the start, left is the index zero and right is the last index. While left is not bigger than right, we calculate the middle index, which is left plus right divided by two with the integer divisions. If the middle element is the target, we return its index. If the middle element is smaller than with than the target, then the target can be only on the right side. So left becomes middle plus one. If the middle element is bigger, then the target can be only on the left. So right becomes middle minus one. If the borders cross, the element is not in the list and we return minus one. Let's run it on the sorted list 2 5 8 12 16 23 38 56 92 91. For the number 23, the middle was 16, so we went right. Then the middle was 56, so we went left. Then the middle was 23 and we found it on the index five. Three steps instead of six for the linear search. For the number 91, we needed four steps. And for the number seven, which is not in the list, the program made three steps and returned minus one. Every step cuts the list in half. So how many steps do we need for 1 million elements? 1 million is about 1 to the power of 20. So the answer is about 20. I checked it. I searched for the last element in a sorted list of 1 million numbers and the program made exactly 20 steps instead of 1 million. I also tried 2000 random targets and the biggest number of steps was 20. So the binary search is of log n. If is a list grows to 1 billion elements, we need only 30 steps. That is the magic of the logarithm. The only price is that the list must be sorted and sorting costs of n log n. So it makes sense when we search many times. There is one very important mistake. If the list is not sorted, the binary search gives wrong answer and it doesn't it quietly. And it does it quietly. I ran it on the list 5 1 9 3 7 and I looked for the number 3 which is in the list and the program returned minus 1. So always check that the list is sorted. Another source of errors is the borders, the the plus 1 and the minus 1 and the sign smaller or equal. If you forget one of them, the program can skip an element or it can run forever. So when you write the binary search, check the cases with one element, with two elements, and with the missing targets. In Python, we don't need to write it every time because there is the model bisect. The function bisect left finds the place where the target is or where is it should be inserted. I ran it in our list. For the number 23, it returned five. For the number 24 which is not in the list it returns six. The place between 23 and 38. For a number bigger than all the elements it returned 10 the length of the list. And for the number one it returned zero. There is also a function insert which inserts an element and keeps the list sorted. I inserted the number 30 and the list stayed sorted with 30 before 38. Remember that the insert into list cost of n because the elements must move but the search for the place is of log n. Now the speed test. I made a sorted list with 1 million numbers and I searched for for the last number. The word n which is the linear search took about 9 milliseconds. The bisect took less than 1 microsecond. The binary search was about 28,000 times faster on my computer. And here's a nice trick with the bisect. Imagine that a teacher gives a grade by the score below 60 is F, from 60 is D, from 70 is C, from 80 is B, and from 90 is A. We keep the borders in a list 60, 70, 80, and 90 and the function bisect gives us the index of the grade. I ran this for the scores 30 33, 60, 75, 89 90 and 100 and and I got F D C B A A. No chain of if and else is needed. Now the last idea which is the most powerful one the binary search on the answer. We don't need a list at all. We need only a question with a a yes or no answer where the answer changed from no to yes in one place. For example, what's the smallest number whose square is at least 2000? If a number is too small, the answer is no, and from some number it is always yes. We search between zero and 1000. We take the middle and we ask the question. If the answer is yes, we move the right border to the middle, and if it's no, we move the left border behind the middle. I ran this and the answer was 45 because 44 squared is 1936 and 45 squared is 2025. The same idea finds the square root of a number as an integer. For 99 it gave nine and for 1 million it gave 1000. The same idea is used for the question, what's the smallest speed, size, or time so that the task is possible? Whenever the answer to the question change in one place from no to yes, you can use the binary search. Let's remember three things. First, the linear search checks the elements one by one and it is O of N, but it works for any list. Second, the binary search needs a sorted list and it cuts the list in half every step, so it's O log N, 20 steps for 1 million. Third, Python use the module bisect and remember that the idea of the binary search works not only for lists, but for any questions where the answer change from no to yes. In the next section we will see how to sort the elements because the fast search needs a sorted list. Sorting algorithms. Sorting is one of the oldest problem in computer science and it shows up everywhere. Search the results, leaderboards and database queries all depend on putting items in order. In this section we will build five classic sorting algorithms. Count their steps and see what Python does for us. Let's start with the simplest idea called bubble sort. Bubble sort walks through the list, compares each pair of neighbors and swaps them if they are in the wrong order. After one full pass, the largest value has bubbled up to the end. [clears throat] And then we repeat the pass on the remaining items. I done this code on the list five two four one three and it needed 10 comparisons. If a If a whole pays pass makes no swaps, the list is already sorted so we can stop early. On an already sorted list of 1,000 items that early stop needs only 999 comparisons. [clears throat] But on a random list of the of 1,000 items, bubble sort made 498,122 comparison and the time complexity is O of n squared. Next Next is selection sort. It finds the smallest value in the unsorted part and swaps it into the first open position. Then it repeats for the next position and the next. On the random list of 1,000 items, it made exactly 499,500 comparison and that number never change even for a sorted list. So selection sort is always O of n squared and its only advantage is very few swaps. [clears throat] The third algorithm is insertion sort. Think of sorting playing cards in your hand. You pick up one card at a time and slide it left until it sits in the right place. On the on the random list of the thousand items it it made 252,093 comparison about half of the others. And on an already sorted list it made only 999 so it's O of n squared in in the worst case but O of n on nearly sorted data. All three of these are fine for a few dozen items but there are slow for large list so we need a better idea. That idea is divide and conquer. And the first algorithm is merge sort. [snorts] Merge sort splits the list in half, sorts each half and then merges the two sorted halves. [snorts] The real works happen in the merge step. We keep one pointer at the front of each half and we take the smaller of the of the two front values. Merging takes a single pass and a list of 1,000 items [snorts] can be halved only about 10 times. So merge sort is O of n log n. I ran it on the random list of 1,000 items and it made only 8,723 comparisons compared with almost 500,000 for bubble sort. The price is memory because merge sort builds new lists so it needs O of n extra space. The second divide and conquer algorithm is quick sort. It picks one value called the pivot and puts every smaller value on the left and every larger value on the right. Then we sort the left side and the right side the same way using recursion. On the random list of 1,000 items, my version did about 11,726 element checks. [clears throat] On average, quick sort is O of n log n. But if the pivot is always the smallest or largest values, the work grows to O of n squared. That is why good implementation choose the pivot carefully, for example, at random. Now let's compare them on a real clock time with a random list of 3,000 numbers. Bubble sort took about two thirds of a second. Insertion sort about three tenths of a second. And Python's built-in sorted function took about 36 hundredths of a millisecond. That means the built-in is roughly 1,800 times faster than bubble sort and about 850 times faster than insertion sort. It is written in C and its algorithm is called Timsort, which combines merge sort with insertion sort. Timsort is O of n log n in the worst case and O of n when the data is already sorted. So in real project, you almost never write your own sort. You call sorted or the sort method. The function sorted returns a brand new list and the list method sort changes the list in place and returns none. A very common bug is to write numbers equals numbers dot sort, which replace your list with none. Both accept the parameter parameter reverse and when it is true, the order goes from largest to smallest. Now the most useful parameter parameter called key. The key is a function that is called once for each item and the items are ordered by the value it returns. Takes the words pear, fig, banana, kiwi, and apple. Sorted alphabetically, they come out as apple, banana, fig, kiwi, pear, and with key equal to len, they come out as fig, pear, kiwi, apple, and banana. Notice that pear stays before kiwi just as in the original list. That property is called stability. A stable sort keeps equal items on their original order, and Python's sort is a stable. Imagine four people with scores N 90, Bob 85, Sid 90, and Dan 85. We sort them by score, and the result is Bob, Dan, N, and Sid. Now, what if you want the highest score first and names is alphabetical order for ties? We return a tuple from the key function, minus the score, then the name. The negative scores puts higher scores first, the names breaks ties, and the result is and Sid, Bob, and Dan. You can also sort the items of a dictionary by value using a lambda or the function item getter from the operator module. Now, let's talk about the limits of comparison sorting. It can be proven that no comparison-based sort can beat O(n log n) in the worst case. But if we know something extra about the data, we can cheat. And the classic example is counting sort. Suppose we are sorting ages between 0 and 100. We make 101 counters and add one to the matching counter for each age. Then we read the counters in a order and write each value out as many times as it was counted. That takes O(n + k), where k is the size of the range with no comparison at all. So, how do you choose? For real code, use [clears throat] sorted and pass a key when you need one. For for learning and for interviews, know insertion sort, merge sort, and quick sort well. [clears throat] Now that bubble sort and selection sort are O of n squared and that merge sort is O of n log n but need extra space. And now that quick sort is O of n log n on average but on O of n squared is the worst case. And that Python sort is stable. There is one more habit worth building. Before you write a clever algorithm, ask whether sorting the data first makes the problem easy. Duplicate sit next to each other. Two sorted lists can be merged in one pass and a sorted list can be searched with binary search. Sorting costs O of n log n and that's often a bargain. Let's wrap up. Bubble, selection, and insertion sort are simple but it's O squared O of n squared. [clears throat] Merge sort and quick sort use divide and conquer to reach O of n log n. Tim sort, behind sorted and sort is stable, fast, and ready to use. The key parameter lets you sort anything by any rule. In the next next section, we move on the on to problem solving patterns like two pointers and sliding windows. Problem solving patterns. By now, you know the main data structures and you know how to measure an algorithm. In this section, we put that knowledge to work. Most problems are not new and they follow a small number of patterns. Once you recognize the pattern, the solution almost writes itself. We will cover six patterns and for each one, I will show you when to use it. The first pattern is two Use it when the data is sorted or when you need to compare items from both ends. We place one pointer at the start and one at the end and move them toward each other. Let's find two numbers that add up to 10 in the sorted list 1 3 4 6 8 11. We start with 1 and 11 which add up to 12 and that's too big. So [clears throat] excuse me. So we move the right pointer left and now 1 + 8 is 9 which is too small. So we move the left pointer right. 3 + 8 is 11 too big and so on. In my run we found 4 + 6 after five steps. Each step throws away one candidate so the whole search is O(n) and it uses O(1) extra space. The brute force version checks every pair and that is O(n^2). The same idea checks palindromes, merge sorted lists and removes duplicates in place. The second pattern is a sliding window. Use it when the question is about a continuous part of list or a string called a subarray or a substring. The window is a range with a left and a right end. We move the right end forward to grow the window and we move the left end forward to shrink it. Consider the list 2 1 5 1 3 2 and the question is a [clears throat] largest sum of three neighbors in a row. The slow the slow way adds up every group of three from scratch. The fast fast way adds in one new value on the right and subtract one one old value on the left. The answer is 9 from 5 1 and 3 on a list of numbers with a window of 1,000, the sliding version was about 60 times faster than recalculating every sum. In general, we turn O of n times k into O of n. Sliding windows can also have a flexible size. Here's a classic example, the longest substring with no repeated letters. For the text abc abc bb, the answer is three. We keep a dictionary with the last position of each letter. When the right and when when the right end meets a letter already inside the window, we jump the left and pass its previous position. For the text p ww k k e w, the answer is also three. [clears throat] This runs in O of n because each end only moves moves forward. The third pattern is a prefix sum. Use it when you must answer many questions about the sum of a range. We build a helper list where each entry holds the sum of everything before that positions. [snorts] For the list three one four one five nine, the prefix list is zero three four eight nine 14 23. Now the sum of any range is one subtraction. For example, the sum sum of the items at position two to four equals the prefix at five minus the prefix at two. That is 14 minus four which equals 10 10 and indeed four plus one plus five is 10. Building the prefix list costs O of n once and every query after that costs O of one. A next extension combines prefix sums with a dictionary. To count the subarrays that that up to a target, we store how many times each prefix sum has appeared. For the list one, two, three, minus one, two and the target three, the answer is because one plus two and the single tree was work. The solve in O of N a problem that looks like O of N squared. The first pattern is fast and slow pointers. Use it for linked lists and for anything that may loop. One pointer moves one step at a time and the other moves two steps. If there is a cycle, the fast pointer eventually catches the slow one like a faster runner on a circular track. In my test, the nodes led to a loop and the two pointers met at node three after three steps. If there is no cycle, the fast pointer simply reaches the end. The same trick finds the middle of the list in one pass. When the fast pointer reaches the end, the slow pointer is exactly in the middle. The memory cost is O of one, which is better than storing every visited visited node in a set. The fifth pattern is merging intervals. Use it when you see range like meeting or time slots. First sort first sort the interval by their start. Then walk through them and if the next interval starts before the current one ends, extend the current end. Otherwise, start a new one. For the interval one to three, eight to 10 two to six, 15 to 18 and 17 to 20 the result is three intervals. There there are there are one to six, eight to 10 and 15 to 20. Sorting cost O O of N log N and the walk cost O of N. So the total is O of N log N. The sixth pattern is dynamic programming and the simple form is to remember answer you have already computed. We met it in the recursion section as memoization. Use it when the problem breaks into smaller copies it of itself and the scope is repeat. A famous small example is climbing stairs where you take one or two steps at a time. The number of ways to reach step 10 is 89. For step 40 it's 165 million 580,000 and 141. [clears throat] Without without memory the recursion will take forever but with memory it is instant. Another favorite is the maximum subarray where you track the best sum ending at each position. For the list minus two one minus three four minus one two one minus five for the best sum is six. At each item you either extend you the current sum or start free or start fresh at this item and you keep the best value you have seen. So that's O of n and O of one space. So how do you pick the pattern? Sorted data or two ends means two pointers. A continuous range means a sliding window. Many range sums mean a prefix sum. A loop or middle point in a linked list means fast and slow pointers. Ranges that overlap means sort and merge. Repeated subproblems mean dynamic program programming. And whenever you are stuck ask what you would do you what what you would do by hand. Then ask what you keep recomputing. And those two questions lead to most of these tricks. You know have a toolbox and the last step is using it under pressure. In the next section we turn to interview problem and how to approach them. Interview problems. This is the last section of the course and here we bring everything together. A coding interview is not only a test of what you know. It is a test of how you think and how you talk about the problem. So let's start with a simple routine you can use every time. Step one is to repeat the problem in your own words and ask question. Can the list be empty? Can there be duplicates? How large can the input be? Step two is to write one or two example including an edge case. Step three is to state the brute force solution out loud even if it's slow. A working slow answer is a good starting point and it shows that you are understand the problem. Step four is to look for a better idea. Ask yourself which data structure or which pattern fits. Step five is to write the code slowly and clearly and to state what you are doing. Step six is to test your code on your examples line by line. Step seven is to state the time and space complexity using using big O. If you follow these seven steps you will look calm and organized and that matters as much as the code. Let's practice on four problems. [clears throat] The first problem is valid parenthesis. You get a string of bracket round square and curly and you must say whether they are balanced. The tools for the job is a stack which we studied earlier. When we see an opening bracket we push it in onto the stack. When we see a closing bracket we pop the stack and the bracket must be its matching partner. If the stack is empty at that moment or the match is wrong, the answer is false. At the end, the stack must be empty. For the string round, square, curly, curly closed, square closed, round closed, the answer is true. For round followed by square closed is it's false. And for two opening round brackets with nothing to close them, it's also false because two brackets are left on the stack. We visit each character once, so the time is O of N and the stack takes O of N space. The second problem is the best time to buy and sell stock. You get the price for each day and you can buy once and sell once later. For the prices 7 1 5 3 6 4, the best profit is 5. You buy at 1 and you sell at 6. The brute force tries every pair of days, which is O of N squared. The better idea is to scan once, keep the lowest price seen so far, and each day compute the profit if we sold today. We keep the biggest of those profits. This is O of N time and O of 1 space and it's really of a Cartesian of the maximum subarray from the last section. The third problem is the product of an array except itself. For the list 1 2 3 4, the answer is 24 12 8 6. Each value is the product of everything except the item at that position. You are not allowed to use divisions. The idea is to do two passes. In the first pass from the left, we store at each position the product of everything to its left. In the second pass from the right, we multiply in the product of to its right. That keeps the right answer in of n time with no extra space apart from the output. This is the prefix idea from the previous section in a new discuss. The first problem is a missing number. You get a list of number from zero to n with exactly one number missing. For the list three 0 1 5 2 the answer is four. There are many ways to solve it. You can sort and look for the gap which is O of n log n. You can put everything in a set and test each number which is O of n time and O of n space. Or you can use the formula for the sum from zero to n and subtract the sum of the list. That is O of n time and O of one space. A good interviewer loves when you walk through these options and compare them. Notice what we did in all four problems. We named the pattern or data structures first and only then wrote code. The stacks, the single scan, the two passes and the sum formula all came from tools you already have. A few last tips. If you get stuck, think out loud because the interviewer wants to help and silence gives them nothing to work with. [snorts] Start with the brute force and improve it step by step. Test with an empty input a single item and duplicates. Name your variables clearly. And if you make a mistake, calmly fix it because everyone makes mistakes and what matters is how you react. Practice is what turns knowledge into skill. Solve a few problems each week and after each one review it and ask what pattern it used. And let's finish the whole course with a short review. We started with big O to measure how code grows. We learned arrays, linked lists, stacks and queues queues the basic containers. We used hash tables for fast lookup, trees for hierarchy heaps for priorities and graphs for networks. We studied recursion, searching and sorting the core algorithms and we [snorts] learned the patterns that connect them all. We now have the foundation that every good programmer builds on. Thank you for learning with me and good luck with your next project and your next interview.

Generated algorithmically for Search Engine Indexing.

Summarize Another Video