This requires us to think about the optimal data structure behind a database, which mostly used to implement get and put.

LRU Cache This is implemented through a map<key, iterator of list> to store the map between key and its position in the list, and a list<pair<value, key> > to store the actual value. To realize only keeping most recent elements, the list is actually a double linked list and always push from front and pop from back if bigger than the capacity. hashMap<key, iterator> is used when searching by key; list<value, key> is used when putting at the front and pop at back. Why the list need to store pairs of <value, key>? To get(key) and put(key, value), only list[value] is enough, but when we are out of capacity and we want to delete not only list last element, but also the hash element. To where it is in hash, only know the iterator is not enough, we need to know the key, so we also store the key in the pair.

LFU Cache It takes me a while to get it right. Similar to LRU, need to have map<key, <count, value>> key2Cnt, map<count, list> cnt2Key, and for the purpose of quick lookup when trying to delete key in cnt2Key, we use a map<key, list::iterator> to keep track of the position. To know which count is the min, we use a variable called minCount to track it.

Insert Delete GetRandom O(1) - Duplicates allowed Use a map<key, set and vecotr to store the result.

Trie It is the classics of classics. Create a seperate TrieNode stuct,, containing TrieNode*[26] and a boolean variable indicating whether the end of a word or not. Done. ** Remember to put memset in the constructor to avoid memory misalignment.

struct TrieNode{
public:    
    TrieNode(){
        wordEnd = false;
         memset(node,0,sizeof(TrieNode*)*26);
    }

    TrieNode* node[26];
    bool wordEnd;
};

Find Median from Data Stream Two easy data structure can keep it i O(lgn) time. (1) Through two heaps, one minHeap & one maxHeap. (2). Through a self-balanced tree with two pointers to the median_lo and median_hi. In C++, multiset can keep track of sorted array.

Flatten Nested List Iterator Use a stack to store the element at initialzation reversely. When call hasNext, if the top is a list, then pop out the list and push all its element back to stack, if the top element is still a list, then do the same thing, until the tap of the stack is an integer. When call getnext, just return the top of the stack(it is guaranteed to be an integer.

Flatten 2D vector It is trivial to use a queue to implement. But the question ask to use iterator instead, which I haven't figure out how.

Shuffle An Array In order to reset, need to maintain both curr array and orig array.

Min Stack Similar to shuffle array, need to maintain both stack and min Stack.

Serialize and Deserialize Binary Tree Use a queue to serialize a tree, each time pop out a node, add to string and push its children to the series; Also use a queue to deserialize, push the first number to the queue, then each time pop out the front of the queue, assign the stoi(strNum) to the children of the node, and push these children to the queue.

Serialize and Deserialize N-ary Tree User recursion to serialize the tree in format node val follow by the number of its kids.

Serialize and Deserialize BST This is easier than the previous one, since a BST can be represented as a preorder string uniquely. To further save memory, use 4 byte to encode int, instead of use comma. (See https://leetcode.com/problems/serialize-and-deserialize-bst/discuss/93167/Concise-C++-19ms-solution-beating-99.4)

Design Tic-Tac-Toe One smart way is just store the number of player 1 per row, col, (anti)diag. When meet player 2's move, reduce the values by 1. if find some row/col/diag with sum == size or sum == -1 * size, return either player 1 or player 2.

Encode and Decode Strings Use a substring length as a prefix when concatenating, also these length needs to be unified to the same length.

Design Hit Counter I use a queue to cache hit time within the 300 window, while use a dictionary to track the hit frequency at each time.

Read N Characters Given Read4 II - Call multiple times It takes me a while to understand the question, as the I am not familiar with the read ptr in C. The solution is to use a buffer to contain the element read from read4 and use a counter and ptr to keep track of the size of the buffer and the last reading position of buffer. The buf in the function call is an output to be filled, instead of an input. For further explanation, see(https://leetcode.com/problems/read-n-characters-given-read4-ii-call-multiple-times/discuss/49607/The-missing-clarification-you-wish-the-question-provided).

exam-room

maintain a sorted seated seats list. find the max interval when seating, and insert in the middle. O(p).

peeking-iterator

This is like a brainteaser, simply store the next value as a temp variable.

design-phone-directory

It seems so unfairly easy using python set.

time-based-key-value-store

Use '{' as a the first character bigger than alphabet z, ord('{') = 123.

design-snake-game

Use a deque to mimic the snake body, to check if the snake bite itself in O(1), use a set to store snake body as well.

design-log-storage-system

convert time to intgeter and find the lower bound and upper bound when searching. However, the solution appears in python discussion seems no string to int conversion is needed.

all-oone-data-structure

Use a doubly linked list to attain O(1), insert and delete. and Use a hash map to store the key to the node in LL.

631. Design Excel Sum Formulaset()时O（1）操作，cell[i][j]中存val或list of dependency; get时，若cell[i][j]中存有list，则对每个元素分别用get; dependency在sum时设置\

1472. Design Browser Historydynamic array, 设置指针curr_idx, last_idx\

3408. Design Task Managerheap; Lazy Removal\