Practice/Amazon/Design a System to Track Recently Viewed Items

Design a System to Track Recently Viewed Items

Object Oriented DesignMust

Problem

Design and implement a class that tracks recently viewed items for an e-commerce platform. The tracker should maintain a fixed-size history of item views, automatically removing the oldest items when the capacity is exceeded. When a user views an item that's already in their history, it should be moved to the most recent position rather than creating a duplicate entry.

Your RecentItemsTracker class should support the following operations:

• Constructor: Initialize the tracker with a maximum capacity
• view_item(item_id): Record that an item has been viewed
• get_recent_items(): Return a list of recently viewed items in order from most recent to least recent

Requirements

1. The tracker must have a fixed capacity specified at initialization
2. When viewing an item that exceeds capacity, the least recently viewed item should be removed
3. If an item is viewed again, it should be moved to the most recent position without duplication
4. The get_recent_items() method should return items ordered from most recent to least recent
5. All operations should be efficient (ideally O(1) for view operations)

Constraints

• 1 ≤ capacity ≤ 10,000
• 1 ≤ item_id ≤ 1,000,000
• At most 100,000 view_item operations will be called
• Item IDs are unique positive integers

Examples

Example 1: Basic Usage

tracker = RecentItemsTracker(3) tracker.view_item(101) tracker.view_item(102) tracker.view_item(103) tracker.get_recent_items() // Returns: [103, 102, 101]

Example 2: Exceeding Capacity

tracker = RecentItemsTracker(2) tracker.view_item(1) tracker.view_item(2) tracker.view_item(3) // Item 1 is evicted tracker.get_recent_items() // Returns: [3, 2]

Example 3: Updating Position

tracker = RecentItemsTracker(3) tracker.view_item(10) tracker.view_item(20) tracker.view_item(30) tracker.view_item(20) // Move 20 to front tracker.get_recent_items() // Returns: [20, 30, 10]