Katkat
Back

Design an ads retrieval service using a heap

GoogleSoftware Engineer · Onsite
EasySoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

This question tests the ability to design a retrieval system using a priority queue and the implementation of efficient operations to maintain a sorted collection of ad candidates.

Ad Retrieval Service Design

Design an AdRetrievalService that maintains a collection of active advertisement candidates, each with an associated score. The service must support high-frequency retrieval of the top-k highest-scoring ads for a given request.

API Requirements

Implement the following methods:

  1. add_ad(ad_id: int, score: float): Adds a new ad to the service. If the ad_id already exists, update its score.
  2. remove_ad(ad_id: int): Removes an ad from the service.
  3. get_top_k(k: int): Returns a list of the top k ad_ids based on their scores, sorted in descending order.

Constraints

  • n (total ads) can be up to 100,000.
  • k is typically small (e.g., k <= 100).
  • Efficient performance is required for both updates and retrieval.

Examples

service = AdRetrievalService()
service.add_ad(101, 0.95)
service.add_ad(102, 0.88)
service.add_ad(103, 0.99)

# Expected: [103, 101]
print(service.get_top_k(2))

service.remove_ad(103)
# Expected: [101, 102]
print(service.get_top_k(2))

Considerations

  • How will you handle the "update" operation if the ad is already in the heap?
  • Consider the trade-offs between using a standard heap versus other data structures like a balanced BST or a hash map combined with a heap.

Hints

Hint 1

A standard heap does not support efficient arbitrary updates or deletions; consider using a hash map to store references to the ads.

Hint 2

For the 'remove' and 'update' operations, you can use lazy deletion by keeping a 'tombstone' or 'version' flag in the heap and cleaning it up during retrieval.

Hint 3

If heap updates are too expensive, compare the complexity of rebuilding the heap versus using a balanced Binary Search Tree to maintain sorted order.

Follow-up questions

  • How would you modify your design if the ad scores change continuously in real-time based on incoming traffic?
  • What are the concurrency implications if multiple threads are calling `add_ad` and `get_top_k` simultaneously?
  • If the number of ads grows to billions, how would you distribute this service across multiple servers?