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:

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