How does a hash table handle collisions?
- By ignoring collisions and overwriting existing values.
- By rearranging the elements in the table.
- By resizing the hash table to accommodate more elements.
- By using techniques such as chaining or open addressing to resolve conflicts.
Hash tables handle collisions by employing techniques such as chaining or open addressing. Chaining involves maintaining a linked list at each bucket to store colliding elements, while open addressing involves finding the next available slot in the table.
Multidimensional arrays are arrays of _______ arrays.
- Heterogeneous
- Homogeneous
- Linear
- Non-linear
Multidimensional arrays are arrays of homogeneous arrays, meaning that each element in the outer array points to another array of the same data type.
Reversing a linked list recursively involves changing the _______ of each node.
- Data
- Next pointer
- Previous pointer
- Value
Reversing a linked list recursively involves changing the previous pointer of each node. In each recursive call, the next pointer of each node is redirected to its previous node, gradually reversing the entire list.
In the context of strings, what does the term "edit" refer to in the Edit Distance algorithm?
- All of the above.
- Deleting characters from a string.
- Inserting characters into a string.
- Modifying characters in a string.
In the context of strings and the Edit Distance algorithm, the term "edit" refers to all three operations: deleting characters, inserting characters, and modifying characters in a string. These operations are used to transform one string into another.
Which shortest path algorithm is suitable for finding the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights?
- Bellman-Ford Algorithm
- Dijkstra's Algorithm
- Floyd-Warshall Algorithm
- Prim's Algorithm
Dijkstra's Algorithm is suitable for finding the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights. It uses a greedy approach, iteratively selecting the vertex with the smallest known distance to the source.
In the coin change problem, what is meant by the term "minimum number of coins"?
- The fewest number of coins required to represent a given amount.
- The least valuable coins in the currency.
- The lowest denomination of coins in the given set.
- The smallest physical size of the coins.
In the coin change problem, the term "minimum number of coins" refers to the fewest number of coins needed to represent a given target amount. The goal is to optimize the combination of coins used to minimize the total count.
Compare and contrast separate chaining and open addressing collision resolution strategies in hash tables.
- Both methods involve creating secondary data structures to handle collisions. Separate chaining uses linked lists, while open addressing stores elements directly in the hash table.
- Separate chaining and open addressing are identical in their approach to collision resolution.
- Separate chaining and open addressing both involve redistributing colliding elements to other locations. Separate chaining uses a single array, while open addressing uses multiple arrays.
- Separate chaining uses a single array to store all elements, while open addressing distributes elements across multiple arrays. Both methods avoid collisions by using dynamic resizing.
Separate chaining and open addressing are two common strategies for handling collisions in hash tables. Separate chaining involves creating linked lists at each index to store colliding elements, while open addressing places elements directly in the hash table, using methods like linear probing or quadratic probing to find alternative locations for collisions.
Naive pattern matching compares each character of the pattern with each character of the text _______.
- In reverse order
- One by one
- Randomly
- Simultaneously
Naive pattern matching compares each character of the pattern with each character of the text one by one. It involves a simple character-by-character comparison, starting from the beginning of the text, and sliding the pattern one position at a time until a match is found or the end of the text is reached.
Metacharacters in regular expressions are special symbols used to represent _______.
- Numbers
- Patterns
- Special characters
- Variables
Metacharacters in regular expressions are special symbols used to represent special characters. These characters have a special meaning in the context of regular expressions, allowing for flexible and powerful pattern matching.
What are some strategies to avoid infinite loops in DFS?
- Limiting the search depth
- Maintain a visited set
- Resetting the stack
- Use a timestamp
To avoid infinite loops in DFS, maintaining a visited set is a crucial strategy. This set keeps track of the visited vertices, preventing revisiting the same vertex during the traversal. By marking and checking visited vertices, the algorithm ensures that each vertex is explored only once, effectively avoiding infinite loops. This approach is fundamental for the correct functioning of DFS in scenarios where revisiting nodes must be prevented.