---

[!info] related notes 算法面试题型 MOC

Data Structure Design Interview Notes

setAll HashMap

• Store for each key: (value, setTime).
• Maintain global (setAllValue, setAllTime).
• get(k) returns key’s value if keyTime > setAllTime, else returns setAllValue.

LRU Cache

• HashMap for key -> node.
• Doubly linked list for recency order.
• Operations:
  • get: move node to tail.
  • put: update + move, or insert; if over capacity, evict head.

Insert/Delete/GetRandom in O(1)

• Array stores values.
• HashMap stores value -> index in array.
• Delete by swapping with last element and updating index.

GetRandom with Duplicates Allowed

• Similar, but value -> set of indices.

Median from Data Stream

• Two heaps:
  • max-heap for smaller half
  • min-heap for larger half
• Balance sizes so that size diff <= 1.

Related

• 堆常见题