1.
In the case of Union by Rank, the rank is increased based on the rank of the tree with:
2.
Which of the following are true for the amortized time complexity of DSU having N nodes after applying path compression and union by size?
A. 
B. 
Proportional to Ackermann Function
C. 
D. 
E. 
3.
You are given a list of N elements. You will be asked Q queries. Each query will ask you to print the minimum value in a range [L, R]. Which of the following data structures can be used to provide the fastest query answers (Here, N, and M both are in the range of 10^5)?
4.
Consider that you are participating in a programming contest. It’s almost the end of the contest. You have one last problem to solve. The problem involves performing an efficient range sum query in a 1D array. The queries contain both range updates and printing the range sum. You only have enough time to implement and debug one of the following algorithms. Which one do you choose?
5.
Which of the following range queries does a single Fenwick Tree support?
A. 
B. 
C. 
D. 
E. 
6.
In practice, the implementation of Fenwick Tree is similar to that of:
A. 
B. 
C. 
D. 
E. 
7.
Each integer can be represented as the sum of the integer power of:
A. 
B. 
C. 
D. 
8.
Consider that we have 10^6 strings. We want to find out the number of unique strings using the polynomial hash function with m = 10^9 + 9. In that case, there will definitely be a collision. To avoid the problem without increasing much time complexity, we can:
A. 
B. 
Compare the strings if two hash values match
C. 
Use the same hash function twice, each time with different p
D. 
9.
Given a string of length N, and a pattern of length M to look for, what is the time for pre-processing in the Rabin-Karp Algorithm?
A. 
B. 
C. 
D. 
E. 
F. 
G. 
H. 
I. 
10.
Given a string of length N, and a pattern of length M to look for, the time complexity of Rabin-Karp in the worst case:
A. 
B. 
C. 
D. 
E. 
11.
Why is it best to use a prime number as a mod in a hashing function?
A. 
B. 
Have more common factors with the hash value
C. 
Higher Number of Slots in Hash Table
D. 
Higher chance of existence of inverse
12.
Which of the following can be considered as a collision in the Hash table?
A. 
Two key-value pairs that have equal keys but different values
B. 
Two key-value pairs that have different keys and hash to different indices
C. 
Two key-value pairs that have different keys but hash to the same index
D. 
Two key-value pairs that have equal keys but hash to different indices
13.
Consider that, you have a hash function that converts each character of a string using a formula, f(x), and then concatenates them to find the hash value. Which of the following formulae will you use to convert each character to ensure no collision (Here, x denotes the ASCII value of the character)?
14.
String hashing performs worse than the brute force algorithm when doing a single comparison.
15.
While calculating the hash of a string using Polynomial Hash Function, we map each character to 0, 1, 2, … and so on.
16.
To reduce collision, the hash function should derive a hash value depending on the pattern that might exist in the strings.
17.
We can use the polynomial hash function for calculating the rolling hash given modulo is prime.
18.
Since Fenwick Tree stores prefix sum, we cannot get the sum for a specific range that doesn’t involve prefix.
19.
Fenwick Tree is slower than the prefix array in answering range sum queries.
20.
We can use Fenwick Tree to keep track of prefix GCDs.
21.
In DSU, two elements having the same representatives might belong to different sets.
22.
In Kruskal’s Algorithm, DSU is used to find the edge with the lowest weight.
23.
Path compression in a tree with N nodes transforms find_set() operation from having time complexity [Blank] to [Blank]
24.
The depth of any tree with N nodes if we use union by rank is [Blank]
25.
Consider that in a rolling hash, we have a window of size 23. We shift the window by removing the first character and adding a new character at the end. The old and the window have [Blank] characters in common.