This is an old revision of the document!
Algorithm Problems
For general techniques, see Algorithm Techniques.
For helpful reference, see Coding Cheat Sheet.
An algorithm interview is like being in a race in a maze with hidden clues and signs to tell you where you should go, all while trying to get to the finish line in under 30 minutes. If you miss a sign, you're fucked. If you go too slow, you're fucked. So just go steady, watch the signs and down blow past them!
Binary Search
Given a sorted (in ascending order) integer array nums of n elements and a
target value, write a function to search target in nums. If target exists, then
return its index, otherwise return -1.
This is BEDROCK code that I sometimes forget. Binary Search of sorted data. This
is what gets you O( Log N ) search of data.
1. Left pointer = 0 and right pointer = to last element 2. While left is less then or equal to right 3. Find middle 4. Check if our target is in the middle, return it if we found it 5. If our target is less than the middle element 6. explore left, mid; 7. If our target is greater than the middle 8. explore mid+1 and right; 9. return -1 if not found.
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size();
int mid;
while(left<=right){
mid = left + (right-left)/2;
if (nums[mid]==target){
return mid;
}
else if (nums[mid] > target)
right = mid -1;
else left = mid+1;
}
return -1;
}
Move Zeros
Given an array nums, write a function to move all 0's to the end of it while
maintaining the relative order of the non-zero elements.
This is a classic problem of iterating over an array with two pointers, a standard one and a fast one.
Algorithm:
1. Create a pointer called last_good that starts at zero 2. Iterate i from 0 to end 3. if Nums[i] is not 0 4. swap it with last good, and increment last good
Regular Expression Matching
Given an input string (s) and a pattern (p), implement regular expression
matching with support for '.' and '*'.
This problem can be solved recursively without too much code, once you break into these 3 cases!
- Base Case: Pattern is empty
- Case 1: We don't have a star after next character in pattern
- Case 2: We have a star after the next character in pattern
We call isMatch(string s, string p) recursively, giving a new input and a
new pattern string, and we operate on the first character. This calls for using
the string::substr() function which is slow, but easy. We can also speed
this up by implementing start pointers.
Algorithm:
Code:
bool isMatch(string s, string p) { int p_len = p.length(), s_len = s.length(); // base case if(p_len == 0) { return s_len == 0; } // CASE 1 if(p_len == 1 || (p_len > 1 && p[1] != '*') ) { if(s_len == 0) return false; if(p[0] == '.' || p[0] == s[0]) return isMatch(s.substr(1), p.substr(1)); return false; } // CASE 2 second char is a * else { if( isMatch( s, p.substr(2) ) ) return true; int i = 0; while(i < s_len && (s[i] == p[0] || p[0] == '.')) { if(isMatch(s.substr(i+1), p.substr(2))) return true; i++; } return false; } }
This code can be optimized by creating an overloaded function that takes in a
start index for p and s.
Wildcard Matching
Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.
'?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence).
This is a DP problem but can be solved recursively. I solved it recursively but it still fails leetcode. But I am getting comfortable with breaking the cases down. These kinds of problems lend themselves well to flowcharts!
Algorithm:
bool helperMatch(string &s, int p_s, string &p, int p_p) { // EMPTY CASE if(p_p >= p.length()) { if(p_s >= s.length()){ return true; }else{ return false; } } // p[0] is a '?' or a character else if(p[p_p] == '?' || isalpha(p[p_p])){ // s is empty if(p_s >= s.length()){ return false; } // s not empty else{ // character match if(p[p_p] == '?' || p[p_p] == s[p_s]){ return helperMatch(s,p_s + 1, p, p_p + 1); } // characters don't match else{ return false; } } } // p[0] is a '*' int i = 0; while(i <= s.length()) { if( helperMatch( s, p_s + i, p, p_p + 1 ) ){ return true; }else{ i++; } } return false; } bool isMatch(string s, string p) { int i = 1; while(i < p.length()){ if(p[i-1]=='*' && p[i] == '*'){ p.erase(i,1); }else{ i++; } } return helperMatch(s, 0, p, 0); }
Trapping Rain Water
Ah what a classic! Couple of ways of doing this one. Also good to know the brute force.
Brute Force
For every height h, find the maximum left height, and the maximum right height.
The water at that h will be the minimum of the two minus h.
Dynamic Programming (NOT BAD)
The DP solution is really straight forward! You just do two passes, use the minimum from each pass and add it to a result. O(1) time by O(n) space.
Algorithm:
1. Create res, and max_h, set to 0 2. Create a vector of left max heights 3. Iterate h over heights from 0 to end 4. max_h = max of h and max_h 5. left max push in max_h - h, this is the max this height can support 6. Reset max_h to 0 7. Iterate h over heights from end to 0 8. max_h = max of h and max_h 9. res += min(left max at i, max_h - h) 10. return res
Code:
int trap(vector<int>& height) { int res = 0, max_h = 0; // iterate from left vector<int> left_max; for(int i = 0; i < height.size(); i++) { max_h = max(max_h, height[i]); left_max.push_back(max_h - height[i]); } // reset the maximum max_h = 0; for(int i = height.size() - 1; i >= 0; i--) { max_h = max(max_h, height[i]); res += min(left_max[i], max_h - height[i]); } return res; }
Two Pointer
This is the nifty 0(1) time and space solution. Start with two pointers at the end and track max left and max right. Move up the pointer of the smallest element. This solution works because you are moving the smaller of the sides, so you are always calculating the minimum water with you can trap for each element, which is what we need.
Algorithm:
1. Create a left pointer L = 0, right pointer R to size - 1 2. Create left max LM and right max LM and a res of 0 3. While L < R 4. IF H[L] is smaller than H[R] 5. Set LM to MAX(LM, H[L]) 6. RES += LM - H[L] 7. Increment L 8. Else 9. Set RM to MAX(RM, H[R]) 10. RES += RM - H[R] 11. Decrement R 12. Return Res
Code:
int trap(vector<int>& h) { // left pointer, right pointer, left max, right max, result int l = 0, r = h.size() - 1, lm = 0, rm = 0, res = 0; while(l < r) { // move up the pointer to the smaller element if(h[l] < h[r]) { lm = max(h[l], lm); res += lm - h[l++]; }else { rm = max(h[r], rm); res += rm - h[r--]; } } return res; }
Edit Distance (DP)
Given two words word1 and word2, find the minimum number of operations
required to convert word1 to word2.
You have the following 3 operations permitted on a word:
- Insert a character
- Delete a character
- Replace a character
I learned how to solve this using DP. It is really cool how the memo table maps to the problem. The 3 operations, insert, delete, and replace map amazingly well to it.
This is a great video on the problem.
Algorithm:
Code:
int minDistance(string word1, string word2) { int m = word1.length(), n = word2.length(); // return non zero length if a length is zero if(n*m == 0) return n+m; // init memo vector to all zero's vector<vector<int>> memo(m + 1, vector<int>(n + 1,0)); // init left and top rows for(int i = 0; i <= m; i++) memo[i][0] = i; for(int j = 0; j <= n; j++) memo[0][j] = j; for(int i = 1; i <= m; i++) { for(int j = 1; j <= n; j++) { if(word1[i-1] == word2[j-1]) { memo[i][j] = memo[i-1][j-1]; } else { memo[i][j] = min(min(memo[i][j-1], memo[i-1][j-1]), memo[i-1][j]) + 1; } } } // Return the last element return memo[m][n]; }
One Edit Distance
Given two strings s and t, return true if they are both one edit distance apart, otherwise return false.
I initially solved this problem using 3 hard-coded cases. This was not very elegant and I learned a trick how to get the data in function in a way that eliminates code.
The trick was to ensure that string 1 is always bigger than string 2. The way to do that was to call the function recursively with the flipped strings in the case that string 1 was smaller than string 2.
We also rely on the fact that that the substrings after the non matching character should be the same.
Algorithm:
1. Set bigger equal to string 1 length, and smaller equal to string 2 length 2. If bigger < smaller 3. return call functions with flipped strings 4. 5. if bigger == smaller we need to do a replace 6. iterate i over bigger 7. if s1[i] != s2[i] 8. return s1.substring(i+1) == s2.substring(i+1) 9. if we get here that means strings were equal to return false 10. if bigger - smaller = 1 11. iterate i over smaller 12. if s1[i] != s2[i] 13. return s1.substring(i+1) == s2.substring(i) 14. return true if we get here 15. return false if we get here, because it means strings are more than 1 away from each other
Code:
bool isOneEditDistance(string s, string t) { // we want bigger s, and smaller t int bigger = s.length(), smaller = t.length(); if(bigger < smaller) return isOneEditDistance(t, s); // replace or equal if(bigger == smaller) { for(int i = 0; i < bigger; i++) { if(s[i] != t[i]) return(s.substr(i+1) == t.substr(i+1)); } // if we get to here, no replacement was made and the strings are equal // so we return false return false; } // Delete one character from bigger s else if(bigger - smaller == 1) { for(int i = 0; i < smaller; i++) { if(s[i] != t[i]) return(s.substr(i+1) == t.substr(i)); } // if we get here it means the last character in the bigger string is what remains return true; } return false; }
Delete Operation for Two Strings (DP)
Given two words word1 and word2, find the minimum number of steps required to
make word1 and word2 the same, where in each step you can delete one character
in either string.
The cool thing about this problem is that when you solve it iteratively, the Dynamic problem version becomes really easy, and also a natural next step.
This problem breaks down into searching for the maximum common subsequence. This search breaks down in a recursive character by character scan that goes as follows:
- Base Case if
string1orstring2are empty, return 0 - Try checking the rest of the string without touching the first characters.
- Add 1 to this if equal.
- Delete a character from
string1and recurse - Delete a character from
string2and recurse - Return the maximum of those 3 results
I first solved this problem by starting from the beginning of the strings and recursively calling with trimmed substrings. This solves the problem with $O(2^{max(m+n)})$.
If you change the recursive function just a bit, it makes it a breeze to convert to DP using a memo matrix. All you have to do is start from the end, instead of passing substrings, pass two pointers.
Here is the algorithm:
1. FUNCTION: maxSub(string S1 and S2, pointers M and N, memo matrix) 2. if M or N are 0, return 0 3. if memo[M][N] is valid, return it 4. 5. int x = 1 if S1[M-1] is equal to S2[N-1] 6. int SAME = maxSub(S1, S2, M-1, N-1, memo) + x 7. int DEL_S1 = maxSub(S1, S2, M-1, N, memo) 8. int DEL_S2 = maxSub(S1, S2, M, N-1, memo) 9. 10. return the max of the 3 11. 12. FUNCTION isValid(S1, S2) 13. M = S1 length, N = S2 length 14. Make a memo vector that is M+1 and N+1, init all to -1 15. return ( M + N - 2* maxSub(S1, S2, M, N, memo)
Code:
// make our own fancy 3 way max function int max(int x, int y , int z) { return ::max(::max(x,y),z); } // return max equal sub string of s1 and s2 int maxSub(string& s1, string& s2, int m, int n, vector<vector<int>> &memo) { if(m * n == 0) return 0; // If it's in the memo, return it! if (memo[m][n] != -1) { return memo[m][n]; } int x = (s1[m - 1] == s2[n - 1]) ? 1 : 0; int same = maxSub(s1, s2, m - 1, n - 1,memo) + x; int del_s1 = maxSub(s1, s2, m - 1, n,memo); int del_s2 = maxSub(s1, s2, m, n - 1,memo); memo[m][n] = max(same, del_s1, del_s2); return memo[m][n]; } int minDistance(string word1, string word2) { int m = word1.length(), n = word2.length(); vector<vector<int>> memo(m+1, vector<int>(n+1, -1)); int max_sub = maxSub(word1, word2, m, n, memo); return(m + n - 2*max_sub); }
Maximum Length of Repeated Subarray (DP)
Given two integer arrays A and B, return the maximum length of an subarray
that appears in both arrays.
This is a very simple DP algorithm! The brute force way is $O(n^3)$ and fails at pretty small strings.
For brute force, iterate over every possible combination of indices for A
and B. For each possible index, if the characters are the same, run a while
loop and see how far you can go till both characters are not longer the same.
The DP algorithm is really simple. You create a 2D memo matrix that is 1 larger
on both axes. Then iterate over i and j and if the characters at
A[i-1] and B[j-1] are equal, set the element memo[i][j] to one
larger than the upper left diagonal.
Algorithm:
Code:
int findLength(vector<int>& A, vector<int>& B) { int m = A.size(), n = B.size(); vector<vector<int>> memo(m+1, vector<int>(n+1, 0)); int ans = 0; for(int i = 1; i <= m; i++) { for(int j = 1; j <= n; j++) { if(A[i-1] == B[j-1]) { memo[i][j] = memo[i - 1][j - 1] + 1; ans = max(memo[i][j], ans); } } } return ans; }
Missing and Duplicate
Find duplicate and missing number.
Input is an array of unsorted consecutive integers.
Has 1 duplicated number, and a missing number.
For example {5, 2, 3, 2, 1}, missing 4, duplicate 2.
I got this problem for a phone screen. I first solved in in O(N log(n)) by
sorting first, then with a hint I was able to solve it in O(N) using a set
and tracking max and min in a two pass. Dima told me to always watch out
for max and min when consecutive numbers are involved.
Algorithm O(N log n):
1. Sort input array 2. Iterate i start at index 1 over array 3. if(num[i] == num[i - 1] then it is a duplicate 4. else if(num[i] == num[i]-2 it is a missing element 5. 6. return duplicate and missing
Algorithm O(N):
1. create min set to INT_MAX and max set to INT_MIN 2. create unordered set 3. iterate n over input 4. if n in set 5. dupe = n 6. insert n in set 7. min = min ( min and n) 8. max = max ( max and n) 9. 10. iterate i from min to max 11. if i is not found in our set, we have our missing!
Linked List Cycle II
Given a linked list, return the node where the cycle begins. If there is no
cycle, return null.
To represent a cycle in the given linked list, we use an integer pos which
represents the position (0-indexed) in the linked list where tail connects to.
If pos is -1, then there is no cycle in the linked list.
Super super cool Floyd's algorithm for loop detection. The following algorithm does all the proper checks in case of null lists and also lists that are not cycles.
Algorithm:
1. Make pointer q and q both equal to head 2. 3. while q and p, and p->next 4. p advance twice 5. q advance once 6. if p == q, break 7. 8. When we get here we either have a loop or an NULL end. 9. if( !p OR !p->next) // the OR order is important, so we don't have runtime errors 10. We have the end, so no loop! return NULL 11. 12. We have loop, so we have to find where it starts 13. q = head 14. while p != q 15. p advance once 16. q advance once 17. 18. return q // or q, it doesn't matter :)
Code:
ListNode *detectCycle(ListNode *head) { ListNode *q = head, *p = head; while(q && p && p->next != NULL) { p = p->next; p = p->next; q = q->next; if(q == p) break; } if(!p || p->next == NULL) return NULL; q = head; while(p != q) { p = p->next; q = q->next; } return q; }
Find the Duplicate Number
Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
Crazy cool algorithm called Floyd's Algorithm!!
For this to work conceptually we have to treat it as a linked list. The cool thing is that because there is one duplicate, and they are consecutive numbers, they won't point out of bounds.
This is a two part problem, we first detect a cycle in the linked list, and then we detect where the cycle started which is the duplicate.
1. p = nums[0] and q = to num [0] 2. DETECT CYCLE 3. while true 4. move p twice 5. move q once 6. if p == q, break ( we have a cycle ) 7. 8. FIGURE OUT WHERE CYCLE IS BASED ON FLOYD'S ALGO 9. q = nums[0] 10. while(p != q) 11. move p once 12. move q once 13. 14. return q :)
int findDuplicate(vector<int>& nums) { int p = nums[0], q = nums[0]; while(true) { p = nums[p]; p = nums[p]; q = nums[q]; if( p == q) break; } q = nums[0]; while(p != q) { p = nums[p]; q = nums[q]; } return p; }
Unique Paths (Easy DP)
Find the unique paths a robot can take to get to an end of an array. He can only move one down or one right.
We solve this problem by creating a 2d vector of the path space. We then add up the possible ways we can enter a square, but adding the possible ways its top square has, and its left square has. The top row and left column start with 1, but theres only one way to enter those.
Algorithm:
1. create memo array 2. set memo[0][:] to 1 3. set memo[:][0] to 1 4. 5. for i 1 to m 6. for j 1 to m 7. memo[i][j] = memo[i-1][j] + memo[i][j-1] 8. 9. return memo[size - 1][memo[0]size-1]
Code:
int uniquePaths(int m, int n) { // vector of all 1's vector<vector<int>> memo(m,vector<int>(n,1)); for(int i = 1; i < m; i++) for(int j = 1; j < n; j++) memo[i][j] = memo[i-1][j] + memo[i][j-1]; return memo[m-1][n-1]; }
Basic Calculator II
I solved this problem in a pretty complicated, but fun way! The bulk of the work is processing the string, which is a pain in C++. Learn the ways of string manipulation! While avoiding having to learn how to use stringstreams of course :).
[1] very long complicated solution showclass Solution { public: enum NodeType { NUM, MULTIPLY, DIVIDE, ADD, SUBTRACT}; typedef list< pair<NodeType, int> > MyList; MyList exp; list< MyList::iterator > listAS; list< MyList::iterator > listMD; void process(string& s) { // get rid of spaces int i = 0; while(i < s.length()) { if (s[i] == ' ') s.erase(i,1); else i++; } s += ' '; int p = 1, start = 0; while(p < s.length()) { if(!isdigit(s[p])) { string snum = s.substr(start, p - start); exp.push_back( make_pair(NUM, stoi(snum)) ); switch(s[p]){ case '/': exp.push_back( make_pair(DIVIDE,0) ); listMD.push_back( prev(exp.end()) ); break; case '*': exp.push_back( make_pair(MULTIPLY,0) ); listMD.push_back( prev(exp.end()) ); break; case '+': exp.push_back( make_pair(ADD,0) ); listAS.push_back( prev(exp.end()) ); break; case '-': exp.push_back( make_pair(SUBTRACT,0) ); listAS.push_back( prev(exp.end()) ); break; } start = p + 1; } p++; } return; } int calculate(string s) { process(s); for(auto& it : listMD) { if(it→first == DIVIDE) prev(it)→second = prev(it)→second / next(it)→second; else if(it→first == MULTIPLY) prev(it)→second = prev(it)→second * next(it)→second; exp.erase(next(it)); exp.erase(it); } for(auto& it : listAS) { if(it→first == ADD) prev(it)→second = prev(it)→second + next(it)→second; else if(it→first == SUBTRACT) prev(it)→second = prev(it)→second - next(it)→second; exp.erase(next(it)); exp.erase(it); } return exp.front().second; } };
Here is a much more concise solution I found online:
int calculate(string s) { stack<int> myStack; char sign = '+'; int res = 0, tmp = 0; for (unsigned int i = 0; i < s.size(); i++) { if (isdigit(s[i])) tmp = 10*tmp + s[i]-'0'; if (!isdigit(s[i]) && !isspace(s[i]) || i == s.size()-1) { if (sign == '-') myStack.push(-tmp); else if (sign == '+') myStack.push(tmp); else { int num; if (sign == '*' ) num = myStack.top()*tmp; else num = myStack.top()/tmp; myStack.pop(); myStack.push(num); } sign = s[i]; tmp = 0; } } while (!myStack.empty()) { res += myStack.top(); myStack.pop(); } return res; }
Interval List Intersections
I was given this problem at a interview and boy I did not get through. I then went back to code it a month later after more studying, and I still flubbed it!!!
Group Shifted Strings
What a great problem!!! The trick here is to realize that if two people are running on a circle, no one is really ahead of anyone at any given time. You can add a positive number to either and get to the same spot as the other one.
This thinking helps framing on how to deal with wrapping. In this problem, we need to create keys for each string that define their letters relative position. It is up to you to pick what is greater than what, just keep it simple. You got this man, it makes sense!
Algorithm:
1. FUNCTION: CALC DISTANCE BETWEEN CHARACTER A AND CHARACTER B -> return a char 2. Int d = A - B 3. if D is negative, then D += 'z' - 'a' + 1 4. Reutrn D :) 5. FUNCTION GROUP SHIFTED -> RETURN vector of vector of strings 6. create an OUTPUT vector of vector of strings 7. Create a map of string, int : key is the "relationship between letters" and 8. value is the OUTPUT index for this group of strings that has the same key 9. Iterate s over input strings 10. Create a temp key (string) 11. Iterate i over s, starting at position 1. 12. temp key += DISTANCE(s[i-1], s[i]) 13. IF key is found in map: 14. add s to the right spot in OUTPUT 15. else 16. add s to a NEW spot in output and add this index to the MAP 17. RETURN OUTPUT
Code:
// how much we have to add to a to get to b char dist(char a, char b) { int d = b - a; return (d < 0) ? d += ('z' - 'a' + 1) : d; } vector<vector<string>> groupStrings(vector<string>& strings) { vector<vector<string>> out; unordered_map<string, int> shift_map; for(auto& s : strings) { // build our key for this string string key; for(int i = 1; i < s.length(); i++ ) { key += dist(s[i-1], s[i]); } if(shift_map.find(key) == shift_map.end()) { // not in the map, create new entry out.push_back({s}); shift_map[key] = out.size() - 1; } else { out[shift_map[key]].push_back(s); } } return out; }
Passing Yearbooks
We are giving an array that represents the path a yearbook will take to get signed. The index of each element represents the student. We optimize by keeping track of what students are part of a circuit of signatures. Those student's path do not then need to be calculated.
Course Schedule
I spent all day on this :) and learned a lot! This problem requires you to understand that this a graph cycle detection problem. Once you realize that, you can solve the problem.
There is another way of solving this problem with an “in degree” array where you track count of dependencies. Video about it here.
Cycle detection and optimization
The input is directed graph that is not guaranteed to be strongly connected. An approach is to a DFS on the starting vertex of every edge. Then walk through that path and mark it seen. If you end up a previously seen node, you have a cycle, so there's no way you can take the classes!
Keep in note that you have remove a leaf nodes from the seen list once we finish on it.
We also keep a “good” list of vertices we have visited and fully explored. That way we don't have to explore them again! This is an optimization that changes our complexity from $O(V²+E²)$ to $O(V+E)$.
Algorithm:
1. OPTIMIZATION: Build unordered set of explored vertices called GOOD 2. Build adjacency list Adj (unoredered map of vector<int>) 3. Iterate over edges, adj[left vertex].push_back(right vertex) 4. 5. Iterate v over Adj list 6. OPT: If v is in good, CONTINUE, no need to check 7. create seen set of ints 8. If cycleDFS of v vertex returns TRUE, we have a cycle 9. return false 10. 11. // Return true if there is a cycle, false otherwise 12. FUNCTION cycleDFS( take in Adj, seen, and vertex v) 13. OPT: If v is in good, return false, no need to check 14. check if v in seen 15. If true, return true, there is a cycle 16. iterate over n Neighbors of vertex v 17. OPT: If n is in good, continue 18. If cycleDFS of n is true 19. return true 20. // if we are here there are no cycles 21. Remove v from seen, so we can backtrack without false positives 22. return false
class Solution { public: // This marks nodes that are already explored as good unordered_set<int> good; bool cycleDFS(unordered_map<int, vector<int>>& adj, int v, unordered_set<int>& seen) { if(good.find(v) != good.end()) return false; // If we found this node before, we have a cycle if(seen.find(v) != seen.end()) return true; seen.insert(v); // Iterate over neighbors for(auto& n : adj[v]) { if(good.find(n) != good.end()) continue; if( cycleDFS(adj, n, seen) ) return true; } // we have come to the end of this exploration. seen.erase(v); good.insert(v); return false; } bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { // Build the adjacency list unordered_map<int, vector<int>> adj; for(auto& e : prerequisites) { adj[e[0]].push_back(e[1]); } // Iterate over the adjancey list, and run cycleDFS on each node for(auto& v : adj) { // This is our optimization. If we enouter a vertex we have already // marked as good, we don't a DFS on it if(good.find(v.first) != good.end()) continue; // we start an empty seen set for every exploration // if we didn't we would encounter nodes from other explorations unordered_set<int> seen {}; if(cycleDFS(adj, v.first, seen)) { return false; } } return true; } };
Course Schedule II
This problem is an extension of Course Schedule. We use a topological sort algorithm to solve this problem. The only difference between this and the Course Schedule one problem is that we maintain a list of taken classes, which we use an output. We also iterate over all the classes n.
Algorithm:
class Solution { public: // we need to keep a set to allow O(1) lookups of elements present, // but we still need to keep an order which will be output vector<int> taken_list; unordered_set<int> taken; bool DFS(unordered_map< int, vector<int> >& adj, unordered_set<int> &seen, int v) { if(taken.find(v) != taken.end()) return true; if(seen.find(v) != seen.end()) return false; // only run neighbor check on vertices that have adj list if(adj.count(v) > 0) { // insert v into seen to mark that we saw it on this path seen.insert(v); // iterate over v's neighbors for(auto& n : adj[v]) { // if we taken this class we don't need dfs if(taken.find(n) != taken.end()) continue; if( DFS(adj, seen, n) == false) return false; } seen.erase(v); } // add the class to the taken list taken.insert(v); taken_list.push_back(v); return true; } vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) { taken_list.reserve(numCourses); // build adj list unordered_map< int, vector<int> > adj; for(auto& e : prerequisites){ adj[e[0]].push_back(e[1]); } for(int v = 0; v < numCourses; v++) { // if we already took the class, then we don't have to explore it if(taken.find(v) != taken.end()) continue; unordered_set <int> seen; if( DFS(adj, seen, v) == false) return {}; } return taken_list; } };
Course Schedule III
There are n different online courses numbered from 1 to n. Each
course has some duration (course length) t and deadling d day. A course
should be taken continuously for t days and must be finished before or on
the dth day. You will start at the 1st day.
Given n online courses represented by pairs (t,d), your task is to find the
maximal number of courses that can be taken.
The technique here is a two stage process. First we sort by end dates. That lets us start trying to fit courses. We keep track of time and start at 0.
Then we try the next course. If you can take it, great, take it! If you can't take it, we try something special.
What we do is see if we can replace it with a course that we already took, that is longer. If we can do that, then great, take that one instead AND shift back our time by the time that we saved. SO the only thing we end up needing is a multiset of durations of courses we've taken. Then at the end we just return the size of the set!
Algrithm:
1. make a multiset of numbers 2. sort by end date 3. start a last_end int to 0 4. iterate i from 0 to end of courses 5. if we can take the class : if last_end + courses[i][0] <= courses[i][1] 6. take it: last_end += courses[i][0], set insert courses[i][0] 7. if we CAN't take the class 8. is the largest element in the taken set longer or EQUAL to this course we can't take? 9. delete the largest elemetn in the set, and insert this new one. 10. last_end doesnt' stay the same! It gets shifted back by our time saved 11. return size of set
Code:
int scheduleCourse(vector<vector<int>>& courses) { // set of durations of classes that we have taken multiset<int, greater<int>> taken; // sort our courses by end date sort(courses.begin(), courses.end(), [](vector<int>&a, vector<int>&b){return a[1]<b[1];}); int last_end = 0; for(int i = 0; i < courses.size(); i++) { // can you this course? is the end time smaller equal to deadline if(courses[i][0] + last_end <= courses[i][1]) { last_end += courses[i][0]; taken.insert(courses[i][0]); } else { // lets try to swap this course the biggest possible taken one int old_len = *taken.begin(); if(old_len >= courses[i][0]) { // swap the courses taken.erase(taken.begin()); taken.insert(courses[i][0]); // we also have to shift over our time savings! last_end -= old_len - courses[i][0]; } } } return taken.size(); }
Minimum Number of Arrows to Burst Balloons
There are a number of balloons whose width is defined by the position in 1D space as start and end pairs. Some of theses balloons may overlap. Calculated the mininum number of arrows required to pop all balloons.
This is an iteresting problem that is smiliar to the meeting room problem. You sort by end position and greedily check if the next balloon overlaps. If it does, great, we already have an arrow to pop it. If it doesn't overlap, then we need a new arrow for it.
Algorithm:
FUNCTION findMinArrows( 2d array of baloon bounds)
sort INPUT array by end locations
ANS = 0, LAST_END = LONG_MIN
Iterate i from 0 to INPUT size
if start of INPUT[i] is greater than LAST_END
// need a new arrow!
ANS++
LAST_END = end of INPUT[i]
return ANS
Code:
int findMinArrowShots(vector<vector<int>>& points) { // Sort by end first sort(points.begin(), points.end(),[](vector<int>&a, vector<int>&b){return a[1]<b[1];}); // Initialize last end to smaller number than possible with int long last_end = LONG_MIN, ans = 0; for(int i = 0; i < points.size(); i++) { // If the current point ends after the previous, we need a new arrow if(points[i][0] > last_end) { ans++; // Update last end last_end = points[i][1]; } } return ans; }
Maximum Number of Meetings In A Room
There is one meeting room in a firm. There are N meetings in the form of start times and end times. The task is to find the maximum number of meetings that can be accommodated in the meeting room. Print all meeting numbers.
I first solved this recursively by sorting with start times, and then recursively trying the maximum of every possible path. You get the right answer but with a $O(2^n)$ time. Amazingly if you sort by end times, and iterate over the meetings and pick the one that fits, you will come to the right answer. This is called a greedy appraoch.
Algorithm:
1. sort by end times 2. set last end to a negative number 3. iterate i over meetings 4. if start time of i is greater or equal to last end, 5. ans++, last meeting = this one 6. print out the meeting 7. return ans
Code:
int greedyMeeting(vector<vector<int>> &m)
{
sort(m.begin(), m.end(),[](vector<int>&a, vector<int>&b){ return a[1]<b[1];});
int last_end = -1, ans = 0;
for(int i = 0; i < (int)m.size(); i++)
{
if(m[i][0] >= last_end)
{
// take the meeting
last_end = m[i][1];
ans++;
cout << "Taking meeting number: " << ans << " - "
<< m[i][0] << ":" << m[i][1] << endl;
}
}
return ans;
}
Meeting Rooms II
Given an array of meeting time intervals consisting of start and end times
\[\[s1,e1],[s2,e2],…] (si < ei), find the minimum number of conference rooms
required.
Fantastic question! My first approach was to do the brute force. You check every interval and see if it conflicts with each other. My first issue was figuring out how to check for overlap. I had nested if statements and it was not concise.
To do this, you simply check if the maximum start is greater or equal to the minumum end, If that's true then there is no overlap.
The next approach was to sort by starting inveral. You do this in C++ by creating a compare function like so:
bool compare(const vector<int>& a, const vector<int>&b) { // a will go before b if this is true: return ( a[0] < b[0] ); } sort(my_vector.begin(), my_vector.end(), compare);
After sorting the intervals by start time, I then created a list of rooms, (which just contained indices of intervals). I then processed each interval in order. For every interval I check through my room's list. If I find a room with no overlap, I insert the index of that interval and return. If i dont find a room, I create a new room and put the interval index in there.
There is a lot of wasted processing here.
First, we don't even need to a full list of intervals in a room, we can just keep track of the last meeting because they are in order.
Second, we are iterating through each room every time to find a fit. What we should be doing is using a set, and more importantly in C++ a multiset of rooms. That way we always just check the room with the earliest end time.
Third, all we need to store are end times! We then compare a start time with the earliest end time and we're good! Very elegant solution to this.
bool compare(const vector<int> &a, const vector<int> &b) { // element a[0] should come before b[0] if it is smaller return a[0] < b[0]; } class Solution{ public: void process(multiset<int> &rooms, vector<int>& interval) { // check to see if earliest ending meeting is <= to our start if(*rooms.begin() <= interval[0]) { // erase our old meeting because we are gonna put in the new one :) rooms.erase(rooms.begin()); } // put in the new end time rooms.insert(interval[1]); } int minMeetingRooms(vector<vector<int>> &intervals) { if(intervals.size() == 0) return 0; // sort our intervals by start time, earliest first sort(intervals.begin(), intervals.end(), compare); // make a multiset of rooms so we can store end times of the last meeting // there may be end times that end at the same time, so we need to allow for // dupes multiset<int> rooms = { intervals[0][1] }; for(int i = 1; i < intervals.size(); i++) { process(rooms, intervals[i]); } return rooms.size(); } };
Jump Game
Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index.
This is a deceivingly medium kind of problem. You would think that it would be very easy, but nopppeeeee. It is actually a dynamic problem that can be solved with just a few lined of code in a greedy way.
The idea is to iterate i from 0 to either the end of the array or the until we reach a maximum reach that we can.
FUNC: isPossible(array INPUT)
MAX_REACH = 0, i = 0;
Increment i from 0 to either INPUT size or MAX_REACH
MAX_REACH = max ( MAX_REACH, INPUT[i]+i )
return true if i got to the end of the array
First Missing Positive
This a problem that requires us to use constant extra memory, forcing us to use the input array itself to encode more data on it without losing the element information. Information about key assumptions must be had.
The minimum positive element is going to be anywhere between 1 and n+1. Here is why.
If we have the perfectly ordered array with n = 5: [1 2 3 4 5]
The next positive element is 6 (n+1).
The smaller possible positive element is going to be 1. This means our range spans the same number of elements as we have in the input. Which means if there was a way to overlay this boolean state of whether or not we have seen this number in the array, we can solve this problem with no further memory required.
We do this in three steps:
First pass: Search for a 1, and if we find any numbers out of possible solutions (negative or greater than n), we reset them to 1.
Second pass: Map the value of each element to its index and then set that value to negative if present in the array. Hard problems would not be hard if they were easy to explain.
Thirst pass: Look for the first non present negative number. If not found, handle the edge case and return n+1.
YOU GO THIS!
Unique permutations with unique result
https://www.youtube.com/watch?v=9lQnt4p7_nE
- Sort input candidates.
- Make a boolean flag array to track used elements.
- Recurse over the candidates, choosing and building a solution, and then unchoosing.
- If the next option is the same, skip it.
Power Function
Implement your own power function. The following is the naive algorithm and takes too much time:
class Solution { public: double myPow(double x, int n) { double ans = 1; if(n == 0) return 1; for(int i = 1; i <= abs(n); i++) { ans = x * ans; } if(n < 0) ans = 1/ans; return ans; } };
class Solution { public: double fastPow(double x, long long n) { if ( n == 0) return 1.0; double half = fastPow(x, n / 2); if( n % 2 == 0) { return half * half; } else { return half * half * x; } } double myPow(double x, int n) { long long N = n; if(N < 0) { x = 1/x; N = -N; } return fastPow(x, N); } };
Remove Dupes from sorted array
Did a vector erase first but that wasn't ideal. I then learned how to do it with a two pointer approach. First pointer is a “last valid” location and second pointer sweeps through array. As it sweeps and find good ones, it swaps them with the valid. Valid then becomes my new array size.
Search in a Rotated Array II.
Really interesting one cause theres dupes and rotations. Idea is to split the array and based on its bounds, you have 3 possible situations:
- You have a normal sorted list cause left bound smaller than right bound. Do a normal bin search
- Left bound is == to right bound, do a linear search
- You have a pivot somewhere. You check to see if the left array is sorted right. If it is, check to see if your target is in it. If it is, search in it.
- If it isn't in it, it's gotta be on the other side! Remove duplicates from a sorted list
Partition List
Make sure elements greater. Had a hard time with this one because I picked a bad approach from the start. I was moving elements to the back of the list if they met a certain condition. Problem was that I entered an infinite loop because I would get to the nodes I pushed back and keep pushing them back. I came up with a better one pass solution after I redid it.
Maximum Subarray
Maximum Subarray Greedy / Kadane's Algorithm
This problem can be solved amazingly easily in a one pass greedy approach. You keep track of a local maximum that can reset, and a global maximum.
int maxSubArray(vector<int>& nums) { int cur_max = nums[0], max_out = nums[0]; for(int i = 1; i < nums.size(); i++) { cur_max = max(nums[i], cur_max + nums[i]); max_out = max(cur_max, max_out); } return max_out; }
This is a tricky algorithm to understand. It touches on dynamic programming. Here's a good write up on it.
Maximum Subarray Divide and Conquer
The maximum subarray problem can be solved using divide and conquer.
By breaking up the input array into two subarrays of $n/2$ length as follows:
- A[low..mid]
- A[mid+1..high]
The maximum subarray A[i..j] can only be located in one of 3 places; in the first one, crossing the middle, or the end. To solve this equation we must find the maximum subarray in each of those 3 places and simply pick the biggest one.
Theres lots of little details in the maxCross function. Especially with dealing with finding the maximum of the subarrays when you have negative numbers. Where you start on the mid line counts. You had to go mid to left and mid+1 to the right. If you go mid-1 to the left you're screwed.
Find-Max-Crossing-Subarray Algorithm
int maxCross(vector<int>&nums, int& l, int &mid, int& r) { // We don't have to do bounds checks because we know l won't equal r, // because that's check for in the caller function. // With that knowledge we can set max_l and max_r both to INT_MIN's cause // I know there is going to be at least one element in each. You can also // set to nums[mid] and nums[mid+1] int max_l = INT_MIN, max_r = INT_MIN; // find max left int sum = 0; for(int left = mid; left >= l; left-- ) { sum += nums[left]; max_l = max(sum, max_l); } // find max right sum = 0; for(int right = mid+1; right <= r; right++ ) { sum += nums[right]; max_r = max(sum, max_r); } // return the added sum. return max_l + max_r; } int maxSub(vector<int>& nums, int l, int r) { if(l == r) return nums[l]; int mid = (l+r) / 2; int max_left = maxSub(nums, l, mid); int max_right = maxSub(nums, mid + 1, r); int max_cross = maxCross(nums, l, mid, r); return max(max_left, max(max_right, max_cross) ); } int maxSubArray(vector<int>& nums) { if(nums.size() == 0) return NULL; return maxSub(nums, 0, nums.size()-1); }
This problem can also be solved very easily with a greedy version. Maximum Subarray Greedy
Best Time to Buy and Sell Stock
There are variations to the Kadane's algorithm. Here is a buy and sell stock. The idea is to keep track of the minimum price, and then check the current minimum against the current price. You then check that potential profit against a running max_profit variable.
int maxProfit(vector<int>& prices) { int max_profit = 0, min_price = INT_MAX; for(int i = 0; i < prices.size(); i++) { min_price = min(prices[i], min_price); max_profit = max(max_profit, prices[i] - min_price); } return max_profit; }
Maximum Product Subarray
Very interesting problem, that requires a clever extension of Kadane. The trick here is that negative numbers can flip a minimum to a maximum.
You keep track of a min_so_far, which is min of current number, current number
times min so for, and current number times max so far.
And you keep track of a max_so_far which is the max of current number,
current number times max_so_far and current number times min_so_far. Then you
keep track of a result max, which you max against max_so_far.
Amazingly you get to test every possible subarray in one pass. Really awesome!
int maxProduct(vector<int>& nums) { int min_so_far = nums[0], max_so_far = nums[0], result = nums[0]; for(int i = 1; i < nums.size(); i++) { int cur = nums[i]; int temp_max = max(nums[i], max( nums[i] * min_so_far, nums[i] * max_so_far)); min_so_far = min(nums[i], min( nums[i] * min_so_far, nums[i] * max_so_far)); max_so_far = temp_max; result = max(max_so_far, result); } return result; }
Product of Array Except Self
Very cool little problem that you solve by creating “product list” which is
similar to a prefix sum. You do a pass from the left and create this product
list, and then come in from the left one element at a time. You rely on the fact
that out[i] = prod * a[i - 1]. prod is the running product from the left.
vector<int> productExceptSelf(vector<int>& nums) { vector<int> out(nums.size(), 0); int left_prod = 1; for(int i = 0; i < nums.size() - 1; i++) { left_prod *= nums[i]; out[i] = left_prod; } int right_prod = 1; for(int i = nums.size() - 1; i > 0; i--) { out[i] = right_prod * out[i - 1]; right_prod *= nums[i]; } out[0] = right_prod; return out; }
Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Find the longest substring without repeating characters. Cute use of an unordered_set to keep track of seen characters while implement two pointers for a sliding window. The sliding window is your valid substring. You have a left and right pointer. Advance the right pointer and if the character is not in the set, great, ans = max(right - left, ans). If the character is found in the set, remove the character at the left pointer, advancing the left and try again. Point is you keep advancing the left pointer till you're good to advance the right. Worst case, the left pointer will go all the way to the right and you start with an empty set. Cool!
int lengthOfLongestSubstring(string s) { unordered_set<char> seen; int i = 0, j = 0, n = s.length(), ans = 0; while(i < n && j < n) { if( seen.find(s[j]) == seen.end() ) { seen.insert(s[j++]); ans = max(ans, j - i); } else { seen.erase(s[i++]); } } return ans; }
Find All Anagrams in a String
Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.
Nice and mellow problem! Make a key from the pattern of the characters and counts, keep a sliding window on the string with with characters and counts and compare to the key. If it's a match, add the index to the output.
I learned that you can just use the == operator on 2d vectors and unordered
maps.
1. Create key of characters and counts 2. Create a window key of empty characters and counts, and output list 3. Iterate i from 0 to end of input string s 4. add character at i to window key 5. if i - p.length() is >= to zero, remove character from window key 6. compare window and key, if match add i - p length + 1 to output 7. Return output
Vector based code;
vector<int> findAnagrams(string s, string p) { vector<vector<int>> key = vector(26,vector<int>(1,0)); vector<vector<int>> window = vector(26,vector<int>(1,0)); // build our key for(auto& c : p) key[c-'a'][0]++; vector<int> out; for(int i = 0; i < s.length(); i++) { window[s[i]-'a'][0]++; int last_valid = i - p.length(); if(last_valid >= 0) window[s[last_valid]-'a'][0]--; if(check()) out.push_back(last_valid + 1); } return out; }
Map based code:
vector<int> findAnagrams(string s, string p) { unordered_map<char, int> key, window; // build our key for(auto& c : p) key[c]++; vector<int> out; for(int i = 0; i < s.length(); i++) { window[s[i]]++; int last_valid = i - p.length(); if(last_valid >= 0) { window[s[last_valid]]--; if(window[s[last_valid]] == 0) window.erase(s[last_valid]); } if(key == window) out.push_back(last_valid + 1); } return out; }
Palindrome Partitioning
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
The trickiest part of this problem is implementing a way of partitioning the
string in a sliding window fashion. The easiest way to do this is to create new
substrings A and B but this takes time and memory that unnecessary
because our input string and two pointers, start and end is all we need to
define any substring in S.
Algorithm:
1. FUNCTION isPalindrome ( string s, left pointer, right pointer) 2. while left pointer is less than right pointer 3. if character under left pointer is not the same as right pointer character 4. return false 5. return true 6. 7. FUNCTION explore(string S, int START, 8. array of string CUR, array of array of strings OUT) 9. if START is equal to string length 10. push in CUR to OUT, and return 11. Iterate from I = START to S.length() 12. if the string from START to I is NOT a palindrome, continue 13. create a substring that goes from START to I and push it into CUR 14. explore S, i + 1, CUR, OUT 15. pop the last element of CUR 16. 17. Call explore with START of 0
Code:
// return true if string is palindrome, false otherwise bool isPalin(string& in, int start, int end) { int l = start, r = end; while(l < r) { if(in[l++] != in[r--]) return false; } return true; } // partition string into all possible partitions void part(string& s, int start, vector<string> &cur, vector<vector<string>> &out) { if(s.length() == start) { out.push_back(cur); return; } // partitioning for(int i = start; i < s.length() ; i++) { if(!isPalin(s, start, i)) continue; cur.push_back(s.substr(start, i - start + 1)); part(s,i + 1, cur, out); cur.pop_back(); } return; } vector<vector<string>> partition(string s) { vector<vector<string>> out; vector<string> cur; part(s,0, cur, out); return out; }
Longest Palindromic String
Tricky son-of-a-gun. Easiest way is to brute force, and check if every possible substring is a palindrome.
Next best thing is O(n²) solution by doing a two pass. First pass you check every character and go middle out, next pass find any double characters and then middle out them.
Palindrome Pairs
Easiest is to brute force. It would be n²*k where k is the length of the
string.
You solve this by created a hashtable of the words in the array. Then you have these cases to deal with:
- Finding a word which is the exact reverse of the word you have
- Finding a shorter word that would be prepended to the word you have
- Finding a shorter word that would be appended to the word you have and make it a palindrome
The way to deal with prepend and append, is to take the word that you have, pop off a character and save that to a new word. If the new word is a palindrome, and you can find the reversed version of the original word without the popped off bits, you good bro.
Append Example:
// Matching the following: word1 = petonot word2 = ep word3 = tonote revered_word1 = tonotep You keep pooping off and looking and if what you popped off by itself is a palindrome, and you foudn the reverse of whats left, you're good | Reversed | Poppedoff | Popped off | Found Match? | Reversed | Reversed | | | | Palindrome? | Popped off? | Palindrome? | Match? | |----------+-----------+-------------+--------------+-------------+----------| | tonotep | | Yes | No | No | No | | onotep | t | Yes | No | No | No | | notep | to | No | No | No | No | | otep | ton | No | No | No | No | | tep | tono | No | No | No | No | | ep | tonot | Yes | Yes | No | Yes | | p | tonote | No | No | Yes | Yes |
The hashtable gives the 0(1) lookup speed, and avoids the linear search.
Generate Parenthesis
This is a backtracking algorithm where you either close or open a parenthesis.
Task Scheduler
I tried solving this problem by implementing a task scheduler that prioritized tasks that had no cooldown and also the largest task count.
The information that I actually did come across, but didn't use it well enough, is that the answer, which is the least time units it takes to do all tasks is bounded by the most frequent task.
So for a task list of 3 A's, 2 B's , 1 C the answer becomes:
A B C COOLDOWN A B COOLDOWN A
Which becomes:
(count of most frequent task - 1) * max(COOLDOWN, count_of_tasks - 1) + count of most frequent task
Populating Next Right Pointers in Each Node
Took me a little bit of time to get my head around how to do it, but it was not
bad at the end! You pass in a right node to each explore iteration. The
left child gets passed in the right child and then right child gets
passed in NULL or right child→child. Thats it!
Algorithm:
Code:
void explore(Node* node, Node* pr) { if(node == NULL) return; node->next = pr; //if we have children: if(node->left && node->right) { // left child explore(node->left, node->right); // right child: if(pr == NULL) explore(node->right, NULL); else explore(node->right, pr->left); } return; } Node* connect(Node* root) { explore(root, NULL); return root; }
Flatten Binary Tree to Linked List
This one was took a bit of time to wrap my head around it. I originally starting trying to check for a node with no grand-children. Remember, if you are checking for grandchildren in a recursive tree traversal, you are doing something wrong!
The trick here is that you need to break down the problem to a simple bottom base node, and work out the 4 different conditions:
- No children
Leftpresent,RightnullLeftnull,RightpresentLeftandRightpresent
The second important thing is to realise you need to return a tail, which will be the lowest right node of this newly shuffled subtree. When a node is null, it should return null, and when it has no children, it should return itself. Those are two base case returns.
We then have to deal with the return of the node that received either of those two returns from left and right children.
Algorithm:
Code:
TreeNode* flatten_child(TreeNode* node) { if( node == NULL ) return NULL; // no children to move, this is the right tail if( node->left == NULL && node->right == NULL ) return node; TreeNode* left_tail = flatten_child(node->left ); TreeNode* right_tail = flatten_child(node->right); if(node->left != NULL) { left_tail->right = node->right; node->right = node->left; node->left = NULL; } // return the right most real tail if(right_tail == NULL) return left_tail; return right_tail; }
Binary Search Tree Iterator
Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST. Calling next() will return the next smallest number in the BST.
Struggling hard with this one. First I tried a simple stack, that I would build on initializing that would go down to the current smallest element. This breaks down when having to explore right children of a parent node.
Then I thought about two stacks, but that's ridiculous and does not solve the problem.
Then I tried to think of some kind of process engine, that would change logic based on the step. This was not good.
Then I figured out a way with a stack that tracked a “seen” variable for each node! Which was unnecessary! I was hung up on what to do when encountering the parent node again.
class BSTIterator { public: enum Status{ UNSEEN, SEEN}; stack< pair<TreeNode*, Status> > stack; // look for minimum. void buildMin(TreeNode* node) { if(node == NULL) return; stack.push( make_pair(node, UNSEEN) ); if(node->left) { buildMin(node->left); } return; } BSTIterator(TreeNode* root) { buildMin(root); } /** @return the next smallest number */ int next() { // we have not seen this node if(stack.top().second == UNSEEN) { stack.top().second = SEEN; int out = stack.top().first->val; buildMin( stack.top().first->right ); return out; } // node is seen stack.pop(); return next(); } /** @return whether we have a next smallest number */ bool hasNext() { while(stack.size() > 0 && stack.top().second == SEEN) { stack.pop(); } return (stack.size() > 0) ? true: false; } };
Algorithm:
1. FUNC: BUILD MIN ( Take in a node ) 2. if node NULL return 3. Add node to stack 4. if node has left child-> BUILDMIN(LEFT CHILD) 5. 6. FUNC: NEXT() 7. Node OUT = stack top 8. pop stack top 9. BUILD MIN( OUT->right child) 10. return OUT's val 11. 12. FUNC: HAS NEXT() 13. return true if size of stack greater then 0, false otherwise
Code:
class BSTIterator { public: stack<TreeNode*> stack; // look for minimum. void buildMin(TreeNode* node) { if(node == NULL) return; stack.push(node); if(node->left) { buildMin(node->left); } } BSTIterator(TreeNode* root) { buildMin(root); } /** @return the next smallest number */ int next() { TreeNode* out = stack.top(); stack.pop(); buildMin(out->right); return out->val; } /** @return whether we have a next smallest number */ bool hasNext() { return (stack.size() > 0) ? true: false; } };
Binary Tree Right Side View
Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
Do a level order traversal, and push the right most element in an output array
Algorithm:
1. create a queue 2. push first node into the the queue 3. while queue isn't empty 4. level size = queue size 5. take the back of the queue and add it output 6. for( i to level size) 7. cur = pop front of queue 8. if cur has children, put them in the back of the queue
Code:
vector<int> rightSideView(TreeNode* root) { // output result vector<int> out; if(root == NULL) return out; // level queue queue<TreeNode*> levelq; // push in first element, which is the root levelq.push(root); while(!levelq.empty()) { // add the right most element to the output; out.push_back( levelq.back()->val ); // we need to count how many elements are in this level, so we can get the right // most element int level_size = levelq.size(); // pop off all the elements from this level while(level_size-- > 0) { // set cur to be the front of the queue and pop it TreeNode* cur = levelq.front(); levelq.pop(); // if we have children, starting with the left, add them to the queue if(cur->left) levelq.push(cur->left); if(cur->right) levelq.push(cur->right); } } return out; }
DFS
We would explore the graph in a depth first way by keep track of levels. We could keep a map of results, so that if we end up at that level, we overwrite whatever is in that result map.
I used a map because I was worried that we would end up touching nodes we thought were at the right most and valid for that level. That's just not true, and silly on my part, because I had the firm assumption (and correct) that the left node was also the first most level at that level.
So all we have to do is start from the right and track levels!!! We can track levels in a really cutesy way too.
Algorithm:
Explore function that takes in node, level, ref to output array
if node is null return
if level equal out size
push in node val to out
if right child
explore right child, level + 1, output
if left child
explore left child, level + 1, output
return
Code:
void explore(TreeNode* node, int level, vector<int> &out) { if (node == NULL) return; // Right most node we ever touch at this level! if (level == out.size()) out.push_back(node->val); // Check the children if(node->right) explore(node->right, level + 1, out); if(node->left) explore(node->left, level + 1, out); return; } vector<int> rightSideView(TreeNode* root) { vector<int> out; explore(root, 0, out); return out; }
Lowest Common Ancestor
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
This was a fun problem and I solved it in a cutesy way with two lists to keep a trace of the lineage to target node.
Algorithm:
1. Create two traces lists one for p and for q 2. explore p and build a left trace list 3. explore q and build a right trace list 4. while the two front elements of the traces equal each other 5. set out to the front of one element 6. pop the first element of both traces off 7. 8. // FUNCTION 9. Explore starting from a node with a target and reference of the trace list 10. If node is null, return false 11. Push out node on the trace list 12. if node == target, that means we found it! 13. return true 14. Explore the left, and the right child. If either returns true 15. return true 16. We haven't found the target from this root, pop our element off the trace list 17. return false
Code:
bool explore(TreeNode* node, TreeNode* target, list<TreeNode*>& trace) { if(node == NULL) return false; // push ourselves on the trace trace.push_back(node); if(node == target) return true; if( explore(node->left, target, trace) || explore(node->right, target, trace) ) { return true; } // not found in either child, get rid of our entry from the trace trace.pop_back(); return false; } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { list<TreeNode*> p_trace, q_trace; explore(root, p, p_trace); explore(root, q, q_trace); // init out TreeNode* out; while(p_trace.front() == q_trace.front()) { out = p_trace.front(); p_trace.pop_front(); q_trace.pop_front(); } return out; }
Binary Tree Paths
Given a binary tree, return all root-to-leaf paths.
I fell in a little pitfall with this problem! We have to travel all the way down to the leaf, building a string as we go down, and then triggering an append to an output array when a node has no children.
Algorithm:
Explore with a node, a string and a reference to output array
If the node is null, JUST RETURN. (we can be in a node with only one child!)
if our string is NOT empty, add the "->"
add the number of our node to the string
If we don't have any children
add the string to the output array and RETURN
Explore the left child
Explore the right child
Code:
void explore(TreeNode* node, string path, vector<string> &out) { // A null node by itself is NOT a leaf! if(node == NULL) { return; } // Add the arrow if the string isn't empty if(path != "") path += "->"; // Add our number to the string path += to_string(node->val); // If the node doesn't have children, we have a leaf! if(node->left == NULL && node->right == NULL) { out.push_back(path); return; } // Explore the left and the right explore(node->left, path, out); explore(node->right, path, out); return; }
Diameter of Binary Tree
Had a little hiccup understanding the definition, cause I dove right in thinking the root node added up the path. READ THE QUESTION. UNDERSTAND IT.
Go down to the null, and return 0, then add 1 to that as you bubble up. At each node, check the max path on the left, max path on the right, Check if your max is bigger than the output.
Algorithm:
Explore node with out ref if node is null, return 0 left path is explore left node's max path right path is explore right node's max path out is max of left path and right path return max of left path + 1, right path + 1
Code:
int explore(TreeNode* node, int& out) { if(node == NULL) return 0; int lp = explore(node->left, out); int rp = explore(node->right, out); out = max(out, lp + rp); return max(lp + 1, rp + 1); } int diameterOfBinaryTree(TreeNode* root) { int out = 0; explore(root, out); return out; }
Path Sum with Binary Tree
You're given a binary tree and need to find the number of paths along the tree that add up to a number.
Dima helped me out with an algorithm that keeps an array of sums. At every node, you add the value of the node to every element in that array, and also push back the value of the node itself. At each node you also iterate through the array and check to see if any values add to up the sum that is requested.
int helper(TreeNode* node, int target, vector<int> sums) { if(node == NULL) return 0; int out = 0; // add current node value to all elemnts of sums // and also check if they are valid solutions for(auto& entry : sums) { entry += node->val; if(entry == target) out++; } // append this elements value to sums sums.push_back(node->val); // check if node itself is a possible solution on its own. if(node->val == target) out++; // return out and children solutions return out + helper(node->left, target, sums) + helper(node->right, target, sums); } int pathSum(TreeNode* root, int sum) { vector<int> sums; return helper(root, sum, sums); }
Prefix Sum
There is another way to solve this problem with a hashmap based prefix sum. I don't understand how this works. Here is the code:
Also funny, found some poor guy on the internt who also thinks this is magic.
class Solution { public: int count = 0; int k; unordered_map<int,int> h; void helper(TreeNode* node, int cur_sum) { if(node == NULL) return; cur_sum += node->val; if(cur_sum == k) count++; if(h.count(cur_sum - k) > 0) count += h[cur_sum - k]; h[cur_sum]++; helper(node->left, cur_sum); helper(node->right, cur_sum); h[cur_sum]--; } int pathSum(TreeNode* root, int sum) { k = sum; helper(root, 0); return count; } };
Contiguous Array with Binary Array
Find the longest contiguous subarray that contains equal number of zero's and ones.
I first tried using divide and conquer but that doesn't work. Divide and conquer breaks down the problem into 3 possible solution locations, left, right and crossing the middle. This appraoch fails this problem because the solution cannot be split up because the sub-solutions are not independant. You can have 8 one's on the left, which is an invalid solution.
So this is another pre-fix with hashmap problem. Man i really don't get these problems and don't think they'll be asked.
Symmetric Tree
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
This can be solved in two ways, recursively in a depth first manner, and iteratively in a breath first manner.
Recursive DFS
Take in two nodes, which should be reflections of each other. Initially these will be first children left and right.
If they are null and equal, return true, great. We don't recurse past this node because there are no children.
If only one is NULL, then return false. Tree is not symmetric.
Then check the following:
- Values of both first and second node are equal
- Recurse with the outer children of the two nodes
- Recurse with the inner children of the two nodes
Return all three cases && together.
class Solution{ public: bool isMirror(TreeNode* t1, TreeNode* t2) { if(t1 == NULL && t2 == NULL) return true; if(t1 == NULL || t2 == NULL) return false; // now we have to check if the two nodes are mirrors // if their inner children are mirrors, or if theyre // outer children are mirrors return t1->val == t2->val && isMirror(t1->right, t2->left) && isMirror(t1->left, t2->right); } bool isSymmetric(TreeNode* root) { if(root == NULL) return true; return isMirror(root->left, root->right); } };
Iterative BFS
Use a queue, push in the first two children.
Pop out 2 nodes at a time, and compare them. Push in the children nodes in symmetric pairs.
class Solution { public: bool isSymmetric(TreeNode* root) { if(root == NULL) return true; queue<TreeNode*> q; q.push(root->left); q.push(root->right); while(q.size() > 0) { TreeNode* t2 = q.front(); q.pop(); TreeNode* t1 = q.front(); q.pop(); if(t1 == NULL && t2 == NULL) continue; if(t1 == NULL || t2 == NULL) return false; if(t1->val != t2->val) return false; // outer pair q.push(t1->left); q.push(t2->right); // inner pair q.push(t1->right); q.push(t2->left); } return true; } };
Insert In a Sorted Circular Linked List
Given a node from a Circular Linked List which is sorted in ascending order, write a function to insert a value insertVal into the list such that it remains a sorted circular list.
This problem becomes hard because of the cases you have to check for, for proper insertion of the value.
You have to check these cases:
- case 1: Simple, value fits between a
prevandcurrpointer. - case 2: We have a pivot,
prev>curr. That means we fit if we are greater thanprev, OR we are less thancurr. - case 3: We reach back to the start of the list. Just pop us in man.
Took me a while to nail down these cases. It is VERY easy to get lost in nested if statements.
class Solution { public: void insertAfter(Node* node, int i) { Node* temp = new Node(i); temp->next = node->next; node->next = temp; } Node* insert(Node* head, int insert_val) { // Lets take care of the NULL case if(head == NULL) { Node* temp = new Node(insert_val); temp->next = temp; return temp; } // two pointers Node *p = head, *n = head->next; while(n != head) { if(p->val <= insert_val && insert_val <= n->val) { insertAfter(p, insert_val); return head; } else if(p->val > n->val) { if(p->val <= insert_val || insert_val <= n->val) { insertAfter(p, insert_val); return head; } } p = n; n = n->next; } insertAfter(p, insert_val); return head; } };
Merge Intervals
Given a collection of intervals, merge all overlapping intervals.
Example 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Algorithm:
1. If input is less than 2 elements return 2. Sort by starting interval 3. Put first interval in out array 4. Iterate i from 1 to input end 5. min end = min(end of last interval in out, end of input[i] 6. if start of last interval in out is LESS OR EQUAL to min end 7. Overlap, set end of last interval to the max end of the two 8. Else 9. No overlap, push in input[i] to out 10. Return out
Code:
vector<vector<int>> merge(vector<vector<int>>& in) { // Take care of edge case if(in.size() < 2) return in; // Sort the intervals by start sort(in.begin(), in.end(), [] (vector<int> &a, vector<int> &b) {return a[0] < b[0];}); // Build the output array vector<vector<int>> out; // Add first interval to our output out.push_back(in[0]); // Iterate from second element to finish for(int i = 1; i < in.size(); i++) { // The max start will always be the new interval, cause we sorted it int max_start = in[i][0]; // Meat of the problem int min_end = min(out.back()[1], in[i][1]); if(max_start <= min_end) out.back()[1] = max(out.back()[1], in[i][1]); else out.push_back(in[i]); } return out; }
Merge Sorted Array
You need to do a merge sort in place. One array is big enough to hold both of them. You work with 3 pointers.
One pointer at the end of the long array that will be the output, another pointer at the end of the valid data, and another pointer at the end of the other array.
You take the biggest element and put it in the end of the array and shift the pointers left.
At the end you might still have some shit left in the second array. If you do, just put em in the array.
Kth Largest Element in an Array
This was a nice and easy one. Idea is to keep a heap of the size that we require. In C++ we would just use a multiset to allow for duplicates. We iterate through the input array and insert elements into the set. If the set is bigger than k, we remove the smallest element from the set. We then return the smallest element of the set which will be the k'th largest element.
Clone A Graph
There are 2 different ways of solving this problem:
DFT recursively, BFT.
DFT Recursively
Depth First Traversal recursively with an unordered map of seen nodes and copies.
Algorithm:
1. If node is NULL return NULL 2. Add node and copy to map 3. Explore Node with Map 4. iterate over neighbors A 5. if not in Map 6. add copy of A to map. 7. Explore A with Map 8. Push back copy of A to copy of Node neighbors
Code:
void explore(Node* node, unordered_map<Node*, Node*> ©_map) { // iterate over neighbors of node for(auto& A : node->neighbors) { if(copy_map.find(A) == copy_map.end()) { // if we have NOT seen this node yet copy_map[A] = new Node(A->val); explore(A, copy_map); } copy_map[node]->neighbors.push_back(copy_map[A]); } } Node* cloneGraph(Node* node) { if(node == NULL) return NULL; unordered_map<Node*, Node*> copy_map; copy_map[node] = new Node(node->val); explore(node, copy_map); return copy_map[node]; }
BFT Iteratively
Breath First Traversal iteratively with a queue and an ordered map of seen nodes and copies.
Algorithm:
1. If node is NULL return NULL 2. Insert node, and a copy of that node (with just the value for now) in a map 3. Push node in a queue 4. While queue is not empty 5. deque the front of the queue and call it N 6. iterate over the neighbors of N, call each one A. 7. if A is not in the map 8. Insert A, and a copy into the map 9. add the copy of A to the neighbor list of the copy of N. 10. Return the copy of node.
Code:
Node* cloneGraph(Node* node) { if(node == NULL) return NULL; unordered_map<Node*, Node*> copy_map; queue<Node*> q; // create entry in copy_map of node, copy of node copy_map[node] = new Node(node->val); q.push(node); while(!q.empty()) { Node* n = q.front(); q.pop(); // iterate over adjacent nodes for(auto& a : n->neighbors) { // if we have not visted this node yet if(copy_map.find(a) == copy_map.end()) { // make a copy and add it to our map copy_map[a] = new Node(a->val); // add node to our queue q.push(a); } // we add this newly copied neighbor to the copy of the node we are examining copy_map[n]->neighbors.push_back(copy_map[a]); } } return copy_map[node]; }
Number of Islands
Graph problem, we explore connected land parts and then mark them as seen. Then we go through the graph and check if we encounter any new unseen land areas. If we do, increment result counter and explore and mark seen :).
I spent a great deal of effort coding a system that will look at all neighboring elements along with diagonals. The question didn't ask this!!! Remember to read the question!!
I also had a lot of effort in trying to create an ordered map/set of pairs. You can't do that easily in C++, so I just modified the input the input grid.
Algorithm:
1. Iterate over every element of the graph 2. If the element is unseen land 3. Increment result counter 4. Explore unseen land 5. Mark land as seen 6. Explore all unseen connected land
Code:
vector< vector<int> > landN(vector<vector<char>>& grid, int& i, int& j) { int max_i = grid.size() - 1; int max_j = grid[0].size() - 1; vector<vector<int>> out; // top if(i - 1 >= 0 && grid[i-1][j] == '1') out.push_back({i-1, j}); //left if(j - 1 >= 0 && grid[i][j-1] == '1') out.push_back({i, j-1 }); //down if(j + 1 <= max_j && grid[i][j+1] == '1') out.push_back({i,j + 1}); //right if(i + 1 <= max_i && grid[i+1][j] == '1') out.push_back({i+1, j}); return out; } void explore(vector<vector<char>>& grid, int& i, int& j ) { // assume we are on a land element grid[i][j] = 'X'; // get a list of neighbors that are land vector< vector<int> > neighbors = landN(grid, i, j); for(auto n : neighbors) { explore(grid, n[0], n[1]); } return; } int numIslands(vector<vector<char>>& grid) { int islands = 0; for(int i = 0; i < grid.size(); i++) { for(int j = 0; j < grid[0].size(); j++) { if( grid[i][j] == '1') { islands++; explore(grid, i, j); } } } return islands; }
Is Graph Bipartite?
I don't know you tell me bro.
I did a deep dive in this problem. To solve it, we have to start at a node, color it, and then check to see if any of its neighbors have the same color. Then iterate over the neighbor nodes, if they are uncolored, then color them a different color than their current node.
Algorithm:
1. Create color map, key will be vertex index and value will be color or unseen 2. color: -1 = unseen, 0 one color, 1 another color 3. Iterate i from 0 to end of graph. Do this to take care of disconnected sub graphs 4. if the vertex at i is unseen (-1) 5. create a stack of ints 6. push i in the stack 7. color the vertex i 0 8. while stack is not empty 9. vertex cur will equal top element popped from stack 10. // we are now in a colored node. we need to check its neighbors 11. iterate n over neighbors of vertex cur 12. if color of n == -1 meaning not colored/seen yet 13. set color of n the opposite of color of cur 14. suspend cur by pushig it to the stack 15. push n to the stack 16. break out of the iteration 17. if color of n == color of cur 18. return false cause this is not BIPARTE
Code:
bool isBipartite(vector<vector<int>>& graph) { unordered_map<int, int> color; // initialize color map to all -1 for(int i = 0; i < graph.size(); i++) color[i] = -1; // this for loop is to take in account disconnected vertices for(int start = 0; start < graph.size(); start++) { // if a vertex has not been colored. If it has, we've already done a // full search of its connected vertices. We do this for every // disconnected graph if(color[start] == -1) { stack<int> s; s.push(start); // color the first vertex. We assume every vertex in the while loop is // colored color[start] = 0; while(!s.empty()) { // grab the top of the stack int cur = s.top(); s.pop(); // iterate over its children. We are looking for one un colored // vertex to dive deeper into. for(auto n : graph[cur]) { if(color[n] == -1) { // we have to suspend our current vertex, we'll get back // to it later. s.push(cur); // lets push in our new node to search s.push(n); // this sets the color to the opposite of our vertex n // using the bitwise XOR operator color[n] = color[cur] ^ 1; // break out of this vertex's exploration. we want to // pursue this new deeper vertex. break; } else if(color[n] == color[cur]) return false; } } } } return true; }
Accounts Merge
This is a really interesting graph problem, and theres a couple of parts to to it. The trick to understand is that bulk of the problems lies with accounts tying other accounts together. For example:
Account 1: A B Account 2: C D Account 3: A C
A trick early in this problem was simplify the email strings, and the whole name crap, and boil it down to the root problem. Strings that if found in other accounts, need to be merged into one.
First is building the graph itself, in the form of an adjacency list. Next is to create a map of seen emails, with the key being the first node they were seen in. Then iterate over the accounts, and for each account, iterate over the emails. If the email address has been found already, add an adjacency entry connecting that node to the node the email address was found.
After this we'll have a nifty adjacency list that defines our graph, which is all we need to build our output list of accounts.
What we do is do Depth First Traversal on each node we find. Throughout that traversal, we keep adding all the emails we see into a set for that node, and also mark each node as seen as we explore it. That's it!
Algorithm:
1. Build an array of sets of ints to serve as adjancency list 2. Initialize the array to have empty set for every index in accounts 3. Create a map called EMAP of key: email string and value: index of account first seen with it 4. Iterate A over accounts 5. iterate E for all emails of A 6. if E is in EMAP 7. create adjacency connections: 8. A to EMAP[E] and EMAP[E] to A 9. else add EMAP[E] = A 10. 11. Build our output: create a vector of vectors of strings called OUT 12. Create a SEEN set of ints 13. iterate A over Accounts 14. if A isn't in SEEN: 15. create a vector of strings, and add in the name as the first element 16. Pass this vector and node A into Explore! Explore will fill in the emails 17. Return OUT! 18. 19. SUBROUTINE: 20. Explore DFS with params: 21. accounts ref, 22. adjacency list, 23. seen set 24. output string set ref 25. node index 26. 27. if the node is in the seen set, RETURN 28. add the nodes emails to the emails output string set 29. iterate over the neighbors 30. explore them!
Code:
// Depth first traversal of our graph, that builds a set of emails for that connected group void dfs(vector<vector<string>>& accounts, vector< set<int> > &adj, unordered_set<int> &seen, int node, set<string> &emails) { if(seen.find(node) != seen.end()) return; // node not seen, add its email to the emails set, bool first = true; for(auto& e : accounts[node]){ if(first){ first = false; continue;} emails.insert(e); } //mark it seen seen.insert(node); //explore its neighbors for(auto& n : adj[node]) dfs(accounts,adj,seen, n, emails); return; } vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) { // initialize empty adj list, set to avoid duplicate adjacencies vector< set<int> > adj(accounts.size(), set<int>()); unordered_map< string, int > emap; // Build the adj list and emails map for(int id = 0; id < accounts.size(); id++) { // iterate over emails see if any are found for(int j = 1; j < accounts[id].size(); j++){ if(emap.find(accounts[id][j]) != emap.end()) { adj[emap[accounts[id][j]]].insert(id); adj[id].insert(emap[ accounts[id][j] ]); } else emap[accounts[id][j]] = id; } } // build output vector<vector<string>> out; unordered_set<int> seen; for(int i = 0; i < accounts.size(); i++) { if(seen.find(i) != seen.end()){ continue; } // we haven't found this yet, so build it, starting with name out.push_back( {accounts[i][0]} ); set<string> emails; dfs(accounts, adj, seen, i, emails); // iterate over emails set and add them to out for(auto& e : emails) { out.back().push_back(e); } } return out; }
To give you some perspective, this was my first crack at this algo:
Remove Dupes from sorted array
Did a vector erase first but that wasn't ideal. I then learned how to do it with a two pointer approach. First pointer is a “last valid” location and second pointer sweeps through array. As it sweeps and find good ones, it swaps them with the valid. Valid then becomes my new array size.
Search in a Rotated Array II.
Really interesting one cause theres dupes and rotations. Idea is to split the array and based on its bounds, you have 3 possible situations:
- You have a normal sorted list cause left bound smaller than right bound. Do a normal bin search
- Left bound is == to right bound, do a linear search
- You have a pivot somewhere. You check to see if the left array is sorted right. if it is, check to see if your target is in it. If it is, search in it. If it isn't in it, it's gotta be on the other side! Remove duplicates from a sorted list
Partition List
Make sure elements greater. Had a hard time with this one because I picked a approach from the start. I was moving elements to the back of the list if they met a certain condition. Problem was that i entered an infinite loop because i would get to the nodes i pushed back and keep pushing them back. I came up with a better one pass solution after i redid it.
Merge k Sorted Lists
Very nice little problem. Many ways to solve but here's the nice optimized way. We have list of nodes and we need to keep track of the minimum one. We make use of an ordered container to do this. This container needs to keep our list of nodes ordered by the value of the container and also store a handle to that node.
Algorithm:
1. Create a dummyhead and a pointer last that points to it 2. Create a multimap with key (value of node) and value (pointer to node) 3. Iterate over input lists and insert every ListNode and value into the map 4. only add non null elements 5. While multimap has at least 2 elements 6. pop off the smallest node from the mulitmap = cur 7. set last->next = to cur 8. set last = last next 9. if cur next isn't null 10. add it to the multimap 11. if multimap is only one element 12. make last next point to it 13. break 14. return dummyhead next
Code:
ListNode* mergeKLists(vector<ListNode*>& lists) { if(lists.size() == 0 ) return NULL; ListNode dh, *last; last = &dh; // create the map of first elements multimap<int, ListNode*> mmap; for(auto& ln : lists) { if(ln != NULL) mmap.insert(make_pair(ln->val,ln)); } while(mmap.size() > 1) { // set a current node to the minimum node and remove it ListNode* cur = mmap.begin()->second; mmap.erase(mmap.begin()); // set our last pointer to point to this min element last->next = cur; last = last->next; // if there are still nodes in this list, put the next one in the map if(cur->next != NULL) { mmap.insert(make_pair(cur->next->val, cur->next)); } } //mmap is going to have one element left if(mmap.size() == 1) last->next = mmap.begin()->second; return dh.next; }
LRU Cache
The all time favorite :)
We make use of the splice function in its single element version to move an
element by its iterator to the top of the list.
void splice (iterator position, list& x, iterator i)
Code:
class LRUCache { public: list< pair<int, int> > lru; unordered_map< int, list< pair<int,int> >::iterator > table; int cap; LRUCache(int capacity) { cap = capacity; } int get(int key) { // we search the table for the element auto search = table.find(key); // if not found, return -1 if(search == table.end()) { return -1; } // if found, move up the lru node lru.splice(lru.begin(), lru, search->second); return search->second->second; } void put(int key, int value) { // we search the table for the element auto search = table.find(key); // if found, move lru and update value if(search != table.end()) { lru.splice(lru.begin(), lru, search->second); lru.front().second = value; return; } // if we don't find it, need a newone lru.push_front(make_pair(key, value)); table[key] = lru.begin(); // check size if(lru.size() > cap) { table.erase(lru.back().first); lru.pop_back(); } return; } };