Algorithm Question: Please do not write a real program. The answer should be an
ID: 3886360 • Letter: A
Question
Algorithm Question:
Please do not write a real program.
The answer should be an explaination of your algorithm or pseudocode. Try to answer clearly and concisely. Thank you very much. I will upvote all answers.
Question:
Give a data structure for the following.
Every item has two keys namely key 1 (x) and key 2 (x). Show a data structure for the following:
1. Insert(x, S) (x is associated with key 1 (x) and key 2 (x)). You will need them for
the insert).
2. Delete(x, S)
3. Search(x, S)
4. DeleteAll(S, k) You have to delete all the elements whose first key, key 1 (x) = k
(try not to Use (n) time here).
Explanation / Answer
A Hash table is the apt datastructure for the aforementioned problem.Because it stores data in an associative manner, so here we can store the value of x based on k1(x) and k2(x).
The Hash table can be implemented in terms of a three dimensional array,Where the first index can indicate the x value and k1 and k2 indicates the two keys associated with it.
Based on the value of K1 and k2, the x can be hased and it can be used to find its resting position in the array.
1. Insertion
Whenever an element is to be inserted, compute the hash code of the keys k1 and k2 passed and locate the index using that hash code as an index in the array and find the value element x.
function insert(x,element_table)
{
element_table[hash(x)][x.k1][x.k2]=x
}
2. Deletion
Every element has its associated key value k1 and k2, so whenever an element x is presented for its deletion, compute its hash using its corresponding k1 and k2 and locate x and delete it
funciton delete(x,element_table){
if element_table[hash(x)][x.k1][x.k2] == x:
element_table[hash(x)][x.k2][x.k2].remove()
}
3. Search
As already mentioned identify an elements position through hashing and use it as a index to locate it.
funciton search(x,element_table)
{
if element_table[hash(x)][x.k1][x.k2] == x:
print "Element found at location x"
}
4.Delete all
Every element contains two keys now use the second index which directs k1 to search all values by varying k1 and keeping k2 constat and then use all possible hash value producing the same x value. If it produced the same result then remove all such elements.
function Delete_All(element_table,k)
{
while i <length(element_table)
{
if hash_inverse(yi,y.k,y.k2i) ==xi then
{
element_table[yi][yik][yik2i].remove()
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.