educative.io

The data structure Min-Heap is not the most efficient to store the parking spots in the order of the shortest distance from the entrance

Courses
,
#1

The data structure Min-Heap is not the most efficient to store the parking spots in the order of the shortest distance from the entrance.

Clearly this will be inefficient if there are multiple entrances and multiple entry gates. The following step can cause the entire heap to be re-constructed.

  • We mark the parking spot as reserved and remove it from the available set. We also remove it from the min-heaps of other entrances.

A tree map would be a better data structure to be used here.

Course: Grokking the Low Level Design Interview Using OOD Principles - Learn Interactively
Lesson: Class Diagram for the Parking Lot

1 Like
#2

Hi @Kanishka_Jaiswal, Thanks for reaching out to us.

Thank you for your insightful observation regarding the parking problem coding strategy. We appreciate your attention to detail and your consideration of alternative data structures.

Upon reviewing your suggestion to use a TreeMap instead of a min-heap, We completely agree with your assessment. Using a TreeMap seems to be a more efficient choice for our scenario, especially when dealing with multiple entrances and the need to efficiently remove reserved parking spots.

The TreeMap’s logarithmic time complexity for insertion, deletion, and search operations aligns well with our requirements. It will allow us to maintain the order of parking spots based on their distance for each entrance while facilitating the removal of reserved spots in an efficient manner.

Your input has been invaluable, and We’re grateful for your contribution to optimizing our parking coding strategy.

If you have any further suggestions or questions, please feel free to share them. Your feedback is much appreciated. :blush: