Task Examples Using Hash Tables

8.1 Task for Finding Duplicates in an Array

Task: Given an array of numbers. You need to find and return all duplicates in the array.

Solution: Use a hash table to keep track of numbers that have already been encountered. If a number appears again, add it to the list of duplicates.

Implementation example:

def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

# Examples of usage
arr1 = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr1))  # Output: [2, 4]

arr2 = []
print(find_duplicates(arr2))  # Output: []

arr3 = [1, 2, 3, 4, 5]
print(find_duplicates(arr3))  # Output: []

Explanation:

• Create an empty set seen to keep track of unique numbers.
• Loop through each element in the array. If the element is already in seen, add it to the duplicates list.
• If the element is not found in seen, add it.
• Return the list of duplicates.

Note that the function works correctly with an empty array and an array without duplicates, returning an empty list in both cases.

8.2 Task for Checking Anagrams

Task: Given two strings. You need to determine if they are anagrams (contain the same characters in the same frequency).

Solution: Use a hash table to count character frequencies in both strings and compare the results.

Implementation example:

def are_anagrams(str1, str2):
    # Convert strings to lowercase to consider different letter cases
    str1 = str1.lower()
    str2 = str2.lower()
    
    if len(str1) != len(str2):
        return False
    char_count = {}
    # Count character frequency in the first string
    for char in str1:
        char_count[char] = char_count.get(char, 0) + 1
    # Subtract character frequency in the second string
    for char in str2:
        if char in char_count:
            char_count[char] -= 1
        else:
            return False
    # Check if all values in the dictionary are 0
    return all(count == 0 for count in char_count.values())

# Examples of usage
print(are_anagrams("listen", "silent"))  # Output: True
print(are_anagrams("hello", "world"))  # Output: False
print(are_anagrams("", ""))  # Output: True
print(are_anagrams("Tea", "Eat"))  # Output: True

Explanation:

• If the lengths of the strings don't match, they can't be anagrams.
• Use the dictionary char_count to count character frequencies in the first string.
• Loop through the second string and subtract character frequencies.
• Check that all values in the dictionary are zero. If so, the strings are anagrams.

Note that the function accounts for case sensitivity by converting both strings to lowercase before comparing. It also correctly handles empty strings, considering them as anagrams of each other.

8.3 Task for Finding Pairs with a Given Sum

Task: Given an array of numbers and a target sum value. You need to find all pairs of numbers that sum up to the target value.

Solution: Use a hash table to store numbers and check if they form a pair with the current number that gives the target sum.

Implementation example:

def find_pairs_with_sum(arr, target_sum):
    seen = set()
    pairs = []
    for num in arr:
        complement = target_sum - num
        if complement in seen:
            pairs.append((complement, num))
        seen.add(num)
    return pairs

# Example of usage
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_with_sum(arr, target_sum))  # Output: [(1, 5), (1, 5)]

Explanation:

• Create an empty set seen to track numbers.
• For each number in the array, calculate its complement complement (the difference between the target sum and the current number).
• If the complement is already in seen, add the pair (complement, num) to the pairs list.
• Add the current number to seen.
• Return the list of pairs.

It's important to note that this algorithm has a time complexity of O(n), where n is the number of elements in the array. This is significantly more efficient than a naive double loop solution, which has a complexity of O(n^2). Using a hash table allows us to find all pairs in a single pass through the array, which is especially important when working with large data volumes.

For comparison, here's what the naive solution with a time complexity of O(n^2) would look like:

def find_pairs_naive(arr, target_sum):
    pairs = []
    n = len(arr)
    for i in range(n):
        for j in range(i+1, n):
            if arr[i] + arr[j] == target_sum:
                pairs.append((arr[i], arr[j]))
    return pairs

# Example of usage
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_naive(arr, target_sum))  # Output: [(1, 5), (1, 5)]

As you can see, the naive solution requires two nested loops, making it inefficient for large arrays. The hash table solution allows us to achieve the same goal much faster.

2

Task

Python SELF EN, level 54, lesson 3

Locked

Finding Duplicates

Finding Duplicates

Open

2

Task

Python SELF EN, level 54, lesson 3

Locked

Anagrams

Anagrams

Open