715. Range Module

https://leetcode.com/problems/range-module/description/
Solution 1. Use map
class RangeModule {
    map<int,int> m;
public:
    RangeModule() {
       
    }
   
    void addRange(int left, int right) {
        auto l = m.upper_bound(left), r = m.upper_bound(right);
        if(l != m.begin()) {
            l--;
            if(l->second < left) l++;
        }
        if(l != r) {
            left = min(left, l->first);
            r--;
            if(right < r->second) right = r->second;
            r++;
            m.erase(l,r);
        }
        m[left] = right;
    }
   
    bool queryRange(int left, int right) {
        auto l = m.upper_bound(left);
        if(l!=m.begin()) {
            l--;
            return l->second >= right;
        }
        return false;
    }
   
    void removeRange(int left, int right) {
        auto l = m.upper_bound(left), r = m.upper_bound(right);
        if(l != m.begin()) {
            l--;
            if(l->second < left) l++;
        }
        if(l==r) return;
        int l1 = min(l->first, left);
        r--;
        int r1 = max(r->second, right);
        r++;
        m.erase(l,r);
        if(l1 < left) m[l1] = left;
        if(right< r1) m[right] = r1;
    }
};

Solution 2. Use vector<int> (196 ms)
class RangeModule {
    vector<int> v;
public:
    RangeModule() {
     
    }
 
    void addRange(int left, int right) {
        if(v.empty()) { v= {left, right}; return;}
        auto l = lower_bound(v.begin(), v.end(), left);
        auto r = upper_bound(v.begin(), v.end(), right);
        int i = l - v.begin();
        int j = r - v.begin();
        if(l == r) {
            if(i%2 == 0) {
                l = v.insert(l, right);
                v.insert(l, left);
            }
            return;
        }
        if(i%2 == 0) { *l = left; l++;}
        if(j%2 == 0) { *l = right; l++; }
        else { *l = *r; l++; r++;}
        if(l<r) v.erase(l, r);
    }
 
    bool queryRange(int left, int right) {
        // note that here l = upper_bound(..., left) and r = lower_bound(..., right)
        auto l = upper_bound(v.begin(), v.end(), left);
        auto r = lower_bound(v.begin(), v.end(), right);
        int i = l - v.begin();
        return (i%2 != 0) && l == r;
    }
 
    void removeRange(int left, int right) {
        if(v.empty()) { return;}
        auto l = lower_bound(v.begin(), v.end(), left);
        auto r = upper_bound(v.begin(), v.end(), right);
        int i = l - v.begin();
        int j = r - v.begin();
        if(l==r) {
            if(i%2 != 0) {
                l = v.insert(l, right);
                v.insert(l, left);
            }
            return;
        }
        if(j%2 != 0) { r--; *r = right;}
        if(i%2 != 0) { *l = left; l++;}
        if(l<r) v.erase(l,r);
    }
};

384. Shuffle an Array

https://leetcode.com/problems/shuffle-an-array/description/
class Solution {
    vector<int> nums;
public:
    Solution(vector<int> nums) {
        this->nums = nums;
    }
 
    /** Resets the array to its original configuration and return it. */
    vector<int> reset() {
        return nums;
    }
 
    /** Returns a random shuffling of the array. */
    vector<int> shuffle() {
        int N = nums.size();
        vector<int> res(nums);
        for(int i=0; i<N; i++) {
            int j = rand() % (N-i);
            swap(res[i], res[i+j]);
        }
        return res;
    }
};

382. Linked List Random Node

https://leetcode.com/problems/linked-list-random-node/description/
Solution 1. Reservoir sampling
class Solution {
    ListNode* head;
public:
    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    Solution(ListNode* head) {
        this->head = head;
    }
    /** Returns a random node's value. */
    int getRandom() {
        ListNode* node = head;
        int res = node->val;
        node = node->next;
        int k=1, kpi=2;
        while(node) {
            if(rand()%kpi == 0) res = node->val;
            kpi++;
            node = node->next;
        }
        return res;
    }
};
Solution 2.
class Solution {
    int N;
    int len = 1000;
    ListNode* hd;
    vector<ListNode*> vl;
public:
    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    Solution(ListNode* head) {
        hd = head;
        ListNode* p=head;
        N = 0;
        while(p) {
            if(N%len == 0) vl.push_back(p);
            N++;
            p = p->next;
        }
    }
    /** Returns a random node's value. */
    int getRandom() {
        random_device rd;
        uniform_int_distribution<int> dist(0, N-1);
        int n = dist(rd);
        ListNode*p = vl[n/len];
        n = n%len;
        while(n) {
            p = p->next;
            n--;
        }
        return p->val;
    }
};

676. Implement Magic Dictionary

https://leetcode.com/problems/implement-magic-dictionary/description/
class MagicDictionary {
    unordered_map<string,vector<pair<int,char>>> d;
public:
    /** Initialize your data structure here. */
    MagicDictionary() {
     
    }
 
    /** Build a dictionary through a list of words */
    void buildDict(vector<string> dict) {
        for(string s : dict) {
            for(int i=0; i<s.size(); i++) {
                string w = s.substr(0, i) + s.substr(i+1);
                d[w].push_back({i, s[i]});
            }
         
        }
    }
 
    /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
    bool search(string word) {
        for(int i=0; i<word.size(); i++) {
            string w = word.substr(0, i) + word.substr(i+1);
            if(d.count(w)) {
                for(auto& p : d[w]) {
                    if(p.first == i && p.second != word[i]) return true;
                }
            }
        }
        return false;
    }
};

System design

https://github.com/donnemartin/system-design-primer

535. Encode and Decode TinyURL

https://leetcode.com/problems/encode-and-decode-tinyurl/description/
class Solution {
    unordered_map<string, string> encodeMap;
    unordered_map<string, string> decodeMap;
    string dict = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
public:

    // Encodes a URL to a shortened URL.
    string encode(string longUrl) {
        if(encodeMap.count(longUrl)) return encodeMap[longUrl];
        string shortUrl = "http://tinyurl.com/";
        int n = encodeMap.size(), nd = dict.size();
        while(n) {
            shortUrl += dict[n%nd];
            n /= nd;
        }
        encodeMap[longUrl] = shortUrl;
        decodeMap[shortUrl] = longUrl;
        return shortUrl;
    }

    // Decodes a shortened URL to its original URL.
    string decode(string shortUrl) {
        return decodeMap[shortUrl];
    }
};