EECS 281 – Hashing || 100% Accurate Answers.
For which of the following applications would a hash table NOT be appropriate? Select all
that apply.
a.) printing out all of the elements in sorted order
b.) storing passwords that can be looked up by uniqname
c.) returning a person's name given their phone number
d.) finding the k-th largest element in an array
e.) creating an index for an online book correct answers a, d
Two pairs (a,b) and (c,d) are symmetric if b = c and a = d. Suppose you want to find all
symmetric pairs in the array. The first element of all pairs is distinct.
For example, given {(14, 23), (11,2), (52,83), (49,38), (38,49), (2,11)}, the symmetric pairs
are {(11,2), (2, 11)} and {(49,38), (38,49)}
What is the average-case time complexity of accomplishing this task if yo use the most
efficient algorithm? If hashing is involved, assume that both search and insert methods work
in O(1) time.
a.) O(1)
b.) O(log n)
c.) O(n)
d.) O(n log n)
e.) O(n^2) correct answers c.) O(n)
Use a hashtable! The first element of each pair is the key, and the second element is the
value.
Go through the array once. For each current pair, check if the current second element is in the
hashtable, and if it is, check that its value is the same as the current first element. If it
matches, it's a symmetric pair.
What is the complexity for finding a value given a key and inserting a key into the hash table
on average? What is the worst case? correct answers Average: O(1)
Worst Case: O(n)
struct Student {
string name;
int year;
bool cs_major;
};
vector<Student> all_students;
How would I add a student in to all_students? correct answers
all_students.emplace_back("Maya", 3, true);
What are the two basic operations that Dictionary ADT's support? correct answers insert and
search
For which of the following applications would a hash table NOT be appropriate? Select all
that apply.
a.) printing out all of the elements in sorted order
b.) storing passwords that can be looked up by uniqname
c.) returning a person's name given their phone number
d.) finding the k-th largest element in an array
e.) creating an index for an online book correct answers a, d
Two pairs (a,b) and (c,d) are symmetric if b = c and a = d. Suppose you want to find all
symmetric pairs in the array. The first element of all pairs is distinct.
For example, given {(14, 23), (11,2), (52,83), (49,38), (38,49), (2,11)}, the symmetric pairs
are {(11,2), (2, 11)} and {(49,38), (38,49)}
What is the average-case time complexity of accomplishing this task if yo use the most
efficient algorithm? If hashing is involved, assume that both search and insert methods work
in O(1) time.
a.) O(1)
b.) O(log n)
c.) O(n)
d.) O(n log n)
e.) O(n^2) correct answers c.) O(n)
Use a hashtable! The first element of each pair is the key, and the second element is the
value.
Go through the array once. For each current pair, check if the current second element is in the
hashtable, and if it is, check that its value is the same as the current first element. If it
matches, it's a symmetric pair.
What is the complexity for finding a value given a key and inserting a key into the hash table
on average? What is the worst case? correct answers Average: O(1)
Worst Case: O(n)
struct Student {
string name;
int year;
bool cs_major;
};
vector<Student> all_students;
How would I add a student in to all_students? correct answers
all_students.emplace_back("Maya", 3, true);
What are the two basic operations that Dictionary ADT's support? correct answers insert and
search
