FastPrep
Problem · Hash Table

In-Memory Database Historical Lookup

Learn this problem
● HardAnthropicOA

Problem statement

Implement a field-based in-memory database that can answer historical lookback queries. Every operation argument is encoded as a string, and operation timestamps are strictly increasing.

Operations

  • ["SET_AT", key, field, value, timestamp]: set or overwrite the field beginning at timestamp. The value does not expire. Return an empty string.
  • ["SET_AT_WITH_TTL", key, field, value, timestamp, ttl]: set or overwrite the field. It is visible during the half-open interval [timestamp, timestamp + ttl). Return an empty string.
  • ["DELETE_AT", key, field, timestamp]: delete the value visible at timestamp. Return true if a visible field was deleted, or false otherwise.
  • ["GET_WHEN", timestamp, key, field, at_timestamp]: return the value that was visible at at_timestamp. Return null if the record or field did not exist then. It is guaranteed that at_timestamp <= timestamp.
  • When at_timestamp is 0, return the value currently visible at the operation's own timestamp.

Keep expired and deleted versions in history so earlier lookback queries remain answerable. A newer write replaces the older value from its own timestamp onward; an older value does not reappear when the newer value expires.

Function

inMemoryDatabaseHistoricalLookup(operations: String[][]) → String[]

Examples

Example 1

operations = [["SET_AT","A","score","10","1"],["SET_AT_WITH_TTL","A","score","20","5","5"],["GET_WHEN","6","A","score","2"],["GET_WHEN","7","A","score","5"],["GET_WHEN","10","A","score","9"],["GET_WHEN","11","A","score","10"],["SET_AT","A","score","30","12"],["GET_WHEN","13","A","score","0"],["DELETE_AT","A","score","14"],["GET_WHEN","15","A","score","13"],["GET_WHEN","16","A","score","14"]]return = ["","","10","20","20","null","","30","true","30","null"]

The value 20 is visible on [5,10), so the lookback at 9 finds it while the lookback at 10 returns null. Deleting at 14 does not erase the value 30 from earlier history.

More Anthropic problems

drafts saved locally
public String[] inMemoryDatabaseHistoricalLookup(String[][] operations) {
  // write your code here
}
operations[["SET_AT","A","score","10","1"],["SET_AT_WITH_TTL","A","score","20","5","5"],["GET_WHEN","6","A","score","2"],["GET_WHEN","7","A","score","5"],["GET_WHEN","10","A","score","9"],["GET_WHEN","11","A","score","10"],["SET_AT","A","score","30","12"],["GET_WHEN","13","A","score","0"],["DELETE_AT","A","score","14"],["GET_WHEN","15","A","score","13"],["GET_WHEN","16","A","score","14"]]
expected["", "", "10", "20", "20", "null", "", "30", "true", "30", "null"]
checking account