Bird
Raised Fist0

What is the time complexity of searching for an available parking spot in a parking lot implemented as a list of spots per level, assuming N spots per level and L levels, when the system checks spots sequentially?

medium🪤 Complexity Trap Q5 of Q15
OOP & Design Patterns - Design a Parking Lot - LLD with OOP (Classes, Patterns, Extensibility)
What is the time complexity of searching for an available parking spot in a parking lot implemented as a list of spots per level, assuming N spots per level and L levels, when the system checks spots sequentially?
AO(N) because only one level is searched at a time
BO(L * N) because all levels and spots may be checked sequentially
CO(log N) if spots are sorted by availability
DO(1) due to direct indexing of spots
Step-by-Step Solution
Solution:

  1. Step 1: Understand the data structure

    Each level has N spots stored in a list; L levels exist.

  2. Step 2: Analyze search process

    Sequential search checks spots one by one per level, potentially across all L levels.

  3. Step 3: Calculate complexity

    Worst case: all L levels * N spots each -> O(L * N).

  4. Step 4: Evaluate other options

    O(N) ignores multiple levels; O(log N) assumes sorted structure which is not given; O(1) assumes direct access which is not possible for availability check.

  5. Final Answer:

    Option B -> Option B

  6. Quick Check:

    Sequential search across all levels multiplies complexity [OK]
Quick Trick: Sequential search over L levels and N spots is O(L*N) [OK]
Common Mistakes:
MISTAKES
  • Ignoring multiple levels and picking O(N)
  • Assuming sorted spots for O(log N)
  • Assuming direct indexing for O(1)
Trap Explanation:
PITFALL
  • Candidates often forget to multiply by number of levels, underestimating complexity.
Interviewer Note:
CONTEXT
  • Tests understanding of complexity in multi-level data structures.
Master "Design a Parking Lot - LLD with OOP (Classes, Patterns, Extensibility)" in OOP & Design Patterns

2 interactive learning modes - each teaches the same concept differently

SolutionTrace

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More OOP & Design Patterns Quizzes
Command Pattern - Undo/Redo, Request Queuing & Logging - Command Pattern - Undo/Redo, Request Queuing & Logging - Quiz 12easy Encapsulation - Data Hiding, Getters/Setters & Access Modifiers - Encapsulation - Data Hiding, Getters/Setters & Access Modifiers - Quiz 12easy Inheritance - Types, Method Resolution Order & Diamond Problem - Inheritance - Types, Method Resolution Order & Diamond Problem - Quiz 8hard Inheritance - Types, Method Resolution Order & Diamond Problem - Inheritance - Types, Method Resolution Order & Diamond Problem - Quiz 5medium Iterator & Composite Pattern - Traversal Abstractions - Iterator & Composite Pattern - Traversal Abstractions - Quiz 1easy Observer Pattern - Event System, Publish-Subscribe - Observer Pattern - Event System, Publish-Subscribe - Quiz 9hard Polymorphism - Compile-Time (Overloading) vs Runtime (Overriding) - Polymorphism - Compile-Time (Overloading) vs Runtime (Overriding) - Quiz 5medium Polymorphism - Compile-Time (Overloading) vs Runtime (Overriding) - Polymorphism - Compile-Time (Overloading) vs Runtime (Overriding) - Quiz 7medium Singleton Pattern - Thread Safety, Double-Checked Locking & Lazy Init - Singleton Pattern - Thread Safety, Double-Checked Locking & Lazy Init - Quiz 1easy Strategy Pattern - Replace Conditionals with Polymorphism - Strategy Pattern - Replace Conditionals with Polymorphism - Quiz 5medium