Great video Jordan. The attention to detail is incredible. Suggestion: You could consider adding additional feature - how would active users ( who are current travelling from source to destination ) get real time updates on traffic condition + suggestion on alternate best route. Pull : May be user at regular intervals requests for revised ETA from their current location to destination OR Push: alternate best route to active users
Yeah this is an interesting one! If I had to make a solution right off the bat, I'd probably have a table from short road ID: userIds that are currently on a route taking that short road (they get removed from the table after they pass it). That way, if we change a short cut road, we know to notify those users to recalculate their route.
Probably so, just 1) I'm less familiar with A* 2) Didn't feel like it was that important for the system design interview if more people are familiar with Djikstra's it may be easier to teach
Can you explain how do we design the transit system in google map. Basically which bus, train, ferry to take to go from source to destination taking into account waiting time, walking distance, fewer transfers etc?
I guess this is more algorithmic, but I really think its more of the same. Effectively just map out each bus route and train route as if they were a road.
@@jordanhasnolife5163 that makes sense! instead of using the actual map locations, we can store the bus/train/freey route co-ordinates in our geohash table/index and then use to find the shortest route using Djikstra's algorithm or A* algorithm
How does shortcut edges dependencies gets updated? I see an arrow from Graph -> Shortcut Edge dependencies table. Is there a cyclic dependency from Flink (roadETAUpdates) -> graphs -> shortcut edges db -> Kafka -> flink again?
Yep! You can either do that if you have arbitrary numbers of shortcut edges, or you could just edit all of the graphs at once from flink originally off of a road ETA update.
I don't think the full graph of road networks is actually that big. Offline satellite navigation systems have existed since the 90s. Those early systems couldn't fit the whole world on them, you'd have to switch a physical medium if you left your region. I remember the entire USA road network fitting on a 2GB SD card in 2010-ish, which also included the address database and physical map geometry, not just abstract connected graph data.
Haha that makes sense! I imagine the roads themselves may not be that big, but when you actually factor in the locations on the roads/individual addresses it becomes much more of a large graph.
Please do a google calendar system design. There are very few videos of it and most of them don't support recurring events and their edits. Thank you once again.
Interesting thought - see from a systems design perspective I don't know how challenging this one is but you should definitely look up the recurring calendar problem, there's a paper on it I believe
Nice video, just want to ask to use some different colour when you draw/write smth on a diagram that you prepared beforehand. It sometimes hard to follow p.s. I'd be glad to see the design of Google Faps btw
Audio and video are way out of sync. It looks like you're saying something but drawing something else. Makes it a little difficult to watch your otherwise excellent videos.
how do you handle querying the sparse map if the start/end nodes are in different partitions. you would have to do cross partition traversal i guess you could use the more sparse graph, but then you lose accuracy also, what reference did you use to create this video? i want to read more about it
It's a tradeoff - I'd say use the sparser graph, but you could also deal with a cross partition traversal. I'd just start googling contraction hierarchies and go from there!
Just had a design interview, punching out of my weight class given my experience so I struggled a bit. High level was alright and even some specifics. The biggest issue though was addressing technology specific questions. Not about trade offs but more about how I am actually interacting with each technology code-wise. Half of these I’ve never actually used so those questions were unanswerable for me. For the future I think maybe running through docs examples in code for all of these components before I use them in a design interview could help me with those kind of questions.
@@jordanhasnolife5163 Just general questions. I might say something like let’s use X here and they might ask “how would you implement that”. I assume I can still answer that on a high level but there is a decent amount of abstraction assumed in these interviews like maybe some system in front of the db you don’t feel you have to draw a box for. A lot of times I stumbled on the answers if you go down to a very granular level on how the data is flowing through the system. I missed a few services that are sort of implicitly assumed and usually skipped for the sake of time in an interview, but I should be able to answer if they ask. As for future videos, I’d be interested in seeing how you would approach a problem where scale is large but only for a portion of the problem. At a high level imagine being a portal between some low performant external system and having it be as available and fast as possible for a massive user base. Can’t change this system though so you have to build around it. Also I have some feedback now. Was moved a level lower but continued in the process and just got an offer, these videos definitely helped me get there so thanks!
when people say Jordan is the GOAT, I think of this Jordan
I'm more of a bron guy anyways
That intro is CRAZYYYYYY funny, love you man
Great video Jordan. The attention to detail is incredible. Suggestion: You could consider adding additional feature - how would active users ( who are current travelling from source to destination ) get real time updates on traffic condition + suggestion on alternate best route. Pull : May be user at regular intervals requests for revised ETA from their current location to destination OR Push: alternate best route to active users
Yeah this is an interesting one! If I had to make a solution right off the bat, I'd probably have a table from short road ID: userIds that are currently on a route taking that short road (they get removed from the table after they pass it). That way, if we change a short cut road, we know to notify those users to recalculate their route.
Awesome video, why do you not use A* instead of djikstra? I feel like L2 distance is a solid enough heuristic and may be faster?
Probably so, just 1) I'm less familiar with A* 2) Didn't feel like it was that important for the system design interview if more people are familiar with Djikstra's it may be easier to teach
Can you explain how do we design the transit system in google map. Basically which bus, train, ferry to take to go from source to destination taking into account waiting time, walking distance, fewer transfers etc?
I guess this is more algorithmic, but I really think its more of the same. Effectively just map out each bus route and train route as if they were a road.
@@jordanhasnolife5163 that makes sense! instead of using the actual map locations, we can store the bus/train/freey route co-ordinates in our geohash table/index and then use to find the shortest route using Djikstra's algorithm or A* algorithm
Really enjoyed and learnt a lot from this video! Thanks ❤🔥
Another Jordan classic!
How does shortcut edges dependencies gets updated? I see an arrow from Graph -> Shortcut Edge dependencies table. Is there a cyclic dependency from Flink (roadETAUpdates) -> graphs -> shortcut edges db -> Kafka -> flink again?
Yep! You can either do that if you have arbitrary numbers of shortcut edges, or you could just edit all of the graphs at once from flink originally off of a road ETA update.
I don't think the full graph of road networks is actually that big. Offline satellite navigation systems have existed since the 90s. Those early systems couldn't fit the whole world on them, you'd have to switch a physical medium if you left your region. I remember the entire USA road network fitting on a 2GB SD card in 2010-ish, which also included the address database and physical map geometry, not just abstract connected graph data.
Haha that makes sense! I imagine the roads themselves may not be that big, but when you actually factor in the locations on the roads/individual addresses it becomes much more of a large graph.
Please do a google calendar system design. There are very few videos of it and most of them don't support recurring events and their edits. Thank you once again.
Interesting thought - see from a systems design perspective I don't know how challenging this one is but you should definitely look up the recurring calendar problem, there's a paper on it I believe
Nice video, just want to ask to use some different colour when you draw/write smth on a diagram that you prepared beforehand. It sometimes hard to follow
p.s. I'd be glad to see the design of Google Faps btw
I see the design around once per day - nice suggestion I may do this soon!
Keep up the good work 🎉🎉
How do I get in touch with you? Can I have your discord ?
I don't really use discord, here's my LinkedIn - www.linkedin.com/in/jordan-epstein-69b017177?
Jordan, why did you leave google?
Well I'd write it here, but I made a whole video about it when I quit, so I'll let myself speak for myself
Audio and video are way out of sync. It looks like you're saying something but drawing something else. Makes it a little difficult to watch your otherwise excellent videos.
e.g. 21:26 you're saying this road, but not pointing at anything.
Noted will try to improve for future
how do you handle querying the sparse map if the start/end nodes are in different partitions.
you would have to do cross partition traversal
i guess you could use the more sparse graph, but then you lose accuracy
also, what reference did you use to create this video? i want to read more about it
It's a tradeoff - I'd say use the sparser graph, but you could also deal with a cross partition traversal.
I'd just start googling contraction hierarchies and go from there!
Just had a design interview, punching out of my weight class given my experience so I struggled a bit. High level was alright and even some specifics. The biggest issue though was addressing technology specific questions. Not about trade offs but more about how I am actually interacting with each technology code-wise. Half of these I’ve never actually used so those questions were unanswerable for me. For the future I think maybe running through docs examples in code for all of these components before I use them in a design interview could help me with those kind of questions.
Seems like reasonable next steps! Definitely would be curious to hear more about what you felt stuck on
@@jordanhasnolife5163 Just general questions. I might say something like let’s use X here and they might ask “how would you implement that”. I assume I can still answer that on a high level but there is a decent amount of abstraction assumed in these interviews like maybe some system in front of the db you don’t feel you have to draw a box for. A lot of times I stumbled on the answers if you go down to a very granular level on how the data is flowing through the system. I missed a few services that are sort of implicitly assumed and usually skipped for the sake of time in an interview, but I should be able to answer if they ask.
As for future videos, I’d be interested in seeing how you would approach a problem where scale is large but only for a portion of the problem. At a high level imagine being a portal between some low performant external system and having it be as available and fast as possible for a massive user base. Can’t change this system though so you have to build around it.
Also I have some feedback now. Was moved a level lower but continued in the process and just got an offer, these videos definitely helped me get there so thanks!
@@lieblius Congrats, and sounds like a good starting point to work on!
LMAO