146. LRU Cache

Difficulty: Hard

Frequency: N/A

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class LRUCache{
public:
    LRUCache(int capacity) : cap(capacity) { }
    
    int get(int key) {
        auto iter = map.find(key);
        if (iter == map.end()) return -1;
        touch(iter);
        return iter->second.first;
    }
    
    void set(int key, int value) {
        auto iter = map.find(key);
        if (iter != map.end()) touch(iter);
        else {
            if (map.size() == cap) {
                map.erase(lru.back());
                lru.pop_back();
            }
            lru.push_front(key);
        }
        map[key] = {value, lru.begin()};
    }
private:

    typedef list<int> IntList;
    typedef pair<int, IntList::iterator> IntIntList;
    typedef unordered_map<int, IntIntList> Map;
    
    int cap;
    IntList lru;
    Map map;
    void touch(Map::iterator iter) {
        int key = iter->first;
        lru.erase(iter->second.second);
        lru.push_front(key);
        iter->second.second = lru.begin();
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:
Advertisements

237. Delete node in a linked list

Difficulty: 

Frequency: 

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.


 

My solution:
Data structure:
list
Steps:
1. Copy the next node to current node
2. Delete next node
Complexity:
Runtime: O(1)
Space: O(n)
Test cases:
Corner cases:
Code:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
    void deleteNode(ListNode* node) {
        ListNode *temp = node-&gt;next;
        *node = *node-&gt;next;
        delete temp;
        temp = NULL;
    }
};



Things to learn:
1. Remember to free the data
 

163. (Locked)Missing Ranges

Difficulty: Medium

Frequency: N/A

Given a sorted integer array where the range of elements are [0, 99] inclusive, return its missing ranges.

For example, given [0, 1, 3, 50, 75], return [“2”, “4->49”, “51->74”, “76->99”]

Example Questions Candidate Might Ask:

Q: What if the given array is empty?
A: Then you should return [“0->99”] as those ranges are missing.

Q: What if the given array contains all elements from the ranges? A: Return an empty list, which means no range is missing.


My solution:
Data structure:
array, list
Steps:
1. For each two adjacent ints in the array(including start – 1 and end + 1), calculate the range
2. how to calculate the range between a and b
  2.1 If b – a == 1, nothing
  2.2 If b – a == 2, return (b + a) /2
  2.3 If b – a > 2, return (a + 1)->(b – 1)
Complexity:
Runtime: O(n)
Space: O(n)
Test cases:
[0, 1, 3, 50, 75]
Corner cases:
[]
[0, 1, …, 99]
Code:

class Solution {
public:
    vector&lt;string&gt; findMissingRanges(array&lt;int&gt; vals, int start, int end) {
        vector&lt;string&gt; results;
        int prev = start - 1;
        for (int i = 0; i &lt;= vals.size(); i++) {
            // handle the last element(end)
            int curr = (i == vals.size()) ? end + 1 : vals[i];
            if (curr - prev == 2) {
                results.push_back(to_string(prev + 1));
            } else if (curr - prev &gt; 2) {
                string val = to_string(prev + 1) + &quot;-&gt;&quot; + to_string(curr - 1);
                results.push_back(val);
            }
            prev = curr;
        }
        return results;
    }
}

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:
1. It is very import to unify the problem, then do not need to handle special case
2. Need to know handy c++ functions