Differences

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

--- algorithm_problems [2020/10/10 07:14]
127.0.0.1 external edit
+++ algorithm_problems [2020/10/19 19:58] (current)
@@ Line 18: / Line 18: @@
 ===== 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.
@@ Line 2807: / 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 2883: / 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 2964: / 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 4302: / 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 4459: / 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 4523: / 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 4580: / 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>