Design A Parking Garage | Google SWE Teaches Low Level Design Episode 4

Selling 2 parking spots - one upper level one lower level, prices vary per level, please message my only fans if interested

[@ritikchhillar4963]

Better approach for removing parking spot from multiple entrance queues as most languages can support this out of the box - 1. Change the underlying distances of parking spot from entrances to a INTEGER.MAX_VALUE value. 2. Heapify queues with O(logn) complexity - this will push occupied spot to the bottom of heap. Also, as we are maintaining free spots separately we never get to poll these invalid spots.

[@priyanshubajpai6925]

I am enjoying your videos, thanks for sharing the knowledge! Content is crisp, delivery is consistent. So I don't need to change the playback speed often, which happens to be the case with many other channels!

[@hanibal43]

I got this question I went with an itoration approach first then used a quque to reach O(1). Used an array and a hashmap for keeping the orderes of spot

[@rvpandey99]

I come here after watching your video with Gaurav Sen doordash system design interview.

[@supritdk2956]

As already pointed by a couple other comments, when you add/ remove elements from priority queue, you would heapify which changes the index for the spot in underlying array. This would mean your hashmap goes out of sync not only for the element that is being inserted/deleted but in worst case for all the elements in the map. You would then have to construct the entire map again which I dont think is very good and negates the value provided by the priority queue. At this point you may as well do a linear search. Am I missing something here?

[@jordanhasnolife5163]

Yep in retrospect something like a doubly linked list with hash map would have been better here.

[@axellbrendow1]

It's possible to keep the hashmap updated if you implement your own priority queue and update the map at every add, delete or swap between elements inside the heap. That wouldn't change the time complexity of the priority queue and would provide you O(logn) deletes even in the middle of the heap.

[@sudhirdharmadhikari1938]

Nice ! Question. Wouldn't priority queue array index vary based on adding/removing of other vehicles in the queue ?

[@jordanhasnolife5163]

Yeah you'll just have to change that hash entry 😭, it doesn't change time complexity

[@Rakeshkumar-po2yg]

@jordan Can you please elaborate more on parkingSpotHashMap and pQueues ? How these are defined .

[@jordanhasnolife5163]

I think the main point to realize is from each entry certain spots are more preferable, hence we need a priority queue to represent this. However there are multiple entrances, and each one is at a different location in the lot, so the rankings of spotsos different for each entrance, meaning we may want multiple different priority queues, one per entrance. Unfortunately, this means that we need to keep them in sync - to do that a hash map that points from a spot in a pqueue to the corresponding spots in the other pqueues allow us to quickly find and remove the corresponding nodes when a single spot is taken up.

[@Rakeshkumar-po2yg]

@@jordanhasnolife5163 hey Jordan thanks for your prompt reply.

[@blenderbottle382]

@@jordanhasnolife5163 to keep them in sync, you'd need to re-heapify each pqueue after removal correct?

[@priyanshubajpai6925]

ig you put EXIT_NUMBER as a parameter in the method signature instead of the entrance_number

[@jordanhasnolife5163]

Yup nice catch

[@priyanshubajpai6925]

enter method would also need to remove the 'location in p_queue' from parkingSportHashMap? or is it redundant?

[@jordanhasnolife5163]

That seems fair to me, though I'm not sure it's entirely necessary

[@huazhou2]

@9:54, wouldn’t add element into min heap also change the index of array? i.e. the value in the hashmap?

[@jordanhasnolife5163]

Yes good point, you can just build the heap first and then add in the hash-map.

[@huazhou2]

Thanks@@jordanhasnolife5163! but the idea of using hashmap is to reduce time complexity for deleting/adding element from minheap, each element deletion or addition to the minheap will change like half branch's elements' indices (the worst case), and the deleting element from minheap is always o(logn) even if using a hashmap as a byside data structure (in this case, we also need to update hashmap whenever there's entry or exit of car, which increases time complexity), what do you think a way to reduce complexity for manipulating minheap in this case?

[@maheshkumar-sl8eq]

Why can’t we use data base.. we can store the in database when parking in booked and we can delete record when they vacate ..

[@jordanhasnolife5163]

This is a low level design problem, so I'm not even bothering to discuss databases

[@amen652]

Yo Jordan, I have a OOP type technical interview coming up. Been watching through your videos. Do you have any resources you could point me to that helped you with breaking down these problems, etc? (I like men)

[@jordanhasnolife5163]

Thanks for specifying that you like men at the end there, that helps. No specific resources, I think you should just try to search for the types of problems that get asked in these interviews, come up with your own solution, and then if you're struggling look up solutions online. Then from there iterate and look to apply what you learned!

[@Rakeshkumar-po2yg]

Hey @jordanhasnolife5163 I had a interview where I need to design a way where two screen are connected to each other (like a video wall Screens) and when we press "ON" button on remote controller both the screens will be turned on and when we press "OFF" button both will be turned of. Can we do with the help of sockets or if you can suggest a way to do so? Please help me.

[@jordanhasnolife5163]

Is this a LLD or systems design question? If the latter than sure websockets work

[@kunparekh1886]

i come here only for the descriptions

[@jordanhasnolife5163]

I come only for the men

[@zuowang5185]

Typical parking lot doesn’t assign spot

[@jordanhasnolife5163]

Correct but then this problem wouldn't be worth doing. You'd just enter lol