go over how do we design a navigation application like Google Maps.

Now let's go over some Functional and Non Functional Requirements(NFRs) that we want

this platform to support. So the very first thing is when a person wants to

move from point A to point B, this platform should be able to give them a

couple of information . 1) What is the route that they should follow

2) Given that route how much distance they'll have to cover and how much time

it will take. As an enhanced variant we could also build a system in which we

show them 2-3 routes and then let them choose that they want to minimize the

distance or minimize the time. 3) The next thing is that it should have a very

pluggable model. So let's say we make a very basic design which just has no

traffic data or anything of that sort. Now let's say if you want to plug in

traffic information it should be easy enough to add it. Now post that let's say

if you want to add information about weather or accidents or construction

going on somewhere or road blockages or something of that sort, it should have a

very easy way to input this data and not make a change in whole of the architecture.

So that's the main idea of making a pluggable. 4) There's one more

thing that we'll cover in a very brief thing, that is basically how do you

identify roads. So there are two three ways in which we can identify new roads.

So one very basic or the most efficient way is to just ask government sources

to give us all the information about all the roads data that they have. Now

they might not have all the data but at least we'll have a good starting point.

Now beyond that we can capture a lot of organic data. So let's say if a lot of

users are going on to a place or a route kind of a thing which we don't identify

as a road, then we can easily say that it there is a road that we don't know of

and we can kind of onboard that Road onto our system. Now we can use some data

like number of people traveling on it, which sides are they traveling to, what

is the volume of traffic, what is the speed and correlate that with the

existing roads that we have and try to even come up with how wide the road is!!

Is it a single lane road or if it's a four lane/six lane kind of a road. All

of those information could be figured out. But we will still not go into this in much

depth over the video. Mainly what we'll focus on is

How do we efficiently find the route between two points?

Now coming to the non-functional requirements the very first thing is the system should be

always Available. This should not go down. The next thing is it should have a good

enough accuracy. Now let's say if you are not giving the very best route but if

even if you are giving a good enough route that should be okay, unless it's

not a terrible route, okay. And it should not be too slow so let's say if it takes

1 second/2 seconds/3 seconds to do all the calculations and come up with

output that should be okay. It's not that it should respond back in a millisecond

with the best route between two points. That's a bit too much to ask for,

a couple of seconds one, two, three seconds should be okay. But it should not be too slow.

Like it should not take 15 seconds to come back with the response, okay!!

Coming to the scale, again I do not know if these numbers are authentic, but from

what I've heard and read, Google Maps roughly has a billion MAU (Monthly Active

Users) and these users generally access Google Maps a couple of times in a day

or maybe a couple of times in a week at least.

What that means is we'll probably have roughly five to ten billion

requests coming in a month for time, distance and route between two points from users.

Then there are also five million companies which use Google map so

companies could be companies like Uber who are using Google Maps to come up

with the Navigation and Pricing System, or it could be smaller companies which

have a very similar use case. But that means that we need to keep these things

in mind that we have a very large volume of users who are coming into system who

will be using this platform and design it accordingly.

now building this

Navigation App is a very hard problem to solve. Not because of the kind of

Algorithms that we'll use. But more because of the kind of requirements this has. So

for example, if we try to calculate the number of roads in the world there are

various theories, which you know come up with various numbers. In general people

cannot claim that there are somewhere close to 50-100 million roads in the world.

It could be you know even a much larger number. Now if we try to model it as a

graph it would probably have somewhere close to 50 million vertexes and maybe

you know hundreds of millions of edges if we divide the roads into multiple

chunks and all of that, right. So that is a very very massive data set.Now a lot of

companies don't even have access to this kind of a data, where in what road is

connecting from where to where. That kind of information is kind of non-existent

throughout the whole world and there is no single place where you can fetch

that, which makes it a very hard problem to build an navigation system like this.

The next thing is, it is very hard to even quantify a lot of

attributes that will impact the ETA. For example traffic and weather condition

and Road quality. Things like these are very hard to quantify so there is not a

very easy mathematical formula that you can come up with to calculate the ETA

that will be required to cover a particular distance. One more challenge

this is, a lot of things into the whole road systems are very unpredictable.

There could be and a random accident happening somewhere, there could be a

road closure due to any kind of reason and those things are not really

predictable and that's the main reason why you know a lot of companies have not

been able to build this kind of system successfully.

We will be using an

ideology of Dynamic Programming while we try to solve this problem. So basically

what we will do is, we will try it for a very small area, and then we will try to

solve it for a larger area, and then even larger area and then across cities and

countries and so on and so forth. So before we get started let me introduce

you a concept called "Segment". Now this is not an industry standard term I just

made up this name on my own, so just keep that in mind. A Segment is basically a

small area that is small enough that we can easily operate on to it. Think of it

like this we can have segments of one kilometer by one kilometer throughout

the globe. So let's just say if you have a city, something like this, what we'll do is

we'll divide the city into multiple segments. Now ideally there will be a lot

more segments than what we are drawing but for understanding this should be

good enough, okay. Now the idea behind these segments is that it will have four

coordinates which are the four corners of a Segment, through which we can

identify the segment boundaries and each segment would have an identifier. You can

say this segment s1, this is s2, something of that sort. Now the thing with segments

is whether a point lies within a particular segment? - is something we

should be easily be able to calculate. So for example think of it like a

coordinate system you have these x axis and y axis, this is your point (0,0),

this is your point (0,1), this is your point (1,0) and let's say this

is your point (1,1). This is your square of one each, right. Now whether a point

lies within this or outside this we can easily identify based on what its

coordinates are right and similarly for this based on its XY coordinates we

should be able to identify whether this lies in this particular segment or not.

So what we will try to do is each user will try to map it to some segments

basis their coordinates, right! Now one good thing about these segments is

because these are functions of Lat-Long, we should easily be able to

identify some approximate distance between two segments. So let's just say

if you want to identify this distance between these this segment and this

segment, right. So basically let's say if we come up with the center points of

both of these and these are two lat/longs we can easily find the

distance between (aerial distance) between these two points. We use this in the

later sections but it's a very easy mathematical calculation given

two lat/longs, find the aerial distance between these, right? Now what we'll

actually do is, let's say the whole globe for example, we will actually

divide the whole globe into multiple segments some of the segments would just

have water and nothing else but most of the segments would have some localities

and we will be solving for one segment each and then we will extend the

solution for multiple segments segments which will then cut across multiple

cities and countries and whatnot, okay!! Now the way we model the road network is

like a graph. So think of two points let's say this is point A and this is

point B, and then the road between these two points, okay. So this becomes one

vertex(A), this becomes another vertex(B) and the road between them can be represented

as an edge. Now each road would have a weight. Now will not have one weight

like you normally have in usual graphs, will have multiple weights. so let's say this

road is of length 2 kilometers so one of the weights on this road would be 2

We could have a bit more weights along with that. We would have a

traffic weight, we could have a time-based weight. So let's just say we

come up with the average number thing in general it takes 150 seconds to cross

this road, so 150 becomes another weight. okay! So this is how we represent a

particular road and similarly there could be other weights that we can add.

Now a road, even though it looks like a non-directional thing, but it is actually

are directed relationship. Normally how would you represent it? - you'll say that

this one Road from A to B which is 2 kilometers long, takes 150 seconds. There's

also another road which is from B to A, which is again two kilometers long,

but this one probably takes 200 seconds to cover, right! Why do we need a directed

relationship here? - Firstly in order to handle if there is a different ETA or

different traffic pattern or something of that sort. Plus more importantly, if

this says that it takes infinite amount of time to reach here that's basically a

way to say that it's a one-way Road. Only you can go from point A to point B but

not from B to A, right! So we can use all of these ways to track various things

like one ways or various different kinds of roads. Now even though if it's a

directed graph but for all the like talking within this video I will draw a

single line thinking of it as a non directed relationship, because it makes

the drawing easier and explanation easier, but when you are actually going

to implement it, you will implement it as a directed relationship.

Now let's look at what happens when you want to find the distance between two points within a

segment or even ETA or something of that sort? So let's say this is a graph of all

the roads, within a particular segment and there are these ABCDEFGH... are the

junctions or the points where you might want to start or end from, and

everything else is basically in edge. And edges could have weights, assuming that all the

edges have certain weight. Let's say this edge has a weight of, first attribute is the

length which could mean 2 kilometers the next attribute might say that how much

time it takes to cover that 2 kilometer. This would have a length of 5

kilometers and would take 700 seconds to cover that. Now let's say if you

want to go from point A to point C, how can we go? - There could be

multiple routes. So one of the routes could be from A to B to C. There could be

another route from A to B to E to C there could be another route from A to I

to H to G to B to C and there could be another, a lot more number of routes.

How do you find the best route from going from point A to point C?

This is a very standard problem in the Graph Data Structures, there are various

algorithms to solve it. We can use anything like a Dijkstra or a Bellman Ford Algorithm

to come up with the shortest path between point A to point C.

Once you have calculated this and we might as well decide to cache it.

Because within a segment, it's good to know how can you move from point A to

point B. Normally what you would do is you would run something like a

Floyd-Warshall Algorithm, which calculates the shortest path between all possible edges

in all possible vertexes within a particular segment and then store that

information so that you do not have to recalculate it. So what it will end

up being is, there are these all normal roads which are edges and then

there could be a calculated edge also which says that, for A to C, the shortest

path takes ten kilometers, it takes two thousand seconds and it is via Point A

then B then E then C, something of that sort could be a calculated edge as

an output of Floyd-Warshall Algorithm, which can be stored in another Data Store

which can then be looked up if you want to quickly look at how much time

does it take from reaching a point A to point C. Now what we looked at earlier

was given a junction A and given a junction C how do we calculate the

shortest distance between those two junctions. What if the point with what we

are looking at is not really a junction which is the meeting point of two roads