HASHIT - Hash it!
Your task is to calculate the result of the hashing process in a table of 101 elements, containing keys that are strings of length at most 15 letters (ASCII codes 'A',...,'z'). Implement the following operations:
- find the index of the element defined by the key (ignore, if no such element),
- insert a new key into the table (ignore insertion of the key that already exists),
- delete a key from the table (without moving the others), by marking the position in table as empty (ignore non-existing keys in the table)
When performing find, insert and delete operations define the following function:
integer Hash(string key),
which for a string key=a1...an returns the value:
Hash(key)=h(key) mod 101, where
Resolve collisions using the open addressing method, i.e. try to insert the key into the table at the first free position: (Hash(key)+j2+23*j) mod 101, for j=1,...,19. After examining of at least 20 table entries, we assume that the insert operation cannot be performed.
t [the number of test cases <= 100]
n1 [the number of operations (one per line)[<= 1000]
DEL:string [other test cases, without empty lines betwee series]
For every test case you have to create a new table, insert or delete keys, and write to the output:
the number of keys in the table [first line]
index:key [sorted by indices]
Input: 1 11 ADD:marsz ADD:marsz ADD:Dabrowski ADD:z ADD:ziemii ADD:wloskiej ADD:do ADD:Polski DEL:od DEL:do DEL:wloskiej Output: 5 34:Dabrowski 46:Polski 63:marsz 76:ziemii 96:z
Last edit: 2013-06-27 17:41:06
just simply write the program like what it said.no other thing need to take into consideration,and u can AC it
Important: To note that the open-addressing method calculates hashes j=1...19 on the original hash and not on the previous hash.
my solution works on ideone but here it is repeatedly giving NZEC
Is the open addressing performed by adding j^2+23*j to the previous hash code or to the original hash code h(.)?
"After examining of at least 20 table entries"
Jeevan K. S. Chalam:
Done :)Last edit: 2011-05-28 09:00:22
input with string length ZERO allowed?
@Parag gupta - "(ignore insertion of the key that already exists)" - read the specification carefully and don't assume that the input is wrong not You.
the test case answer should be 6 and should contain "marsz" two times. one at index 63 and other at 87. explain plz..