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

Explore essential concepts of removing duplicates, counting frequencies, and understanding time complexity in arrays and hash maps. This quiz is designed to deepen your grasp of algorithms such as deduplication and frequency analysis, focusing on Big-O efficiency and practical scenarios.

1. Duplicate Removal Efficiency

   Given an unsorted array of 1,000 integers with potential duplicates, which approach is likely to achieve deduplication in linear time complexity?

   1. Sort the array first, then scan for duplicates
   2. Compare each element to every other element using nested loops
   3. Use a hash set to check each element and add unique values
   4. Store elements in a stack as you iterate

   Explanation: Using a hash set allows each lookup and addition to occur in roughly constant time, resulting in overall linear time, O(n), for deduplication. Sorting the array takes at least O(n log n), which is less efficient. Comparing each element to every other using nested loops is O(n^2) and much slower. Storing elements in a stack does not provide deduplication, as stacks do not enforce uniqueness.

2. Frequency Count in Arrays

   Which data structure is most appropriate for counting how many times each element appears in a large unsorted array of strings?

   1. Hash map
   2. Queue
   3. Binary search tree
   4. Array list

   Explanation: A hash map allows you to store and efficiently update counts for each unique string, giving constant average time for lookups and inserts. Queues and array lists do not associate keys with counts, making frequency tracking cumbersome. Binary search trees can be used, but hash maps are generally more straightforward and efficient for this purpose.

3. Big-O for Naive Deduplication

   What is the worst-case time complexity of removing duplicates from an array by checking each element against all others using nested loops?

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

   Explanation: Using nested loops to compare every element against every other results in quadratic time complexity, or O(n^2). Sorting-based methods would take O(n log n), which is more efficient. O(log n) and O(1) are not achievable for full deduplication in this way; O(1) only applies to constant-time operations, not whole-array processing.

4. Deduplication Result Example

   If you deduplicate the array [2, 2, 3, 1, 3], which resulting set accurately represents all unique elements?

   1. [2, 2, 3, 1, 3]
   2. [1, 2, 3]
   3. [1, 1, 2, 3]
   4. [2, 3, 1, 2]

   Explanation: The correct deduplicated set contains each unique element only once, which here is [1, 2, 3]. Option [2, 3, 1, 2] and [2, 2, 3, 1, 3] both contain duplicates, so they do not represent deduplication. [1, 1, 2, 3] repeats the value 1, again violating the uniqueness requirement.

5. Time Complexity for Frequency Counters

   In the context of string frequency analysis using a hash map on an array of n elements, what is the average time complexity for building the frequency table?

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

   Explanation: Building a frequency table with a hash map typically requires a single pass through the array, yielding O(n) average time complexity. O(n^2) would only occur with a less efficient approach, while O(log n) relates to balanced trees and O(1) applies only to simple single operations, not the process as a whole.