Hash functions are fundamental building blocks that map input data of arbitrary size to fixed-size output values. These functions must be deterministic, ensuring the same input always produces the same hash value. In interview scenarios, we often leverage hash tables to achieve O(1) average time complexity for insertions, deletions, and lookups.

Handling Hash Collisions

When two different enputs produce identical hash values, we encounter a collision. The separation chaining method resolves this by creating linked lists at collision points. For example, keys "alpha" and "omega" might both hash to index 42, causing them to be stored as a chain of nodes at that position. Each node contains the key-value pair and a reference to the next colliding element.

Common Interview Problems

Valid Anagram Detection

Given two strings source and target, determine if they're anagrams (contain identical character frequencies).

Example 1:

Input: source = "listen", target = "silent"
Output: true

Example 2:

Input: source = "hello", target = "world"
Output: false

Approach 1: Character frequency comparision using arrays:

def check_anagram(first_str, second_str):
    if len(first_str) != len(second_str):
        return False
    
    freq = [0] * 26
    for char in first_str:
        freq[ord(char) - ord('a')] += 1
    
    for char in second_str:
        freq[ord(char) - ord('a')] -= 1
        if freq[ord(char) - ord('a')] < 0:
            return False
    
    return True

result = check_anagram("listen", "silent")
print(result)

Approach 2: Using dictionary for character counting:

def validate_anagram(text_a, text_b):
    char_counter = {}
    
    for character in text_a:
        char_counter[character] = char_counter.get(character, 0) + 1
    
    for character in text_b:
        if character not in char_counter:
            return False
        char_counter[character] -= 1
        if char_counter[character] < 0:
            return False
    
    return True

Two Sum Problem

Find indices of two numbers in an array that sum to a target value. Each input has exactly one solution.

Example 1:

Input: values = [3, 8, 12, 7], target = 15
Output: [0, 3]
Explanation: values[0] + values[3] == 15

Example 2:

Input: values = [1, 1], target = 2
Output: [0, 1]

Solution using hash map for constant-time lookups:

class SolutionFinder:
    @staticmethod
    def find_two_indices(numbers, desired_sum):
        seen_values = {}
        
        for position, current_val in enumerate(numbers):
            complement = desired_sum - current_val
            if complement in seen_values:
                return [seen_values[complement], position]
            seen_values[current_val] = position
        
        return []

# Example usage
result = SolutionFinder.find_two_indices([3, 8, 12, 7], 15)
print(result)

Three Sum Problem

Identify all unique triplets in an array that sum to zero. Triplets must be distinct in terms of values and positions.

Example 1:

Input: nums = [-2, -1, 1, 2, 3]
Output: [[-2, -1, 3], [-2, 1, 1], [-1, -1, 2]]

Example 2:

Input: nums = [0, 0, 0, 0]
Output: [[0, 0, 0]]

Two-pointer solution after sorting:

def three_sum_zero(arr):
    arr.sort()
    result = []
    n = len(arr)
    
    for i in range(n - 2):
        if i > 0 and arr[i] == arr[i - 1]:
            continue
            
        left, right = i + 1, n - 1
        
        while left < right:
            current_sum = arr[i] + arr[left] + arr[right]
            
            if current_sum == 0:
                result.append([arr[i], arr[left], arr[right]])
                
                while left < right and arr[left] == arr[left + 1]:
                    left += 1
                while left < right and arr[right] == arr[right - 1]:
                    right -= 1
                    
                left += 1
                right -= 1
            elif current_sum < 0:
                left += 1
            else:
                right -= 1
    
    return result

This approach ensures O(n²) time complexity with O(1) additional space (excluding output). The sorting step takes O(n log n), but the two-pointer technique efficiently finds all unique combinations with out using extra data structures.