OpenAI疑似从没见过的新题

[Blind上看到的，大家自行判断]
.. Resumable Versioned Key-Value Store

. ΧYou're building an in-memory key-value store used by a distributed training job to checkpoint model metadata.

Part 1. Implement set(key, value, timestamp) and get(key, timestamp). get returns the value that was set at the closest timestamp at or before the given timestamp. Timestamps are strictly increasing per key, but writes may arrive out of order due to network delay, and your store should handle that gracefully.

. 1point 3 acresPart 2. Add get_latest(key), which returns the most recent value. "Most recent" means the value with the highest timestamp, unless a newer write has been received, in which case it should reflect what the client most recently intended.

Part 3. The store must be serializable so a crashed job can resume. Implement serialize() and deserialize(). A deserialized store must behave identically to the original, including for any writes that were in flight at serialization time.

Part 4. Values are immutable once read. If get returns a value, any later set for that key at an earlier timestamp should be rejected. However, backfilling historical data must still be supported.

Constraints: All operations O(1). Memory usage should not grow with the number of versions. Thread-safe, though you may assume single-threaded access. If a key doesn't exist, return None or raise, whichever is consistent with Part 4.

Follow-up: How would you scale this to 10,000 GPUs?

我自己瞎想的
先不考虑scale 问题。
构造一个 Hash Table, key就是key， value部分是一个double linked list, 按照timestamp 排序，大的在最开始。如果插入比第一个list node相同或更早timestamp的记录就拒绝。

“but writes may arrive out of order due to network delay, and your store should handle that gracefully.” 是什么意思？timestamp小的如果后到，那么被拒绝是合理的吗？

这两个结构都是serializable的。

没有解决的问题是，如何做到o(1) get key/timestamp. 遍历timestamp的double linked list需要o(k), 不知道是否算o(1). 也可以加指针map，指示double linked list 中若干节点位置，快速找到起始点，开始搜索 （简单点就是维护头尾中三个点的指针）。这还是不能保证完全o(1). 这个需求要clarify
另外，Memory usage should not grow with the number of versions. 是什么意思？存多个版本而不增加内存，显然不合理，是不是有误会，需要进一步理解一下需求。

如果解决了这个问题，那么下一步就是scale， 那么consistent hashing加多台服务器走起，开始envolpe计算。“scale this to 10,000 GPUs”是不是有问题？这个key/value不是gpu的活, 没有矩阵乘法啊？

Hashtable 太重的话，用hashmap + redis 做key级别的访问锁, 或者用concurrentHashMap

抛砖引玉

这是system design还是coding？

请问这题看到是New Grad的吗？还是在职的？他们家这在职和new grad 的coding题库挺不一样的。