[Leetcode] 1981. Minimize the Difference Between Target and Chosen Elements

 1981. Minimize the Difference Between Target and Chosen Elements

You are given an m x n integer matrix mat and an integer target.

Choose one integer from each row in the matrix such that the absolute difference between target and the sum of the chosen elements is minimized.

Return the minimum absolute difference.

The absolute difference between two numbers a and b is the absolute value of a - b.

Constraints:

m == mat.length

n == mat[i].length

1 <= m, n <= 70

1 <= mat[i][j] <= 70

1 <= target <= 800

Analysis:

Let look at the brute-force way: there are n^m combinations in total. If n == m == 70, this number could be as large as 70^70, which is too overwhelming...

We need to figure out some way with reduced complexity.

Bitset would be a good choice to this question. The key idea is to use the index of the bits representing the sums.

For example, if a bitset bt[80] = 1, meaning the bit at the index of 80 is 1, then there is a sum equal to 80.

Bitset has an important operation: bit shift.

When we need to add a number to many others sums, then bit shift would greatly reduce the time complexity: since one bit shift operation would shift all the bits in a bitset by only one operation! More details can be found here.

In this question, initially we can have a bitset to record all the elements in the first row: basically set the corresponding bits as 1.

Then move on to the next row. 

For each number in the second row, we need to add it to all the possible sums stored in the bitset from the previous row. Bit shift can perfectly handle this. After performing this bit shift operation to each number in the row, we need to store all the possible sums into a new bitset, which is needed for the next row. An or (|) operation is good enough for this.

We just repeat this step row by row, to the last row.

After finishing all of this, all the possible sums are stored in the last bitset. We just need to check all the possible sums, to see which one gives the minimum abs(sum - target).

See the code below:

class Solution {
public:
    int minimizeTheDifference(vector<vector<int>>& mat, int target) {
        int m = mat.size(), n = mat.front().size(), cs = 40000, res = cs;
        bitset<40000> bt;
        for(int i=0; i<n; ++i) bt[mat[0][i]] = 1;
        for(int i=1; i<m; ++i) {
            bitset<40000> pre = bt, nxt;
            for(int j=0; j<n; ++j) {
                nxt |= pre << mat[i][j];
            }
            bt = nxt;
        }
        for(int i=0; i<cs; ++i) {
            if(bt[i]) res = min(res, abs(i-target));
        }
        return res;
    }
};

This question can also be solved by dfs + memo.  

memo[r][sum] means: the minimum abs(possible sums - target) starting with row number r and the starting sum value as sum.

The optimization lines and trim lines are needed, otherwise, it cannot pass the OJ.

See the code below:

class Solution {
public:
    int minimizeTheDifference(vector<vector<int>>& mat, int target) {
        int m = mat.size(), n = mat.front().size();
        for(auto &a : mat) {
            sort(a.begin(), a.end());
        }
        sort(mat.begin(), mat.end(), greater());
        memset(memo, -1, sizeof(memo));
        return dfs(mat, 0, 0, target);
    }
private:
    int memo[71][4901];
    int dfs(vector<vector<int>>& ms, int r, int sum, int& target) {
        if(r == ms.size()) {
            return abs(sum - target);
        }
        if(memo[r][sum] != -1) return memo[r][sum];
        int res = INT_MAX;
        for(int i=0; i<ms[r].size(); ++i) {
            if(sum + ms[r][i] > target && abs(sum + ms[r][i] - target >= res)) break;
            res = min(res, dfs(ms, r+1, sum + ms[r][i], target));
        }
        return memo[r][sum] = res;
    }
};

[Leetcode 1146] Snapshot Array

 1146. Snapshot Array

Implement a SnapshotArray that supports the following interface:

SnapshotArray(int length) initializes an array-like data structure with the given length.  Initially, each element equals 0.

void set(index, val) sets the element at the given index to be equal to val.

int snap() takes a snapshot of the array and returns the snap_id: the total number of times we called snap() minus 1.

int get(index, snap_id) returns the value at the given index, at the time we took the snapshot with the given snap_id

Constraints:

1 <= length <= 50000

At most 50000 calls will be made to set, snap, and get.

0 <= index < length

0 <= snap_id < (the total number of times we call snap())

0 <= val <= 10^9

Analysis:

This question is designed for data structure.

The snap_id is increased one by one, which means we can use a vector to record the snap information. The id of the vector becomes the snap_id naturally;

The length could be very large, like 50000, so if we use a something with similar sizes, it would be too large. Instead, we just need to record the elements that are updated (or set with values). One solution can use a unordered_map for this. The key will be the data index, and the value is the data value to be set.

Thus, the overall data structure is vector<unordered_map<int, int>>.

See the code below:

class SnapshotArray {
public:
    SnapshotArray(int length) {
        vmps.resize(1);
    }
    
    void set(int index, int val) {
        // assume index and snap_id are always valid
        vmps[id][index] = val;
    }
    
    int snap() {
        vmps.push_back(vmps[id]);
        return id++;
    }
    
    int get(int index, int snap_id) {
        // assume index and snap_id are always valid
        return vmps[snap_id][index];
    }
private:
    int id = 0;
    vector<unordered_map<int, int>> vmps;
};

/**
 * Your SnapshotArray object will be instantiated and called as such:
 * SnapshotArray* obj = new SnapshotArray(length);
 * obj->set(index,val);
 * int param_2 = obj->snap();
 * int param_3 = obj->get(index,snap_id);
 */

 

Leetcode 430: Flatten a Multilevel Doubly Linked List

https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/description/

You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.

Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.

Example:

Input:
 1---2---3---4---5---6--NULL
         |
         7---8---9---10--NULL
             |
             11--12--NULL

Output:
1-2-3-7-8-11-12-9-10-4-5-6-NULL

Explanation for the above example:

Given the following multilevel doubly linked list:

We should return the following flattened doubly linked list:

Notes:

This is a high-frequency interview question.

There are a lot of ways to solve this problem, and here I want to share two of them.

One is recursive, the other is iterative. Both are pretty straightforward.

Let's look at the first one:

When we meet with a non-nullptr child note, we just run a flatten(child). If we can return the head and tail, then we can simply insert this flattened result into the previous position.

 See the code below:

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;

    Node() {}

    Node(int _val, Node* _prev, Node* _next, Node* _child) {
        val = _val;
        prev = _prev;
        next = _next;
        child = _child;
    }
};
*/
class Solution {
public:
    Node* flatten(Node* head) {
        flat(head);
        return head;
    }
private:
    pair<Node*, Node*> flat(Node* head) {
      //  if(!head) return {head, head};
        Node* end = head;
        while(end) {
            Node* p = end->next;
            if(end->child) {
                auto res = flat(end->child);
                end->child = nullptr;
                end->next = res.first;
                res.first->prev = end;
                res.second->next = p;
                if(p) p->prev = res.second;
                else end = res.second;//must have
            }
            if(!p) break;
            end = p;
        }
        return {head, end};
    }
};

Now let us look at another method.

When we meet with a non-nullptr child, we just insert the next layer starting with the child note after the cur node position. Then continue the scan, and repeat the above process, done.

See the code below:

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;

    Node() {}

    Node(int _val, Node* _prev, Node* _next, Node* _child) {
        val = _val;
        prev = _prev;
        next = _next;
        child = _child;
    }
};

*/
class Solution {
public:
    Node* flatten(Node* head) {
        Node *p = head;
        while(p) {
            if(p->child) {
                Node* q = p->next;
                p->next = p->child;
                p->child->prev = p;
                p->child = nullptr;
                Node *r = p->next;
                while(r->next) r = r->next;
                r->next = q;
                if(q) q->prev = r;
            }
            p = p->next;
        }
        return head;
    }
};

Leetcode 381: Insert Delete GetRandom O(1) - Duplicates allowed

https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/description/

Design a data structure that supports all following operations in average O(1) time.

Note: Duplicate elements are allowed.

1. insert(val): Inserts an item val to the collection.
2. remove(val): Removes an item val from the collection if present.
3. getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.

Example:

// Init an empty collection.
RandomizedCollection collection = new RandomizedCollection();

// Inserts 1 to the collection. Returns true as the collection did not contain 1.
collection.insert(1);

// Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1].
collection.insert(1);

// Inserts 2 to the collection, returns true. Collection now contains [1,1,2].
collection.insert(2);

// getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3.
collection.getRandom();

// Removes 1 from the collection, returns true. Collection now contains [1,2].
collection.remove(1);

// getRandom should return 1 and 2 both equally likely.
collection.getRandom();

Notes:

This question can be viewed as a follow up to Leetcode 380: Insert Delete GetRandom O(1).

If we still use a vector to keep all the elements, the getRandom() should be still in O(1). But now we need to deal with the duplicates.

One identifier to duplicates are their indexes in the vector. So one way is that we can use the index as one part of the key of the hashmap.

See the code below:

class RandomizedCollection {
public:
    /** Initialize your data structure here. */
    RandomizedCollection() {

    }

    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    bool insert(int val) {
        int len = v.size();
        ump[val][len] = 1;
        v.push_back(val);
        return ump[val].size() == 1;
    }

    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    bool remove(int val) {
        if(!ump.count(val) || ump[val].empty() ) return false;
        int id = ump[val].begin()->first, a = v.back(), len = v.size();
        v[id] = a;
        ump[val].erase(id);
        ump[a][id] = 1;
        ump[a].erase(len-1);
        v.pop_back();
        return true;
    }

    /** Get a random element from the collection. */
    int getRandom() {
        return v[rand() % v.size()];
    }

private:
    unordered_map<int, unordered_map<int, int>> ump;//<val, <indx, ct>>
    vector<int> v;
};

/**
 * Your RandomizedCollection object will be instantiated and called as such:
 * RandomizedCollection* obj = new RandomizedCollection();
 * bool param_1 = obj->insert(val);
 * bool param_2 = obj->remove(val);
 * int param_3 = obj->getRandom();
 */

Another way is that we can define the following data structure:

unordered_map<int, vector<int>> mp;  // <val, <index>>;

Then how can we localize the index of the element inside <index> above? We can store this information inside the vector:

vector<pair<int , int>> //<pair<val, index inside mp[val] or <index>>

When a new element is inserted:

mp[val].push_back(v.size());
v.push_back({val, mp[val].size() - 1});

In this way, mp[val[i].first][val[i].second] = i. Thus, from the element inside the v, we can localize the element position inside the mp <int, vector<int>>.

Leetcode 380: Insert Delete GetRandom O(1)

https://leetcode.com/problems/insert-delete-getrandom-o1/description/

Design a data structure that supports all following operations in average O(1) time.

1. insert(val): Inserts an item val to the set if not already present.
2. remove(val): Removes an item val from the set if present.
3. getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.

Example:

// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();

// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);

// Returns false as 2 does not exist in the set.
randomSet.remove(2);

// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);

// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();

// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);

// 2 was already in the set, so return false.
randomSet.insert(2);

// Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();

Notes:

The key to this question is that: how can we achieve O(1) in getRandom()? since there is exiting data structures for insert() and remove() in O(1), for example, hashmap.

Vector or array can localize the element or getRandom() in O(1) (by using rand() for getRandom()), but how can we achieve O(1) in deleting one element?

It is known that we can pop_back() of a vector in O(1). So if we do not care about the deleted element any more, we can do a trick here:

Swap the A[i] with the A.back(). Then we can pop_back(). Both steps are in O(1). So we just need to use a hashmap to memorize the location of the A[i], then we can perform all swap and delete in O(1).

See the code below:

class RandomizedSet {
public:
    /** Initialize your data structure here. */
    RandomizedSet() {
       
    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    bool insert(int val) {
        if(!ump.count(val)) {
            ump[val] = data.size();
            data.push_back(val);
            return true;
        }
        return false;
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val) {
        if(ump.count(val)) {
            int indx = ump[val], last = data.back();
            data[indx] = last;
            ump[last] = indx;
            ump.erase(val);
            data.pop_back();
            return true;
        }
        return false;
    }

    /** Get a random element from the set. */
    int getRandom() {
        int len = data.size();
        return data[rand()%len];
    }

private:
    unordered_map<int, int> ump;
    vector<int> data;
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet* obj = new RandomizedSet();
 * bool param_1 = obj->insert(val);
 * bool param_2 = obj->remove(val);
 * int param_3 = obj->getRandom();
 */

Leetcode 907: Sum of Subarray Minimums

https://leetcode.com/problems/sum-of-subarray-minimums/description/

Given an array of integers A, find the sum of min(B), where B ranges over every (contiguous) subarray of A.

Since the answer may be large, return the answer modulo 10^9 + 7.

Example 1:

Input: [3,1,2,4]
Output: 17
Explanation: Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. 
Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.  Sum is 17.

Note:

1. 1 <= A.length <= 30000
2. 1 <= A[i] <= 30000

Notes:

Since the size of the array is very large, the naive O(N^2) method cannot pass the OJ.

The optimal solution can be O(N), by using a stack.

One of keys to this question is to find the minimum element and also its range.

Let say there is one local minimum arr[i], and the smaller first element on the left side is at index j, and the first smaller element on the right side is at index k. Then there are (i - j) * (k - i) subarrays with arr[i] as the minimum. So the contribution to the final results is arr[i]*(i-j)*(k-j).

And we need to do this for every element. A stack can be used to find j and k for each arr[i] by one pass.

The key is to maintain a monotonically increasing stack.

Since we need to figure out the distance, the stack will store index instead of values.

When meet with a smaller element (< stack.top()), the first smaller element on the right side of the arr[stack.top()] element can be found directly;

After popping out all the larger ones, the remaining are smaller or equal ones. So the current stack.top() is the left boundary of arr[i]. (The equal situation can also be included correctly.)

In order to easy code, element 0 has been placed before and after the array. In this way, all the elements in the original array can be popped out at the end of the code.

See the code below:

class Solution {
public:
    int sumSubarrayMins(vector<int>& A) {
        int res = 0, mod = 1e9+7;
        A.insert(A.begin(), 0);
        A.push_back(0);
        vector<int> L_idx(A.size(), -1), R_idx(A.size(), -1);
        stack<int> sk;
        for(int i=0; i<A.size(); ++i) {
            while(sk.size() && A[sk.top()] > A[i]) {
                int t = sk.top();
                sk.pop();
                R_idx[t] = i;
                long dis1 = t - L_idx[t], dis2 = R_idx[t] - t, val = A[t];
                res = (res + (dis1 * dis2 * val) % mod) % mod;
            }
            if(sk.size()) L_idx[i] = sk.top();
            sk.push(i);
        }
        A.erase(A.begin());
        A.pop_back();
        return res;
    }
};

Leetcode 1152: Analyze User Website Visit Pattern

https://leetcode.com › problems › analyse-user-website-visit-pattern

We are given some website visits: the user with name username[i] visited the website website[i] at time timestamp[i].

A 3-sequence is a list of websites of length 3 sorted in ascending order by the time of their visits.  (The websites in a 3-sequence are not necessarily distinct.)

Find the 3-sequence visited by the largest number of users. If there is more than one solution, return the lexicographically smallest such 3-sequence.

Example 1:

Input: username = ["joe","joe","joe","james","james","james","james","mary","mary","mary"], timestamp = [1,2,3,4,5,6,7,8,9,10], website = ["home","about","career","home","cart","maps","home","home","about","career"]
Output: ["home","about","career"]
Explanation: 
The tuples in this example are:
["joe", 1, "home"]
["joe", 2, "about"]
["joe", 3, "career"]
["james", 4, "home"]
["james", 5, "cart"]
["james", 6, "maps"]
["james", 7, "home"]
["mary", 8, "home"]
["mary", 9, "about"]
["mary", 10, "career"]
The 3-sequence ("home", "about", "career") was visited at least once by 2 users.
The 3-sequence ("home", "cart", "maps") was visited at least once by 1 user.
The 3-sequence ("home", "cart", "home") was visited at least once by 1 user.
The 3-sequence ("home", "maps", "home") was visited at least once by 1 user.
The 3-sequence ("cart", "maps", "home") was visited at least once by 1 user.

Note:

1. 3 <= N = username.length = timestamp.length = website.length <= 50
2. 1 <= username[i].length <= 10
3. 0 <= timestamp[i] <= 10^9
4. 1 <= website[i].length <= 10
5. Both username[i] and website[i] contain only lowercase characters.
6. It is guaranteed that there is at least one user who visited at least 3 websites.
7. No user visits two websites at the same time.

Notes:

After reading this question several times, I still cannot get the point of this question. Roughly it is asking for the top 3 rank of three-websites comb visited. One of the requirement is that these three website must be visited by the same person, and then it is counted as 1.

There is no much algorithm involved, and it is question for date structure.

First step, we can built up a map: the key will include the person. And we need to know all the websites the person has visited. A person may visit the same website several times but at different times, so the visiting time can also be used as one part of the key. In this way, we can record the combos composing with the same website but visited at different time.

The next step will be building all the possible three-website combos for the same person.

Then we can save this result using another map, but this time the three-website combo are the key. Thus we cannot use unordered_map if we use a string vector as the key.

We still need to know which person visits this three-website combo, so person can again be one part of the key for labeling.

After this map is finished, we just need to find the one with the largest counting.

See the code below:

vector<string> mostVisitedPattern(vector<string>& username, vector<int>& timestamp, vector<string>& website) {
    int len = username.size();
    unordered_map<string,map<int,string>> data;
    for(int i=0; i<len; ++i) {
        data[username[i]][timestamp[i]] = website[i];
    }
    map<vector<string>,unordered_map<string,int>> cts;
    for(auto &d : data) {
        if(d.second.size()<3) continue;
        for(auto i=d.second.begin(); i!=d.second.end(); ++i) {
            auto j = i; j++;
            for(; j!=d.second.end(); ++j) {
                auto k = j; k++;
                for(; k!=m.second.end(); ++k) {
                    ++cts[{(*i).second,(*j).second,(*k).second}][d.first];
                }
            }
        }
    }
    vector<string> res;
    int largest = 0;
    for(auto &i : cts){
        if(i.second.size() > largest){
            res = i.first;
            largest = i.second.size();
        }
    }
    return res;
}

A good reference can be found here:

https://github.com/ScientificKnights/Leetcode-Templates-and-Examples/blob/master/code/1152.%20Analyze%20User%20Website%20Visit%20Pattern.h

Leetcode 460: LFU Cache

https://leetcode.com/problems/lfu-cache/description/

---

Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

LFUCache cache = new LFUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.get(3);       // returns 3.
cache.put(4, 4);    // evicts key 1.
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

Note:

This question is a follow-up to Leetcode 146: LRU

The key points are:

(1): We need to get() a element in O(1), so hash map is a choice;

(2): We need to memorize both frequency and order of the elements, which are not covered by a hash map. So we need add some other kind of data structure. Since we need to erase a element in O(1) too, so list should be a choice;

(3): Using a list, it is true that we can erase one element in O(1), but we need to localize the position of the element in O(1) too. So another hash map is needed to correlate the key and the position in the list;

(4): We also need to record the frequency of each element;

(5): We need to maintain the least frequency as well.

See the code below:

class LFUCache {
public:
    LFUCache(int capacity) {
        cap = capacity;
        minF = 0;
    }

    int get(int key) {
        if(!ump.count(key)) return -1;
        freq[ump[key].second].erase(itr[key]);
        ++ump[key].second;
        freq[ump[key].second].push_back(key);
        itr[key] = --freq[ump[key].second].end();//cannot use rbegin() here; 
                                                                     //different iterator types
        if(freq[minF].empty()) ++minF;
        return ump[key].first;
    }

    void put(int key, int value) {
        if(cap<=0) return;
        if(get(key) != -1) { //must use get() here, to update the freq and minF; 
                                                 //otherwise, we have to update them individually.
            ump[key].first = value;
            return;
        }
        if(ump.size() >= cap) {
            ump.erase(freq[minF].front());//smallest freq and least used;
            itr.erase(freq[minF].front());
            freq[minF].pop_front();
        }
        ump[key] = {value, 1};
        freq[1].push_back(key);
        itr[key] = --freq[1].end();
        minF = 1;
    }

private:
    int cap, minF;
    unordered_map<int, pair<int, int>> ump; //<key, <value, frequency>>
    unordered_map<int, list<int>::iterator> itr; //<key, <iterator of key> in the list>
    unordered_map<int, list<int>> freq; //<freq, <key>>
};

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache* obj = new LFUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

Leetcode 981: Time Based Key-Value Store

https://leetcode.com/problems/time-based-key-value-store/description/



Notes:

This question is pretty straightforward, and it is essentially a question of data structure + binary search. See the code below,

class TimeMap {
public:
    /** Initialize your data structure here. */
    TimeMap() {

    }

    void set(string key, string value, int timestamp) {
        if(ump.count(key) == 0) ump[key].push_back({timestamp, value});
        auto it = upper_bound(ump[key].begin(), ump[key].end(), pair<int, string>(timestamp, ""));
        ump[key].insert(it, {timestamp, value});
    }

    string get(string key, int timestamp) {
        if(ump.count(key) == 0) return "";
        auto it = upper_bound(ump[key].begin(), ump[key].end(), pair<int, string>(timestamp, ""));
        if(it != ump[key].end() && it->first == timestamp) return it->second;
        if(it == ump[key].begin()) return "";
        return (it-1)->second;
    }
private:
    unordered_map<string, vector<pair<int, string>>> ump;
};

/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap* obj = new TimeMap();
 * obj->set(key,value,timestamp);
 * string param_2 = obj->get(key,timestamp);
 */

It should be noticed that inside the upper_bound(), the type of pair has to be written explicitly as pair<int, string>, otherwise compiler error will occur.

Another way using a different structure. Pay attention to the property of map.upper_bound().

int _=[](){//increase run spead
 ios::sync_with_stdio(false);
 cin.tie(nullptr);
 return 0;
 }();

class TimeMap {
public:
    /** Initialize your data structure here. */
    TimeMap() {
       
    }
   
    void set(string key, string value, int timestamp) {
        ump[key][timestamp] = value;
    }

    string get(string key, int timestamp) {
        if(ump.count(key) == 0) return "";
        auto it = ump[key].upper_bound(timestamp); //find the upper bound of the key of the map...
        if(it == ump[key].begin()) return "";
        return (--it)->second;
    }

private:
    unordered_map<string, map<int, string>> ump;
};

/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap* obj = new TimeMap();
 * obj->set(key,value,timestamp);
 * string param_2 = obj->get(key,timestamp);
 */