Core Concepts of Hash Maps and Sets: Lookups, Frequency Counting, and Deduplication Quiz

Test your understanding of hash maps and sets with this quiz covering key concepts like fast lookups, frequency counting, and deduplication. Strengthen your problem-solving skills by applying these data structures to real-world programming scenarios.

1. Identifying Purpose of Hash Maps

   Which task is most efficiently solved using a hash map in a scenario where you need to count how many times each word appears in a paragraph?

   1. Maintaining the order of the words
   2. Finding the median word
   3. Sorting the words alphabetically
   4. Tracking the occurrence of each unique word

   Explanation: Hash maps provide fast access to values associated with unique keys, making them ideal for tracking occurrences. They do not maintain order, so maintaining order or sorting alphabetically is not their primary function. Finding the median word is unrelated to the capabilities of hash maps.

2. Hash Set Deduplication

   If you have an array with repeated numbers, which data structure allows you to efficiently remove duplicates and keep only unique values?

   1. Array
   2. Linked list
   3. Hash set
   4. Queue

   Explanation: A hash set ensures all elements are unique, automatically discarding duplicates during insertion. Arrays, queues, and linked lists allow duplicates by default and require additional algorithms for deduplication. Only the hash set directly enforces uniqueness.

3. Lookup Time Complexity

   What is the average-case time complexity for looking up a value by key in a well-implemented hash map?

   1. O(1)
   2. O(log n)
   3. O(n)
   4. O(n^2)

   Explanation: Hash maps provide constant-time, or O(1), average-case lookups due to direct access by key. O(log n) is typical for binary search trees, while O(n) and O(n^2) are slower and do not reflect typical hash map performance. Poor hash functions or collisions may degrade performance, but ideally, O(1) is expected.

4. Membership Test in Sets

   Given a large collection of integers, which operation is fastest when using a hash set to determine if a number exists?

   1. Counting the total number of elements
   2. Retrieving an element by position
   3. Finding the smallest element
   4. Membership test (e.g., checking if a number is present)

   Explanation: Hash sets excel at fast membership tests, typically in constant time. Finding the smallest element, counting elements, and retrieving by position are either less efficient or unsupported directly in hash sets. Index-based access is not a feature of sets.

5. Handling Missing Keys

   When you try to access a key that does not exist in a hash map, what typically happens?

   1. A random existing value is returned
   2. An error or a special null/undefined value is returned
   3. The key is added to the map with a random value
   4. The operation automatically inserts the key with a default value

   Explanation: Most hash maps return a null equivalent or raise an error for missing keys. Auto-inserting or assigning random values does not occur unless explicitly coded. Returning a random existing value would break the consistency of the structure.

6. Collision Resolution

   What is the purpose of collision resolution in a hash map?

   1. To handle multiple keys that hash to the same index
   2. To compress the stored data
   3. To reorder the original data
   4. To increase the hash table size arbitrarily

   Explanation: Collision resolution deals with cases where different keys produce the same hash index, ensuring no data is lost. Reordering, increasing the size, or compressing data do not address collisions. These distractors refer to unrelated concepts.

7. Frequency Counting Example

   If you want to determine which character occurs the most in the string 'balloon', what is the most effective approach using a hash map?

   1. Store each character in a stack
   2. Use each character as a key and count occurrences as values
   3. Sort the string alphabetically
   4. Convert the string to a linked list

   Explanation: A hash map efficiently associates each character with its frequency count. Sorting or using stacks/linked lists would not directly track the count of each unique character. The specified approach is standard for frequency analysis.

8. Subset Check with Sets

   To quickly check if all elements from list A are present in list B, which approach using sets is most efficient?

   1. Convert both lists to sets and check if set A is a subset of set B
   2. Iterate through list A for each element in list B
   3. Concatenate the lists and look for duplicates
   4. Sort both lists and use binary search

   Explanation: Converting to sets enables efficient subset checks, leveraging fast membership tests. Sorting and binary search are slower due to repeated searching, while concatenation and iteration introduce unnecessary complexity. The subset operation is direct and optimal with sets.

9. Key Uniqueness in Hash Maps

   When inserting key-value pairs into a hash map, what happens if two pairs share the same key but have different values?

   1. Both values are stored separately for the same key
   2. The earlier value is kept, and new insertions are ignored
   3. An error is always thrown
   4. The latest value overwrites the previous value for that key

   Explanation: Hash maps permit only one value per key, so inserting a duplicate key replaces the old value. Storing multiple separate values or always throwing an error are not standard behaviors. Retaining the earlier value is also incorrect; updates typically override.

10. Iterating Over Map Entries

    Which of the following is a correct way to access every key-value pair in a hash map for processing?

    1. Use a queue to store all possible values
    2. Reverse the map and iterate backwards
    3. Iterate over the set of key-value pairs
    4. Refer to entries by index numbers

    Explanation: Accessing entries directly via key-value pairs allows processing all elements. Index-based reference is not supported, as hash maps are not ordered. Queueing values or reversing maps are unrelated to standard map iteration.

11. Handling Case Sensitivity

    If a hash map is used to store word frequencies from the list ['Dog', 'dog', 'DOG'], what should be done to ensure that these are counted as the same word?

    1. Store word lengths instead of actual words
    2. Convert all words to the same case (lower or upper) before inserting
    3. Insert words without modification
    4. Sort the words before inserting

    Explanation: Standardizing case treats 'Dog', 'dog', and 'DOG' as the same word for frequency counts. Without this, each is counted separately. Sorting doesn't address case, and storing lengths simply ignores the actual words.

12. Set Operations: Intersection

    Given two sets, X = {1, 2, 3} and Y = {2, 3, 4}, which set operation will yield {2, 3}?

    1. Intersection
    2. Symmetric difference
    3. Difference (X - Y)
    4. Union

    Explanation: Intersection gives the common elements of both sets, which is {2, 3}. Union would yield {1, 2, 3, 4}, difference would produce {1}, and symmetric difference would result in {1, 4}, not {2, 3}.

13. Dealing with Value Collisions

    If two different keys in a hash map produce the same hash code, what must the data structure do to store both key-value pairs?

    1. Replace one key-value pair with the other
    2. Use a collision resolution strategy like chaining or open addressing
    3. Combine the values into a single entry
    4. Delete both entries

    Explanation: Proper collision resolution allows both pairs to coexist despite the shared hash code. Replacing, combining, or deleting entries would lead to data loss, which is avoided by careful implementation of hash maps.

14. Use Case for Sets

    Which of the following is a suitable use case for a set rather than a list?

    1. Keeping track of the visiting time order
    2. Maintaining the sequence in which visitors arrived
    3. Allowing duplicate entries for statistical purposes
    4. Tracking unique visitor IDs to a website

    Explanation: Sets automatically enforce uniqueness, ideal for unique IDs. Lists are better for ordered or duplicate-allowed requirements. Sets do not preserve insertion order or allow duplicates, unlike lists.

15. Map Access by Index

    Can you directly access an element by its index in a hash map, such as getting the third key-value pair inserted?

    1. Yes, index lookup is supported in all hash maps
    2. Direct index-based access is only possible with stacks
    3. Only if the hash map is sorted
    4. No, because hash maps do not guarantee order

    Explanation: Hash maps are inherently unordered, so index-based access is not possible. Even if sorted externally, hash maps themselves lack indexing. Stacks and sorted data structures involve different types of access mechanisms.

16. Use Cases: Counting vs. Existence

    If you only need to check whether an email address is part of a mailing list and do not care how many times it appears, which data structure is most appropriate?

    1. Array with sorted search
    2. Set
    3. Hash map with counts
    4. List with duplicate removal

    Explanation: A set efficiently tests for existence without tracking counts. Counting or sorting with arrays or lists is unnecessary overhead. Sets suit existence checks due to their unique membership property.