Google Maps System Design Interview Question
Вставка
- Опубліковано 30 вер 2024
- 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
I reckon this will become the best system design channel in youtube. Keep up the good work !
Thanks for the motivation! Do share it with your friends to help us get there 🙂
I second this. This is by far the best system design video I watched on youtube.
true
Exactly.
No doubt about that.
you channel name should be DesignKarle instead 😛
This is brilliant but Im kinda surprised you didnt mention quad trees. They are the standard way to solve problems like this.
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.
very good content, but the audio is a torture.
This was on its way to become the best sys design channel on UA-cam 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!
is it really true that Google Map has 1 billion users? we have 7 billion population and out of them so many kids, old people and huge population of the world might not use these apps.
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.
how is it going now?
What other system design resources do you recommend for the interview preparation?
This is the level of details that helps in real interviews. Thanks!
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
Yeah, true, that could be done :)
@@codeKarle why Cassandra is chosen in this scenario. It is column based databases? why not document db kind of db is used?
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?)
You are pretty smart! Thank you for your videos. I am learning it out of curiosity
Thanks!! Happy that the videos are helping you
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.
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 :)
🎯 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
Quality content as always. But plz do something about your audio.
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.
Can you plz...... teach system design from basics. Playlist
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!
This was an amazing explanation!!! I request you to please post a video about LinkedIn System Design as well. Good Work!!!
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: ua-cam.com/video/9-hjBGxuiEs/v-deo.html
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.
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?
Good Explanation.. Good Job !..
Que: How Zoom Aggragate video streaming in One UI (on Zoom Client)?
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?
Is this series completed? It was a great series... Keep it going man!!!
Awesome work you are doing. I would like if you can do small videos covering topics like SQL/ NoSQL, Micrososervices, Kafka Messaging Queue etc.
Great suggestion! We'll do that too
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?
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.
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
Sure, well try to do that
At 14:44, it doesn't give shortest distance between x and y
surprised we use "segments" instead of geohashes
that would take 10 years to implement
Discussion around - Disputed areas, last bit of inferences like pub goers are social etc..was icing on the cake!!!
How is a user location mapped to some point on a road ?
Can you make a video on spark streaming ?
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?
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.
Loved your approach about calculating distances ..
After 2 years, still an amazing video!
Very smart to include discussion of disputed areas in this video
How does this guy know all of this
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.
Thank you for google map . Didn't find any other video on this topic. u did a wonderful job.🙂
Thanks you :)
Let us know what other videos you'd like to see
@@codeKarle google search 🙂
@@nikitasinghchauhan6239 that would be live soon!!
Amazing bro, I like it, keep it up 👍
Thank you for Sharing
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?
Your all videos are awesome.
A very helpful one.
do you keep a ETA heap for each segment? Not sure how you can efficiently bubble up when a road condition is changed.
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.
Great work. It will be great if you can put some content about Google Doc and git design.
Sure, but that might take a while to be live :)
woah!!! awesome work, keep doing that
Thanks for the kind words!! Do share it with your friends :)
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 :)
Hi, can anyone help with this question: System design question to design a heatmap. user can input any range of times (in minutes) and I want to be able to see the density of drivers on the map color coded You don't have to worry about the actual color coding part (assume you have some UI that will take in the count input and do the coloring for you).
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)
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.
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).
Those are coming soon
@@codeKarle will you be producing more content ?
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.
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?
Hat's off Man!
On the Disputed Areas- what if user see the map from some other country? how do google decide boundaries?
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.
Nice Sandeep. Hope to see more content from you, but scoped to 35 min. But this one was informative to every minute and a nice write up!
Mega Segments: Are you meaning to say that in creating a route from Bengaluru to Mumbai, the constituencies or taluks along the way don't matter in that " outer layer" of computation because those have been reduced to a point (Sholapur or Kolhapur) in that layer where we apply the algorithm? This means something like min of a sum ~= generally a sum of minimums, which avoids end-to-end (massive, over) computation for little to no gain (in fact losing computation time, storage). O(nlogn) is >> O(mlogm) + O(klogk) + .. where m,k are < n (may add up to n). I didn't mean to get into maths, but that is what we are looking at in breaking a continuous spectrum of points to discrete points for each outer layer. Is this about accurate?
I don't see you use spatial database like quadtree. What is your opinion?
So long the Djikstra's algorithm is applied between cities, it picks up the best cached routes for the exit points of the cities of Sholapur or Kolhapur.
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?
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?
Websocket handler/manager is primarly required in the navigation flow not while collecting the lat/lon of users. what do you think ?
Amazing content
Awesome and details content. Can you make a video about distributed scheduler ?
Very strong presentation. Actually the best what I have seen about this topic. Appreciate.
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?
Can you please explain how did u come up with this design? What resources did you follow?
Very comprehensive!!
Liked the "Summary of this video" too.
What is the data schema for the Cassandra that is attached to the Graph Processing Service?
How to calculate the exit point of segment ? ( e.g. s1e1 )
Can you please make a video of how payment systems work? Say Design Square or Design Visa.
Super explanation of a very complex system. Thank you
When to use Cassandra ? and when to use hadoop ?
any differences ?
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.
Thanks a lot for your work! I believe the word you're looking for is "cell" (5:56)
I wonder if a video about stock trading systems can be made?
I didn't understand the difference between theoretically calculated road and cached or real roads? Could you explain?
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?
I love the content! Could you please make video about databases and streaming systems?
Could we use zookeeper instead of web socket manager?
Thanks for keeping the explanations simple. I have seen some videos where people just bombard with jargons reducing interest.
Can i start this series with basic information about System Design?
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?
headphone model brand batao voice quality is nice
Perfect!
Thanks for this awesome video. Next would like some LLD videos too.
So spark streaming is consuming as well as writing back to kafka? or are we going to create a different kafka for that?
Thanks you. Nice explanation
Thank You
Awesome explaination ...
This channel will become a boom ...
This was a really awesome video. The first 40 min. were gem
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?
Thank you, quite insightful
Thanks!
Are we expected to solve this completely for a typical SDE-2 role having 3 years experience ? because this was a lot to digest for me.
Not all of it, but a good portion of it. For an SDE-2, you could skip out analytics and the big data portion completely, and still get a positive feedback. All of it would be required in-case you are applying for an Architect role.
Thanks for the amazing series. I would just recommend going with simple design problems to start with and increment the complexity for beginners. Thanks
Really good video, all parameters considered 👍
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 :)
super。learning new knowledge，ilove it
This is a very solid 1-hr content!