Design Underground System - Bloomberg 2020 Most Asked Interview Question

Check out my interview prep platform for learning the patterns! 📢 Interview Prep Platform: https://algoswithmichael.com 🎧 Join the community Discord:   / discord   💰 Support me on Patreon:   / michaelmuinos   🔗Follow me on LinkedIn:   / michael-muinos   📂Follow me on Github: https://github.com/MichaelMuinos Intro - 00:00 Problem Description - 00:29 Example Walk Through - 01:35 Code Walk Through - 06:15 Complexity Analysis - 13:20 Design Underground System is a popular Leetcode design problem asked significantly at the company Bloomberg. For this problem, we must implement three functions check in, check out, and get average time. There are a couple approached to solve this design question, but the way I explain it is using two maps. Using hashmaps to solve this problem is the best approach because it will allow you to have a constant time complexity for all functions in your class. For the check in functionality, we must allow a custom to check into a station a certain time. For check out, we must check out a customer at an end station at a specific time. Finally, getting the average time involves taking the average travel time of all previous travel between any two stations. Two maps is perfect for this design because we will always have unique id's for each customer, so we can compute averages in O(1) constant time complexity at any point. The space complexity of our solution is going to be big oh O(N + M) where N is the number of customers that have checked in and M is the number of customers that have checked out. We must combine both N and M because a customer cannot be checked in and checkout at the same time.