Google Maps System Design Interview Question

This is a solution for System Design Interview Question where you need to design a Map + Navigation application like Google Maps.
This problem has been asked by a lot of companies like Google, Amazon, Flipkart, Walmart Labs to name a few.
Prerequisites:
How to select the right Database for a Large Scale System: • Database Design Tips |...
Summary of this video: www.codekarle....
Architecture diagram: github.com/cod...
Author: / sandeep1904
If you like this video, please help us grow by sharing this video with your friends on Facebook, connections on LinkedIn and anyone who can benefit from this.
PS: This is not the real architecture of Google Maps or any other similar service. This is my take on how I would answer that problem.
#codekarle #systemdesign #googlemaps #googlemapssystemdesign #system #design #interview #faang #maps

[@getsiva33]

I reckon this will become the best system design channel in youtube. Keep up the good work !

[@codeKarle]

Thanks for the motivation! Do share it with your friends to help us get there 🙂

[@baurks]

I second this. This is by far the best system design video I watched on youtube.

[@rohanagarwal5512]

true

[@satyajeetkumarjha1482]

Exactly.

[@imkx13]

No doubt about that.

[@HusainDalal]

This is the level of details that helps in real interviews. Thanks!

[@prateekchs]

While preparing for interviews for experienced level, one can agree that system design level is the deciding round many times. I also used to struggle in these rounds and hence searched hell lot of resources to understand the concept but nowhere found satisfying result. This is the only channel where I started seeing patterns in designs, role of different components, out of the box solutions and no-fancy/complex components/logic. Designs explained are so simple that after going through few designs, any one can start creating boxes and understand flows between them while approaching to a new problem.

[@codeKarle]

Thanks Prateek! The whole idea of this channel is to propose simple solutions to complex real world problems :) Do spread the word about the channel among your connections! It helps :)

[@benli657]

🎯 Key Takeaways for quick navigation: 00:02 🗺️ Navigation app design like Google Maps requires route, distance, and time info. 00:57 🔌 System design should be pluggable for easy addition of features like traffic, weather, etc. 02:22 🌐 The system needs to handle high availability, good accuracy, and reasonable speed. 03:50 📈 Massive scale: Billions of user requests, millions of companies using the platform. 04:18 🛣️ Building a navigation app is challenging due to vast road data and unpredictable attributes affecting ETA. 22:14 🗺️ Mega-Segment approach: Dividing the map into Mega-Segments containing exit points, simplifying navigation across large areas. 24:32 ⏲️ Weight calculation: Factors like distance, ETA, and average speed influence weights; traffic and weather are attributes, not weights. 27:19 🚗 Traffic data: Utilizing real-time user data for traffic; data is normally distributed, allowing prediction within confidence intervals. 30:05 🔄 Dynamic updates: Changing ETA due to traffic/weather; cascading updates through segments and Mega-Segments when weights change significantly. 39:33 📊 System architecture: Overview of user location tracking, data processing, and updates to enhance map service. 45:32 📍 Hotspot Identifier: Identifying areas with increased activity using location data, enabling better traffic prediction and navigation. 46:32 🚗 Vehicle Identifier: Analyzing location pings to determine the type of vehicle (e.g., car, bus, two-wheeler) and enhance navigation insights. 49:20 🗺️ Area Search Service: Converts location search into lat/long, aiding navigation and route calculation. 50:44 🛤️ Map Service & Navigation Tracking: Handling user navigation, course correction, and analyzing user journeys to improve recommendations. 57:22 ⏰ ETA Accuracy & Analytics: Monitoring accuracy of estimated travel times, analyzing route preferences, and inferring user profiles based on location data. Made with HARPA AI

[@astrostudent2302]

Discussion around - Disputed areas, last bit of inferences like pub goers are social etc..was icing on the cake!!!

[@topgamerprosh75]

I banged the first AWS interview and Meta interview in one go. Thanks for the detailed explanation! Not sure if you are active anymore, but you deserve lot more followers than what you have.

[@illyam689]

how is it going now?

[@pavankalyan6547]

What other system design resources do you recommend for the interview preparation?

[@pkr619]

I have watched quite a lot of system design videos from different sources, and this by far, exceeds most of them in technical depth and breadth. It's not too academic and neither too complex, well done! I am recommending this channel to my peers.

[@aryanrahman3212]

After 2 years, still an amazing video!

[@humeyratopcu3274]

It was an awesome video. Thank you very much! Some friendly suggestions: 1. Data models could be added (KV stores, data size, replication and sharding) 2. Instead of specific technology names, generic names could be used. "Queue" instead of Kafka, "NoSQL database" instead of Cassandra 3. Geospatial index could be mentioned

[@codeKarle]

Yeah, true, that could be done :)

[@KidsGaming-yo8ve]

@@codeKarle why Cassandra is chosen in this scenario. It is column based databases? why not document db kind of db is used?

[@meganfoxyish]

Great Effort to put all the complex pieces together. As we all agree google maps is one of the complex designs in the world and you have done justice to explain this is best possible way. Great Effort.

[@Kevin-jt4oz]

This is brilliant but Im kinda surprised you didnt mention quad trees. They are the standard way to solve problems like this.

[@rjarora]

I don't think quadtrees are used to handle Google Maps use case. They are supposed to return the nearest neighbours, which is a different use case. Although the idea to divide the globe into different segments can be borrowed from quad trees here.

[@atintandon9624]

Very smart to include discussion of disputed areas in this video

[@ravbhaj]

Very comprehensive!! Liked the "Summary of this video" too.

[@rohitvishwakarma9261]

Thanks for keeping the explanations simple. I have seen some videos where people just bombard with jargons reducing interest.

[@coding8696]

Can i start this series with basic information about System Design?

[@gunchoi]

You are pretty smart! Thank you for your videos. I am learning it out of curiosity

[@codeKarle]

Thanks!! Happy that the videos are helping you

[@andriidanylov9453]

Very strong presentation. Actually the best what I have seen about this topic. Appreciate.

[@antonkot6250]

The best video on this topic I found so far

[@EpNews-5012]

Thanks!

[@sanjana8358]

This was on its way to become the best sys design channel on KZbin but why did you stop making videos? All other channels just have scattered information and no clarity of thought. Can you start making videos again and cover more systems asked in interviews? It will be of great help to budding software engineers!

[@puneetagrawal9956]

This was a really awesome video. The first 40 min. were gem

[@nikitasinghchauhan6239]

Thank you for google map . Didn't find any other video on this topic. u did a wonderful job.🙂

[@codeKarle]

Thanks you :) Let us know what other videos you'd like to see

[@nikitasinghchauhan6239]

@@codeKarle google search 🙂

[@codeKarle]

@@nikitasinghchauhan6239 that would be live soon!!

[@RaoVenu]

Questions about the algorithms being chosen: a) In the initial few minutes the presenter mentions Bellman-Ford. Isnt that quite inefficient unless you are trying to look for negative cycles? b) Later he mentions Djistkra'a algorithm. Isn't the A* algorithm better as you don't need to evaluate all paths. Additionally, the heuristic could be dynamic based on traffic patterns. My thoughts were you could use A* for finding cost to go to different entry / exit points from inside for lowest level of granularity and then use the same A* algorithm to evaluate cost between different entry / exit points (like intra city travel)

[@TheMayankrungta]

Your all videos are awesome.

[@andybhat5988]

Super explanation of a very complex system. Thank you

[@intuitive_coder]

Great level of details are captured, Thanks for creating this video. It would be nice to have details on how we would store huge data set of map service, and how we would enable quick update on this dataset.

[@pallavibansal84]

Loved your approach about calculating distances ..

[@avikbagh8391]

Quality content as always. But plz do something about your audio.

[@ir0nt0ad]

Thanks a lot for your work! I believe the word you're looking for is "cell" (5:56)

[@thegeniusone765]

Is this series completed? It was a great series... Keep it going man!!!

[@ektabhalwara7531]

This was an amazing explanation!!! I request you to please post a video about LinkedIn System Design as well. Good Work!!!

[@codeKarle]

Thanks!! That would be almost the same design as Facebook, since both have the same feature set like posts, likes, comments, share, etc. Only the Jobs thing is different, but if we can skip that, I would recommend to watch the Facebook System Design video here: kzbin.info/www/bejne/b17Lm3V9rdqce9U

[@rahulchudasama9363]

Awesome explaination ... This channel will become a boom ...

[@vivekkushwaha2851]

Sorry if this sounds basic, but I'm new to system design and still learning. Can you explain why you didn't save which user is linked to which WebSocket handler at 41:35 in the video? You mentioned polling for this info, but where does it come from exactly? Is it from the WebSocket handler itself? By the way, great video! 🙌 I really learned a lot from it and appreciate your work!

[@alanwsx]

This is a very solid 1-hr content!

[@ankitjain8724]

Excellent content! One of the best explanation of Google map design ever. But there are too many adds, it would be great if that can be reduced.

[@ritubhandarimusic]

But how do you identify what all segments you should consider to calculate distance between two points? You traverse through entire graph or say max 10 segments from each direction?

[@ajayk9929]

Sandeep Kaul Sir ,all your videos are extremely useful for design preparation. if possible please speak little slow or pause for some seconds. Thanks in advance.

[@anmolbhatia2305]

Great video. My question would be regarding what does the data look like which we are storing in Cassandra. For almost all of the storage data you have chosen Cassandra but other factors like data access pattern and what sort of queries will be used on that data should also be considered. It would be great if you can elaborate more on that as well.

[@rajuy18]

Amazing bro, I like it, keep it up 👍

[@metallaser4409]

Thanks for the video. Could you comment a little bit on the schema of the Cassandra tables storing segments/distances between exit points of segments? Also, how come you didn't consider using a graph database such as Neo4j? (I don't know much about it at all, but I would think it is designed specifically for a usecase like this?)

[@twarzo]

This is an awesome system design video given the scope and difficulty of the problem. One suggestion I had was to also add link of slides or screenshots of the diagram drawn at different stages of the video :)

[@amollopes7960]

Really good video, all parameters considered 👍

[@roshanpatro5777]

A very helpful one.

[@nirajpandey3856]

Very well explained !!

[@thakurnitesh27]

Awesome Video. One question though - shouldn't each segment have separate exit and entry point though? There can be scenarios where exit is allowed(one-way) but not entry. In that case, we would have to maintain exit and entry points for each segment and mega-segment.

[@shubhamgarg4227]

woah!!! awesome work, keep doing that

[@codeKarle]

Thanks for the kind words!! Do share it with your friends :)

[@sreenivasulusanduri3453]

Awesome. Very well explained. I have a question on the design: Shouldn't we use some kind of graph database (say, Neo4j for example) to store the graph instead of Cassandra?

[@abhishekaggarwal9774]

Awesome work you are doing. I would like if you can do small videos covering topics like SQL/ NoSQL, Micrososervices, Kafka Messaging Queue etc.

[@codeKarle]

Great suggestion! We'll do that too

[@hqdevelopers3697]

It would be interesting to tackle not so common system design interview questions also. For example, about TinyURL there are a lot of system design videos already. It would be challenging to see a system design video about Google Photos for example and how do they manage to provide "unlimited" storage space for Pixel users (at least).

[@codeKarle]

Those are coming soon

[@sushilrawat502]

@@codeKarle will you be producing more content ?

[@lavkushtiwari2799]

Firstly thanks for this lovely channel. The explanations are so good. I have a doubt: Can Map Service have a Cache so that if multiple people are asking for same location it doesnt need to ask for route to Graph Processing service?

[@knpatel86]

Thanks for the amazing series. I would just recommend going with simple design problems to start with and increment the complexity for beginners. Thanks

[@RekhaS-t9p]

Amazing content

[@kipkip6712]

Amazing work!.. Thank you! So this idea of Exit points on Segments and cutting through exit points to reach destination from source is your own? or is there some reference?

[@codeKarle]

While I did come up with this approach myself, I can't claim that I am the only one who has designed it using this idea, but till the time of recording, I haven't come across anyone else using the same approach. I believe Google would be doing something more optimal than this.

[@samarthgupta7845]

Very nice explanation. Content is really good. This kind of content is not there anywhere on the internet. Can you please make a video on how distributed message queue works?

[@shettyanvita]

Thank you for the detailed explanation of the overview architecture. Can you go in-depth for the upcoming vides of the bottlenecks faced while designing DB/ CAP principles tradeoffs i.e. C/A depending on the requirements/product

[@codeKarle]

Sure, well try to do that

[@nikita12351]

Superb explanation!

[@anupampandey3758]

Thanks for an informative video, Sandeep. Could you also please include the reasoning behind going with specific db choices, external services like hadoop etc instead of a different competitive service?

[@princetoncross-culturaledu1315]

I love the content! Could you please make video about databases and streaming systems?

[@nanjarajeurs3616]

excellent one

[@kamaljosan4376]

Hi, thanks for this awesome video. I have a question around the the design. So at around @31:45 you talk about is the weight of any edge changes, we need to update the cache, and recursively bubble up the results. I want to confirm, if you are a) re-running the shortest path algo again in that segment to evaluate distance between all nodes, or b) just updating the current shortest path with increased value. I think option a) is the correct one. You take the example - if the time take for an edge increases from 10s to 15s, we increase the time taken for route by 5s and then bubble it up. (Which sounds like option b).

[@toppratyush007]

I could be wrong here but I see two variations : 1. Increase in travel time on one of the roads : We can recompute only the paths which used this road since only these would be affected. 2. Decrease in travel time on one of the roads : We can recompute the matrix of all entry and exit points. Doing so on each update would be too expensive, so probably we can wait for a batch of updates.

[@sakshamsrivastava6280]

Hat's off Man!

[@2010aishwary]

wah mza aagya subbed

[@saritakumari-oh8fs]

Thank you for Sharing

[@MrGaurabpaul]

Good video. One suggestion : you could add a section on how search works in google maps. Chinese restaurants near me or best 5 star hotels near bus stop?

[@rahulkushwahafarzirahu]

Thanks for this awesome video. Next would like some LLD videos too.

[@mukeshknit3494]

Awesome and details content. Can you make a video about distributed scheduler ?

[@ShahbazKhan275817]

you channel name should be DesignKarle instead 😛

[@SoumyadipSarbajna]

Design wo de raha hai, hum e code karne bol raha hai

[@SamirPatel-dv8xm]

Good Explanation.. Good Job !.. Que: How Zoom Aggragate video streaming in One UI (on Zoom Client)?

[@DeepakSaini-di7fc]

Great work. It will be great if you can put some content about Google Doc and git design.

[@codeKarle]

Sure, but that might take a while to be live :)

[@alikarooni9713]

Thanks you. Nice explanation

[@TheKshitijagrawal]

Do we really need web socket connection just to collect location info... shouldn't we have web socket only when user is actively using google map. Secondly, if user is not running google map application, will the application be still running somewhere in background to send location?

[@SaiPavanPothuri]

When to use Cassandra ? and when to use hadoop ? any differences ?

[@anandt8362]

Thanks for the video.. 1. If the user changes from the route suggested how the re-route will be calculated and made visible ? Which particular service will be responsible for it?

[@wenhoujx]

very good content, but the audio is a torture.

[@Downicon3]

Thank you, quite insightful

[@harendrapratapsingh8210]

can you please explain why you are using Cassandra as a persistent storage for the graph service? Can we use any graph db for the purpose like neo4J?

[@harshavardhanragi6838]

At 14:44, it doesn't give shortest distance between x and y

[@amrtahlawi]

Thank you for the helpful tutorial. qq: why are you using Cassandra for the Graph Processing service? shouldn't you be using a graph DB like Neo4j? As far as I know, Cassandra is a wide-column DB, not a graph DB.

[@princetoncross-culturaledu1315]

I wonder if a video about stock trading systems can be made?

[@seeva92]

This can be further extended to series of parts. Especially, I am little more interested in the creation of segment, underlying data model of it, persistence logic, and updating the segments. When to increase the current segment range? When to break the current segment range to smaller segments?

[@MaggieMa2138G]

What is the data schema for the Cassandra that is attached to the Graph Processing Service?

[@RK-xl2uq]

great video, i think a little more details on the database schema would have helped more to some readers. At least now i know how google works/worked hypothetically :)

[@zuowang5185]

do you keep a ETA heap for each segment? Not sure how you can efficiently bubble up when a road condition is changed.

[@anilkatakam2738]

On the Disputed Areas- what if user see the map from some other country? how do google decide boundaries?

[@nidhinmahesh4923]

I am watching your tutorials one by one on daily basis, wishing all good for you with upcoming videos. I request you to do a video on Slack

[@jayeshudhani99]

Can you make a video on spark streaming ?

[@navjan13]

So spark streaming is consuming as well as writing back to kafka? or are we going to create a different kafka for that?

[@akshaymonga]

I wish you had gone through the design from component by component, as the meat of this video was about "segments", usually system design interviews dont happen that way.

[@rajatahuja4720]

Websocket handler/manager is primarly required in the navigation flow not while collecting the lat/lon of users. what do you think ?

[@justsaysharu]

Very informative and abstract; given its very challenging design question. Could have broken into 2-3 videos on realtime route algorithm, pre-processing routes, analytics just to justify each of them individually. Also, some points on choosing right datastore and rationale behind each. Wonderful job though :)

[@codeKarle]

yes, trying this 2-3 videos thing in the next one, hopefully we'll be able to make it easy for people to correlate things across videos :) For Datastores, you can look at this: kzbin.info/www/bejne/mYCndKOOqbV7mLM

[@deMErolME]

Great job! Thank you

[@rishikeshkmr]

Perfect!

[@everytwocc]

quite good content

[@piyushshekdar4270]

How is a user location mapped to some point on a road ?

[@作业本-z1s]

super。learning new knowledge，ilove it

[@greuser]

I didn't understand the difference between theoretically calculated road and cached or real roads? Could you explain?

[@JohnWick-to6nr]

How does this approach (considering exits) help in reducing time complexity on the whole, as we are internally applying floyd-warshall for each segment to get the minimum distance between exits of every segment in between and then using this information to build a graph?

[@MithunKumar-xy9pp]

Can you please explain how did u come up with this design? What resources did you follow?

[@Mustaq15]

Can you plz...... teach system design from basics. Playlist

[@dipanshuasri]

How to calculate the exit point of segment ? ( e.g. s1e1 )

[@bowang1825]

can i recommend to talk the 2nd half before the 1st half. I realized the 2nd half is much more valuable. Also can you add some concrete examples during the explanation?

[@codeKarle]

Sure, I can add the examples in the future ones. Editing now if really hard, so we'll try to keep the important parts before in the next ones :)