How should I practice Key-Value Store on a Block Device?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Lambda phone screen problems in FastPrep.

Is Key-Value Store on a Block Device associated with Lambda?

FastPrep tags this as a Lambda phone screen coding practice problem when the problem catalog has that company and stage context.

Key-Value Store on a Block Device

Lambda● MediumFULLTIMEPHONE SCREEN

Problem statement

Build a key-value store on top of a block device. The device has numBlocks blocks numbered 0 to numBlocks - 1, and each block holds at most blockSize characters.

Values live on the device. To store a value, cut it into chunks of blockSize characters (the last chunk may be shorter) and write each chunk to its own block. A value of length L therefore uses ceil(L / blockSize) blocks. The chunks go into the lowest-numbered free blocks: the first chunk into the lowest one, the second chunk into the next lowest, and so on. The blocks a value uses do not have to be next to each other.

Process operations in order. Each operation adds one string to the answer:

["put", key, value]: store value under key, replacing any old value. If key already has a value, its blocks count as available, because they are released first. If the free blocks plus those released blocks are fewer than the blocks the new value needs, nothing changes and the answer is "FULL"; an old value stays in place. Otherwise, release the old blocks, write the new chunks as described above, and answer "OK".
["get", key]: answer the value stored under key, read back from its blocks, or "NOT_FOUND".
["delete", key]: release the blocks of key and answer "OK", or answer "NOT_FOUND" if the key has no value.
["read", block]: answer the chunk stored in block number block. A free block reads as the empty string.

Return the answers in order.

Function

blockKeyValueStore(blockSize: int, numBlocks: int, operations: String[][]) → String[]

Examples

Example 1

blockSize = 4numBlocks = 3operations = [["put","cat","meowmeow"],["read","0"],["read","1"],["get","cat"],["put","dog","woof"],["put","cow","moo"],["delete","cat"],["put","cow","moo"],["read","0"],["get","cow"]]return = ["OK","meow","meow","meowmeow","OK","FULL","OK","OK","moo","moo"]

meowmeow has 8 characters, so it fills blocks 0 and 1 with meow each, and get reads them back as meowmeow.
woof takes the last free block, 2. The device is now full, so putting moo answers FULL.
Deleting cat frees blocks 0 and 1. The second put of moo goes to block 0, the lowest free block.

Example 2

blockSize = 3numBlocks = 4operations = [["put","a","abcdefg"],["put","b","xy"],["put","a","zz"],["read","0"],["read","1"],["read","2"],["get","b"],["put","a","1234567890"]]return = ["OK","OK","OK","zz","","","xy","FULL"]

abcdefg uses blocks 0, 1 and 2 (abc, def, g), and xy uses block 3.
Replacing a with zz releases its three blocks first, so zz lands in block 0 and blocks 1 and 2 read as empty strings.
1234567890 needs 4 blocks, but only blocks 1 and 2 are free and a can release only block 0. That is 3 blocks, so the put answers FULL and a keeps zz.

Example 3

blockSize = 5numBlocks = 2operations = [["get","k"],["delete","k"],["read","1"],["put","k","hello"],["delete","k"],["delete","k"],["read","0"]]return = ["NOT_FOUND","NOT_FOUND","","OK","OK","NOT_FOUND",""]

Getting or deleting a missing key answers NOT_FOUND, and unused block 1 reads as an empty string. After hello is stored and deleted, a second delete answers NOT_FOUND and block 0 is empty again.

Constraints

1 <= blockSize <= 1000
1 <= numBlocks <= 1000
1 <= operations.length <= 500
Each operations[i] is ["put", key, value], ["get", key], ["delete", key], or ["read", block].
Each key has 1 to 10 lowercase letters.
Each value has 1 to 1000 characters, all lowercase letters or digits.
Each block is a decimal number without leading zeros, and 0 <= block < numBlocks.

See Lambda hiring insights