Design an ads retrieval service using a heap
Company: Google
Role: Software Engineer
Category: Software Engineering Fundamentals
Difficulty: easy
Interview Round: Onsite
## Object-Oriented Design: Ads Retrieval (Priority-Based)
Design a component that manages ads and supports retrieving the “best” ads based on a score.
### Requirements
Implement APIs such as:
- `addAd(adId, score, metadata) -> void`
- `removeAd(adId) -> bool`
- `updateScore(adId, newScore) -> bool`
- `getTopAd() -> Ad | null` (or `getTopK(k) -> List<Ad>`)
Assume higher `score` means higher priority.
### Constraints / Expectations
- Use a **heap / priority queue** as the main structure.
- Discuss **time/space complexity**.
- Handle duplicates and updates correctly (e.g., score changes).
### Follow-ups
- How do you handle `updateScore` efficiently given that typical heaps don’t support decrease/increase-key by ID?
- How do you ensure `getTopAd()` doesn’t return ads that were removed or superseded by a newer score?
Quick Answer: This question evaluates understanding of priority queues/heaps, object-oriented API design, and algorithmic techniques for maintaining dynamic priorities such as add, remove, and update operations.