981. Time Based Key-Value Store

How to solve Time Based Key-Value Store (LeetCode 981): the approach in brief

The problem

Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key's value at a certain timestamp.

Pattern

Time Based Key-Value Store is a Design Patterns problem, in the Design (General/Specific) subpattern. The pattern covers tries, LRU/LFU cache, and data structure design

Design and implement data structures: LRU cache, LFU cache, HashMap, and specialized structures.

Approach outline

1. Think about how to efficiently store multiple values for each key, considering the time aspect as an additional dimension.
2. Since timestamps for each key are strictly increasing, consider a data structure that maintains the order of these timestamps along with their associated values.
3. To retrieve the value for a given timestamp, you need to find the closest timestamp less than or equal to the requested one; this suggests using a search method that leverages the sorted order.

Complexity

The reference solution runs in O(1) time and O(K + Q) space.

Asked at

Time Based Key-Value Store has been reported in interviews at Oracle, ByteDance, Uber, Apple, Lyft, Sumologic, Google, Atlassian.