Problems tagged with "hashing"

Suppose \(T\) is a hash table of size 100 (that is, it has 100 bins). 300 elements are inserted into the hash table using a hash function that satisfies the uniform hashing assumption (that is, any element is equally-likely to hash into any bin). What is the expected number of elements in the first bin?

Suppose a hash table is constructed so that collisions are resolved through chaining. The hash table has \(10\) bins, and 100 items are inserted into the hash table.

True or False: it is possible for one of the bins to contain all 100 items.

Assume that a hash table is implemented using chaining to resolve collisions. The hash table stores \(n\) numbers.

Suppose a membership query is made for 42. True or False: more than one bin in the hash table may be checked with a linear search during the query.

Suppose a hash table is constructed using linked lists to store the data within each bin, and that collisions are resolved by chaining. What is the worst case time complexity of inserting a new element into the hash table? You may assume that the hash table will not need to be resized, and that evaluating the hash function takes \(\Theta(1)\) time.

Suppose a hash table is constructed using linked lists to store the data within each bin, and that collisions are resolved by chaining. Suppose \(n\) elements have been inserted into the hash table. What is the worst case time complexity of querying whether an object exists within the hash table? You may assume that the hash table will not need to be resized, and that evaluating the hash function takes \(\Theta(1)\) time.

Suppose we are building a hash table to store numbers. Our hash table will have 1000 bins. True or false: \(f(x) = x \% 2\) is a good hash function. Here, \(x \% 2\) returns the remainder after dividing \(x\) by 2.

Suppose you insert 11 elements into a hash table with 20 bins. True or False: there must exist exactly 9 empty bins, no more, no less, since the number of elements being hashed is less than the number of bins in the hash table by nine.

Consider the code below:

def intersection(A, B):
    common = set()
    for x in A:
        if x in B:
            common.add(x)
    return common

What is the expected time complexity of this code if A and B are Python sets (hash tables) with \(n\) elements each? State your answer as a function of \(n\) using asymptotic notation. You may assume that the hash function used is ``good'' in that it hashes evenly (that is, it satisfies the simple universal hashing assumption).

In the problem below, suppose arr is an array of \(n\) integers. What is the expected time complexity of the code below? Write your answer using asymptotic notation as a function of \(n\).

Remember: set is implemented using a hash table. You may assume that the hash table is large enough to store all of th numbers without needing to resize.

def find_duplicates(arr):
    seen = set()
    duplicates = set()
    for num in arr:
        if num in seen:
            duplicates.add(num)
        else:
            seen.add(num)
    return duplicates

What is the expected time complexity of the code shown below, assuming that numbers is a Python list? Express your answer as a function of \(n\) using asymptotic notation (e.g., \(\Theta(n)\)).

def foo(numbers):
    """Assume that `numbers` is a list containing n numbers."""
    # counts is a Python dictionary, which is implemented using hash table
    counts = {}
    for x in numbers:
        for y in numbers:
            diff = abs(x - y)
            if diff not in counts:
                counts[diff] = 1
            else:
                counts[diff] = counts[diff] + 1
    return counts

Suppose a hash table with \(n/2\) bins stores \(n\) elements, and suppose that when the next element is inserted into the hash table, a ``grow'' will be triggered. That is, the insertion will cause the hash table to resize to \(n\) bins containing the same \(n + 1\) elements, plus the newly-added element.

What will be the time complexity of this single insertion operation that causes the table to grow?

Suppose a hash table in constructed so that collisions are resolved through chaining. The hash table has a number of bins \(k\) that is \(\Theta(n)\), where \(n\) is the number of elements being stored in the hash table; that is, the hash table grows as more elements are inserted.

Suppose the hash function uses only the first \(k / 2\) bins of the hash table, but appears to hash items into these bins evenly.

What is the expected time complexity of a membership query on this hash table? State your answer in asymptotic notation in terms of the number of elements in the hash table, \(n\).

Suppose you will be receiving a stream of numbers, one by one, and you wish to keep track of the largest number seen so far. You will not need to perform membership queries. What should you do?

Suppose you need to keep track of a large dynamic collection of numbers. You will be performing n insertions, n deletions, and a very small number of queries for the maximum element in the collection. You will also be performing membership queries.

Which data structure should you use? You may assume that time complexity is the most important criterion.

Suppose you need to keep track of a large dynamic collection of numbers. The three most common operations you will be performing are insertions, deletions, and queries for the maximum element in the collection. You may assume that the number of maximum queries you will be making is close to the number of insertions/deletions. You will also be performing membership queries.

Which data structure should you use? You may assume that time complexity is the most important criterion.