128. Longest Consecutive Sequence

Difficulty: Medium

Frequency: N/A

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

Test Cases:

Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
int longestConsecutive(vector<int> nums) {
unordered_set<int> s;
for (int n : nums) s.insert(n);
int maxLen = 1;
for (int n : nums) {
if (s.empty()) break;
int curNum = n;
int curLen = 0;
while (s.count(curNum)) {
s.erase(curNum);
curLen++;
curNum++;
}
curNum = n - 1;
while (s.count(curNum)) {
s.erase(curNum);
curLen++;
curNum--;
}
maxLen = max(maxLen, curLen);
}
return maxLen;
}
};

Solution 2:

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

Submission errors:

Things to learn:

325. (Locked)Maximum Size Subarray Sum Equals k

Difficulty: Easy

Frequency: N/A

Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn’t one, return 0 instead.

Example 1:

Given nums = [1, -1, 5, -2, 3], k = 3,
return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)

Example 2:

Given nums = [-2, -1, 2, 1], k = 1,
return 2. (because the subarray [-1, 2] sums to 1 and is the longest)

Can you do it in O(n) time?

Test Cases:

Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
int maxSubArrayLen(vector<int>& nums, int k) {
unordered_map<int, int> m;
int result = 0, cur_sum = 0;
for (int i = 0; i < nums.size(); i++) {
cur_sum += nums[i];
if (cur_sum == k) result = i + 1;
else if (m.find(k - cur_sum) != m.end()) {
result = max(result, i - m[k - cur_sum]);
}
if (m.find(cur_sum) == m.end()) m[cur_sum] = i;
}
return result;
}
};

Solution 2:

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

Submission errors:

Things to learn:

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:

244. (Locked)Shortest Word Distance II

Difficulty: Medium

Frequency: N/A

This is a follow up of Shortest Word Distance. The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it?

Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list.

For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Given word1 = "coding”word2 = "practice”, return 3.
Given word1 = "makes"word2 = "coding", return 1.

Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
class WordDistance {
unordered_map<string, vector<int>> dict;
public:
WordDistance(vector<string> words) {
int n = words.size();
for (int i = 0; i < n; i++) {
dict[words[i]].push_back(i);
}
}
int shortest(string word1, string word2) {
vector<int> pos1 = hash[word1];
vector<int> pos2 = hash[word2];
int dist = INT_MAX;
for(auto p1:pos1){
for(auto p2:pos2){
dist = min(dist, abs(p1-p2));
}
}
return dist;
}
};

Things to learn:

288. (Locked)Unique Word Abbreviation

Difficulty: Easy

Frequency: N/A

An abbreviation of a word follows the form <first letter><number><last letter>. Below are some examples of word abbreviations:

a) it                      --> it    (no abbreviation)

1
b) d|o|g                   --> d1g

1    1  1
1---5----0----5--8
c) i|nternationalizatio|n  --> i18n

1
1---5----0
d) l|ocalizatio|n          --> l10n

Assume you have a dictionary and given a word, find whether its abbreviation is unique in the dictionary. A word’s abbreviation is unique if no other word from the dictionary has the same abbreviation.

Example:

Given dictionary = [ "deer", "door", "cake", "card" ]

isUnique("dear") -> false
isUnique("cart") -> true
isUnique("cane") -> false
isUnique("make") -> true

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
private:
unordered_map<string, vector<string>> dict;
public:
ValidWordAbbr(vector<string> &dictionary) {
for (string s : dictionary) {
int n = s.size();
string key = s + to_string(n - 2) + s[n - 1];
if (dict.find(key) == dict.end()) {
vector<string> val;
val.push_back(s);
dict.insert(make_pair<string, vector<string>>(key, val));
} else dict[key].push_back(s);
}
}
bool isUnique(string word) {
int n = word.size();
string key = word + to_string(n - 2) + word[n - 1];
if (dict.find(key) == dict.end()) return true;
else if (dict[key].size() == 1 && word == dict[key]) return true;
return false;
}
}

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

Things to learn:

030. Substring with Concatenation of All Words

Difficulty: Hard

Frequency: N/A

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in wordsexactly once and without any intervening characters.

For example, given:
s: "barfoothefoobarman"
words: ["foo", "bar"]

You should return the indices: [0,9].

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:

class Solution {
public:
vector findSubstring(string s, vector& words) {
vector results;
if (s.empty() || words.empty()) return results;
int count = words.size(), word_length = words.size();
if (s.size() < count * word_length) return results;
int start = 0;
while (start <= s.size() – count * word_length) {
unordered_map dict;
for (int i = 0; i < words.size(); i++) dict[words[i]]++;
int head = start;
while (head 0) {
dict[tmp]–;
} else break;
}
if (head == start + count * word_length) results.push_back(start);
start++;
}
return results;
}
};

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

Things to learn:

094. Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

1
\
2
/
3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

Questions:
1. Recursive or iteratively

Test Cases:

1. [#] empty
2.  root only
3. [1, 2, #, 3, #, 4] all left
4. [1, #, 2, #, #, #, 3] all right
5. [1, #, 2, 3] normal

Solution 1:
Data structure:
vector, tree
Method:
Recursive:
1. helper(node->left)
2. push(node->val)
3. helper(node->right)
Complexity:
Runtime:
worst case: o(n^2)
average: o(nlogn)
Space:
o(n)
Code:
/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
inorderTraverse(root, result);
return result;
}
void inorderTraverse(TreeNode *node, vector<int>& result) {
if (!node) return;
inorderTraverse(node->left, result);
result.push_back(node->val);
inorderTraverse(node->right, result);
}
};

Solution 2:
Data structure:
Method:
Complexity:
Runtime:
Space:
Code:

Things to learn:
1. Tree Traversals: