FastPrepMulti-Level Inventory Storage System
Problem · Design

Multi-Level Inventory Storage System

Learn this problem
● HardOptiver logoOptiverINTERNOAPHONE SCREEN
See Optiver hiring insights

Problem statement

Researchers are studying squirrels that hide and collect nuts in cone-shaped locations. Implement the behavior of the SquirrelResearch system over a finite sequence of operations.

Practice interface

Implement simulateSquirrelResearch(locations, operations).

  • Each entry of locations has the form "location_id:levels".
  • Each entry of operations is one HideNut or RetrieveNuts action in one of the formats below.
  • Return one string for every operation, in input order. A HideNut result is "true" or "false". A RetrieveNuts result is a bracketed, comma-separated list such as "[nutA,nutB]", or "[]" when no nut is returned.

Locations and levels

Level 0 is the deepest level. Level capacities follow 1, 2, 3, 5, ..., so a three-level location holds at most six nuts. Nuts fill the deepest level first. A higher level cannot receive a hidden nut until every lower level is full.

HideNut

An action has the form "HideNut timestamp location_id nut_id nut_weight time_to_expire".

  • Hide the nut in the first non-full level, scanning from the deepest level upward.
  • Return "false" when the location does not exist, the location is full, or the same nut_id is currently hidden in any location. Otherwise hide the nut and return "true".
  • A nut hidden at time hidden_at is expired only when a later action has timestamp > hidden_at + time_to_expire. It is still live when the two values are equal.

RetrieveNuts

An action has the form "RetrieveNuts timestamp location_id max_squirrel_capacity_in_nuts".

Repeat the following selection until the squirrel has examined max_squirrel_capacity_in_nuts nuts or no nut remains:

  1. Find the uppermost non-empty level.
  2. That level is reachable. If it is occupied to strictly less than 50% of its capacity, the level immediately below it is also reachable.
  3. Among all nuts in the reachable level or levels, select the nut with the greatest weight. Break a weight tie by the alphabetically smallest nut_id.
  4. Remove the selected nut. If it is expired at the action timestamp, discard it and omit its ID from the result. A discarded expired nut still consumes one unit of the squirrel's examination capacity.
  5. If the selected nut came from the lower reachable level, move the lightest nut from the level above into the vacated place. When several falling nuts have the same minimum weight, move the one with the alphabetically smallest ID.

Return the live selected nut IDs in selection order. Return "[]" for an unknown or empty location. Removed and discarded IDs may be reused by later HideNut actions.

All action timestamps are globally strictly increasing. Identifiers contain no whitespace, commas, colons, or brackets.

Function

simulateSquirrelResearch(locations: String[], operations: String[]) → String[]

Examples

Example 1

locations = ["pine:3"]operations = ["HideNut 1 pine a 5 100","HideNut 2 pine b 9 100","HideNut 3 pine c 3 100","HideNut 4 pine d 8 100","RetrieveNuts 5 pine 2"]return = ["true","true","true","true","[b,d]"]

The three levels have capacities 1, 2, and 3. Nut d is alone in the uppermost level, so that level is less than half full and the level below is reachable. Nut b is heavier than d, so b is selected first. Then d, the lightest nut from the level above, falls into its place. The next selection returns d.

Example 2

locations = ["oak:1","pine:1"]operations = ["HideNut 1 oak shared 4 10","HideNut 2 pine shared 9 10","RetrieveNuts 3 oak 1","HideNut 4 pine shared 9 10","RetrieveNuts 5 missing 2","RetrieveNuts 6 pine 1"]return = ["true","false","[shared]","true","[]","[shared]"]

The second hide fails because shared is already hidden in another location. Retrieving it from oak makes the ID reusable, so the later hide in pine succeeds. Retrieving from an unknown location returns an empty list.

Example 3

locations = ["den:1"]operations = ["HideNut 1 den timed 4 2","RetrieveNuts 3 den 1","HideNut 4 den stale 7 1","RetrieveNuts 6 den 1","HideNut 7 den stale 8 1"]return = ["true","[timed]","true","[]","true"]

timed is still live at exactly 1 + 2. Nut stale is expired at time 6, so it is removed but omitted from the result. Its ID can then be used again.

Constraints

  • 2 <= operations.length < 2^15
  • 1 <= locations.length < 2^10
  • 1 <= levels <= 32
  • 0 < nut_weight <= 20
  • 1 <= max_squirrel_capacity_in_nuts < 2^10
  • Timestamps, expiration durations, and weights are positive decimal values with at most three digits after the decimal point.
  • Action timestamps are globally strictly increasing and fit in a signed 32-bit value.
  • Every identifier is non-empty and contains no whitespace, commas, colons, or brackets.

More Optiver problems

drafts saved locally
public String[] simulateSquirrelResearch(String[] locations, String[] operations) {
  // write your code here
}
locations["pine:3"]
operations["HideNut 1 pine a 5 100","HideNut 2 pine b 9 100","HideNut 3 pine c 3 100","HideNut 4 pine d 8 100","RetrieveNuts 5 pine 2"]
expected["true", "true", "true", "true", "[b,d]"]
checking account