Hash Maps and Sets: Entity Lookup and State Tracking Quiz Quiz

Explore your understanding of hash maps and sets with these scenario-based questions focusing on entity lookup and tracking state. This quiz covers key concepts like efficient search, duplication checks, and the differences between common data structures in programming.

1. Efficient Presence Checking

   Given a collection of unique user IDs, which data structure allows you to most efficiently check if a user already exists when processing logins?

   1. Hash Set
   2. Queue
   3. Linked List
   4. ArrayList

   Explanation: A hash set enables constant-time (O(1)) presence checking, making it ideal for verifying if a user ID exists. Linked lists and array lists require linear time (O(n)) for such checks since they scan each element. A queue is primarily designed for FIFO access and is not optimized for fast lookups. Therefore, a hash set is the most suitable option for this scenario.

2. Hash Map Key-Value Association

   When tracking which items have been purchased by a customer in a shopping cart application, which data structure allows you to map each customer ID to a list of item IDs?

   1. Priority Queue
   2. Hash Set
   3. Hash Map
   4. Stack

   Explanation: A hash map efficiently associates a unique customer ID (the key) with a list of item IDs (the value), enabling quick access to each customer's purchase list. Stacks and priority queues are not meant for key-value relationships; they manage elements based on order or priority. A hash set stores unique items but does not support mapping one entity to collections of others.

3. Tracking Unique Visits

   You need to count the number of distinct web pages visited from a list that may contain duplicates. Which approach best ensures that each page is counted only once?

   1. Insert each page into a set
   2. Track visits with a queue
   3. Sort the list and count sequentially
   4. Add page URLs to a stack

   Explanation: Using a set automatically removes duplicates, so each web page is stored only once in the collection. Adding URLs to a stack or queue maintains all entries, including duplicates, making it unreliable for unique counting. Sorting the list could help but requires extra steps and is less efficient in both time and code clarity compared to using a set.

4. Updating Entity State

   If you are managing player scores in a video game where you must update a player’s latest score frequently, which data structure is most appropriate to store and update scores by player ID?

   1. Tree Set
   2. Hash Stack
   3. Hash Map
   4. Array Queue

   Explanation: A hash map allows you to directly associate each player ID with their current score and to update it in constant time. An array queue or stack stores elements linearly and does not provide direct access by player ID. A tree set is best suited for storing unique items in a sorted order, not for key-value pair updates.

5. Handling Missing Entities

   Suppose you want to check if a student's name exists in your registry before assigning them new coursework. What operation would a hash set offer for this scenario?

   1. Slow sequential search
   2. Automatic ordering
   3. Constant-time lookups
   4. Priority-based access

   Explanation: A hash set provides constant-time (O(1)) operations for checking if an item exists, which is ideal for verifying student names quickly. Automatic ordering is not provided by hash sets; ordered sets or trees are used for that. Priority-based access is a feature of priority queues, not sets. Sequential search is common in lists, not in hash sets.