In the context of universal hashing, what makes a family of hash functions 'universal'?
Its use of a single, universally applicable hash function
Its ability to adapt to any data distribution
The property that the probability of collision between any two keys is bounded
The guarantee of zero collisions for any input set
Which collision resolution technique involves using a second, independent hash function to compute the probe sequence?
Linear Probing
Double Hashing
Quadratic Probing
Separate Chaining
When choosing a collision resolution strategy for a hash table, which factors are essential to consider?
Programming language and hardware architecture
All of the above
Size of the keys and values being stored
Expected data distribution and load factor
In a web server, which scenario is best suited for using a hashmap to optimize performance?
Managing the order of user connections to ensure fairness
Maintaining a log of all incoming requests in chronological order
Storing and retrieving user session data
Storing and retrieving static website content like images and CSS files
What is a significant disadvantage of using a fixed-size hash table in conjunction with a hash function prone to collisions?
Increased memory usage due to the fixed size allocation
Degraded performance due to chaining or open addressing for collision resolution
Complexity in implementing the hash function itself
Inability to store data that exceeds the pre-defined table size
What advantage does separate chaining have over open addressing techniques in hash table collision resolution?
Faster search times at high load factors
Simpler implementation
Handles load factors greater than 1 gracefully
Lower memory overhead
You need to count the frequency of each word in a large text document. Which combination of data structures would be most efficient for this task?
A binary tree where words are stored in the nodes and their frequencies are stored in the leaves
Two arrays: one for storing words and one for storing their frequencies
A hashmap where words are keys and their frequencies are values
A sorted linked list where each node contains a word and its frequency
In the context of hashmaps, what does 'probing' refer to?
Determining the load factor of the hashmap.
Searching for a specific key in the hashmap.
Finding an alternative slot for a key when a collision occurs.
Resizing the underlying array to accommodate more keys.
You are implementing an LRU (Least Recently Used) cache. Which data structure, in conjunction with a hashmap, is most suitable for tracking the usage order of cached items?
Queue
Doubly Linked List
Stack
Binary Tree
You need to identify the first non-repeating character in a string. How can a hashmap be utilized to solve this problem efficiently?
Store the characters of the string as keys in the hashmap, and their positions as values. The first character with the lowest position value is the first non-repeating character.
Store the frequency of each character in the hashmap, then iterate through the string and return the first character with a frequency of 1.
Use the hashmap to store the unique characters of the string, then iterate through the hashmap to find the first non-repeating character.
A hashmap cannot be used efficiently for this problem.