Datenstrukturen in Python

This is a beginner-friendly introduction to common data structures and algorithms in Python.

This course is top-by-acquashNS, the co-founder and CEO of Jovian.

Data structures and algorithms in Python is a practical beginner-friendly

encoding focused online course that will help you improve your programming skills,

solve coding challenges and ace technical interviews.

You can also earn a verified certificate of accomplishment by completing this course.

Learn more in register at pythondsa.com.

The course runs over six weeks with two hour video lectures every week with live interactive

coding using the Python programming language. You will get a chance to practice and improve your

coding skills with weekly programming assignments consisting of real interview questions and

you will also build a course project that you can showcase on your resume or LinkedIn profile.

This is a beginner-friendly course and some basic programming knowledge will help you follow along

with the course. Don't worry if you're new to programming, you can learn it as you work on this

course with a little extra effort. You will also get to access the course community forum where you

can ask questions, participate in discussions and share what you're working on during the course.

The course is created by Jovian, a platform for learning data science and machine learning

with a global community of tens of thousands of learners from over 150 countries.

I'm your instructor Akash, co-founder and CEO of Jovian and I'm really excited to

kick off this course with you. Register now and invite your friends to join the course at pythondsa.com.

Hello and welcome to data structures and algorithms in python.

This is an online certification course brought to you by Jovian and today we are at lesson one

binary search, link lists and complex idea analysis. My name is Akash, I'm the CEO and co-founder of

Jovian and I will be your instructor. You can find me on Twitter at at Akash and is.

This course runs over six weeks and over the six weeks if you enroll with for the course

work on four programming assignments and build a course project you can earn a certificate of

accomplishment. Along the process you will also learn about common data structures and algorithms

in python and how to use these skills to is coding interviews and technical assessments.

So let's get started then to begin we need to go to the course website pythondsa.com.

See if you open up pythondsa.com in your browser that will bring you to this page. This is the

course page and you can watch an introductory video about the course here. You can enroll for the

course for free. You will need to sign in into Jovian. You can use your Google GitHub or email

to sign in into Jovian. And once you're enrolled into the course, you can also invite your

friends to join the course. The course is still open for enrollments. So please invite your friends

and colleagues. This course is a beginner friendly introduction to common data structures and algorithms

and this course will help you prepare for coding interviews. We have coding focused hands on

video tutorials every week. So you can either follow along with this video you can pause and run

the code as we speak and you can practice coding on the cloud or you can watch the video right now

and you can practice later. In this course we will solve questions from real programming

interviews and you can earn a verified certificate of accomplishment. So let's go to lesson one binary

search link lists and complexity. On the lesson one page you can see a recording of the lesson

once it is completed and you will also be able to see a Hindi version here and all the code used in

this lesson is linked below. So the first set of code that we will look at today is called linear

and binary search. So let's open it up. So this is the first tutorial that we will work through

in this lesson and you will be able to work through it as well and this is part one and there are

a total of 12 notebooks or 12 tutorials we will go through. Now the course assumes very little

background in programming and mathematics but you still do need to know a little bit for instance

you do need to know basic programming with Python things like variables, data types,

loops and functions and don't worry if you don't know them already you can click through and follow

these links. Each of these is a separate tutorial the tutorial will take you about

half an hour or so each of these and you can learn the basic programming with Python in just a

couple of hours. You will also need to know some high school mathematics and if you want to brush

up things like polynomials, vectors, matrices and probabilities you can click through and read

these. But no prior knowledge of data structures or algorithms is required you do not need to have

an extensive coding background. We will cover any additional mathematical and theoretical concepts

as we we need as we go along. So how to run the code what you will see here is the some

explanations and then you will also see some code so you can see here that there is some code written

here and there is some function so the library is imported and a function from the library is used here.

Now to run the code you have two options you can either run this code using free online resources

which is what we recommend or you can run it on your computer locally and you can read these instructions.

I'm going to use free online resources provided by Jovian so we just scroll up here at the top of

this page and click run and then click run on binder. So this will take a second or two

and what we're doing here essentially is setting up a machine for you on the cloud using

a software called binder. It's an open source software and now what you were looking at here

this was actually not a blog post this is actually something called a Jupiter notebook. A Jupiter

notebook is something that can not only contain explanations but can also contain code and you can

look at the code and it's outputs right here in an interactive fashion. So if I scroll down here

you can see that we have all the same content that we were looking at except this time we can actually

run this code. So we can click the run button here and the run button will run the code and here we

click the second run button and that is going to run the second line of code. Now we will be using

Jupiter notebooks extensively throughout this course because Jupiter notebooks are a great way to

do interactive programming you can change the code for example instead of a mad dot square root you can

use mad dot seal and you can change the value here. So Jupiter notebooks are great for experimenting

with code. Now just a couple of tips that you want to do as soon as you run a Jupiter notebook

you can click on kernel and click restart and clear output. What this will do is this will

remove all the pre executed outputs from your code. So you can now see that the output of the

function is gone and you can see that the numbers here go away. So now you can execute the code

line by line yourself and see the output discover the output. And then one other thing you can do

if you want to hide the UI a little bit is to toggle the header and also toggle the toolbar.

Now you might need the toolbar for the run button but there's a tip here instead of pressing

the run button you can use shift plus enter. So if you press shift plus enter that will execute

a cell and that's a pretty handy shortcut. So once again you go on the lesson page

on the lesson page you will find a link to the notebook called linear and binary search.

On the linear and binary search you can read the explanations but you can't run them to run the code

you need to click run and then select run on binder and clicking run on binder will

set up a cloud machine for you and all the code that you see here will get executed on the cloud.

So you do not need to set up anything on your computer you do not need to download anything

we've done all that for you. So let's get started then. This course takes a coding

focus approach towards learning and in each notebook or each tutorial we will focus on solving

one problem and then learn the techniques algorithms and data structures to device

and efficient solution for that specific problem we will then generalize the technique and apply

to other problems. So in this specific tutorial we will focus on solving this problem and here's

the problem we're solving and this is a typical problem that you will come across in a coding

challenge or a coding interview. So here's how the problem goes Alice has some cards with numbers written

on them and then she arranges the cards in decreasing order and lays them out face down in a

sequence on a table. So this is what it looks like. These are cards each of these cards has a number

below it and the numbers are in decreasing order. She challenges Bob to pick out the card

containing a given number. For example she could say Bob I want you to pick out the number 7

by turning over as few cards as possible. So this is a puzzle that's given to us and we're not

told how many cards Alice has. So you need to write a function to help Bob locate the card.

So Alice can put down any number of cards and the target number that Bob has to pick out could be

anything. So we have to tell Bob not not the solution for a specific problem but a general

strategy that he can use to turn over as few cards as possible. So for instance look at these

7 cards and maybe put some imaginary imaginary numbers before them below them and try to figure

out a strategy try to start thinking about the problem. And this may seem like a simple problem

especially if you're familiar with the concept of binary search but the strategy and technique

that we're learning here will be widely applicable and we will soon use it to solve harder problems.

Now before I'll think about the problem and before we start solving it I just want to talk about

why you should learn data structures and algorithms and whether you're pursuing a career in

software development or data science it's almost certain that you will be asked programming

problems like reversing a leg list or balancing a binary tree in a technical interview or

coding assessment. Now it's well known that you never face these problems in your job as a software

developer so it's okay to wonder why such problems are asked in interviews and they're asked

because they demonstrate the following traits and these are very important traits for a programmer.

Number one is that you can think about a problem systematically and then solve it systematically

step by step two and the number two is that you can envision the different inputs and outputs

in edge cases for your problem because programs when you put them out in the while as part of software

can encounter any kind of inputs and as you have thousands or millions of users you will encounter

any and every possible input and often this has many security implications it can take down the

server it can take down your application or you can have a loss of data or loss of property.

You can communicate your ideas clearly to co-workers that's a very important part of

problem solving and most importantly you can convert your thoughts and ideas into working code

and the code should also be readable to other people. So it's not really the knowledge of specific

data structures or algorithms that's tested in an interview but it is your approach towards

the problem. So you may fail to solve the problem but you may still clear the interview or

vice versa you may solve the problem and still not clear the interview. So in this course we will

focus on the skills to both solve the problem and to clear interview successfully. So that's why

you need to learn data structures and algorithms. So coming back to the problem at hand now you

get the problem and you may have been thinking about it and maybe you have some ideas on how to

solve it and your first instinct might be to just start writing the code for it but that is not

the optimal strategy and you may actually end up spending a longer time to solve the problem due

to coding errors or you may not be able to solve the problem at all. So what we are going to cover

here is a systematic strategy that you should apply in interviews or in coding a problems

on encoding assessments or in general whenever you're faced with a problem like this.

So here's a strategy that we will apply. Step one, state the problem clearly,

identify the input and output formats. Step two, come up with some example inputs and outputs

and try to cover all the edge cases. Step three, come up with a correct solution for the problem.

It can be as simple as possible and state it in plain English. Step four and this is a

step that is optional sometimes. Implement the solution and test it using example inputs

and then fix any bugs in your first solution. In step five, analyze the algorithms complexity

and identify any inefficiencies and finally step six, apply the right technique to overcome

the inefficiency and then go back to step three which is come up with a new correct solution

which is also efficient then implement the solution and analyze the algorithms complexity.

So this is the technique that we will apply over and over for the course of six weeks to many

different problems and applying the right technique is where the knowledge of common data structures

and algorithms comes in handy. So this is the method we'll be using. So let's jump into the solution.

Step one, state the problem clearly. Now you will often encounter detailed word problems

and coding challenges and interviews. They will go on for paragraphs and paragraphs. For

instance, here we are talking about Alice having a deck of cards and then shuffling them,

putting them out on a table, talking to Bob etc etc etc. The first step is to state the problem

clearly and precisely in abstract terms because computers don't understand people, computers don't

understand cards, computers understand numbers. So for in this case, we can represent the sequence

of cards as a list of numbers. So a list is a basic data structure and Python.

And the turning over of a specific card is equivalent to the accessing of the value of the number

at a certain position in the list. For instance, if we think of this set of cards being represented

by this list, you can see here that this list is sorted in decreasing order. Then turning over a

certain card is equivalent to accessing that specific element from the list. So turning over card

number two or as we say in computer science, card number one because this is card number zero.

And this is one thing that you might want to get into your head as well that whenever you're counting

always start counting from zero, otherwise you may turn it to many off by one errors.

So this is position zero and this is position one. So if you turn over the carded position one,

it is as good as accessing an element from a given list, which in this case will turn out to be 11.

So these are the positions in the list starting from zero. And now what we have to figure out

is how many elements do we need to access. So we need to access the minimum number of elements

to get to a particular element. So the problem can now be stated as follows. We need to write a

program to find the position of a given number in a list arranged in decreasing order.

We also need to minimize the number of times we access the elements from a list.

So we're finding the position of the given number seven and the position in this case is three.

And we want to minimize the number of times we access elements from the list. So if we go in

this direction for example, we would need to access 13, 11, 12 and finally we discover seven.

We come from this end, we may discover seven, six, five, four and finally we may discover seven. So

definitely coming from the left is better than coming from the right. But is that the best?

That's what we're solving.

Now once we've defined the problem and what you should do is you should try to write down the

problem in your own words and primarily this is for you to make it clear to yourself.

Either speak it out loud to the interviewer or write it down in your own words as short as

make it as short as as long as possible so that you clearly understand what's in it and then

come up with the inputs in the outputs. So there are two inputs here. There's the input cards,

which is a list of numbers sorted in decreasing order. And then the second input is a query,

which is a number whose position in the array is to be determined. And there is one output,

which is position and the position is simply the position of query in the list of cards. For

example, seven is that position three counting from zero of course. And as soon as you've written

the input and output out, you can now write what is called the signature of our function, which is

a structure of our function without any actual code inside it. So now we can call it death,

locate card with cards and query and the single statement inside it called pass because a function

in Python cannot have an empty body, you need to put in at least one statement. So you always put

in the past statement first because it doesn't do anything. There you go. So now we have framed our

problem in abstract terms. And now we have a function signature to work with. Now a couple of tips

here, this is something that interviewers specifically will look for, but also encoding assessments,

because your code is also shared with the company. So you may want to name your functions properly

and think carefully about the signature. For example, here, you should not call your function f1

or funk1 or f or something like that. It's better to call it locate card because that's what it

is doing. And the similar thing is true for variable names as well. Use descriptive variable

names. One because it's good for coding practice in second because as you work on the problem,

you may lose track of what a variable represents. For example, if you call this a and you call this

b. Now 20 minutes down the line, talking about the problem writing different lines of code,

you may forget what a and b represents. So please call them what they represent, even if it can

get a little long. And finally, if you're unable to come up with a function signature,

if you're unable to come up with a simple description, then discuss the problem with the interviewer,

if you're unsure how to frame it in abstract terms. So keep that in mind, and this is really the

first and most important step, which is stating the clarifying the problem statement and stating it

clearly. Do not start coding before you have done this. Otherwise, you may get halfway into the

code and realize that you have not understood the problem at all. So step 2, now we will come up with

some examples. Example inputs and outputs and our goal will be to cover all the edge cases.

So before we start implementing a function, we want to have some examples. So that once we

implement it, the first thing we want to know is it correct? And in general, the answer is no,

because coding, especially when you get getting started is hard because you have to think about

many different scenarios. So and especially, especially interviews or coding assessments are also

stressful situations. So you may not be able to focus and think about all the different things that

you need to keep in mind. So simplest way to reduce the risk of going wrong is to use

test cases. So here's one test case that we came up with. We what we've done is we've taken the

information that we had listed above in the inputs and outputs and we've written it in as code.

So now we have a variable code cards, which is the list of cards, a list of numbers. Then we have

a query, which has the value 7 and then we have the output, which has the value 3. So the expected

output from the function is 3. And once we have a test case, you can test your function at any point

anything you want to test. You can simply pass the input, for example, cards and query into the

locate card function and get back a result. And you can see here right now because there's nothing

inside the function, the result you get back is none. But later you'll start getting back a proper

result from your function. And what you can then do is you can compare the result with the output

of the test case. So in this case, when we compare them, obviously the output is 3, the result is none,

we get back false. Now one thing we will do in this course to make testing easier because we will be

testing our algorithms again and again as we keep improving them is that we will represent our

test cases as dictionaries. So here for example, this this test case will be represented or

every test case will be represented as a dictionary containing two keys input and output. And the

input will contain one key for each argument to the function. So if your function arguments are called

cards and query in the function signature and that's why we wrote down a function signature first

so that we don't get confused here. So if your function arguments are called cards and query,

then we can take one key called cards and put the value of cards there, one key called query,

put the value of query there and then in the output we simply contain, we simply put the output

that we expect from the function. And now you can test the function like this. So how you might want

to test it first is maybe actually passing values like this. So you have test input cards and

then test input query. But there's a trick here whenever you have a dictionary. So here we have

a dictionary with two keys and we want to pass these two keys as two arguments to a function.

So we want to pass cards as the cards are given to the function locate card and query as a

query argument to locate cards. What you can do is you can simply put the dictionary itself

and just write star star. Now if you write star star what Python does is it takes the key

from this dictionary and the values are then used as arguments for parameters with these names.

So there we are now calling locate card on test input and we can compare it with test output.

And you can see that we get back false. So that's one test case for us. But is that enough?

Is that enough for you to now start writing code? Probably not because out in the while your

function should be able to handle any number of any set of valid inputs every pass into it.

And here are some possible variations that we might encounter and it really helps to list them.

In fact while I was writing these variations I realized that there are many cases that I had not thought of.

So even after coding for 12, 15 years almost I still find it really useful to list out all the

scenarios that we can find our input in. So the simplest scenario is that the query occurs

somewhere in the middle on the list of cards. This is what you imagine when you read the question.

This is what is called the general case. But then there are some special scenarios as well.

What if the query is the first element in cards? And what if the query is the last element in cards?

What if the list cards contains just one element which is the query itself? Or and this is

something that I had not thought of. What if the list cards does not even contain the number query?

What if Alice is bluffing? So what should be Bob's strategy then to figure out that the number

does not exist? What if the list of cards is empty? And what if the list contains repeating numbers?

This is again another interesting thing that may not come to mind because we said a list of numbers

and we did not specify that the numbers are unique. So the list can contain repeating numbers.

And finally what if the number the query itself occurs more in more than one position in cards?

So those are eight cases that I could think of. And this see if you can think of any more variations.

And it's likely that when you first heard the problem, you did not think of all these cases.

Because you often tend to just focus on one generic case. It's hard to hold too many cases in

mind. And that's why it helps to list them down actually right them down. In a coding interview or

in a coding assessment or an interview, you may want to put this in comments. If you have a

page coding page, you can just create a comments and list out all the test cases.

And some of these, especially things like the empty array or query not occurring in

a cards are called edge cases because they represent rare or extreme examples. And while edge

cases may not occur very frequently, your program should be able to handle edge cases. Otherwise,

they may fail in unexpected ways or somebody with the with malintensions can use the edge cases

to hack your software. So let's create some more test cases for the variations that we've

listed. And we'll store all our test cases in a list for easier testing. So here we are creating a

list called tests. And this time we will create all our test cases in the format that we

discuss, which is a dictionary format. And we will keep upending them to our list. Now if you

do not understand lists and dictionaries and upending, then you can go back and review some of the

basic material on Python, which is linked at the top of this notebook. So first we take the one

test case that we already have. We put that and we take maybe one more example of the query occurring

somewhere in the middle. So here you can see this is the card list and that the query one occurs

somewhere in the middle, although it's closer to one end. Then here's one case where the query is

the first element. Four and the output obviously the output expected is zero. Here's one case where

the query is the last element minus 127. And this is another thing the numbers could be negative

as well. Something you may want to keep in mind. Here's another one where the card contains

where cards contains just one element the query itself. Now the problem does not state what to do

if the list cards does not contain the number query. And you may often face these questions where

it may not be clear what to do in a certain situation or if a certain situation can occur.

And when you have questions like this, this is a process you should follow. Step one read

the problem statement carefully or ask the interview to repeat the question. So read the problem

statement carefully and you will often find hints and sometimes these hints are just single number

single words somewhere. Often you will also find some examples provided with the problem.

You will also find if you scroll down to the bottom, you will find some conditions,

you will find limits on what the numbers can be, whether they can be integers or can be

decimals, whether they can be negative or positive. So it's important to read the problem carefully

before you start coding and look through the examples. And then ask the interviewer or maybe

post a question on the platform for a clarification. Often it happens that interviewers because

they take so many interviews, they may forget to specify a certain detail. And or they might

expect you to ask the question because you should not be coding with an insufficient requirement.

So to clarify the specifications of the problem is very important. So if you have any doubt

ask the interviewer, even if you are somewhat sure about it but just want to verify, it's a good

idea to ask. Then finally if you are done with all of these and you still do not have a solution,

then you just make a reasonable assumption stated and move forward. So we will assume that

a function will return minus 1 in case cards does not contain query. So if cards does not contain

query, then we return, we expect the equation to return minus 1. Now here is one of the case where

the cards erase empty and obviously then it does not contain the query as well. And finally there's

one last case which is the number itself can repeat in cards. Numbers can repeat in cards

and then the query itself can repeat in cards. So here the query does not repeat,

three does not repeat but the numbers on the in the cards are a do repeat and the last case is

when the query itself repeats. So you can see here in cards the query occurs many times. Once again,

it is not specified what to do here and sometimes it may be okay sometimes the problem statement

may just say that return any one position but more likely than not what you will want to do is you

may want to make it more deterministic and that will also make it easy for you to test the function.

So what we can say we can impose this additional restriction that we will

expect our function to return the first occurrence of query and that will make it easier for us to test

so that when we when we're testing a problem we we know that if we're getting a failure it's not

because of multiple possible answers it but it's because of some issue in our code right.

So you want to get good feedback from failures and that's why you want your tests to be deterministic.

So here is the final test and now we can see the full list of test cases.

So now we can see the list of test cases here. So you have about eight or 10 test cases here.

You may not need to create this many test cases in an interview or a coding assessment

depending on how much time you have but you should create at least a few at least cover

the three or four edge cases a good number to aim for would be five and this will

not only help you in the coding interview help you solve the problem this will also be

appreciated by the interviewer because it shows that you're thinking about the problem.

So definitely take a minute or two. Now we've spent 10 15 minutes talking about this but once you

start applying this technique over and over you will see that you will start creating test cases

in seconds. So as soon as you read the problem and you state the problem find the

find the input format find the output format write a function signature and write the test and then

you will start working on test the ideas will automatically start coming to you and within maybe

two or three minutes you will be done with both all two both of these steps.

So great we now have a fairly exhaustive set of test cases and creating test cases before

hand allows you to identify different variations and edge cases and sometimes it may happen that

you may have no clue how to work on the problem you may feel completely confused but if you

simply start writing multiple test cases and start looking at them like literally just staring

at the test cases the question and the answer the solution will reveal itself to you.

So don't underestimate the power of writing things down and don't stress it don't stress out if

you can't come up with an exhaustive list of test cases because this takes time it's a skill that

you cultivate with time. So what you can do is you can list out maybe the test cases that come to

your mind right now and put them in a single place and keep coming back whenever a new test case

comes to mind while coding or while discussing or while analyzing you can just come back to the

same place and write down the test case. The important thing is that you have a single place where

you're listing all test cases. So we've written our test cases now and now we can come up with

a correct solution and how do you come up with a correct solution not by writing code but for

I first stating it in plain English. So your first goal and by correct we do not mean the best or

the most efficient solution. First we want to solve the problem. We want to figure out where

the particular number lies in the list and not to minimize because that's solving two problems

at once and sometimes that can get tricky. So first aim for correctness then aim for efficiency

and the simplest or the most obvious solution which almost always exists and is almost always

very easy to see involves checking all the possible answers and this is also called the

brute force solution. So in this problem coming up with a brute force solution is quite easy.

Bob can simply turn over the cards in order one by one till he finds the card with the given

number on it. So this is what this is how it might work. If we want to implement it in code and this

is where writing it in your own words becomes important. So we create a variable called position

inside a function with the value 0. Then we check that the number at the index position in the

card list equals query or not. Now if it does since we are starting from the beginning

if it does then position is the answer and we can return it from our function. But if it does it

then we simply increment the value of position by one and then we repeat the steps. So we go back to

step 2 and then we check whether the number at the index position on in cards equals query and once

again if it does we return position. If not we increment the position once again and repeat and we

repeat that till we reach the last position. And if the number was not found we return minus one.

So it's a simple 4 5 step description. It doesn't take very long. You can either say it out loud

to the interviewer. They will also appreciate it that they will know. You know you may know that

you know the brute force solution and you may not say it because it seems too simple or obvious.

But the interview does the interviewer doesn't know that. So it's important to state the

brute force solution. You may say that the brute force solution is fairly straightforward

and it goes like this. Steps 1, 2, 3, 4, just take 30 seconds. But at the very least it informs

the interviewer that you're able to think of some solution. And it happens very often. I've seen

it in interviews where 30, 40 minutes have passed out of 45 minutes and not a single solution

has been proposed so far even though many lines of code have been written. So it's important

to state your solution and if you state your solution the interviewer will also help you and

correct you as you go forward. So it is a collaborative experience. It is a discussion. So use that.

And if you are in a coding assessment you may just want to write out a few comments.

And what we've implemented here is congratulations. It's just our first algorithm. And then

algorithm is simply a list of statements, a list of steps that can be converted into code and

executed by a computer on different sets of inputs. So this particular algorithm is called

linear search because it involves searching through a list in a linear fashion element by element.

So now we're ready to implement the solution and just a quick tip as I've already said always

try to express the algorithm in your own words and it can be as brief or as detailed as you like

and don't underestimate the power of writing. Writing can be a great tool for thinking.

It's likely that you will find that some part of the solution is difficult for you to express.

And that simply suggests that you are probably unable to think about that part clearly.

So the most more clearly you're able to express your thoughts. The easier it will be for you

to turn it into code and you will not have to come up with a strategy while you're writing the code.

So you can focus on coding and focus on avoiding errors. And that brings us to the next step.

Implement the solution. And then test it using the example inputs. Now you can see how everything

comes together. We've already know what the function signature looks like, what the inputs look like.

We already have some test cases and through the test cases we've also identified what are the

different H cases we need to handle. And we've already written out a description or of description of

what the algorithm looks like. And in fact, what you can do is you can simply write out

comments within your function as the English description and then you simply need to fill out

code for those comments. So for instance, here are the five steps that we are just written down.

Create a variable position with the value 0 set up a loop. Check if the element is matches the

query. If yes, the answer is found. If not increment the position and then go back and then check

if we freeze the end of the array. If we have then we return minus one. So the code now is

pretty straightforward. Now we create the position variable 0. We set while true. So while true

kicks off a loop and we just want to first set up a loop and then we can break out of it when we

need to. Then we check if the element at the value position matches the query. If it does

where it done the position. If it doesn't. So if it doesn't, then this we come to this part.

If it does, then the function exists and none of the code gets executed. But if it doesn't,

then we increment the position. And then we check if we have reached the end. Now if we have

reached the end, obviously, we don't want to continue. So we can simply return minus one and exit

the loop and exit the function itself. But if it, if we have not reached the end, then we go back to

the top of the loop and now position starts out with value 1. So we check value 0 1 2 3 so on

up to the end of the array. Simple enough. Great. So now we have our first function. And let's test

our function with the first test case. So here's our test case once again. And we can simply

call locate card with the test input and the cards in the query. And this is the result we get.

And you can already see that the result matches the output. And that's why when we compare them,

we get the value true. So yeah, the results match the output. And because this is something that

you should be doing very often in this course, we have put together a small function for you

within the Joven Python library. So the Joven platform also offers a Python helper library.

That is that contains some utility functions. So we put together a small function for you

called evaluate test case. And you can write it on your own as well. But you can use this library

so let's install the library. We will install the Joven library using pip install Joven minus minus

upgrade. And then from Joven. Python DSA. So Joven is the name of the library. And then inside

the Joven library, since we have many courses, the Python DSA course, the utilities for this course

are present inside the Python DSA module. From that module, we import the function evaluate test case.

And finally, we can call evaluate test case. And then we can give it the function that we want

to test. So we want to test the locate card function. And the test case, the test case needs to be

defined in this format. So all it is going to do is it is going to pick out the input,

pass it into the function, get the output, compare that output with the expected output. And also

print some information for you to see. So here's what it does. It prints out the input.

It prints out the expected output. It prints out the actual output. It prints the execution time.

And this is something that will become important later and tells you whether the test has

passed or not. So it's nice to have this, because we don't have to look through the output

and import and compare them, especially when you're in a situation where you need to think fast.

It's helpful to create a small function that can just print pass or fail for a test case.

So now while it may seem like we have a working solution, because our test cases passed,

we can't be sure about it until we test the function with all the test cases. So for doing that,

we can use the evaluate test cases function. So just as you have evaluate test cases,

you have evaluate test cases. Also part of the joven library. And you can call evaluate test cases

with the same function locate card. And this time pass it a list of test cases. Each of the

test cases is a dictionary. Again, you don't have to use this function. You can simply put

things into a loop. So you can always just do four test intests. And then simply call evaluate

test with locate card and test. Or you can even just directly call locate card with

the test inputs and the test out and compare the output with the test output. So you can do this as well. And you can simply print that.

So here's a simple way to do this. What we are doing here.

But what we'll do is we'll use the evaluate test cases function because it prints out a lot of useful information for us.

So now you can see that it prints out case case by case. Now test case 0. We have input expected

output actual output. The case has test cases passed. That's what we saw it. In fact, it's the same test

with just did. Test case 1 passes as well. Test case 2 passes. Test case 3, 4, 5, 6. Okay,

all of them are fine. Okay. Test case 6 seems to have caused an error. So here is the error.

It says list index out of range. So that's okay. It's perfectly all right for your functions to

encounter an error. So the first thing they're most important thing is not to panic. In fact,

it's a good thing that we know exactly where the function is failing. If you look back here,

you can see what the issue is. And then we'll see how to fix the error. But one good strategy to

approach this is to keep in mind that there will always be bugs in your code. And approach

writing code not with the assumption that your code will be correct. But go with the default

assumption that your code will be wrong. That there will be issues. What that lets you do is

one, you do not feel demotivated or you do not panic when you see an error. And second,

you then tend to be a little more careful while actually writing the code. So the way you should

be writing code is every time you write a line of code, you should be asking yourself,

how can this line of code go wrong? Or in this particular case, how can cards position

equals equals query in a if statement, go wrong and throw an error. And let's look at it.

One easy way to check this is to add what is called a logging or what is called printing the

information inside a function. So we'll just rewrite a function. In a locate card function,

we will put in cards, we will put in query. The exact same function that we have, we'll set the

position. But before we create the value, we'll simply print the cards in the query. So just for our

information, just so that we can see what the function is working through, we can get some

visibility into the function. We print out cards and query. And then while true, so this is the same

loop. At the beginning of the loop, we will print out the position that we are tracking.

So let's do that. We've simply added some print statements and this print statement will

give us an insight into the inner working of the function. Now if you do not put in a print statement,

then you will have to work it out yourself by reading the code and executing it in your head.

It's always easier to just print all the information and then print it nicely, just say cards

and query. You know, we could also have done this without saying cards here. But then that would

make it a little harder to read than that would be more cognitive overload apart from already

dealing with the stress of solving an error. So just add nice, pretty print statements to make it

very obvious what we're printing. So let's see now, let's get the test case out. So let's get from

test 6, get the input, get the cards, get the query as well and pass it into locate card.

And now we see that initially the cards array is empty in a query 7 and the position is 0.

And then we encounter an error. We encounter the error list index out of range on the line cards position

equals equals query. And now at this point, it should be fairly obvious what the issue is.

The issue obviously is that we have an empty list and empty list has no elements,

but we're trying to access the position 0 which is in normal human condition, the first element

of a list. But there is no first element to access and that is why we get the error list index

out of range. So this is very important whenever you get an error, do not try to start looking at

the code first, just try to understand the error first. And if you're unable to understand the error,

just add some print statements. There are tools like debuggers that people use, but I personally

in 15 years haven't used a debugger. Maybe use it a couple of times, but I don't know how to use it.

Print statements are really simple, you just put them in, chuck them into the function, wherever

you need them as many print statements as you need with nice clear messages, make it very obvious.

And that will almost certainly solve the issue for you. So the card's array is empty, we cannot

access position 0. So what's the solution here? The solution obviously is that before we access

anything from a list, we need to make sure that we can access that list. And this is the way to do

it. So now we've written a function slightly. We once again start out with position 0, but this time

instead of putting in a while true, instead of assuming that we can access the zeroes element

of the list, we say that the position should be less than the length of cards. Now if you have

a card's list of n elements, the indices go from 0 to n minus 1. Or in the case of zero

elements, there are no indices to access. So the position has to be less than the length of

cards for you to be able to access it. And in this case, the length of the cards will be 0. So

0 is not less than 0. So the while loop will not run at all and we will directly return minus 1.

But if the card does have elements, then we can check the element at the value position

compared to the query and return the position. If it does not match the query, we can increment the

position. So that was a fairly straightforward fix, easy save. So let's test the failing case again.

Great. So it looks like the failing case is now passing because we have output minus 1 and

the expected output matches the actual output of the function. Minus 1 because the query does not

exist in the array which is empty of course. Now this is not enough. Every time you make a change

to the code, you want to go back and test all the test cases because what happened is while

fixing one error, you may introduce another error. And that is where having a good set of test

cases is very important. So let's run evaluate test cases once again. You can see here this time that

all the test cases are passing. And it's just nice to it just makes you feel good as well.

Makes you feel motivated as well to see that a bunch of test cases are passing.

Now in a real coding assessment or a real interview, you can probably skip the step of implementing

and testing the brute force solution in the interest of time because it may take about 5 to 10

minutes to implement the solution and then if you have errors in the solution, it may take

some more time to fix those errors. So it's generally quite easy to figure out the complexity which

we'll talk about in second of the brute force solution from the plain English description. And that

is why you should first state it and plain English with which only takes around 20 seconds or so.

And the computer doesn't throw errors at you for speaking. So you can just state the plain English

description and move on to talk about the complexity and start optimizing it. But while you're

practicing always, always implement the brute force solution too. And there's an important

reason why you should know how to implement the brute force solution because in case you're not

able to figure out the optimal solution to the problem, you can still go back and implement the

brute force solution and in a lot of cases that's okay. Sometimes interview us ask hard questions

just to push your boundaries a little bit. But if you're unable to figure out the optimal solution,

then they will allow you to implement the brute force solution. So that is why you should state it

and that is why you should know how to implement it. Okay. So we're done with so we're done now with

the implementation of our brute force or simplest solution and now we need to analyze it.

And this is where we'll now learn about what is called the complexity of an algorithm.

What does it mean? Now recall the statement from the original question,

Alice challenges Bob to pick out the card containing the given number by turning over as few

cards as possible. But right now what we're doing is we can simply turn over cards one by one.

And before we talk about what does it mean to minimize the number of times we turn over cards

or the number of times we access elements, we need a way to measure it. And let's think about it.

You know it's as simple as just thinking about it. Since we access the list element once in every

iteration so here's our code, our code is pretty straightforward. And this is where we are accessing

an element from the list. So since we access the element, since we access the element once

in every iteration for a list of size n, we access the elements from the list up to n times

because we may have to access this element and then this element and this element and so on.

So Bob may need to overturn up to n cards in the worst case to find the required card.

Now let's introduce an additional condition that suppose Bob is only allowed to overturn one card

per minute. So that means it may take him 30 minutes to find the required card in the worst case,

if 30 cards are laid out on the table. Now is this really the best he can do?

Or is there a way for Bob to arrive at the answer by turning over just five cards and save

25 minutes instead of turning over all 30. And this field of study and by the way Bob in this case

is represented of what a computer does and a computer takes some amount of finite time to perform

each instruction. So each array axis actually takes some time although it's so fast that we do not

see it especially for small inputs. But this is something that will become increasingly important

as we go week over week where we see that we will start to see the limits of how long it takes

computers to solve certain problems. So the field of study concerned with finding the amount of time

or the amount of space or the amount of other resources required to complete the execution of a program

is called the analysis of algorithms and the process of figuring out the best algorithm to solve

a problem is called algorithm design and that is what we are doing here. We are actually doing

the analysis of algorithms right now and algorithm design next. So there are a couple of terms

we need to understand and then we will go back to writing code. First thing is complexity and the

second thing is the big one notation and both of these are terms that you will hear very frequently

in when you're talking about data structures and algorithms when you're talking about

coding interviews assessments. So these are terms that you need to understand and they're fairly

simple terms although the term itself is complexity but all it means is that the complexity of an

algorithm is simply a measure some measure of the amount of time or space required by an algorithm

to process an input of a given size. Example if you have a list of size n,

another complexity is the amount of time required or the amount of space required on the ram

to process an input of that size. Now, unless otherwise stated the term complexity always

refers to worst case complexity. So it's possible that the Bob turns over the first card and that is

the answer but we always talk about what is the longest or the highest possible time or space

that may be taken by the program to process an input right. So we need to design our programs

keeping the worst case in mind. Now in case of a linear search which is what we've implemented just

the time complexity of the algorithm is some constant C times n assuming n is the size of the

list n is the number of cards right. So now this constant C obviously depends on the number of

operations that we perform in each iteration. So in each loop for example we have four to five

statements and then the time taken to execute a statement on your specific hardware. Now if you have

a two gigahertz computer that may be twice as fast as a one gigahertz computer. If you're running

it on a phone it may be different. So the C captures all of these things. So information about

the number of specific operations that we perform in each iteration and information about

the actual hardware that you're running on. So C n is the time complexity and n is the size of the

input. So in some sense what we understand from this is that the time complexity is proportional

to the size of the input and that's the important part here. The constant you know it doesn't

change as you change the input the constant doesn't really change. Now similarly the space complexity

now since we're already given an array the additional space that our linear search requires

is simply a single constant when we are calling it C prime or C dash and it is independent of n.

So no matter how many no matter how large a list is given to you and the list is already present in

memory we just need to allocate one new variable called position and that variable is used to iterate

through the array and it occupies a constant space in the computer memory because we keep

going updating the variable. So the space complexity is C or constant it is independent of n.

Now what we do normally is to represent the worst case complexity we often use the big

own notation and in the big own notation what we do is we drop any fixed constants

and we lower the powers of the and we drop any fixed constants and we drop any lower powers

of variables. So the idea here is to capture just the trend just the trend of the relationship

between the size of the input and the complexity of the algorithm. For example if the time

complexity of an algorithm is some constant times n cube plus some constant times n square plus some

constant time n plus some constant where n is the size of the input in the big own notation we simply

say that it is order of n cube which is that you know in the long run in the if you just study the

trend it the trend will be some something which looks a little bit like the n cube function and

it may be offset by a constant or such. So putting it this way the time complexity of linear search

is order n because we just drop the constant C and the space complexity is order 1. So we again

drop the constant C prime and we'll see why it's okay to drop the constant sometimes you

may find that okay we are not exactly doing n iterations but we're doing n minus 1 iterations so

we drop the minus 1 sometimes you will find that we are just doing n by 2 iterations and that's

simply half a fan so we drop the half and you might wonder that okay that that might take twice

or 3 times the amount of time how why are we dropping that constant because that's probably an

important thing to keep in mind but we'll see we'll see soon as we implement our efficient

solution to the problem. So before we move forward before we optimize the algorithm we are just

going to save our work because this notebook as I mentioned to you is running on an online platform

we've set up everything for you you've not had to install anything but because thousands of people are

using this using this platform this will shut down this will not keep running forever and what

you need to do is you need to save your work from time to time and here is how you can save your

work and then pick it up everything happens on the joven platform you there's no need to download

anything although you could download it if you want but you there's no need to download anything

so all you need to do is use the joven library once again we've got another helpful function for you

so you say import joven and then run joven.com it so you run joven.com it and then give it a project

name the project name by which you want to identify this specific notebook and then there are some

other arguments is not too important so you can even skip this and that should be perfectly fine

so now when you run joven.com it we will capture a snapshot of your notebook from this online platform

or wherever it is running even if you're running it on your own computer we will capture a snapshot

of your notebook from your computer wherever it's running and we will upload it and give you a link

where you can access it so let's open up this link here so now you will be able to see this page

called python binary search and it will be on your profile and you can see you can scroll down and see

that it contains all the explanations and it contains all the code so this is a read only version of

the jupiter notebook so the read only version of the jupiter notebook obviously does not require us

to keep servers running so that you can run this code and when when you need to run it you know

your work is saved to whatever extent you have executed things and now when you need to run it you simply

click run and then click run on binder once again okay so and that is how you resume your work so

what this will do is this will set up a new machine for you and on the new machine it will post

the jupiter notebook and it will start up the machine for you open up the jupiter notebook and you will

be able to start running the code and not just you now you can make a notebook's public or you can

keep them private you have multiple viewership options so your public and private not just you but

anybody else you can take this link and tweet it out if there's an interesting problem that you

worked on you want to tweet it out you can just share this link online and anybody will be able

to read through your solution and they can run it as well right in fact the notebook that I've shared

with you is hosted on my profile so jupin is not just a platform for you to learn it's also a platform

for you to build a repository of projects now if you go back to your profile you click on your profile

look click on the jupin logo and you can see here that you will find a notebook step and in the

notebook step you will find all the notebooks that you have worked on in the past okay so anything

that you have committed using jupin.com it you will be able to resume working on it so that's that's

how you save your work and keep saving your work from time to time all you need to do is run

jupin.com it you do not even need to put in this project argument this is just something if you

want to actually give you a project a name otherwise the name will be picked automatically so just keep

running jupin.com it from time to time especially if you're leaving your computer for

half an hour or so then and your computer gets goes to sleep then this server will shut down and

you may lose your work coming back to a problem we've just implemented linear search and we

understood that it has the complexity of order n which is and that's why it's called linear

it runs in a linear time is another expression that is used it is also called linear because

we are going through the array step by step now the next step is to apply the right technique to

overcome this efficiency now of course we've not learned any technique saved but we can

probably figure it out if we think about it and maybe this is something that occurred to you

right at the beginning and the idea that occurred to you is something that we will now implement

so at the moment we are simply going over the cards one by one and not even utilizing the fact

that they're sorted and that's why our approach is pretty poor we're basically checking everything

so it's not a great solution but it would be great if somehow this would be the best case

if somehow Bob realized somehow Bob could guess the card at the first attempt that would be perfect

then that would be an order one that would be a constant time solution but with all the cards

turned over it's simply impossible to guess the right card now the next best idea is to maybe pick

a random card so maybe let's say Bob picks this card and this card turns out to be a 9

now Bob can use the fact that the cards are inserted order so if this card turns out to be 9 that means

all of these cards have numbers greater than 9 and the target card is 7 so the target card cannot

lie in this region so the target card has to lie in this region and just by picking a random card

rather than picking the first card Bob has eliminated four out of seven cards to be checked right so

with one check Bob has eliminated a total of five cards one to three four five and of course if

this number turns out to be seven perfect grade guess but even if it doesn't we've still

eliminated quite a few if this number turns out to be less than seven we've still eliminated three

cards so that's the basic idea here that we pick something not from the edges but somewhere in the

middle now what is the best place to pick something in the middle now obviously when we have

picking a card we do not know whether it is going to be less than or greater than the number that we

want especially when everything is closed so we it's best to just pick the middle card so that

whichever case turns out it turns out to be we're still left with as at most three cards to process

right so if you pick this card and it doesn't turn out to be seven you either need to look at these three

or you need to look at these three so that is the strategy we'll follow and this technique is

called binary search and why do it just once just keep repeating it so each time you pick the

middle card and you can eliminate half of the array and this is what the strategy looks like so here

we have the array and in the array we want to figure out the number six of this slightly different

problem but still decreasing order we want to figure out the number six so we access the middle

okay we compare it with six now it is not six okay it was a bad guess no problem but we know that four

is less than six so that means that six lies to the left of four so we've certainly eliminated half

of the array we've done one access and eliminated half of it and now we left with three numbers we

pick the middle number we get seven seven is greater than six that means the number lies on the right

now we're left with just one card we over turn that last card or we check that last number

okay it is equal to six great if it is not well nothing more left to check all the numbers here

are greater than six are less than six and all the numbers before this are greater than six so if this

number is in six then there's no six and just like that for an array of seven elements we have done

just three checks and arrived at the answer and that was the worst case right it means it will never

take you can verify that it will never take more than three checks if six comes at this position

we guess it immediately if six comes at this position or this position we guess it in two checks

and then if six comes at any of the other positions we will guess it in three checks so that's pretty good

and now the idea if you if you read this part it says apply the right technique to overcome the

inefficiency and then repeat the steps three to six so now we're going to go back to step three

which was come up with a correct solution for the problem and stated in plain English and we have

come up with a solution already we just need to state it so here is how this technique called binary

search is applied to the problem it's called binary because well we take a left and right decision

so first we find the middle element of the list if it matches the query number then we return

the middle position as the answer and if it is less than the query number then we search the first

half of the list and if it's greater than the query number then we search the second half of the list

so the exact thing that we saw here we apply it here and finally if no more elements remain

we simply return minus one so let's just save our work now let's from this point on we'll

keep saving our work from time to time using Jovi.com it so now we've come up with the algorithm and

you can again it's important to write it in your own words whether you want to write a short

description a paragraph or a step by step guide but write it in your own words and you'll do this

in the assignment so next implement the solution now and test it using the example inputs so here's

the implementation so what we'll do is we will look at once again let's go back to this visual

representation and we will keep a track of our search space so current initially our search

space is the entire array so that means we have an array of seven numbers so our search

space goes from position zero to position six and slowly we'll keep reducing our search

space over time so to keep track of the search space we will create two variables low and high

low will have the value zero which is it will point to the first position in the array and

high will have the value pointing to the last position last valid position in the array which is

which is land cards minus one so while low and then the while loop becomes very simple

because as long as we have at least one element in our search space we can go ahead now to have

at least one element in our search space the low value which is the starting index should

be less than or equal to the end value right so while low is less than equal to high because if

the starting index is higher than the end index basically we've exhausted and we've

covered the entire list and there's nothing more that we can search for so we should

exit at this point okay so now once we have once this condition is satisfied and it is initially

let's say you have seven cards low is zero cards is lend card minus one is six then you find the

middle position and you can get the middle position by doing low plus high divided by two and now

let's start applying that strategy here where we say that every time we write a line of code we

should think about how it can go wrong now if you write it like this low plus high divided by two

and think about how it can go wrong okay low plus high may not be divisible by two

and if low plus high is not divisible by two you may end up with a decimal number now if you do end

up with a decimal number in fact the division operator and Python always remains a retainer

floating point number then you cannot use it as an array index because we want to use this

as a position within the array so that's why we need the double slash which is the which is

the integer division which simply returns the quotient so we get the middle position and then we

get the number at the middle position so we also get cards made so we access that element from

the array now this is where it makes it easy for us to count the number of times we access

because here is one axis happening inside the list and there are no other excesses

then we get the mid number and a remember last time we faced an error and we had to add print statements

you might as well just add print statements right away so here's what you can do we can just

print the value of low the value of high the value of mid and the value of mid number what this

will do is this will help you check whether the number is working as expected whether the function

is working as expected or not so now here comes the actual check the meat of the problem

if the middle number matches the query then we return the middle number great we found it well done

now if the middle number is less than the query remember the elements are inserted array

and we are looking for the number query now the middle number is less than the query

so that means the query probably lies to the left of it because the query because the elements

are decreasing order right so if the query lies to the left of it so then we need to search

we decrease the search space from the beginning to the position just before the middle number

right so what we can do is we can simply set high to mid minus one on the other hand if mid

number is greater than query so that means because of the decreasing order of the array the query

lies to the right now we need to move the starting of the search space to beyond the middle number

so we simply set low to mid plus one and that's it and you can see that we've written a

we've used if LF LF loop here so LF stands for L safe in Python and here the last condition

could might as well just have been L's because there are only three possibilities either

that they're equal or mid number is less or it's greater but sometimes it's nice to list out

all possibilities just to make it super clear and it makes it easy for you while debugging fixing

issues as well okay so that's our binary search based algorithm and finally when we exit out of the

loop if you have not returned the middle number if you've not exited the function yet then we

return minus one that the number was not formed so let's test it out using our test cases and we

have our handy evaluate test cases function here but you can also test it manually if you want

by passing individual test cases but I'll just do this from now on so great so now we have test

case 0 this is the input and this is the query and it passed here we have test case 1 this is the

input and this is the query and it passed and now because we have these print statements we can

clearly look into our test cases and actually tell if this is tested correctly or not because

now you can see here that we started out with low 0 high 7 and mid mid value of 3 so 0 1 2 3 we

found the number 7 the query is 1 so we need to check this half of the array and that's exactly

what we did we moved low to 4 and high remains 7 then mid number became 3 so that means once again

we need to check this half of the array and then we check this number and then we found the output so

now you can see exactly how the algorithm works and this is in general what you want as a programmer

you want to have a full understanding of the code that you've written you don't want your code

to work incidentally you don't want it to you don't want to be in a position where you are just

fixing things they're trying out different things and somehow at once the code works you want

to be in complete control you want to know that these this is exactly what the code is doing

and if it is failing why it is failing so we go to test case 2 3 4 5 6 looks good looks like we

may have solved everything or probably not so test case 8 seems to have failed so test case 8

is this number this list and this list contains repeating numbers and not just repeating numbers but

the query itself occurs multiple times and now if we look here and maybe let's go go down and

evaluate just a test case separately so here we are now using the singular version of the

evaluate function so if you look here you can see you have 8 8 6 6 bunch of 6 is then 3 2 2 0

the query 6 so we start out with the low of 0 higher 14 total of 15 elements that gives you a

middle position of 7 and the mid number at that position so let's count 1 0 1 2 3 4 5 6 7 okay

and the mid number at that position is 6 great 6 is also the query so that's why our function

returns 7 but remember that we had decided that our function should return the first position

of the number within the array so our function is failing that condition and why is that happening

because unlike linear search where we start from the left and so we will always bump into the

first position because of the decreasing order of elements so we'll hit will encounter this 6

before we encounter this 6 binary search does not access elements in an order it access elements

sort of randomly if the still strategy but it goes left and right and it also depends on the

values of specific elements whether this element is accessed before this element can depend on the

value of let's say this element right so as such it's kind of a pseudo random kind of order

and so we need an additional condition to keep track of it right so how do we fix it

so the way to fix it is actually quite simple when we find that the middle position in a particular

range is equal to the query we simply need to check whether it is the first occurrence of the query

in the list or not that is whether the number that comes before it is it equal to query or not

if the number that comes before the middle element is also equal to query then obviously the

middle element is not the first occurrence so that simply means that we can go back and because

it can occur multiple times before that simply means that we can now search the left half on the other hand

if the middle element if the number before the middle element is not equal to query and obviously

because it is a sorted list it will be greater than query then all the numbers here are going to

be greater than the query and so this must be the first or the only position okay so make sure

you understand that this must be the first or the only position where the query occurs so once again

to make it easier what we will do is because there is some logic involved here what we will

will define a helper function called test location and this is a very helpful thing that you can

do every time you find that okay you have to cover these special cases and your function may

start to get slightly longer and slightly more complicated what you may want to do is create a

helper function and a good rule of thumb is not to have functions that are more than 10 lines of

code or so I try to keep my functions below 7 lines of code because 7 8 lines is approximately

the amount of information that you can hold in your head at once if your function is about 7 8 lines

you can probably take a quick glance and tell what it is doing identify issues but anywhere beyond

that it is very hard and if you are writing functions that are going into hundreds of lines

please stop doing that please start breaking your code into small functions

there is a there is a code by I forget who it is by but he is a creator of I think it is Eric

Meyer he created the RX library for reactive programming and he said that great programmers

write baby code which is really small bits of code that anybody can understand with a single look

so you should be writing as many functions as many small pieces of code small pieces of logic

as possible so let's see our test location function its purpose is to take the query and then take

just a specific position so forget about binary search for now just take a specific position

and tell if that position is the answer and how do we do that we first get the mid number from the

cards so we get a mid number from cards so we then we print out mid and we print out mid number

and then we compare the mid number with the query so this is the special case that we need to

handle this is where we had the error now what we need to check if if the element before the mid number

is also equal to query so if the element before the mid number is also equal to query then we need to go

left so just to make it super clear what we do instead of setting high low etc we simply say

that we need to go left so we will return the actual string left but one thing to keep in mind here

because once again whenever you're accessing an array you need to make sure that the index is valid

so we simply check that mid minus one should be greater than or equal to zero that we made

is not this position and which can happen as your search space decreases for example if this is your

search space your mid will actually be this position so if it is equal to if the number before the

mid number is equal to query then we return left otherwise we return found once again making it

very obvious that we have found the number so we return found else the other case is if the mid

number is less than query that means that the query lies on the left because of the decreasing order

of the list so once again we need to search on the left else it returns right so a test location

simply tells us whether we found the solution or we need to look on the left or we need to look

on the right now in sometimes you will see programs specially in C++ Java return something like

minus one zero and one and then use that to represent whether you should go left and right

but Python is a high level language and strings are first class sings are first class feature of

the language so just use strings because they're really descriptive they make your code readable

somebody else reading your code will be able to understand now if you're looking at minus one plus one

etc that is going to be difficult for people to understand so now we can now simplify a locate card

once again we have our low high land cards minus one zero and land card minus one the

while loop is the same and we print low and high as well so we're planting row and high inside

the locate card function and then we are printing mid and mid number inside the test location function

wherever is the right place to print something you printed then we get the mid position

and now we simply call test location so we're testing if mid is the answer and if it is not

the answer should we go left or should we go right now that makes it really simple because now

we get this result and we check this result and if it says found then we return mid that's the answer

if it says left then we return mid minus one or then we simply move high to mid minus one

and if it returns right then we simply set low to mid plus one so we are simply changing the

start position of the search space to after the mid element and here we are changing the end

position of the search space to before the mid element right so this makes it extremely obvious

and it's really hard to go wrong when you write code like this especially so when you have

and binary search problems are specially tricky because they always have certain these special

cases that you need to handle and if you start handling them within this if loop so now you have

a while loop inside which you have an if loop inside which you have another another if statement

and it can get pretty tricky and difficult to debug so let's evaluate that test case and

looks like that test case has passed this time perfectly you can go through the logs here to verify

let's evaluate the test case all the test cases as well we should do this every time we change

the function and that is why it's helpful to have a function where you can every time you make a

change you can just run the test and on a coding platform like elite code or hacker rank you will

be given some test cases although those test cases will not be visible to you so you can

submit your solution but you may not get an actual result you may not get to know what the test

case was or where your answer was wrong and that's where you may want to create your own

test cases if you're getting a lot of errors and in fact once you've written out the algorithm

you may realize that maybe you need to add more test cases what if the number lies in the first

half of the array what if the number lies in the second half of the array so this was not an

important factor when we were not thinking about binary search but now that we're thinking in

this direction of splitting the array into half we may want to add some test cases where the number

lies exactly in the middle in the left in the right and the simplest way to do that is now go

back to the test array so you can open a you can create a new cell here by pressing the character

B so if you click outside and press a character B you can create a new cell and then you can simply

do test.append and then write your test case so here is the final code for the algorithm

without without the print statements so we have test location and then we have locate card

and try creating a few more test cases to test your algorithm more extensively and once again

at every step we are going to save our work by running joven.com it.

Now we're down to analyzing the algorithms complexity and identifying inefficiencies if there

are any. Now you may have just read online you can actually look it up just search for complexity

of binary search and you will read and you will find an answer but and you may even just say that

in interviews but it's always nice to just come up with that answer from first principles it's

always nice is especially in an interview if you can talk through it if you can talk through

why it is order why it is whatever it is and we'll see what that is.

So now let's once again try to count the number of iterations in the algorithm because we need

to minimize the number of times we access elements from the array and to do that we know that in

each iteration we are accessing the element just once and then we are comparing it so we're doing

a bunch of other operations but in each iteration we're accessing one element so we need to count

just the number of iterations the number of times the y loop was executed. Now if we start out with

an array of n elements then each time each time the size of the array reduces to half for the next

iteration. Now that's roughly true because when you check the middle element and then you decide

whether to go left or right it's actually probably n by 2 minus 1 if n is even and if n is

odd it is the floor of n by 2 but again with algorithms with complexities we are generally

want interested in studying the trend so we can ignore that small part in the calculation.

So let's say the important part is that even it's okay to over estimate a little bit but

try not to underestimate. So after the first iteration we may be left with the search

space of size n by 2 it may be slightly less than that but it's okay to over estimate.

So we have n so we after n we have after the first iteration we are left with a search space of

n by 2 then we split it into half again so next time we may be left with a search space of n by 4

which is n divided by 2 square and then then we may be left by we may be left with n by 8 and it's

possible that at any of these iterations we may just exit because we may have found the right number

but what we always try to analyse is the worst case complexity of an algorithm what is the longest

possible amount of time or the largest amount of space it can take. So right now we are talking

about time because we are counting iterations and each iteration takes some time.

So n by 8 after iteration 3 that's 2 to the power 3 and I think then you can start to see the

trend here that after the k iteration you will end up with n divided by 2 to the power k

elements. Now when does the iteration stop? So the final iteration is on an area of length 1 and

that is when we access that last element and check whether after all this checking the last

element is equal to the index or not. So we can do n divided by 2 to the power k and if we

set that to 1 we can rearrange the terms and we get back n equals 2 to the power k. So after the

case iteration if you want to be left with one element then that means n divided by 2 to the k should

be equal to 1 or n should be 2 to the k or in other words k should be equal to log n. Remember

logarithms and here obviously log refers to log to the base 2 but what I will argue is that

you can change the base of the logarithm and that will simply add a constant. So that will simply

if you are taking the natural log then that will simply add a constant here and remember when we

talk about time complexity we ignore constants. So we can just generally say that our algorithm

binary search has the time complexity of order of log n. That means as the input grows,

the amount of time taken by binary search is proportional to the logarithm of the number

of elements in the list pass to it or the amount of time taken is logarithm to the size of the

initial search space and you can verify this you can verify that the space complex you can

you can check this out by simply writing it out as well you can take some examples. Let's say you take

a card list of size 10 and then walk through it the worst case and count how many iterations you

have and compare if that is close to log n or not. And then as an exercise you can verify that

the space complexity of binary searches order 1. Can you you can try posting in the YouTube

comments or in the YouTube live chat how the space complexity of binary searches order 1.

I'll let that steam. So let's now compare linear search with binary search.

How are the two different and what we do is we will create a large test case because

you start to see the benefits of the difference between the order n algorithm and the order log

n algorithm. Only when you have larger test cases because small test cases everything runs

instantly so it's not really that much of a hassle.

Secure we have a locate card linear and this is the linear version of the algorithm where we simply

go through each of the cards 1 by 1 and then we have a really large test case here so we have the

input and then we have the cards which goes in the range okay let's see. So that's 1 to 3 so that's

1000 another 3 that's million so we have 10 million elements here. So we have 10 million elements

and we are looking and so we are actually creating a range here so we are using a function in python

so we're creating a list of numbers going down from 10 million all the way to 1 so a decreasing

list going from 10 million to 1 and this is how you created and you can check it out and in this list

we are looking for the number 2 which occurs at the very end so we are sort of creating this is

as we will see if you want to really analyze it this is going to be a worst case scenario both for

linear search and for binary search approximately worst case so the queries to and then the output

is this is the output that we expect obviously because 0 to 9999999 is are the array indices

and the last element is 1 so the element just before is 2 so this is the expected output.

Okay so now we have this large test let us call evaluate test case and let us pass check the linear

search pass in the last test and because this is a huge list we may want to turn of the display

of the output we may not want to actually see the input being displayed so we can simply turn

of the display by passing display equals false and we can just get back the result from the

evaluate test case function so the result will give the output the actual output of the function

whether the test passed and the running time of the algorithm so it takes a second so it looks like

the test did pass or algorithm is correct so that's great and it took 1 to 2 4.291 milliseconds

or about 1.2 seconds to answer it and you can probably tell why because it because this is the

result so it probably took 999998 iterations so it had to go through all the elements to get to the

variant on the other hand when we talk about binary search so now we are passing in the binary search

version once again turning display to false and we are displaying the output okay so this time

the result is the same the test did pass but the execution time is 0.019 milliseconds so that's

55000 times faster than the linear search version and in fact you can tell how many elements we

actually had to access so if we just check log of so log of this number is about 7 and maybe

now if you're checking log 2 we can maybe check something like this so not more than 20 elements

had to be accessed so where we linear search needed to access about 10 million elements binary search

was able to get to the answer with just about 20 checks so that's a lot of times saved and

you can increase the size of the array by a factor of 10 and increase this by factor of 10 as well

and then you will see far bigger difference where for a 10 times larger array linear search would

run for 10 times longer whereas binary search would only require three additional operations

so the linear search would go from 10 million operations to 100 million operations binary search

would go from 20 operations to 23 and that is the real difference between the complexities order

and order login and as the size of as the size of the array's gross bigger another way to

look at it is that if you just divide the complexities binary search runs n by login times faster

than linear search for some fixed constant because there's always some constants involved

and as the size of the input grows larger the difference only gets bigger the difference in

performance and that is what algorithm analysis of algorithms and optimization of algorithms is

all about it's about overcoming the limitations of computers by devising clever techniques to solve

problems and it's something that you can actually apply in real life as well in a lot of cases

there are a lot of things that you may see a brute force solution to but if you just apply your mind

you may find a more optimal solution a more easy way or a more lazy way to do it with less work

so think about that and here is a graph showing how the how you can compare common functions

how the how the running times of common functions vary so people look at all kinds of functions

we look at constant time functions order one for example accessing an element from an array

is order one so even if you have an element of 10 a list of 10 million elements you can access

the last element in constant time on the other hand we've looked at binary search which has

which is order login and we've also looked at linear search which is order n now in the future

we will look at other techniques which have complexities of n square n cube n to the power n

or far far higher and somewhere in between there is a very nice special type of complexity called n login

which is rather nice so we'll talk about that as well n login in fact a lot of questions in

coding assessments and coding interviews tend to be taking algorithms which would be

which would have n square complexity in in a brute force approach and optimizing them either

to order n or to order n login so we'll discuss all of this so don't worry if this doesn't

make sense just yet but I hope you see now why we ignore constants and lower order terms while

expressing the complexity of the big notation so we've covered binary search but we've seen it

in the context of a problem and now we can step away one more step and abstract it out further and

identify the general strategy behind binary search and this general strategy is actually applicable

to a wide variety of problems and this is what you want to keep doing as a programmer you need to

abstract away peel away the layers of specific problems specific details and find the general

technique find the general strategy and then encode that using your functions and programs so

here's the general strategy come up with a condition to determine whether the answer lies before

after or at a given position so we are assuming here that we have some kind of a range and we have

to identify a position within a range or maybe an element within that range but we can access

elements using the position so come up with a condition that that first tells you whether

given a position the answer lies at or before or after that position once you have that condition

first retrieve the midpoint and the middle element of the list now if the middle element of the

midpoint is the answer then return the middle position that is the answer you're done if the answer

lies before it repeat the search so repeat the process with the first half of the list

or the first half of the search space and if the answer lies after it repeat the search with the

second half of the search space so here is the generic algorithm for binary search

implemented in python and you can see a classic detailed documentation here so while

so here you have the binary search is going to take a search space low and high so low is going to be

zero and high is going to be well we will pass in maybe the final we will pass in maybe the final

index of the array but writing it this way rather than passing in array also allows you to use

binary search for problems that are not based on array sometimes these could just be numbers for

example if I ask you to find a number between 1 million and 10 million that is a perfect square

then you can use binary search to do that

then it takes a condition so what it does is it starts a loop so while low less than equals high

we get the midpoint so low plus high divided by 2 that gives us a midpoint then remember earlier we

had this condition test location so our condition simply is supposed to take the middle position

and identify if the middle position is the answer or we need to go left or right so the

condition should return either found left or right so if the condition returns found we return the

midpoint as the answer if the condition returns left we return the high we move to the left side

so which is we take the end of the search space and set it to before the midpoint so we set

high equal to mid minus 1 and if the condition returns right which is the else case here we set

low to mid plus 1 so we take the start point of the search space and move it after the element

then we return minus 1 so that's your binary generic binary search algorithm and if you start using

this what will happen is now this is a tested piece of code and in fact we can see it here

now we can rewrite locate card and locate card can be we are passing in cards and we're passing in

the query and we need to write a condition and here we're using a very interesting feature of Python

we are writing a function inside a function so this is called function closure and it's a very

handy feature so now we can simply write condition inside locate card and what that does is

binary search is going to pass the middle value the middle position but condition can also

access cards and query so which is because it lies inside locate so what we do inside condition

is okay we check them we get the mid element card's mid if card's mid is equal to query

then here we have that check we check whether it is the first occurrence of query or can

query occur before it if query occurs before it we return left else we return found and then these are

the original conditions that we already had so you can verify this by going back and checking

but the important part here is now the while loop has gone away now we can simply call binary search

with zero line cards minus one so the start index the end index and the condition and we can

evaluate the test cases and you can see that the well in test cases are correct and now you can

use this binary search function because we have not tested it with one problem you can use this

exact same function to solve other problems too in some sense it is a tested piece of logic so

here's what we will do we'll take a quick question and we will implement it now we've spent

what one and a half are talking about a particular problem but let's spend maybe two minutes talking

about a new problem and solving it so here's a slightly related question given an area of

integers sorted in increasing order find the starting and ending position of a given number so once again

you have a sorted area this time they're increasing the only difference is now apart from the fact

that they are sorted in increasing order the other difference is that we're looking for both the

start index and the end index so we're looking for both the start index and the end index

of a particular number because the number can repeat like we saw one example and

this is a very simple way to solve this as simple strategy is do binary search once to find the first

position and that's what this function does I let you read through it the only changes here are

this variable this has changed this order because now the now the elements are increasing order

and then the second change and there's no other change here so that this is just one change here and

then there is another function called last position here instead of checking the left we are

checking the right so instead of checking mid minus one we are checking mid plus one and if

mid plus one equals a target we go to the right and of course we have the same change here in this

code because instead of decreasing we have increasing order right so now we write two positions

now we write two functions first position last position and then first and last position is simply

getting the first position once so that's one binary search and getting the last position once that's

two binary searches and that's not bad you know the complexity still order login

two times login or two times some constant times login when you express it in the big

connotation is still login so that's okay and that was quick we were able to reuse most of the

code that we have written and that's the benefit of making generic functions like binary search

and in fact we can test the solution by making a submission here so let's go to leadcode.com

let us here what I've done is I have already copied over the binary search

function the first position function and the last position function so by the way leadcode is

a great platform for practicing so you can go to leadcode.com sign up with any account and you will

find a lot of problems especially on the in the problem step and here you can see that this is exactly

the problem that we have been solving just now so we've just post the code here by research first

position last position first and last position and leadcode requires you to write this class

called solution this is something that they give you beforehand and inside the solution you need

to define a function called search range where we are simply calling our first and last position

here I'll let you see and we simply we can test the code with our test case so you can pass a test

case here and test it out great or we can simply submit it and here you can see that the

problem was submitted successfully and it tells you things like how much runtime it used what was

the memory it used and your solution was accepted right so check out leadcode.com go to the problem

section and you can see all the different problems that they have you can also explore and you

have different problems that come up every day it's a great place to practice so that's binary search

for you but I just want to revisit the method once again so this is the systematic strategy that we

applied for solving the problem we state the problem clearly and we identify the input and the output

formats this this shows that you've understood the problem you know what the solution will look like

then come up with some example inputs and outputs and try to cover all the edge cases so this

shows that you are envisioning what are the different inputs that can come in before you write code

then you come up with a correct solution not necessarily the most efficient one and state it

in plain English now when you try to state it you will have to clarify it and that will help you

clarify your own thoughts and then you can analyze the algorithms complexity and you can implement

the solution and test it using example inputs so this is the basic solution now in interviews and

encoding assessments maybe you know where there's a time limit you may not want to implement

the brute force solution because then you may get stuck in fixing issues with brute force and

you can directly jump ahead to step five but while you're practicing always implement brute force

then step five analyze the algorithms complexity and most of the time it is simply a matter

of counting the number of iterations how many times a while loop or maybe a loop within a loop

is getting executed and identify inefficiencies and if it is a brute force solution it's

generally quite easy to see the inefficiency for example in this case the inefficiency was that

we know that the arrays sorted that anything we do will be better than going line by line right

we could pick a random element and that would help us eliminate a good chunk of the array

so that is the inefficiency and then apply the right technique and we are learning the techniques

so we've learned binary search today and then we're going to learn a lot more techniques

that are asked in interviews so apply the right technique to overcome the inefficiency and repeat

steps 3 to 6 which is go back and come up with a correct solution with the optimized technique

implement the solution and test it using some example inputs and then analyze that algorithms

complexity and identify any inefficiencies so what we've done for you is we have created a

template so you can see this python problem solving template and how you can use this template

is to simply run it so you run the code you run this template and then when you run the template

inside it you will see this question mark in a bunch of places so you can give it a nice project

name and you can commit it to your profile one way you can save a copy over this template to your

profile is by clicking the duplicate button if you click the duplicate button you can copy it in your

profile and you don't have to look for it you can just find it on your joven profile but anyway

once you have it copied you can click the run button and then click run on binder and run the

template then you go down once you run it and you can copy over a problem statement you can copy

over a link to the problem so that when you need to make a submission you can go back and

refer and then here the method is summarized for you and here we have created sections for you

so you can simply start filling out this method, step 1 step 2 step 3 step 4 step 5 so whenever

you are faced with a difficult problem just use this template and I guarantee it one if you

work through this course you will be able to solve a majority of the problems that you come across

and specifically even if you are able to follow maybe about 30 to 40 percent of this course

you will easily be able to solve most questions that are asked in interviews because questions

asked in interviews are fairly simple in terms of the data structures or algorithms they test

but the intention there is more to test your approach look at the quality of your code and

see how clearly you are expressing yourself and this is what is exactly what this method

teaches you to do now to encourage you to do this to encourage you to try it out and you can take

problems from places like lead code code chef code forces there are a few links listed here

you can see practice problems there are a bunch of links listed here so that was today's lesson

for the next lesson common data structures in python so this is data structures and

algorithms in python and online certification course brought to you by Jovian

thank you hello and welcome to data structures in algorithms in python this is an online certification

course pick offered by Jovian today we are looking at assignment one binary search practice

so let's get started first thing we will do is go to the course website pythondsa.com

on the course website you can enroll for the course and view all the previous lectures and assignments

for assignment one you may want to review the video and notebook for lesson one

let's open up assignment one it's called binary search practice

now in this assignment you will apply and practice the concepts that we covered in the first lesson

so you will understand and solve a system solve a problem systematically

implement linear search and analyze it and optimize the solution using binary search and ask

questions and help others on the forum let's open up the start and notebook for the assignment

which contains that problem statement and other information now this is a notebook you're

looking at hosted on Jovian you can see some description here and if you scroll down below

you can also see some code and you will need to execute this notebook modify the code with

within it and record a new version which you can then submit to see your score so let's start reading

through it as you go through the notebook you will find three question marks in certain places

to complete the assignment you have to replace the question marks with appropriate values expressions

or statements to ensure that the notebook runs properly and to end now keep in mind that you need

to run all the cells otherwise you may get errors like name error or undefined variables

you should not be changing any variable names or deleting any cells or disturb any existing code

you can add new code sales or new statements but do not redefine or do not change some of the

existing variables you will be using a temporary online service for code execution and we'll see how to

use it in a moment so keep saving your work by running Jovian.com at regular intervals and then the

question marks optional will not be considered for evaluation although we recommend doing them they

are for your learning but you can make a submission before you have solved the optional questions

now you can make a submission back on the assignment notebook page and we'll see how to do that

and if you're stuck you can ask for help on the community forum it's listed here

and we'll see how to do that as well now one final thing I want to mention is you can get

help with errors or ask for hints you can even share your code and errors that you are getting in the

code but please don't ask or share the full working answer code on the forum this is so that

everybody has the opportunity to work through the problem statement on their own make mistakes learn

from their own mistakes and arrive at the right solution now how do you run this code the recommended

way to run this code is by clicking the run button at the top of the page and selecting run on binder

but you can also run it using some other options like Google, Colab or Kaggle or you can run it on

your computer locally so we're going to use the recommended method run on binder

now we have the notebook running in front of us the first thing I like to do is go to kernel

and click restart and clear output so that we can see all the outputs of the notebook from scratch

and I'm also going to toggle the header and the toolbar so that we can zoom in a bit

so now the same Jupyter notebook is now running online on a platform called binder

and before starting the assignment let's save a snapshot of the assignment to a joven profile so

that we can access it later and continue our work I'm going to run pip install joven

this is going to install the joven library then run import joven to import the library and set a project

here I'm just calling it binary search assignment and run joven.com it now you've taken a

start a notebook which was hosted on my profile and then you've run it on binder where as soon

as you run joven.com it a copy of the start an notebook gets saved to your profile so what you will

see here is a link to a notebook hosted on your joven profile let's open it up here and see

so now this is your personal copy of the assignment notebook any changes that you make here and

run joven.com it will get added to your profile so if you want to come back and continue your

work then you do not have to go back to the original start a notebook which contains all blanks

rather you can come back to your profile and you can come to your profiles simply by opening

joven.ai and on your profile you can go to the notebook step and on the notebook step you will be

able to find as you can see here you will be able to find the binary search assignment here

there you go this is the binary search assignment that we just created and you can open it and

run it on binder to continue your work. So moving along this is the problem we are looking at here

you are given a list of numbers obtained by rotating a sorted list and unknown number of times

okay so we have two new terms here rotating a sorted list and don't worry if you don't know

that means normally if you see any new terms in a problem they will be explained somewhere within the

problem itself. For instance here you can see that there's a definition we defined rotating a list

as removing the last element of the list and adding it before the first element one is

instance rotating the number list 3241 leads to removal of the last number and then placing it

at the very beginning so you end up with the list 1 324 this is a new operation that we are defining

this is not something standard but you will find that a lot of problems will define new terms

or new operations so that it becomes easier for you to understand the problem so that's rotating

a list now rotating a list once produces 1 324 now if you rotate that list again the resulting

list one more time then you will end up with 4132 and so on and then the other term is sorted

so sorted refers to a list where the elements are arranged in increasing order. In this case we have

numbers and the numbers 1 357 are increased arranged in increasing order so this is a sorted list

but if this was 3241 well that's not the numbers are not arranged in increasing order so that's

not a sorted list so you are given a list of numbers obtained by rotating a sorted list and

unknown number of times for instance this sorted list 0 234569 is rotated a certain number of

times and you can verify that if you rotate this three times you end up with the list 5 6 9

sees your 234 right you can see that first a certain 9 comes to the beginning then 6 comes to

the beginning and then 5 comes to the beginning so you need to write a function and you're given

just this the list you're not given the original sorted list you're given the list obtained

by rotating some sorted list and unknown number of times now you need to write a function to

determine the minimum number of times the original sorted list was rotated to obtain the given

your function should have the worst case complexity of order log n where n is the length of the list

and you can assume that all the numbers in the list are unique okay so 3 parts write a function

to determine the minimum number of times you need to rotate the original sorted list in this

case it is 3 the function should have the worst case complexity of log n so this determines correctness

and this determines efficiency and then this is some additional information to help you that you can

assume all the numbers in the list are unique if this was not mentioned you would also have to

handle the case where your list is not contained unique numbers now we will apply the method that we

have been applying all throughout this course for solving the problems number one state the problem

clearly identify the input and output formats number two come up with some example inputs and outputs

and try to cover all the edge cases number three come up with a correct solution for the problem

and state it in plain English number four implement the solution and test it using some example

inputs and having test cases and then implementing a solution allows you to test them using the

example inputs and fix any bugs that's why it's very important to have some test cases number five

analyze the algorithms complexity and identify any inefficiencies and number six apply the right

technique to overcome the inefficiency and then you go back and repeat steps three to six come

up with a correct solution implement the solution and test it and analyze the algorithms complexity

and you can review lesson one for a detailed explanation of this method let's apply it step by step

the first step is to state the problem clearly and identify the input and output formats

now why while it is stated clearly enough it always helps to express it in your own words

in the way that it makes it most clear for you and this is something that you can keep

returning to rather than the original problem statement because this is something that you will

understand better and it's okay if your problem overlaps with the original problem statement

but do try to express it in your own words so in this case what I've just done is I have double clicked

here once you double click you can now edit this text cell and now we can start writing a problem

so let's say given a rotated list we need to find the number of times it was rotated

and okay I think what I've probably missed here is that it is a sorted list so given a

sorted list that was rotated some unknown number of times

we need to find the number of times it was rotated right maybe I'm just going to say given a

rotated sorted list because technically the input is not a sorted list it's a rotated sorted list

so given a rotated sorted list that was rotated and unknown number of times we need to find

the number of times it was rotated but doing this exercise helps you determine

if you understood the problem correctly and you may often find that okay there's a certain

detail in the problem that you missed okay but at this point I'm happy with my description

and you will see that it is matching the description to a large extent but it's something that

I understand better so I'll just refer to this from this point now assuming here that I know

what rotation and sorted means otherwise I could also include those then here's a question

the function will you will write will take one input called names what is it represented

and given example okay so once again we double click on this and one input is

names so this is a sorted rotated list and let's give an example here let's say we take the

sorted list three five six seven nine and then we rotated a few times let's say we rotated a

couple of times so we end up with this sorted rotated list that's our input so we answered the

question here now the first question was to express the problem in your own words this is a solution

the second question was what does the input names represent given example it represents a sorted

rotated list seven nine three five six the third question is the function you will write will return

a single output called rotations what does that represent well you have to write a function that

identifies how many times the list was rotated so this is the number of times the sorted list was

rotated okay and in this case the example that we have is that this sorted list was rotated twice

three five six seven nine was rotated two times so you mentioned to here now you can see these

backcodes that I'm using here this is next to the number one on your keyboard or below the escape key

what these backcodes let you do is they let you express text as code within markdown you can see that

they have a gray background and they have a different font this looks a lot more like code

same is here true for nouns so you can use markdown and its features

to your advantage to organize your descriptions and your text better okay so now based on the above

we can now create a signature of our functions we have a function called counts rotations it takes

the list of numbers and it returns well right now we are just putting pass in here but we know that

it's going to return on single number rotations now after each step remember to save your notebook

so we are going to just run jobin.com it and now if you leave your computer you do not have to be

worried that your work may be lost so you can go in here and you can open up this notebook from your

jobin profile and press run at any point to run this notebook now step 2 is to come up with some

example inputs and outputs and try to cover all the edge cases and our function should be able

to handle any set of valid inputs so here are some variations that you can encounter a list of size

10 rotated 3 times a list of size 8 rotated 5 times so these are two generic examples and then

a list that wasn't rotated at all a list that was rotated just once a list that was rotated

n minus 1 times where n is the size of the list a list that was rotated n times and what you mean

by rotating the list n times well let's see an empty list and a list containing just one element

and if you can think of more test cases you should definitely add more test cases here and what we

do is we will express our test cases as dictionaries so this will help us organize the test cases

and test them all at once more easily using helper functions so you can see here that we've organized

one test case here and we've expressed a test case as a dictionary so here we have the input to the

test case that is the input key and then we have the output to the test case now because a function

can take many arguments the input itself is going to be a dictionary and then for each argument

in this case there's just one so we just call it norms we have the input here and this is the

size of the output okay so let's create the test case and let us then if you want to fetch

actual input an output out of it so here we can fetch test input norms that's going to give us the

norms we can use test input the output should be test outputs this seems to be an error

and the result is counterrotations num 0 okay so this is the actual result obtained by passing

the test case into counterrotations and you can see that the result we get back is none because

right now we do not have any code we just has passed inside and the result and the output are not

equal because the output is the number 3 but the result is null so that's okay our test case is

failing right now because we have not yet implemented the function but as soon as we implemented

we expect to see the test case passing now to help you avoid all of this work we have given

you a function called evaluate test case so from jove not python dsa you can just import

evaluate test case and then call evaluate test case with a function you want to test and the actual

test case and you can see here it prints the output that was passed in the expected output

the actual output that was obtained and the test result in this case the test result was failed

and the execution time is also printed here if you just want to evaluate if a certain

implementation is faster than another so now your job is to create test cases for each of

this scenarios listed above so here is test 0 that is same as the original test case that we had

created now here is test 1 a size a list of size 8 rotated 5 times I will let you create this

but it will look something like this you will open up you replace the three question marks with

let's say a list of size 8 so 1 2 3 4 5 6 7 8 and you can imagine that this was rotated 5 times

then 1 2 3 4 5 or 5 of these numbers will then move to the first position

and you get this as the input numbers and the output well it was rotated 5 times so I think

you can guess that the output here should be 5 now here is a list that wasn't rotated at all

what should be the output here I'm sure you can guess that the output here should be 0 so I let you

fill this out here is a list that was rotated just once so let's try let's fill out this one

so this this list rotated once would give us 7 3 5 there you go a list that was rotated

n minus 1 times where n is the size of the list okay I'll let you do that a list that was rotated

n times where n is the size of the list okay what does that look like

so you take this list and then you first put 10 in the first position and then you put 9 in the first

position so 9 10 comes to the beginning and 3 5 7 8 comes after it then you move 8 to the first position

then you move 7 then you move 5 then you move 3 if you move all of these back to the first position

you end up with the same list so you've rotated it n times now what should be the output in this case

there are about 6 numbers here so is the output 6 I don't know I'm not so sure because remember

the question the original question says write a function to determine the minimum number of times

the original sorted list was rotated to obtain the given list so it has to be the minimum number

of times we may want to just go back and change this we need to find not the number of times

it was rotated but the minimum number of times it was rotated or it needs to be rotated right so

coming back here the output should be 06 but 0 so keep that in mind then here's an empty list

I let you figure out what should be the numbers in the output here and here is a list containing

just one element once again should be pretty straightforward can you rotate a list with one element

I let you decide and then we're taking all the tests and putting them into a single list now

since I have not defined all the tests I'm not going to use this definition which contains all

the tests but I'm just going to pick the number of tests that I have defined so we have defined here

S0, S1, S3, S5 I'm just going to put in S0, S1, S3 and S5

and that's the full sort of tests that we have you definitely need to fill out all the test cases

and if you can think of some other cases that you should be testing and you should include those

test cases here as well okay now to evaluate your function against all the test cases together

you can use the evaluate test cases helper function from Joven so there are two functions

evaluate test case works with the single test case and evaluate test cases works with

a list of test cases so we have a list of test cases here I have four but you should have

about eight at least and a few more if you have created them so we can import from Joven

or Python DSA evaluate test cases and then invoke evaluate test cases with the count rotations

function still it we don't have any logic in the function so we all the test cases should pass

and the list of test cases we've created so you can see test cases zero fails one fails two fails

so out of the four test cases none of them have passed no problem we have completed step two which

is to create some test cases and we'll know once we've defined a function whether the function

definition is correct now the next step is to come up with a correct solution for the problem

and stated in plain English and there's a hint here for you already coming up with a correct

solution is quite easy and it's based on this simple insight if a list of sorted numbers is

rotated k times so you keep rotating at step by step moving the last number to the first position

then the smallest number in the list ends up at position k okay and you can verify this it's very

simple to do this whenever you have a doubt discrete a new cell by the way you can create a new

cell by clicking on the left side of a cell and clicking insert cell below or if you're in a

code cell just click here near the prompt and press the B character and that adds a new cell below

so let's take the list one three five seven five six seven and let's rotate it k times

let's try with k equals two so if you set k equal to two then you're going to take two of these

from their very end and move them to the beginning so that means zero comes at position six comes

at position zero seven comes at position one and the starting element in the sorted list now comes

at position two that's interesting let's move the third element as well okay so now we've moved

three elements or rotated the list three times and the smallest element ends up at position three

so it seems to hold true and you can verify this now with a larger list smaller list empty list

all the test cases that you have if a list was sorted k times sorted list was rotated k times

then the smallest number in the list ends up at position k counting from zero further it is

the only number in the list which is smaller than the number before it and you can see this once again

the smallest number is at position three and all of these numbers are higher than the numbers

that come before them except the number one which is smaller than seven so we simply need to

check for each number in the list whether it is smaller than the number that comes before it

if there is a number before it then our answer is simply which is the number of rotations is

simply the position of this number right so if you can find the position of the number

which is smaller than the number that comes before it the position of the number is also equal

to the number of times to sorted list was rotated and if we cannot find such a number then the

list wasn't rotated at all and that's it you can see here in this list now applying this logic

three is the number the smallest number and not only that three is the only number which is

lower than the number that precedes it the predecessor which is 29 and since three occurs at

position four well actually three occurs at position three 0 1 2 3

the list was rotated exactly three times now we can use the linear searcher algorithm as a first

attempt to solve this problem in the linear search simply involves working through this list

working through this list from the left to the right so now the task for used to describe the

linear search solution in your own words and please write it in your own words but here's how I'm

going to write it let's say create a variable position with values 0 so this is the position

for tracking this for tracking the position then look at the number at the given position and not

only look at it but compare the number at the let's say the current position to the number before it

now if you're starting position with the values 0 maybe we may not there's no number before it so

we may not be able to compare it with something we may even just start with the value 1 that's all right

if the number is smaller than its predecessor then return position because position is the answer

we found the number that is smaller than its predecessor there's only one such number

otherwise increment position and repeat till we exhaust all the numbers

okay simple now you can add more steps if your description of the algorithm requires more steps

that's perfectly all right but at this point we have a very clear description of the solution

now we're starting with the position is 1 not 0 because we also want to track the previous position

now we import Jovian here and commit a project once again I keep saving your work after every step

so that you can continue your work so now we're talking about implementing the solution and testing it

so let's implement the solution we said that we want to start with position

we want to start with position 1 and while venture the loopy terminated well while position

is less than the length of numbers okay that's fair and then what is the success criteria so we have

if position greater than 0 and norms of position less than norms of position minus 1 okay

that's the success criteria here now you can see that there's a condition if position greater than 0 here

so we don't really need to start position at 0 we can start position at or we don't really need to

start position at 1 we can start position at 0 as well and all that will happen is this conditional

gets kept and position will get incrementing and this is a good practice because whenever you iterate

over a list you normally just want to start with 0 just to avoid any confusion later when you're

reading the code that did you intend to write 0 here or 1 etc etc so just put in position equal 0 here

and simply skip the check here or simply skip this comparison if position is not valid

so whenever you're accessing an element from inside a list or inside a dictionary you always want to

make sure that that index or that key is valid okay here we are making sure that the key position

minus 1 is valid by checking position greater than 0 in any case we now have the logic and finally

we are saying that if the number at position is less than the number that comes before it then we return

that and that's just going to if it's not then it's going to increment the position and it's

going to check again and again and again till we run out of numbers now if you've exhausted the

entire list then it follows that there were no rotations or there were end rotations exactly

in either case the number we return should be 0 okay so keep this in mind some you may have the

doubt should you be returning minus 1 here or should you be returning 0 here well the question does

specify clearly that you are given a sorted rotated list and you have to find the number of times

it was rotated now obviously minus 1 rotations are not possible so minus 1 would not be a valid

return value from your function and this is the reason we write test cases 2 now let's evaluate the

test case so let's call evaluate test case for a single test case on countertations linear and let's see

what the test cases this is the test case here and this is the output we call evaluate test case

with countertations linear and test and that gives us a linear search result and you can see here

this was the number the list of numbers this was the expected output then this was the actual output

so great our functions seem to have path to test case now we can evaluate all the test cases by

calling countertations linear on all the test cases together and give that gives us a whole list of

test results test case 0 and 1 and 2 and 3 all of them are passed now if you had put in minus 1 here

you would see that one of the test cases would fail which is the case where the list was

rotated at all or was rotated n times okay so that should tell you that the answer here should be

0 so that's our linear search algorithm and at this point you may face issues you may

feel stuck you may not be able to figure out how to write the code and that's perfectly all right

that's part of learning you may face errors you may face exceptions for instance if you did not have

this check here position greater than 0 or maybe what you had here was some other condition like

position less than equals position plus 1 and that's okay then you can go to the forum and post your

issue so let's open up the forum here this is the forum discussion for assignment 1 and you can

go into the original topic here which is a longer discussion so this is where everybody's posting

small issues so you can see that there's about 321 messages that have been posted you can start

looking through this forum you can start reading through some of the posts you can even search

if you press control left and you can even search for questions here now if you want to post your

own question scroll down to the very end or you can just click this button here and click reply

okay and mention your question here I have an issue should I return minus 1 or 0 in the case the

list has not been rotated okay maybe that's and if you want if you have code that's not working

or there's an error you can also include a screenshot of your code or I'll show you another trick

you can actually include let's say you commit your notebook so let me come up here I've

committed my notebook and if you have a particular line of code that you want to share you can

actually click copy cell link and paste it here so that will give a link to the entire cell

and if somebody clicks on the link then they can view that specific cell of the notebook directly let's see

you can see here that it brings us directly to this specific cell there's another option you can even

click on embed cell okay for embed first secret notebooks we know not allow embedding but copying

the cell link should work and then click reply and your question will be posted and somebody will

reply to your question just come back to the forum in a few hours or maybe the next day and you should

see an answer you will also receive an email so that's the discussion topic you can also go back

to the topic here the category here and create a new question you can see if you want to start your

own thread if you think your question deserves a deeper discussion where multiple people can reply

you can also create a new thread by clicking new topic okay so keep this in mind and do make use of

the forum what we've seen is people who are active on the forum are at least four to five times

more likely to complete the course and on the certificate of accomplishment and continue working

on these topics after the course as well okay so the next step is to analyze the algorithms

complexity and the way to do this if you've seen lesson one is to simply count the number of iterations

number of executions of the while loop now if you have a list of numbers of size n

then you can see here that this is the key loop here while position less than the length of numbers

so then there will be n loops or n iterations and then inside eat each iteration we're performing

certain comparisons and returning things so all of these are in effect constant time and based on

this you can probably tell that the complexity of linear search is order of n so you can just put in

a big o and in the big o notation this will be order n so that's the first part of the assignment

linear search now the next step is to apply the right technique to overcome the inefficiency

and that's where you can now you can now read through the rest of the assignment now the idea here is

this binary search is the technique we'll apply and the key question we need to answer and

binary searches given the middle element can you decide if it is the answer which means if it is

let's say the smallest number in the list or whether the answer lies to the left or the right

of it okay so given the middle element if the middle element is smaller than its predecessor

then it is the answer we already know that because there's only one number in the list at a

smaller than its predecessor so you can see here for example now if the middle element was one

which it's not but suppose that the middle element was one and you can see that one is smaller than

eat then we know that one is the answer so the position of the middle element is the answer

however if it isn't then we need a way to determine whether the answer lies to the left of the

middle element or to the right of it and consider these examples so here you can see that the

middle element is three and the answer is the position two so in this case the answer or the

smallest element lies to the left on the other hand in this case you can see the middle

element is four and the smallest element minus one lies to the right of it so now you need to

apply your mind and think of a check that will help you determine if the middle element

given the middle element if the answer lies to the left or the right of it right and we're

looking for the smallest element remember so the logic here if you just spend a couple of minutes

you will come up with this quite easily if the middle element of the list is smaller than the

last last element of the list okay or the last element of the range that we're currently

looking at that means that all the numbers here are in increasing order so then the answer lies to

the left of it on the other hand if the middle element of the list is larger than the

last element of the range that means that because we know that the list is rotated

list so that means that the numbers increase up to 0. and then there's a decrease and then they

continue increasing that's the only way in which the final element can be smaller so that means

the answer lies to the right of it so that's the logic here for binary search and now what you

have to do is describe the binary search solution in your own words so here once again you have

these four or five lines and it's very important that you do this because if you cannot express it

then coding it is also going to be difficult for you so always do this exercise of expressing

the solution in your own words when you're practicing when you're solving a coding challenge

or something even in an interview it's also very important because the first thing you need to

do is to communicate to the interviewer your thought process and how you're thinking about the

problem so the first thing you need to do is describe a simple solution in your simple words

and then they may or may not ask you to code that solution and then the next thing is to

identify the complexity or identify the inefficiency then the next step for you is to

describe the optimal solution or the binary search solution in your own words okay now

if you don't describe the solution in your own words and you start writing the code they may

not be able to follow your code so even if you written mostly correct code maybe with one or two

edge cases wrong they may still have a feeling that you don't know what you're writing but if you

explain the solution clearly to them they will know that now you understand the solution

and they will be able to follow the code as you write it and they will be able to pick up mistakes or

errors and help you with the errors once secret is that interviews are always open to helping you

unless you make them really confused to keep that in mind and describe the solution in your

words once you do that you can commit now the next step is to implement the solution now the

implement the binary search solution as described in the previous step let's run this again

so you run count rotations define the function count rotations binary now you may want to review

lesson one here on how to start it out you'll see that low starts out at zero and high starts out at

length numbers minus one and I will not solve the rest of this but there is a certain condition here

between low and high so in binary search we are starting with the entire list as the range then we're

looking at the mid number so we're getting the first the mid position and we look at the number

at the mid position then we check if the middle position is the answer so if the middle

position is the answer we return the middle position then we check if the answer lies in the left

half so here's a condition where you decide if the answer lies in the left half and we

once the if the condition holds true all we do is we change the high so which we change the end point

of the range, 2 made minus 1, and then we check if the answer lies in the right half,

in that case we change the starting point of the range to make plus 1 and the y loop

repeats.

Okay, so that's the general logic of binary search.

And one thing you have to keep in mind is if none of the elements satisfy the criteria

that you have, what is the answer?

And this is a very important condition.

This is where it is very easy to go wrong, this is also called the edge case or the

trivial case.

So you should handle and think about this carefully.

And then once you've done that, you can evaluate the test case and you can a single

test case, you can evaluate multiple test cases.

Now, if your test cases are failing, you may want to enable this print statement inside

by uncommenting it, but make sure to comment it out at the end once again.

And the print statement will help you see what the low high end mid points were.

Now, you may want to then take up pen and paper, look at an example that is failing.

Let's see if the printed numbers match what you expect to see.

Debugging your function is a very important scale.

So keep that in mind and use a debugging technique like this by adding print statements

and working out the same problem side by side on paper to fix your issues.

Otherwise you may feel lost if you are not able to look into the internal workings

of the function.

Next, you have to analyze the algorithm's complexity and identify inefficiencies.

This should be straight forward enough.

We've already looked at the complexity of binary search, but all you need to do is make

sure that what you're doing within the algorithm matches the analysis that we've done

earlier.

So the problem size reduces by half each time and then we're doing constant work in each

step before solving a problem of half the size.

So that should roughly give you an answer.

And keep committing your work.

Now finally, to make a submission, you have two options.

Now, one option is to take this link, so your notebook has been committed here and you

can come to the assignment page, let's open up the assignment page, binary search practice.

Come down here and paste this link here and click submit.

Now once you click submit, the assignment will be submitted and it will go into automated

evaluation.

So in about a couple of minutes, maybe up to an hour, depending on the queue of submissions

from different participants, you will receive a grade over email.

Let's just refresh the page and it seems like there was an issue here, the issue was

that count traditions binary was not defined.

So it's possible that this happened, count traditions binary did not get defined because

there are a bunch of question marks here.

So we may need to then fix the issue and then come back and make a submission once again.

Okay, so I've received a fail grade, I will go back and I will fix the issue and then come

back.

Now it's very important for you that's why to have a good set, good set of test cases,

or you to test your function, so that when you submit it or when you get an error,

you can maybe look at your functions, performance on the test cases and fix anything that

needs to be fixed and add new test cases if you need to.

Now, one other way you can submit is by simply running the code by joven.submit assignment

equals Python DSA, I think assignment one.

The code is mentioned here, you can see here that the submission was made and you can verify

your submission on the page.

Okay, so that's assignment one, so what should you do next, review the lecture video if you

need to and execute the Jupyter notebook, you may need to keep, you may want to keep

the Jupyter notebook running side by side, I'll do working on the assignment, then complete

the assignment and even attempt the optional questions if you scroll down here on the assignment

notebook, you will find that there are some optional questions for you.

Here's one bonus question, use the generic binary search algorithm, so inside the Python

DSA module in joven, there is a function called binary search, you can use the generic

binary search example, then here's an optional bonus question to handle repeating numbers,

we did say that you can assume that there are no repeating numbers in the list, but here's

one list with repeating numbers, can you modify your solution to handle the special case,

and then here's an optional bonus question three about searching in a rotated list, so

you're given a rotated list.

Now, instead of finding the number of times it was rotated, you're trying to find the

position of a certain number, well, instead of the position of six, can you apply binary

search and modify your previous solution slightly, to search within the rotated list

and find the position of a given number, okay, now here's a hint, you can simply identify

two sorted sub arrays within the given array and perform a binary search on each sub array,

using, so to identify the two sorted sub arrays, you can use the counteritations binary

search functions, so that's one potential solution, another way is to modify the counteritations

binary function to solve the problem directly, so it's a very interesting problem to solve,

and if you found the assignment easy, then you should definitely solve these bonus questions,

and if you can solve this question by yourself without taking additional help, then you

can solve pretty much any problem related to binary search that may be asked in an interview,

because most of the questions are some variations of something like this, and this is pretty much

the hardest problem you may get asked. You can also test your solution by making a submission

on lead code, and this is only for the final optional question, and there's a thread on the

forum where you can discuss the bonus questions separately as well, so do make use of the forum

thread too. Here it is, optional bonus questions discussion, so that was assignment 1 of

data structures in algorithms, so it's called binary search practice. Hello and welcome to data

structures in algorithms in Python, this is an online certification course by Jovian,

my name is Akash and I am the CEO and co-founder of Jovian, you can earn a certificate of a

accomplishment for this course by completing four weekly assignments and doing a course project,

today we are on lesson 2 of 6. Now if you open up pythonda.com, you'll end up on this course website

where you will be able to find all the information for the course, you can view the previous lessons,

which is lesson 1, and you can also work on the previous assignment, which is assignment 1,

and you can also check out the course community forum where you can get help and have discussions.

So let's open up lesson 2. This is a lesson page here, you will be able to see the video for this

lesson. You can watch live or you can watch a recording here, and you can also see a version of

this video lecture in Hindi. And in this lesson we will explore the use cases of binary search

trees and develop a step-by-step implementation from scratch, solving many common interview

questions along the way. So here is the code that we are going to use in this lesson, all the

different notebooks containing the code are listed here and let's open up the first one.

So here you can see all the explanations on the code for this lesson. This is binary search

trees, traversals, and balancing in python. And this is the second notebook in the course,

you can check out the first notebook in lesson 1. And if you're just joining us,

this is a beginner friendly course, and you do not need a lot of background and programming

with a little bit of understanding of python and a little bit of high school mathematics,

you should be able to follow along just fine. If you do not know these, then you can follow

these tutorials to learn the prerequisites in just about an hour or two. Now the best way to learn

the material that we're covering in this course is to actually run the code and experiment with it

yourself. So to run the code, and you can see here if we scroll down, you can see that there is

some code here on this page as well. Now to run the code, you have two options, you can either

run it using an online programming platform, or you can run it on your computer locally.

So to run this code, we will scroll up and click on the run button and then click run on binder.

And this is going to start executing the code that we were just looking at. So once again,

you can go on the course page by kndsa.com, open up lesson 2, and you can watch the video there,

and on lesson 2, you can open up the link to the code where you can read the code and the

explanations here. And if you want to run the code, just click the run button, and that will execute

the code for you. So once you click the run button on binder, you should be able to see an interface

like this. This is the Jupiter notebook interface, the same explanations that we were seeing on the

lesson page. You can see here, the same explanations are now available here. But the differences,

you can now edit these explanations and you can go down and you can actually run some of the code

in this tutorial. You can see here that you have a run button and when you click the run button,

that is going to run the code in this particular cell. And this is a Jupiter notebook made up of cells.

Now we'll do a couple of things here. The first thing we'll do is we click on kernel and click on restart

and clear output. But this will do is we'll clear all the outputs of the code cell so that we can

execute them ourselves. And then I'm just going to zoom in here and hide the interface so that we can

look at the explanations and the code. So finally we have some running code and in this notebook,

we will focus on solving this specific problem. And this is a common question. A question of

this sort can be asked in interviews. So this is an interview question, but along the way,

we will also learn how to build binary trees and binary search trees and how to apply them to several

other questions. So here's the question. As a senior back-end engineer at Jovind,

you are tasked with developing a fast-end memory data structure to manage profile information,

which is username, name, and email for 100 million users. It should allow the following

operations to be performed efficiently. You should be able to insert the profile information for

a new user, find the profile information for a user given their username, and then update the

profile information of a user once again given their username, and list all the users of the

platform sorted by username. And you can assume here that using names are unique. So this is a very

realistic problem that you might face if you're working at a company where you have a lot of users.

So let's see how we solve this problem. Now here's a systematic strategy that we'll apply

for solving problems, not just here, but throughout this course. This first step is to state the

problem clearly and in abstract terms, and then identify the input and output formats.

Then come up with some example inputs and outputs to test any future implementations

and try to cover all the edge cases. Then come up with a simple correct solution for the problem.

It doesn't have to be efficient, it just has to be correct and stated in plain English.

And then implement the solution and test it using some example inputs. Fix bugs if you face any.

And finally analyze the algorithms complexity and identify inefficiencies if any.

Now once you identify it, inefficiencies, then we apply the right technique and that's where

data structures and algorithms comes into picture. So we apply the right technique to overcome

the inefficiencies and then we go back to step three. So come up with a new correct solution,

which is also efficient, state it in plain English, implement it and then analyze the complexity.

Now if you follow this process, you should be able to solve any programming problem or interview

question. So step one, we state the problem clearly and we identify the input and output formats.

Now we can reduce the problem to a very simple, single line statement. We need to create a

data structure which can efficiently store 100 million records and we should be able to perform

insertion, search, update and list operations, all of them as efficient as possible.

Now the input, the key input to our data structure, the solution that we are building is going to

be user profiles which contains username, name and email for user. Now before we come up with a

solution, we need a way to represent user profiles and a Python class would be a great way to

represent the information for a user. So you may have heard of the term object oriented programming

and that is what we're going to look at now. If you're not familiar with the class, it's very

simple. A class is simply a blueprint for creating objects and what's an object well,

everything in Python is an object whether you're looking at a number, a dictionary, a list,

anything and you can create your own custom objects with custom properties and custom methods

by creating your own custom classes. So here's the simplest possible class in Python with nothing

inside it. We're creating a class user. So this is how you declare a class and then we're putting

nothing inside it. So whenever you put nothing inside a function or a class or anything you can

you need to put the past statement because Python cannot accept empty blocks of code. So here

we're creating a class which does not have anything inside it and we can create an object or

it's often called instantiation which is creating an instance of a class, instantiate an object

of the class by calling it like a function. So we say user one is user. So this creates an object

and the variable user one points to that object. Now we can verify that the object is of the

class user by simply printing it or by checking it's type. User one and type user one are both

user. Now the object user one does not contain any useful information. So let's add what's called

a constructor method. So constructor method is used to construct an object to store some

attributes and properties. So now we're defining the class user once again but inside it we're

defining this function and you can see that this function is inside the class because there is some

indentation here. So we define this function underscore underscore in it and it takes four arguments.

Now the first argument is a special argument called self and we'll talk about this and then we have

three arguments username, name and email. And inside in it what we're doing is we're

setting self dot username. So we're setting a property on self to username. We're setting a property

on self to name and we're setting a property on self to email. And finally we're printing user

created. So let's see let's create another user user to and you can see that user to is also

an object of the class user. Now here's what happened in conceptually when we do this. The first

thing that happens is when you invoke this function, when you invoke user as a function,

Python first creates an empty object of the class user and then stores it in the variable user

to and then Python invokes the init function and to the init function it passes user to the

object that was just created as self and then the other arguments that were passed while creating the

object as the rest of the arguments. So you can imagine that we are basically doing

your basically calling user dot underscore and score in it. The function with user to an empty

object and these arguments John, John, and John dot com. And then inside the init function,

we simply set these properties on user to. So now we get user to dot username is John,

user to dot name is John, and user to dot email is John, John, and do dot com. So that's basically

how classes work in Python. And that's why you always have this additional extra argument in all

class methods which will refer to the object that finally gets created. So once user to is created

with the values John, John, and John dot com, you can check that user to dot name is John,

and user to dot email is John, and user to dot username is John. Now you can also define

some custom methods inside a class. So obviously we had the init method, but here we are also

defining another method called introduce yourself. Now introduce yourself takes again two arguments,

the first argument is self which will refer to the actual object that gets created later.

And then we have a guest name, and we basically say hi, guest name, I am such and such,

contact me, it's such and such. So these blanks are filled in using the guest name,

self.name and self.email. So that's how you define a method in a class. So here we have

another user we're creating, Jane and Jane do a Jane at do dot com. And you can see here that when

we call introduce yourself with David. So user three which is Jane becomes self and then David

becomes guest name, and that's why we get hi David, I am Jane do contact me at Jane at do dot com.

So that's a quick refresher on classes and Python. Now there's a lot more to classes,

but the simplest thing you need to know is you how to define a class, how to create a constructor

which is underscore underscore in it, how to set some properties, like we said the properties,

name, email, and username, and finally how to define methods, like we defined the method

introduce yourself. And that's all we will need today. So we won't need much more than that.

And one final thing that we're doing with our class is we're defining two other special

functions underscore underscore REPR, rapper and underscore underscore STR.

So now these two functions, these two functions are used to create a string representation

of the object. And you can see here once we create an object user for, now and if you try to

print user for, you can see that user for is now printed like this. So use it three,

you was not printed, I mean user three was a printed just as a user, but with user four,

we have all this information printed here as well. So now here's an exercise for you,

which also brings us to the first quiz of the day. Now we are going to do three quizzes

in this video and you can answer these quizzes on LinkedIn. So go to our LinkedIn profile

if you see the posts, you will see a new post here, which will give you a question. And the

question is what is the purpose of defining the functions STR and rapper within a class?

And how are these two functions different? Now leave a comment with your answer and we will pick

the right answer one right answer and one lucky winner will get us to act back from us.

So that was the input. We now have a way to represent users by creating classes.

And then the output that we want the final output that we want to create for our problem is a data structure.

So a data structure is once again something that we can define using a class. So we can define,

we can expect our final output to be a class called user database, which has four methods.

Insert, find, update and list all. An insert takes a user and inserts it into the database,

find takes a username and returns the user, update takes a user,

and updates the data for that user and finally list all returns a list of the users. So this is

what the class will look like and we have not implemented it yet, but we now have an interface.

So now the next step is to come up with some example inputs and outputs.

So let's create some sample user profiles that we can use to test our functions once we implement them.

So we're going to create these seven user profiles and you can see that we're creating these seven

user profiles with a username, name, and an email and storing them in these variables.

Using the user class that we have just defined earlier and we're also going to store the list of users

in this variable called users. And as you can see, we can access different

fields within a user profile using the dot notation. So you can check barrage.username is barrage

and barrage.email is barrage.example.com and barrage.name is barrage task.

Now you can also view a string representation of the user as we have seen. So if we print the user,

you can see some information about the user and here is the full list of users that we have created.

So it's always a good idea to set up some input data set up some test inputs that you can

use to test with your implementation later on. And since we haven't implemented our data structure yet,

it's not possible to list any sample outputs, but you can try to come up with some

different scenarios to test any future implementations. So let's list some scenarios,

we're testing the methods of our user database class. So the methods are insert, find, update,

and list all. And for inserting, you may want to test that you're inserting a user into an

empty database of users. So that's what's called in hk's. And then the general case is to insert

a user into the database assuming that the user already does not exist. Then another hk's is trying

to insert a user with a username that already exists. So these are all the different ways in which

we can use the insert function and there can be some more. So here's an exercise where you try

coming up with all the different scenarios in which you would like to test the different functions

insert, find, update, and list. So that completes step two. Now we have some sample inputs and

then we have some scenarios in which you're going to finally test our function. So the next step

is to come up with a simple correct solution and then state it in plain English. Now here

is a simple and easy solution to the problem. We simply store the user objects in a list sorted

by user names. That's simple enough and suppose we do that. So inside our data structure we have

a list which simply contains a bunch of user objects. Then the various functions can be implemented

like this. So you have the insert function, the insert function simply requires looping through the

list and then adding the new user at a position that keeps the list sorted. So for instance if

you have the users, a cache, a month and so on already and then you're inserting the user

barrage then you can tell that barrage should go between a cache and a month in alphabetical order.

So that's how you insert a new user and maintain the sorted property of the list.

Then to find the user we simply loop through the list and then find the user object

with the username matching the query. So that's, if you're looking for a

payment for instance you start from the beginning you go through a cache, perage and finally

hit a payment and then you can retrieve the user object associated with a payment.

And then you have update. Now updating is very simple as well. It's similar to find. So you find

the user object matching the query and then update the details of that user object.

And then finally because our internal representation is already a list of user objects sorted by

user names so we can simply return that list when we want to list the users.

So that's our plain English description and it's always a good idea to describe your solution

in plain English so that you can clarify any doubts you have. Even during interviews it's a good

idea to have a conversation with the interviewer before you actually implement the solution.

And now one fact that we can use is that using names which are strings can be compared using

the less than greater than or equal to operators. So we can compare strings just like numbers and

Python. So that'll make it easy for us to implement these functions. And that brings us to the

implementation and the code for implementing these is also fairly straightforward. So now we have

the user database class. We are actually implementing this class and here you see that we have

a constructor and the constructor does not take any additional arguments apart from self.

And all we do is inside self we set a property dot users and that property dot users is set to an

empty list. Then we come to insertion. So now assume that we already have some users in a user database.

So we start out with a pointer set to zero and we go through all the valid positions in the

users list. So which is from zero to n minus one if there are n users. And then we find the first

user name greater than the new users use a name. So for instance if you're inserting a

himant then you go through a cache and barrage and then finally you realize that the next value is

probably Siddhan. So you want to insert himant before Siddhan. Right. So you want the first

user name that's greater than the new users use a name. And you check this property and as soon

as you find the next that the next user is greater than the user that needs to be inserted.

We break out and then we insert that user at that position. So this is the insertion you can

you know it's just four or five lines of code. So you can work through this code try to read this

code line by line and see how it works. Now similarly you have the fine function, the update

function and the list function they're all pretty straightforward. There's really not much here.

So this is an exercise for you because this is also the brute force of the simple implementation.

So this is an exercise for you to go through each of these functions and try it out.

And use the interactive nature of Jupiter to experiment and add print statements inside each of the

functions if you need inside each of the loops if you need more visibility into what's happening.

Okay. But what we will do is we will try and test this implementation out.

And the first thing we do is instantiating a new database of users using the user database class.

So here we say user database and that gives us a database of users.

And now let's insert some entries into this database. So we can now insert for instance,

we can insert the value hemant, Akash and Sadhanth. So here we have inserted three values into the

database. And now we can retrieve the data for a given user given their username using the

find method. So now we say database dot find Sadhanth that returns a user and we can check the value

of user. And you can see that now we have retrieved the data for Sadhanth, which is user names

Sadhanth names Sadhanth and emails Sadhanth at example.com. Now let's try changing the information

for a user. So to change the information we can call database dot update and then simply

pass in a new user object. So let's say we want to change the information from Sadhanth

Sadhanth you. So this is how we do it. We call database dot update.

And now if we find the information once again, if you can't find call database dot find once again,

we get back a user object and this time with the updated information. So we have created the

database, we have inserted some values into it and then we have retrieved values out of it and we

also updated them. And finally we can retrieve a list of the users in alphabetical order.

So now if we list it out, you can see here that we have the username Akash, we have the username

Himant and we have Sadhanth. These are the three values that were inserted and they are all

in alphabetical order of username. Now if we insert a new user, let's say let's say we insert

a barrage. We can make sure that barrage is inserted into the right position.

Okay, so that's how we use the data structure that we just created and you can use the empty

cells here to try out the various scenarios when you run the notebook. So just to recap,

we created a simple class inside which we are storing a list of users in sorted order of

username and then insertion is pretty easy. We simply loop through find the right position and insert

any new values. Finding values is very easy as well. We simply loop through and keep comparing

and updating values is simply a matter of finding them and then updating that specific value.

And listing is simple because we can simply return the internal list representation that we're

already storing in the sorted order of username. So that's the simplest solution or one of the

simplest solutions. There can be even simplest solutions maybe. So the next step now is to

analyze the algorithms complexity and identify any inefficiencies. So typically in an interview

setting, you may not want to implement the simplest solution. So you can actually skip step 4.

Now when you've described what the simplest solution is in English, in plain English, which was step 3,

you can directly jump to analyzing its complexity and then move on to optimization and

implementing the optimized version. But when you're practicing or when you're learning, it's always

a good idea to implement even the brute force solutions. So let's analyze the complexity. The

operations insert, find, update, involve, iterating over the list of users. And in the worst case,

they may take up to n iterations to return a result. Where n is a total number of users.

Now the list all function is slightly different because it simply returns an existing list.

So the list all function does not take linear time, it takes constant time.

Now based on this information, it's very easy to check to guess the time complexities of the various

operations. Insert, find and update have a order n post case time complexity, which means they can

take up to n iterations. However, the list function has an order 1 complexity, which means

irrespective of how many users you have in your database, it returns the list in the same amount of time.

Now if you want to display the list or if you want to iterate over the list, that may take you

additional effort. But getting the list itself is a constant time operation.

So that was the time complexity and an exercise for you is to verify that the space complexity

of each operation is order 1. And if you're wondering what we mean by complexity, then you can

go back and watch less and 1 where we talk about analysis of all the algorithms, complexities,

and the big own notation. What we're calling order of n, the big own notation, all of these

explain in a lot more detail. So you can go back to less and 1 and check it out.

Now we've created a simple solution and our first question might be to wonder if this is good enough.

And to get a sense of how long each function might take if there are 100 million

numbers, users on the platform. Let's create a while loop. Let's create a for loop.

And let's run it for let's see how many this is 1, 2, 3, 4, 5, 6, 7, 8. So let's run it for

10 million or 100 million numbers. So here we are creating a range of 100 million numbers.

And we're running a for loop which iterates over the entire range. And we're simply

performing a simple operation which we're not really using. We just multiplying the number by itself

to simulate what might happen if we have a database of 100 million users and we're trying to

access find a user. Now what is the worst case scenario here? Let's run this and you can already

see that it is taking a while. For 100 million users, the loop takes about 10 seconds to complete.

Here it took about 9.45 and a 10 second delay for fetching user profiles will definitely lead to

a suboptimal user experience and that may cause users to stop using the platform all together.

Now imagine you came to joven.ai and it took 10 or 15 seconds to load your profile and then

maybe even longer to load the other information and display it. You would not be happy with

the experience. And then a 10 second processing time for each user for each request each profile

request will also significantly limit the number of users that can access the platform at a time.

Because if you're running the back end server on one computer which has 8 cores, then each core

will be busy for 10 seconds each time a user tries to access the platform. So you can only

serve about 8 users in 10 seconds time. Now that's pretty bad. That could significantly limit

the number of users. You will have a significant outage if a lot of users come to the platform.

Or on the other hand, you may have to increase the cloud infrastructure at more servers at

bigger hardware, more cores, more RAM. And that could increase the cloud infrastructure cost for

your company by millions of dollars. So as a senior back end engineer, you must come up with a

more efficient data structure. And this is why choosing the right data structure for the

requirements at hand is a very important skill. Now we can clearly see that using a sorted list of

users may not be the best data structure to organize a profile information. So let's see what

better we can do here. And before we do that, let's save our work. So remember that

this notebook, we were running it on an online platform called binder and binder can shut

down at any moment because it is a free service. So what you want to do is run PayPal install

a Jovian and then import the Jovian library and you can then run Jovian.com it.

Now when you run Jovian.com it, what this does is this captures a snapshot of your Jupyter

notebook, whether you're running it on binder or you're running it on your own local computer and

it saves a snapshot of this Jupyter notebook on your Jovian profile. So here you can see now on my

Jovian profile. I have this notebook and I can go back on my profile and view the other

notebooks that I've created in the past. So your Jovian profile becomes a collection of all the Jupyter

notebooks that you're working on. So always just it takes just a couple of lines import Jovian

and run Jovian.com it. So always run Jovian.com it inside your notebooks. And if you want to resume

any work that you were doing, then all you need to do is click on the run button and then click

run on binder once again and then you can start executing the code within the Jupyter notebook once again.

So remember that binder is a free service so it will shut down after about 10 minutes of

inactivity which is if your computer goes to sleep or you change your tab, keep running Jovian.com

it from time to time. So now we have a simple implementation and we've analyzed it and determined

that it is not efficient, it is inefficient. So now we need to apply the right technique to overcome

the inefficiency. And we can limit the number of iterations required for common operations like

find, insert and update by ditching the linear structure that we hide earlier and organizing our

data in a more tree-like structure. So this is the structure that we use for our data and we will

call this a binary tree. Now this is called a tree because it vaguely resembles an inverted tree

trunk with branches. So you can think of this as the root. So this has the root and then you can

see each of these are like branches and then there are nodes where branches then split into multiple

branches. So these are called nodes and finally at the end you will have individual nodes which

do not have any more branches and those are called leaves. So these are some terms that I used.

The tree represents the entire structure. The top node is called the root and each element in the

tree is called a node. The top node is called a root and then the bottom most nodes which do not

have any sub trees or what are called children which do not have any children are called

leaves. So the root node has two children and then each node there with can have 0, 1 or two children.

So it's not necessary to have exactly two children but up to two children is what determines

a binary tree. So that's a binary tree. But the binary tree that we need will have some

additional properties which was what will make it efficient for our purposes. So you can see

one thing you can observe here is that the root node seems also seems to be the central value

if you sort the keys in increasing order. So what you will notice is on the left we have

keys which have which lie before jadish and on the right we have keys which lie after jadish.

So that's one thing and that is actually the second property listed here that the left

subtree of any node consists only of nodes which have keys that are lexical graphically smaller

than the nodes key. So the key for this node is barrage and that is lexical graphically smaller

than jadish and similarly himantanakash are all smaller than jadish and then this property

holds at every node. So at every node if you check sonach you can see that siddhanth is

less than sonach and vishal which comes to the right is a more than sonach and then siddhanth

vishal all three are greater than jadish. So when a binary tree satisfies this property it is

called a binary search tree. So that's what we are looking at here this is a binary search tree.

So that's the first property but we need the second property is that our nodes will have both

keys and values. Now sometimes you can create binary nodes, binary trees with just keys each

node will have a single number or a string inside it and you can call it the key or value or

element or whatever you wish. But what we want is we want the keys to be usenames so that we can

compare the keys easily. But along with each node we also want to associate a value which is the actual

user object. So if we are looking for himant let's say we started the root node. We see that jadish

is the root node and since it is a binary search tree we know that himant lies to the left

then we reach barrage. We know that himant will lie to the right of barrage so we go right

we reach himant and then we access the value stored at himant which is the user details for himant.

So we need both keys and values in a binary tree and this is what is called a tree map or a map.

In many languages. And then finally this tree that we will create this data structure that we will

create it will be balanced. So here what we are looking at is each node has two children left and

right but it is also possible to have an unbalanced tree where you only have one child on each

on maybe one of the sites. So we will require it to be balanced which means that it does not

skew too heavily in one direction and we will talk about what balancing means and we will talk

about how to check if a tree is balanced and how to keep a tree balanced. So we will go over all

of these things step by step but these are some of the properties that we want our final data

structure to have. So one important property of a tree of a binary tree is the height of a tree.

In fact if you start counting you can say this is level zero where you have one node and this

is level 2. This is level 1 where you have two nodes, the left and right,

the left and right child. Of the root node and then this is level 3 level 2 where you have 4 nodes

the left and right child of the first node on level 1 and the left and right child of the

second node on level 1. So you can see that the number of nodes in each level in a balanced binary

tree is double of the number of nodes of the previous level. So if you have a tree

of height k, which means a tree which has exactly k levels, then here is the list of the

number of nodes at each level. Now level 0 will have one node, the root node. Level 1

will have two nodes, its children. Level 2 will have four nodes, their children, so that's

four nodes is two times two or two to the power two. Level 3 will have eight nodes,

two nodes for each of these four nodes, so that's two to the power three. And similarly,

if you keep going down, level k minus one, the final level will have two to the power

of k minus one nodes. So that if the total number of nodes in the tree is n, then it follows

that n is 1 plus 2 plus 2 square plus 2 cube plus so on plus two to k minus one. So what we're

trying to determine here is what is the relationship between the height of the tree and

the total number of nodes in the tree. And this is the relationship and we can simplify

it a bit. If we add 1 to each side, you can see here that this side we get n plus 1 and

this side we get 1 plus 1, which gets simplified as 2 or 2 to the power 1. And then we

can add 2 to the power 1, we're 2 to the power 1 and that gets simplified as 2 to the

power of 2. Then we can add 2 to the power of 2 and 2 to the power of 2 and that gets

simplified 2 to the power of 3. And we can keep performing this reduction, we can keep adding

these together, till we finally end with 2 to the power k minus 1 plus 2 to the power

k minus 1, which is simply 2 to the power of k. So what that gives us is that k, the

height of the tree is log of n plus 1, which is approximately or in almost never case less

than log n plus 1. So that's a bit of an approximation we're doing here, but it is the height

of the tree is less than log n plus 1. So to store n records, we require a balanced binary

search tree of height no larger than log n plus 1. Now this is a very useful property

in combination with the fact that nodes are arranged in a way that it makes it easy to find

a specific key simply by following a path down from the root, the binary search tree property.

And we'll see soon by the end of this lesson that the insert find and update operations

in the balanced binary search tree have complexity order of log n. So in our original

implementation a brute force implementation they had order n and this time we reduce the complexity

to order log n and that is far better and we'll see how that happens. So that's a quick introduction

to binary search trees we've had enough theory now let's get into some implementation.

But before that we have the second question. Now binary trees are very commonly used as data structures

for our idea of different in a variety of different languages for instance java c plus plus python

java and c plus plus have this concept of a map which is represented using a binary tree.

And it is also used in file systems. So binary trees are also used in file systems to store

indexes of files. So when you browse your file system or when you search for a specific file it

is a binary tree that is used to look up the file and find the location of the file.

Now that's where that brings us to our second question of today.

Now you can find the second question on a LinkedIn profile. So once again go to

LinkedIn.com slash school slash java in AI and you will find the second question here.

The second question is which tree-based data structure is used to store the index

in the Windows file system and who invented the state structure. So like this question follow us

and comment with your answer and you can start chance to win a swag pack.

So if you repeat the question which tree-based data structure is used to store the index

in the Windows file system also known as anti-FS and who invented the state structure.

Okay so let's get to the implementation of binary trees. And here's a very common interview

question that you might get. Implement a binary tree using python and then show its usage

with some examples. So what we will do as we implement binary trees and binary search trees is

to also cover many common interview questions. In fact we will cover exactly 15 so that's a quite

a few. And the first one is to implement a binary tree. And to begin we will create a very simple

binary tree. So we will not have any of the special properties like key value pairs and binary

search tree and balancing rather and we will also use key numbers as keys within our nodes

because they are simpler to work with. So here is an example binary tree so we have a root node

and then we have a left child in right child. And here's a simple class representing this

representing a single node within the tree. So we are calling this class tree node and it has a

constructor function. It simply takes a key and it sets self dot key to key. It also has a

couple of other properties self dot left and self dot right which are initially set to none. So

each node when it's created exists independently of other nodes. And now let's create nodes

representing each of these nodes. So we have node 0 we're calling it we're calling tree node

with the value three then we have node one and node two. So there you go now we've created the

nodes and we can verify that it is of the type to a node you can see here. And if we check the key

of node 0 you can see that it has value three. And we can now connect the nodes by setting

the dot left and dot right properties of the root node. So if you go to node 0 and set dot

left to node one, now we've connected node 0 to node one. And similarly if we set node 0 dot right

to node two, now we've connected node 0 and node two. And that's it we're done. So now we have

three nodes and then we've connected each of those nodes and we may also just want to track

which is the root node. So we can create a new variable called tree and simply point it to node

0. So tree points to the root node of the tree and then the root node is connected to its

children and the children will be connected to their children and so on. So you can check here

that if we check tree dot key, we get three and if we check tree dot left dot key.

So three is the root node. It has a value three. 3 dot left is this node. So it should have the

value four and tree dot right dot key should have the value five. Okay so pretty straight forward

and that's pretty much the answer to the question implement a binary tree and Python.

Now going forward we will use the term three to refer the node root node to refer to the root

node and the term node can be used to refer to any node in a tree not necessarily just the root.

Okay so here's an exercise for you. Try to create this binary tree. So now you have a root

node here and then you have a left child and right child and then this left child has another