Algorithm

There are two special keys - 0 and 1. Values for these are stored separately. Algorithm for the special keys:

GET: To get a value for a special key, check the flag. If it is 1, return the value generated by encoding the bytes corresponding to that special key. Else return 0.

PUT: To put a value for a special key, first set the flag corresponding to that special key as 1 Then convert the value into 4 bytes using the encoding scheme and store it at the indices corresponding to that special key.

DELETE: To delete a value, set the flag as O and set all bytes corresponding to that special key as 0.

For other keys, first get the page number. This can be found simply by taking the remainder while dividing with the number of pages. For example, if the key is 32 and the number of pages are 10, the page index is 2. In the page,the records are stored sequentially with fixed 8 bytes per record. Algorithms for the rest of the keys:

GET: Iterate through the pages till you reach a record where the key matches or you reach the end (key is 0). Return the value if found else return 0.

PUT: Try the get algorithm to find the index of the key. If found, update the value for that record and return. If not, find the first record where the key is 0 or -1. Update the key and value for that record. If the page doesn't have sufficient free space, throw an error.

DELETE: Try the get algorithm to find the index of the key. If found, update the key to -1 and value to 0.

Data Structure

The hash map can be thought of as a large byte array.

Bytes 03: These store the page size.

Bytes 4-7: These store the number of pages.

Byte 8: This store whether we have a value for the special key '-1'

Bytes 9-12: These store the value for key '-1'.

Byte 13: This store whether we have a value for the special key '0'

Bytes 14-17: These store the value for key '0'

After that the pages.

Page structure

Bytes 03: Key 1

Bytes 47: Value 1

Bytes 8-11: Key 2

Bytes 12-15: Value 2

And so on...

Encoding format for storing keys and values

Key and values are stored in big-endian format as bytes. This means that when you convert the integer to bytes, the most significant byte will be stored at the lowest index, the next most significant byte at the next higher index and so оп.

Encoding format for printing the hash map byte array

Convert each byte into 2 nibbles (4-bit values) with the more significant nibble first. Covert each nibble into a character as per base-16 using the characters 0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f.

Print each of the six fields in the data structure as per the above with a space between the fields. Each of the pages is printed surrounded by square brackets, with a space after the square brackets. Within each page, the entries are separated by a comma (.) and the keys and values by a colon (). So overall format is:

(page size) (number of pages) {value for -1 present or not) {value for -1) {value for 0 present or not) (value for } [[key1]: [value1].....]...

Input / Output

Each input line will consist of one of the following 5 commands:

INIT <page size in # byte> <# pages>: Create a new data structure, deleting old one if any. Do not output anything.

GET : Output the value corresponding to that key (or O if key is not found) in a new line.

PUT : Set the value to that key. Do not output anything.

DELETE : Delete the key. Do not output anything.

DUMP: Take the entire byte array for the data structure and encode using the encoding format (for printing byte array). Output this string in a new line.

Note:

Your code must be able to print the sample output from the provided sample input. However, your code is run against multiple hidden test cases. Therefore, your code must pass these hidden test cases to solve the problem statement.

Limits

Time Limit: 5.0 sec(s) for each input file

Memory Limit: 256 MB

Source Limit: 1024 KB

Scoring

Score is assigned if any testcase passes

Allowed Languages

Bash, C, C++14, C++17, Clojure, C#, D. Erlang, F#, Go, Groovy. Haskell, Java 8, Java 14, Java 17, JavaScript(Node.js), Julia, Kotlin, Lisp (SBCL). Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3. Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift, TypeScript, Visual Basic

Sample Input

Init 16 4
Dump

Sample output
0000010 00000004 00 00000000 00 00000000 [00000000:00000000,00000000:00000000,][00000000:00000000,00000000:00000000,][00000000:00000000,00000000:00000000,][00000000:00000000,00000000:00000000,]