Differences

This shows you the differences between two versions of the page.

--- algorithm_problems [2020/09/20 01:39]
127.0.0.1 external edit
+++ algorithm_problems [2020/10/19 19:58] (current)
@@ Line 15: / Line 15: @@
   - Think simple.
   - Validate psuedocode with a simple case
+===== Top K Frequent Words =====
+[[https://leetcode.com/problems/top-k-frequent-words/|Leedcode 692]].
+**Given a non-empty list of words, return the k most frequent elements.
+Your answer should be sorted by frequency from highest to lowest. If two words
+have the same frequency, then the word with the lower alphabetical order comes
+first.**
+This problem is broken in two parts:
+  - Track/store the words and their frequency
+  - Order the words and their frequency
+For storing the words and their frequency there are two ways to do it:
+  - hashmap of string and int, increment count every time you see the int
+  - Using a trie
+For ordering you can do the following:
+  - Using an ordered set and return only the elements needed.
+    - This is bad because you are sorting all the words when you only need some of them.
+  - Maintain a priority queue of all the words with a custom ordering and then pop off only the needed elements.
+    - This is not great because you are storing a priority queue with every possible word.
+  - Build a MIN HEAP.
+    - If the min heap is bigger than the size we are looking for, when inserting an element check it against the current min. If it is bigger, insert it and pop off the min.
+Implementation of the logic is straight forward. The tricky part is setting the
+custom ordereding in C++. Use the following for ordering a prioirty queue with
+the frequency and then lexicographically as a fallback.
+<code cpp [enable_line_numbers="true"]>
+typedef pair<string, int> p_d;
+class Compare{
+public:
+    bool operator() (const p_d& a, const p_d& b){
+        if(a.second == b.second){
+            return a.first > b.first;
+        }else {
+            return a.second < b.second;
+        }
+    }
+};
+priority_queue<p_d, vector<p_d>, Compare> heap;
+</code>
+To create a custom compare ordered container and not fall into C++ errors,
+creating a compare class works.
+===== Longest Increasing Path =====
+[[https://leetcode.com/problems/longest-increasing-path-in-a-matrix/|Leetcode 329]].
+**Given an integer matrix, find the length of the longest increasing path.**
+Solved this with a dfs approach. Spent a bit of time with seen, and didn't even
+need it in the end! The numbers are increasing so you don't need to check for
+that.
+<code pseudo [enable_line_numbers="true"]>
+array of positions getNeighbors(pos, the matrix)
+    return top if inbounds and bigger
+int explore and return the longest path (Pos, seen set of positions)
+    have we seen it?
+        yes: return 0
+    add this position to seen
+    getNeighbors of this position (in bounds and increasing positions)
+    int path = 0;
+    iterate over neighbors
+       path = max(1 + explore(neighbor), path)
+    remove this pos from seen
+    return path
+keep running max
+start from every element in the array
+explore it, get longest path, compare to runnign max
+return the max
+</code>
+<code cpp [enable_line_numbers="true"]>
+class Solution {
+public:
+    vector<vector<int>> memo;
+    int rows;
+    int cols;
+    bool inBounds(vector<int> &p){
+        if(p[0] < 0 || p[0] >= rows || p[1] < 0 || p[1] >= cols){
+            return false;
+        }
+        return true;
+    }
+    vector<vector<int>> getNeighbors(vector<vector<int>>& matrix, vector<int> &p){
+        int val = matrix[p[0]][p[1]];
+        vector<int> l = p, r = p, t = p, b = p;
+        l[1]--;
+        r[1]++;
+        t[0]--;
+        b[0]++;
+        vector<vector<int>> out;
+        if(inBounds(l) && matrix[l[0]][l[1]] > val)      { out.push_back(l); }
+        if(inBounds(r) && matrix[r[0]][r[1]] > val)      { out.push_back(r); }
+        if(inBounds(t) && matrix[t[0]][t[1]] > val)      { out.push_back(t); }
+        if(inBounds(b) && matrix[b[0]][b[1]] > val)      { out.push_back(b); }
+        return out;
+    }
+    int explore(vector<vector<int>>& matrix, vector<int> &p){
+        if(memo[p[0]][p[1]] > 0){ return memo[p[0]][p[1]]; }
+        int path = 1;
+        vector<vector<int>> nays = getNeighbors(matrix, p);
+        for(auto& n : nays){
+            path = max(path, 1 + explore(matrix,n));
+        }
+        memo[p[0]][p[1]] = path;
+        return path;
+    }
+    int longestIncreasingPath(vector<vector<int>>& matrix) {
+        if(matrix.size() == 0){
+            return 0;
+        }
+        rows = matrix.size();
+        cols = matrix[0].size();
+        memo = vector<vector<int>>(rows, vector<int>(cols, 0));
+        int pathMax = 0;
+        for(int r = 0; r < rows; r++){
+            for(int c = 0; c < cols; c++){
+                vector<int> p = {r,c};
+                pathMax = max(pathMax, explore(matrix, p ) );
+            }
+        }
+        return pathMax;
+    }
+};
+</code>
 ===== Binary Search =====
@@ Line 1253: / Line 1402: @@
        fast = fast next
        slow = slow next
-   if slow != head
+    prev next = null
-        prev next = null
     return slow
@@ Line 1278: / Line 1426: @@
     fast = fast->next->next;
   }
-  if(slow != head){
-    prev->next = NULL;
+  prev->next = NULL;
-  }
   return slow;
 }
@@ Line 1301: / Line 1449: @@
   return root;
+}
+</code>
+===== Binary Tree Zigzag Level Order Traversal ====
+[[https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/|Leetcode 103]]
+**Given a binary tree, return the zigzag level order traversal of its nodes'
+values. (ie, from left to right, then right to left for the next level and
+alternate between).**
+Just have to realize to do a BFS with a queue and output the data reversed every
+other level. When doing BFS with a stack, you have to deliniate the current
+level and the next level. Doing it with a null node is a nice way.
+Algorithm:
+<code pseudo [enable_line_numbers="true"]>
+init a queue of nodes
+put in the root in the queue
+put in null node
+output array (2d)
+empty level array
+while queue inst' empty
+    set cur to queue front
+    pop it off
+    if(cur is not null)
+        put in our level array
+        if children aren't null, push into queue
+    else we reached the end of the level
+        if rev is true
+            reverse level array
+        push in our level array
+        clear the level array
+        toggle rev
+        if q isn't empty
+            push in a null
+</code>
+===== Binary Tree Maximum Path Sum =====
+[[https://leetcode.com/problems/binary-tree-maximum-path-sum/|Leetcode 124]].
+**Given a non-empty binary tree, find the maximum path sum. There can be negative
+numbers.**
+I was asked this in an interview. The core concept is that at every node, the
+maximum will either be the following:
+  * left path plus node
+  * right path plus node
+  * both paths rooted through the node.
+This problem can be simplified really well into short code by making use of
+''max()'' calls on return data. Also we need to keep track of a global max, and
+also return the max path, either left or right.
+<code pseudo [enable_line_numbers="true"]>
+explore function (node, global max) -> max path from this node
+  if this node is null, return 0
+  left max  = max(recursive call on left child, 0)
+  right max = max(recursive call on right child, 0)
+  max both  = node val + max (left, right max)
+  global max = max(global max, both)
+  return node val + max(left, right)
+</code>
+<code cpp [enable_line_numbers="true"]>
+int explore(TreeNode* node, int& max_sum)
+{
+  if(node == NULL){
+    return 0;
+  }
+  int max_left = max(explore(node->left, max_sum), 0);
+  int max_right = max(explore(node->right, max_sum), 0);
+  int max_both = node->val + max_left + max_right;
+  max_sum = max(max_both, max_sum);
+  return node->val + max(max_left, max_right);
+}
+int maxPathSum(TreeNode* root) {
+  int max = INT_MIN;
+  explore(root, max);
+  return max;
 }
 </code>
@@ Line 1388: / Line 1630: @@
 </code>
+===== Best Meeting Point =====
+[[https://leetcode.com/problems/best-meeting-point/|Leetcode 296]].
+TODO
+<code cpp [enable_line_numbers="true"]>
+    int minTotalDistance(vector<vector<int>>& grid) {
+        if(grid.size() == 0){
+            return 0;
+        }
+        // find all peeps
+        vector<Point> peeps;
+        for(int i = 0; i < grid.size(); i++){
+            for(int j = 0; j < grid[0].size(); j++){
+                if(grid[i][j] == 1){
+                    peeps.push_back(Point(i,j));
+                }
+            }
+        }
+        int minDist = INT_MAX;
+        for(int i = 0; i < grid.size(); i++){
+            for(int j = 0; j < grid[0].size(); j++){
+                // iterate through all our peeps
+                int totalDist = 0;
+                for(auto& peep : peeps){
+                    totalDist += Point::dist(peep, Point(i,j));
+                }
+                minDist = min(totalDist, minDist);
+            }
+        }
+        return minDist;
+    }
+    </code>
 ===== Passing Yearbooks =====
@@ Line 1894: / Line 2171: @@
 </code>
+===== Frog Jump =====
+[[https://leetcode.com/problems/frog-jump/|Leetcode]].
+Frog jump problem. Fucking confuused. Wtf??? I think i solved it but have no
+idea how it works out.vTheres a test case that I don't understand. I figured
+out what I did wrong, i misread the probem!!! k is the previous jump. My
+memo approach was spot on tho. NEED TO WRITE NOTES ON THIS.
+Had to memo it to make it.
 ===== Jump Game =====
@@ Line 2521: / Line 2808: @@
   return ans;
 }
+</code>
+===== Minimum Window Substring =====
+[[https://leetcode.com/problems/minimum-window-substring/|Leetcode 76]].
+**Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity ''O(n)''.**
+You can solve this problem not in ''O(n)'' easily with two maps and compare the count of each letter in the dictionary and window map as you do a sliding window. The tricky part is using a "factor" variable that is equal to the unique number of letters and their counts.
+You keep a running ''factor'' of the window and run logic on additions and removals of characters. If the character that you added gives you a count equal to the key count of that character you can increase your factor. If when you remove a character it equals one less they key count, you decrement the factor. This gives you an ''O(1)'' check for window validity.
+**Algorithm:**
+<code pseudo [enable_line_numbers="true"]>
+build a map called dic of letters and count of the t string
+min_size = 0
+start = 0;
+factor is the number of unique characters of atleast a count
+factor = size of dict
+pointer left = 0, right = -1
+while right is less than length - 1
+    advanced the right and add it
+    while window valid // while factors are equal
+        check if min_size is 0 or greater than right - left + 1
+            start = left
+            update min_size
+        advance the left
+ if min_size == 0, return ""
+return s.sub(start, min_size)
+add a character:
+    if char isn't in dic return
+    window[char]++
+    if window[char] == dic[char]
+        factor++
+remove a char:
+    if char isn't in dic return
+    window[char]--
+    if window[char] == dic[char] - 1
+        factor--
+</code>
+**Code**
+<code cpp [enable_line_numbers="true"]>
+class Solution {
+public:
+    unordered_map<char, int> dict, window;
+    int factor;
+    void addChar(char c){
+        if(dict.count(c) == 0){
+            return;
+        }
+        window[c]++;
+        if(dict[c] == window[c]){
+            factor++;
+        }
+    }
+    void removeChar(char c){
+        if(window.count(c) == 0){
+            return;
+        }
+        window[c]--;
+        if(dict[c] - 1 == window[c]){
+            factor--;
+        }
+    }
+    string minWindow(string s, string t) {
+        if(t.length() == 0 || s.length() == 0){
+            return "";
+        }
+        for(auto& c : t){
+            dict[c]++;
+        }
+        factor = 0;
+        int start = 0, min_size = 0;
+        int left = 0, right = -1;
+        while(right < (int)s.length() - 1){
+            //advance right
+            right++;
+            addChar(s[right]);
+            while(factor == dict.size()){
+                int win_size = right - left + 1;
+                if(win_size < min_size || min_size == 0){
+                    start = left;
+                    min_size = win_size;
+                }
+                removeChar(s[left]);
+                left++;
+            }
+        }
+        return (min_size == 0) ? "" : s.substr(start, min_size);
+    }
+};
 </code>
@@ Line 2597: / Line 2992: @@
   }
   return out;
+}
+</code>
+===== Longest Palindromic Substring =====
+[[https://leetcode.com/problems/longest-palindromic-substring|Leetcode 5]].
+**Given a string ''s'', return the longest palindromic substring in ''s''.**
+This is an ''O(n²)'' solution. There is no easy way to solve this problem in
+''O(n)'' time. The ''O(n)'' solution is [[https://en.wikipedia.org/wiki/Longest_palindromic_substring#Manacher's_algorithm|here]].
+{{:pasted:20200715-000341.png?500}}
+You solve this by doing the following:
+  - Iterate through each character in the string
+  - For every character try middle out from that character
+  - For every character assume prev character is the same and middle out it
+I fell in a bit of a pitfall with this problem when coding the middle out
+palindrome checker. I kept getting tripped up on what the set the condition of
+the while loop. I kept getting off by one and had a hard time coming down with a
+case that didn't give me off by one. Should I check for the current case and
+then increment the pointers and invalidate them? What about the initial case?
+If yes, then simply subtract one from the output! The assumption that I needed
+to grasp is that is we check to see if the current case is valid, and we
+increment, we will always have a result that is one bigger. Which is fine, just
+need to correct for it.
+**Algorithm:**
+<code psuedo [enable_line_numbers="true"]>
+int isPali(string, left and right)
+    while char at left and char at right are the same and left and right are in bounds
+        move left left and right right
+    return out with left pointer + 1, and count with r - l + 1
+struct POD start len
+for every letter
+    single = isPali(index index)
+    double = isPali(index - 1, index)
+    pick the bigger one and max against global
+return substring
+</code>
+**Code:**
+<code cpp [enable_line_numbers="true"]>
+struct Out{
+  int index;
+  int len;
+  Out(int i = 0, int l = 0){
+    index = i;
+    len = l;
+  }
+};
+Out pal(string& s, int l , int r){
+  // while inbounds and same char
+  while(l >= 0 && r < s.length() && s[l] == s[r]){
+    l--;
+    r++;
+  }
+  // Shift back the start pointer because it's gonna be off by one
+  // r will be off by one to the right, so subtract r from l and then dec 1
+  return Out(l + 1, r - l - 1);
+}
+string longestPalindrome(string s) {
+  // first is index, second is len
+  Out max;
+  // first pass single char mid out
+  for(int i = 0; i < s.length(); i++){
+    // Single character check
+    Out cur1 = pal(s, i, i);
+    // Double character check
+    Out cur2 = pal(s, i-1, i);
+    // Pick the biggest one
+    Out cur = (cur1.len > cur2.len) ? cur1 : cur2;
+    max = (max.len > cur.len) ? max : cur;
+  }
+  return s.substr(max.index, max.len);
 }
 </code>
@@ Line 2678: / Line 3161: @@
 }
 </code>
-===== 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.
-{{:pasted:20200715-000341.png?500}}
 ===== Palindrome Pairs =====
@@ Line 2732: / Line 3207: @@
 The hashtable gives the 0(1) lookup speed, and avoids the linear search.
+===== Isomorphic Strings =====
+[[https://leetcode.com/problems/isomorphic-strings/|Leedcode]].
+**Given two strings s and t, determine if they are isomorphic.
+Two strings are isomorphic if the characters in s can be replaced to get t.
+All occurrences of a character must be replaced with another character while
+preserving the order of characters. No two characters may map to the same
+character but a character may map to itself.**
+This wasn't THAT easy! I created a map from one string to another but then
+realized that doesn't work for all cases, because two different characters can't
+map to the same character. I then created two maps from both directions but the
+code is pretty hard to read.
+A much more elegant solution is to simple run the algorithm twice from both
+sides.
+<code pseudo [enable_line_numbers="true"]>
+if char lenghts aren't the same, return false
+keep a dictionary array of characters
+for i 0 to s size
+    tchar = t[pointer], schar = s[pointer]
+    if dictionary[tchar] is equal to some flag character, set it equal to schar
+    if dictionary[tchar] doesn't equal schar, return false
+return true
+</code>
+<code cpp [enable_line_numbers="true"]>
+bool isIsomorphic(string s, string t) {
+  vector<char> smap(256, '*');
+  vector<char> tmap(256, '*');
+  if(s.length() != t.length()){
+    return false;
+  }
+  for(int i = 0; i < s.length(); i++){
+    char tchar = t[i], schar = s[i];
+    if(tmap[tchar] != schar && smap[schar] != tchar){
+      if(tmap[tchar] == '*' && smap[schar] == '*' ){
+        tmap[tchar] = schar;
+        smap[schar] = tchar;
+      } else{
+        return false;
+      }
+    }
+  }
+  return true;
+}
+// NEW WAY:
+bool isIsomorphic(string s, string t) {
+  return isIso(s,t) && isIso(t,s);
+}
+bool isIso(string s, string t) {
+  vector<char> map(256, '*');
+  if(s.length() != t.length()){
+    return false;
+  }
+  for(int i = 0; i < s.length(); i++){
+    char tchar = t[i], schar = s[i];
+    if(map[tchar] == '*'){
+      map[tchar] = schar;
+    }
+    if(map[tchar] != schar){
+      return false;
+    }
+  }
+  return true;
+}
+</code>
 ===== Generate Parenthesis =====
@@ Line 3940: / Line 4491: @@
   }
   return true;
+}
+</code>
+===== Open the Lock =====
+[[https://leetcode.com/problems/open-the-lock/|Leetcode 752]].
+**You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots:
+''0, 1, 2, 3, 4, 5, 6, 7, 8, 9''. The wheels can rotate freely
+and wrap around: for example we can turn 9 to be 0, or 0 to be 9' Each
+move consists of turning one wheel one slot.
+The lock initially starts at ''0000'', a string representing the state of the 4
+wheels.
+You are given a list of deadends dead ends, meaning if the lock displays any of
+these codes, the wheels of the lock will stop turning and you will be unable to
+open it.
+Given a target representing the value of the wheels that will unlock the lock,
+return the minimum total number of turns required to open the lock, or -1 if it
+is impossible.**
+This is a really interesting problem that I thought was a backtracking problem
+at first. It is a graph problem. Each string has 8 neighbors and you have to
+make the mental connection that for every turn you can only change one digit at
+a time. You also need to realize that a BFS is the way to go here, because we
+are looking for one target, and if you do DFS you'll be digging into every path.
+Standard BFS techniques apply. I got a litle tripped up with implementing a
+seperator based system for the queue instead of keeping track of layer size.
+Also for keeping track of turns you have to realize that every layer is a turn.
+**Algorithm:**
+<code pseudo [enable_line_numbers="true"]>
+Build a set of deadends and a seen set
+Create a queuefor BFS. For less code, you keep a count for the layer
+add '0000'
+while the queue isn't empty
+    increment a turn count
+    iterate the number of the size of the queue
+        pop off the top element
+            if the element is our target, we're good
+            if the element isn't a dead or seen
+                add it to seen
+                add each of its neighbors the queue
+return -1 if we get out
+</code>
+**Code:**
+<code cpp [enable_line_numbers="true"]>
+int openLock(vector<string>& deadends, string target) {
+  unordered_set<string> d(deadends.begin(), deadends.end()), seen;
+  queue<string> q;
+  q.push("0000");
+  int turns = 0;
+  while(!q.empty()){
+    int layer = q.size();
+    while(layer--){
+      string cur = q.front();
+      q.pop();
+      if(cur == target){
+        return turns;
+      }
+      if(d.count(cur) == 0 && seen.count(cur) == 0){
+        // Push in our cur to seen
+        seen.insert(cur);
+        for(int d = -1; d < 2; d+=2){
+          for(int i = 0; i < 4; i++){
+            // generate 8 strings that are increments and decrements
+            string n = cur;
+            n[i] += d;
+            n[i] = (n[i] > '9') ? '0' : (n[i] < '0') ? '9' : n[i];
+            q.push(n);
+          }
+        }
+      }
+    }
+    // We are done with a layer so increment the code
+    turns++;
+  }
+  return -1;
 }
 </code>
@@ Line 4097: / Line 4738: @@
 ===== Merge k Sorted Lists =====
-[[https://leetcode.com/problems/merge-k-sorted-lists/|Leetcode 23]]
+[[https://leetcode.com/problems/merge-k-sorted-lists/|Leetcode 23]].
+**You are given an array of k linked-lists lists, each linked-list is sorted in
+ascending order.
+Merge all the linked-lists into one sorted linked-list and return it.**
 Very nice little problem. Many ways to solve but here's the nice optimized way.
@@ Line 4161: / Line 4807: @@
     return dh.next;
+}
+</code>
+===== Sort List =====
+[[https://leetcode.com/problems/sort-list/|Leetcode 148]].
+**Given the head of a linked list, return the list after sorting it in ascending order.**
+This problem is easily solved by using ordered containers giving you ''O(n log
+n)'' time and ''O(n)'' space complexity.
+You can get ''O(log n)'' space complexity by doing a merge sort. The trick with
+merge sort is to use a fast and slow pointer to find the middle of the list.
+We do this recursively and our base case is a ''NULL'' and a single node.
+**Algorithm:**
+<code psuedo [enable_line_numbers="true"]>
+Merge sort
+  divide the list in two
+  mergesort left list
+  mergesort right list
+  merge left and right
+</code>
+**Code:**
+<code cpp [enable_line_numbers="true"]>
+ListNode* mergeSort(ListNode* node){
+  // If we're a null node
+  if(node == NULL){
+    return NULL;
+  }
+  // If we're a single node
+  if(node->next == NULL){
+    return node;
+  }
+  // find the middle with fast and slow pointer
+  ListNode *fast = node, *slow = node, *slowPrev = NULL;
+  while(fast && fast->next){
+    slowPrev = slow;
+    slow = slow->next;
+    fast = fast->next->next;
+  }
+  // break the lists in two
+  if(slowPrev){
+    slowPrev->next = NULL;
+  }
+  // Node is gonna be head of left list,
+  // slow is head of right list
+  ListNode* left = mergeSort(node);
+  ListNode* right = mergeSort(slow);
+  // Merge two sorted lists:
+  ListNode dh, *cur;
+  cur = &dh;
+  while(left && right){
+    // find the smallest of the two
+    if(left->val < right->val){
+      // left has the smaller value
+      cur->next = left;
+      left = left->next;
+    }else{
+      // right has the smaller value
+      cur->next = right;
+      right = right->next;
+    }
+    cur = cur->next;
+  }
+  // Take care of any remaining nodes
+  if(left){
+    cur->next = left;
+  }
+  else if(right){
+    cur->next = right;
+  }
+  return dh.next;
+}
+ListNode* sortList(ListNode* head) {
+  return mergeSort(head);
 }
 </code>
@@ Line 4218: / Line 4953: @@
     }
 };
+</code>
+===== Word Ladder II =====
+[[https://leetcode.com/problems/word-ladder-ii/|Leetcode 126]].
+**Given two words (beginWord and endWord), and a dictionary's word list, find all
+shortest transformation sequence(s) from beginWord to endWord, such that:
+  - Only one letter can be changed at a time
+  - Each transformed word must exist in the word list. Note that beginWord is not a transformed word.  **
+I learned some new concepts with this problem. Particularly how to store a trace
+of a path when doing BFS.
+This problem breaks down in first identifying that this is a graph problem. We
+have a bunch of vertices that are one edit distance away. We then have to find
+the SHORTEST paths to the end.
+If we needed to find all paths, an exhaustive DFS would work. But in this case
+we need all shortest paths. This means if we do a BFS, all the shortest paths
+will be on one layer.
+At first I built a graph represented by an adjacency list, which was
+''O(length_of_word * number_of_words²)'' with a memory space of
+''O(number_of_words²)''. Then I did a one edit away function. You can also build
+a map of word combinations of each letter removed, requiring
+''O(number_of_letters*number_of_words)'' space.
+The other tricky part is the handling seen words. I handled it by removing words
+in the wordset that we used on this level.
+**Algorithm:**
+<code psuedo [enable_line_numbers="true"]>
+Create a wordList set to give us O(1) lookup in the words
+Create a queue of string paths
+Create a bool flag called done and set to false
+Create an output list of strings
+Add in the begin word in the queue as the seed path.
+While we're not done and q isn't empty:
+  Grab the level size
+  While levesize--
+    get the path in the front of the q and pop it
+    If the path is the end word
+      add the path to the output list and set done to true
+    add all the neighbors of this word to the base path
+    push these new paths to the queue
+    Add the added words to a visited list
+  remove all the visited words from the word list
+</code>
+**Code:**
+<code cpp [enable_line_numbers="true"]>
+vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wL) {
+  queue<vector<string>> q;
+  unordered_set<string> wordList;
+  for(auto w : wL){
+    wordList.insert(w);
+  }
+  q.push({beginWord});
+  bool done = false;
+  vector<vector<string>> out;
+  // Do a BSF Search
+  while(!done && !q.empty()){
+    int level = q.size();
+    // run this loop for every path in this level
+    list<string> visited;
+    while(level--){
+      vector<string> path = q.front();
+      q.pop();
+      if(path.back() == endWord){
+        out.push_back(path);
+        done = true;
+      }
+      // add our the neighbors:
+      // Theres multiple ways of doing this.
+      for(int i = 0; i < path.back().length(); i++){
+        string orig = path.back();
+        for(char c = 'a'; c <= 'z' ; c++){
+          orig[i] = c;
+          if(wordList.count(orig)){
+            path.push_back(orig);
+            q.push(path);
+            path.pop_back();
+            visited.push_back(orig);
+          }
+        }
+      }
+    }
+    for(auto & w : visited){
+      wordList.erase(w);
+    }
+  }
+  return out;
+}
+</code>
+===== Word Ladder =====
+[[https://leetcode.com/problems/word-ladder/|Leetcode 127]].
+**Given two words (beginWord and endWord), and a dictionary's word list, find
+the length of the shortest transformation sequence(s) from beginWord to endWord,
+such that:
+  - Only one letter can be changed at a time
+  - Each transformed word must exist in the word list. Note that beginWord is not a transformed word.  **
+I did this problem after I did part 2 and it was easier. There are a couple of
+things that are different that you don't need. Namely, we don't need to track
+paths, so it becomes a much easier BFS problem.
+**Algorithm:**
+<code psuedo [enable_line_numbers="true"]>
+build a set of words
+make a queue of paths and add first word in it
+int dist = 0
+while q isn't empty
+    dist++
+    layer = q size
+    make a seen word list
+    while(layer--)
+        pop off path in the q
+        curword = end of path
+        if curword is out end word
+            retun dist
+        iterate over every char in the curword
+            mod = curword
+            iterate c from a to z
+                mod[i] = c
+                if(mod in word set)
+                    add it to the path and add it to the q
+                    add mod to the seen word list
+    remove all the seen words from the wordSet
+    dist++
+return 0
+</code>
+**Code:**
+<code cpp [enable_line_numbers="true"]>
+int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
+  unordered_set<string> wordSet;
+  // build the word set
+  for(auto& w : wordList){
+    wordSet.insert(w);
+  }
+  queue<string> q;
+  q.push(beginWord);
+  int dist = 0;
+  while(!q.empty()){
+    dist++;
+    int layer = q.size();
+    while(layer--){
+      string cur = q.front();
+      q.pop();
+      if(cur == endWord){
+        return dist;
+      }
+      for(int i = 0; i < cur.length(); i++){
+        string mod = cur;
+        for(char c = 'a'; c <= 'z'; c++){
+          mod[i] = c;
+          if(wordSet.count(mod) != 0){
+            wordSet.erase(mod);
+            q.push(mod);
+          }
+        }
+      }
+    }
+  }
+  return 0;
+}
+</code>
+===== Copy List With Random Pointer =====
+[[https://leetcode.com/problems/copy-list-with-random-pointer/|Leetcode 138]].
+**A linked list is given such that each node contains an additional random
+pointer which could point to any node in the list or null.
+Return a deep copy of the list.**
+I first approached this problem by thinking I can just two pass it and build a
+vector array that I can use to index the nodes. I had the right idea but the
+random pointers point to a node and not a number, and the numbers aren't unique.
+What is unique is the memory location.
+You have to look at the problem and not be scared of writing down the high level
+algo. That's the whole point of psuedo code, very high level code.
+I solved it with a map. You can also solve this problem recursively, also with a
+map and a very neat way of building the copy. The recursive function returns a
+copy of the node that was called with the following cases:
+  - If the node is null return null
+  - If the node has been seen already, return the copy in the seen map
+  - If none of the above, make a copy and add it to the seen
+  - Then set the next pointer to a copy of the next node
+  - Then set the randomon pointer to a copt of the random pointer
+  - Return the copy
+**Algorithm Iterative:**
+<code psuedo [enable_line_numbers="true"]>
+make a dummy head
+make a curcopy pointer, cur original
+while cur orignal isn't null
+    curcopy next = new node with val of original
+    add curcopy to a vector
+    curcopy = curcopy next
+    curorig = curorign next
+second pass for random index:
+walk the original list and keep a counter:
+    int randpointer = cur random
+    vector[counter]->rand = vector[rand]
+    counter++
+return dummy head next
+</code>
+**Code Iterative:**
+<code cpp [enable_line_numbers="true"]>
+Node* copyRandomList(Node* head) {
+  Node dh(0), *curOrig = head, *curCopy;
+  curCopy = &dh;
+  // key is orig, val is the copy
+  unordered_map<Node*, Node*> map;
+  // make a first pass copy
+  while(curOrig != NULL){
+    curCopy->next = new Node(curOrig->val);
+    // add it to the array
+    map[curOrig] = curCopy->next;
+    // advanced our pointers
+    curCopy = curCopy->next;
+    curOrig = curOrig->next;
+  }
+  // second pass to copy the random pointers
+  curOrig = head;
+  while(curOrig){
+    map[curOrig]->random = map[curOrig->random];
+    curOrig = curOrig->next;
+  }
+  return dh.next;
+}
+</code>
+**Algorithm Recursive:**
+<code psuedo [enable_line_numbers="true"]>
+maintain a visisted map key: original val: copy
+helper(node) return the copy
+    if(null ) return null
+    if( node is in visited )
+        return the copy
+    Node copy = new node with original's val
+    Copy next = helperCopy(original's next)
+    Copy rand = helperCopy(original's rand)
+    add copy to the visited map
+    return copy
+</code>
+**Code Recursive:**
+<code cpp [enable_line_numbers="true"]>
+class Solution {
+  public:
+    unordered_map<Node*, Node*> seen;
+    Node* helper(Node* orig){
+      if(!orig){
+        return NULL;
+      }
+      if(seen.count(orig)){
+        return seen[orig];
+      }
+      Node* copy = new Node(orig->val);
+      // This is very important that we add it our seen list here, beause if not
+      // we will hit infinite recursion with the random pointers
+      seen[orig] = copy;
+      copy->next = helper(orig->next);
+      copy->random = helper(orig->random);
+      return copy;
+    }
+    Node* copyRandomList(Node* head) {
+      return helper(head);
+    }
+};
+</code>
+===== Two Sum =====
+[[https://leetcode.com/problems/two-sum/|Leetcode 1]].
+**Given an array of integers nums and an integer target, return indices of the
+two numbers such that they add up to target.**
+You can quickly do an ''O(n²)'' by checking every pair. You can do it quicker
+with ''O(n)'' time and space by building a dictionary and looking for the
+complement number. You have to keep in mind that you can't return the same
+number!
+You can two pass it by building a dictionary, or do it better and simpler by
+building the numbers as we go along and looking for the complement in the
+previous numbers.
+**Algorithm:**
+<code psuedo [enable_line_numbers="true"]>
+iterate over all the numbers with an index
+  check if complement exists in the map
+    return it if so
+  add this number to the map
+</code>
+**Code:**
+<code cpp [enable_line_numbers="true"]>
+vector<int> twoSum(vector<int>& nums, int target) {
+  // key: number val val: index
+  unordered_map<int,int> map;
+  for(int i = 0; i < nums.size(); i++){
+    if(map.count(target-nums[i])){
+      return {i, map[target-nums[i]]};
+    }
+    map[nums[i]] = i;
+  }
+  return {};
+}
 </code>