Arrays and Hash Maps: Deduplication u0026 Frequency with Big-O Basics Quiz

Test your knowledge of arrays and hash maps, focusing on deduplication, frequency counting, and their Big-O time and space complexities. This beginner-friendly quiz helps reinforce essential concepts and best practices in algorithm efficiency and data structure usage.

1. Identifying Duplicate Elements in Arrays

   Given an array of integers, which data structure is commonly used to detect duplicates in O(n) time?

   1. Array list
   2. Linked queue
   3. Hash set
   4. Binary tree

   Explanation: A hash set allows for O(1) average time lookups, making it efficient for checking if an element has already appeared. Array lists do not provide constant time searches, so they can result in slower performance. Binary trees require O(log n) time per operation and are more complex for this use. Linked queues do not support fast lookups and are not suitable for deduplication.

2. Frequency Counting in Simple Arrays

   Which approach efficiently counts how many times each value occurs in an integer array?

   1. Sorting and then traversing
   2. Using a hash map
   3. Using a stack
   4. Applying recursion only

   Explanation: A hash map can track the frequency of each element with O(1) insertions, leading to O(n) total time. Sorting and traversing works but is less efficient due to the sorting step. A stack does not support key-based access or frequency tracking. Recursion does not inherently provide a counting mechanism or improve efficiency here.

3. Big-O Time for Array Deduplication

   What is the average-case time complexity for removing duplicates from an array using a hash set?

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

   Explanation: Each element can be checked or inserted into the hash set in O(1) on average, so the overall process is O(n). O(n^2) results from nested loops without hashing. O(log n) applies to balanced trees, not hash sets. O(1) is incorrect because it ignores scanning all elements.

4. Unique Integer Extraction Example

   If you want to extract unique integers from the array [1, 2, 2, 3], which structure lets you do so with O(n) time and stores only unique values?

   1. Queue
   2. Stack
   3. Array
   4. Hash set

   Explanation: A hash set only keeps unique values and provides O(1) operations, ensuring O(n) time overall. Queues and stacks may store duplicates unless managed manually, losing the efficiency and property of uniqueness. A regular array does not enforce uniqueness.

5. Counting Word Occurrences

   To count how many times each word appears in a list of strings, which technique is most efficient?

   1. Adding words to an array
   2. Reversing the list
   3. Using a binary search tree only
   4. Mapping each word to a counter in a hash map

   Explanation: Mapping each word to a counter in a hash map takes O(1) time per word, making it efficient and straightforward. Simply adding words to an array does not count their occurrences. A binary search tree complicates insertion and may not guarantee O(1) time. Reversing the list does not assist in counting frequencies.

6. Big-O Space for Counting Frequencies

   What is the space complexity of counting the occurrences of each distinct string in an array with n elements and k unique strings?

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

   Explanation: O(k) space is used because each unique string occupies a slot in the frequency map. O(n^2) is incorrect as space does not scale quadratically here. O(1) space is not realistic as more unique elements require more storage. O(log n) is unrelated to the scenario.

7. Eliminating Duplicates: Input Order

   If you want to remove duplicates and keep the original order of elements in an array, which approach is both efficient and order-preserving?

   1. Reverse the array and remove duplicates
   2. Randomly shuffle before deduplication
   3. Sort the array then remove duplicates
   4. Use a hash set and build a result list sequentially

   Explanation: Adding elements to a result list only if they are not yet in a hash set ensures both order preservation and efficiency. Sorting loses the original sequence. Reversing changes the order and does not guarantee uniqueness alone. Shuffling randomizes the order, which is not desired.

8. Hash Map Properties

   Why is a hash map preferred for frequency counting over arrays when element values can be very large or negative?

   1. Arrays are always faster
   2. Hash maps can't store counts
   3. Arrays can store any kind of key
   4. Hash maps do not require index-based keys

   Explanation: Hash maps allow any kind of key, including large or negative numbers, while arrays rely on non-negative, contiguous indices. Arrays can only be faster if the possible keys are few and within array bounds, which is rare in such cases. Arrays cannot store arbitrary keys. Hash maps clearly store counts using key-value pairs.

9. Frequency Counting Edge Case

   If an array contains many repeated appearances of the same value, how does this affect space complexity when using a hash map for counting?

   1. Duplicates reduce memory needed
   2. The space depends only on the number of unique values
   3. Space increases with each duplicate
   4. Space complexity becomes O(n^2)

   Explanation: A hash map stores only unique keys and their counts, so overall space relates to the count of unique elements. Each duplicate merely increases the value of an existing key, not the number of keys. Space does not become quadratic from duplicates alone. Duplicates do not reduce or save memory usage in this context.

10. Big-O Time for Hash Map Lookups

    What is the average-case time complexity for checking if a hash map contains a specific key?

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

    Explanation: Hash maps offer average-case O(1) time for key lookups, making them highly efficient for frequency tasks. O(n) arises for linear searches, not hash maps. O(n^2) is unrelated to key checks. O(log n) applies to balanced search trees instead.

11. Deduplication: Modifying Arrays In-Place

    What is a potential drawback of removing duplicates from an original array in-place?

    1. It sorts the array automatically
    2. It always uses extra arrays
    3. It may require shifting many elements
    4. It cannot be done for integers

    Explanation: Removing elements in-place may require shifting remaining values to fill gaps, which can be slow. Extra arrays are not always needed, so that answer is incorrect. Deduplication applies to integers just like other types. It does not automatically sort the array.

12. Space Complexity of Hash Set Deduplication

    What is the worst-case space complexity when using a hash set to deduplicate an array of n elements?

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

    Explanation: In the worst case, where all elements are unique, the hash set will store all n of them, so space is O(n). O(1) only applies if there are a constant number of unique items, which is not generic. O(log n) is unrelated to hash sets. O(n^2) is unnecessarily large for this purpose.

13. Comparing Arrays and Hash Maps for Deduplication

    Why is using only an array inefficient for deduplication compared to a hash set or hash map?

    1. Checking for duplicates is slower without fast key lookups
    2. Arrays cannot store integers
    3. Hash maps sort values automatically
    4. Arrays always use more memory than hash maps

    Explanation: Without constant-time lookups, arrays require scanning through the list for each value, which is slow. Arrays can certainly store integers, so that distractor is incorrect. Arrays do not always use more memory. Hash maps do not sort by default, making that option irrelevant.

14. Counting Frequencies: Empty Array

    What is the time complexity of counting frequencies in an empty array using a hash map?

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

    Explanation: An empty array leads to no operations, so the time complexity is considered O(1). O(n) would apply if there were n elements, which is not the case here. O(n^2) and O(log n) are incorrect as there is nothing to process.

15. Best Case for No Duplicates

    If an array contains all unique values, how does this affect the efficiency of deduplication using a hash set?

    1. It uses less memory than with duplicates
    2. Each element is checked and added once, still O(n)
    3. The operation becomes O(1)
    4. It cannot deduplicate unique arrays

    Explanation: Even if all values are unique, each one is checked and added, resulting in O(n) time and space. O(1) is not accurate since each value needs processing. Deduplication is still valid for an all-unique array. Memory use is not reduced, because all elements must be stored in the set.

16. Hash Map Use in Text Analysis

    When analyzing a paragraph of text, why is a hash map practical for counting how often each letter appears?

    1. It relates each letter to a unique count efficiently
    2. It always ignores uppercase letters
    3. It cannot process special symbols
    4. It sorts the letters by frequency automatically

    Explanation: A hash map can track each letter and its count efficiently during a single scan. Ignoring uppercase letters is not automatic; that requires custom logic. Hash maps can handle any symbol provided as a key. Sorting by frequency is not inherent, as hash maps do not manage order.