Differences

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

--- coding_cheat_sheet [2020/07/11 23:50]
paul [Coding Cheat Sheet]
+++ coding_cheat_sheet [2021/11/08 00:09] (current)
paul [Using Custom Data With Priority Queues]
@@ Line 1: / Line 1: @@
 ====== Coding Cheat Sheet ======
+For general techniques, see [[Algorithm Techniques]].
+For explanations of problems see [[Algorithm Problems]].
+===== Strings =====
 Length of a string:
 C++:<code c> stringVar.length() </code>
-Python: <code python> len(stringVar) </code>
 Adding a character to a string:
@@ Line 16: / Line 21: @@
 </code>
-=== Sorting a 2D Vector ===
+To convert anything into a string use ''to_string()''.
-To make a sorting function do as follows:
+To erase characters, we use ''string.erase(pos, len)''.
+To convert to upper case or lower case you have to iterate over every character
+and use ''tolower(int c)'' or ''toupper(int c)''. They return the case converted
+character.
+To check if a character is alphanumeric (letters and numbers) or just
+alphabetic:
 <code cpp>
-bool sortFunc(const vector<int> &v1, const vector<int> &v2)
+isalnum(char c) // alpha numeric
+isalpha(char c) // alphabetic
+isdigit(char c) // is a number
+</code>
+Returns false (0) if not.
+==== Split ====
+How to split a stream in an array of words.
+<code cpp>
+// Utility function to split the string using a delim. Refer -
+// http://stackoverflow.com/questions/236129/split-a-string-in-c
+vector<string> split(const string &s, char delim)
+{
+    vector<string> elems;
+    stringstream ss(s);
+    string item;
+    while (getline(ss, item, delim))
+        elems.push_back(item);
+    return elems;
+}
+</code>
+===== Maps =====
+==== Going to middle element ====
+Use ''std::advance()'' to advance the iterator from begin to ''size()/2''
+<code cpp>
+#include <iterator>
+auto it = mySet.begin();
+std::advance(it, mySet.size()/2);
+</code>
+==== Iterating over a map and deleting an element ====
+This is tricky! The following does NOT work!!
+[[https://stackoverflow.com/questions/8234779/how-to-remove-from-a-map-while-iterating-it|Stack overflow article]].
+<code cpp>
+for(auto& entry : dm)
 {
-  return v1[0] < v2[0];
+  if( dm.find(entry.second) == dm.end() )
+  {
+      dm.erase(entry.first);
+      changed = true;
+  }
 }
 </code>
-=== Initialize 2D Vector ===
+Use a regular for loop with constant interators.
+<code cpp>
+for (auto it = m.cbegin(); it != m.cend() /* not hoisted */; /* no increment */)
+{
+  if (must_delete)
+  {
+    m.erase(it++);    // or "it = m.erase(it)" since C++11
+  }
+  else
+  {
+    ++it;
+  }
+}
+</code>
-<code cpp>vector<vector<int>> nums(NUMBER_OF_ROWS, vector<int>(NUMBER_OF_COLS, 0) );</code>
+==== Removing Whitespace from a string ====
-====Time Complexity====
-=== Difference Between O(log(n)) and O(nlog(n)) ===
+<code cpp>
+s.erase(std::remove_if(s.begin(), s.end(), ::isspace), s.end());
+</code>
-https://stackoverflow.com/questions/55876342/difference-between-ologn-and-onlogn/55876397
+==== String to Number ====
+you can use
-Think of it as O(n*log(n)), i.e. "doing log(n) work n times". For example, searching for an element in a sorted list of length n is O(log(n)). Searching for the element in n different sorted lists, each of length n is O(n*log(n)).
+''std::stoi( str )''
+where str is your number as ''std::string''.
-Remember that O(n) is defined relative to some real quantity n. This might be the size of a list, or the number of different elements in a collection. Therefore, every variable that appears inside O(...) represents something interacting to increase the runtime. O(n*m) could be written O(n_1 + n_2 + ... + n_m) and represent the same thing: "doing n, m times".
+There are version for all flavours of numbers: long stol(string), float stof(string), double stod(string),... see http://en.cppreference.com/w/cpp/string/basic_string/stol
-Let's take a concrete example of this, mergesort. For n input elements: On the very last iteration of our sort, we have two halves of the input, each half size n/2, and each half is sorted. All we have to do is merge them together, which takes n operations. On the next-to-last iteration, we have twice as many pieces (4) each of size n/4. For each of our two pairs of size n/4, we merge the pair together, which takes n/2 operations for a pair (one for each element in the pair, just like before), i.e. n operations for the two pairs.
+===== Ordered Container Order =====
-From here, we can extrapolate that every level of our mergesort takes n operations to merge. The big-O complexity is therefore n times the number of levels. On the last level, the size of the chunks we're merging is n/2. Before that, it's n/4, before that n/8, etc. all the way to size 1. How many times must you divide n by 2 to get 1? log(n). So we have log(n) levels. Therefore, our total runtime is O(n (work per level) * log(n) (number of levels)), n work.
+In C++ associative containers such as sets and maps store values in ascending order. You can easily change this by passing a comparative function that takes in two parameters a and b and returns true if a goes before b. STL provides basic versions of these functions for you!
+<code cpp>
+// Here if greater<int> is used to make
+// sure that elements are stored in
+// descending order of keys.
+map<int, string, greater <int> > mymap;
+</code>
-  * Doubly Linked List
+===== Vectors =====
-  * Linked list
-  * Hash table
-  * Binary Search Tree
-  * Set
-  * List
-  * LRU Cache
+==== Sorting a 2D Vector ====
-==== Hashtable ====
+To make a sorting function do as follows. Remember, it means what has to be true
+for v1 to go before v2.
-A hashtable allows for the rapid lookup of data based on a key. It works as follows:
+<code cpp>
+bool compareFunc(const vector<int> &v1, const vector<int> &v2)
+{
+  return v1[0] < v2[0];
+}
-  - a hash function converts a key to an index.
+// use the sort function by passing in the custom compare fucnction
-  - the value is stored or retrieved from that index.
+sort(myVect.begin(), myVect.end(), compareFunc);
+</code>
-===== Scratch Notes =====
+Or with a lambda:
+<code cpp>
+sort(in.begin(), in.end(), [] (vector<int> &a, vector<int> &b) {return a[0] < b[0];});
+</code>
-Learned:
+==== Initialize 2D Vector ====
-  - unordered_set: It is an ordered set of unique numbers that are stored by a key, which is equal to the number in each element. They are not ordered and allow for the fast retrieval and insertion of each element (constant time O(1)). To make them you use the following syntax:
+Use the std::vector::vector(count, value) constructor that accepts an initial
+size and a default value.
-<code c++>
+<code cpp>vector<vector<int>> nums(NUMBER_OF_ROWS, vector<int>(NUMBER_OF_COLS, 0) );</code>
+===== Unordered Set =====
+An ordered set of unique numbers that are stored by a key, which is equal to the
+number in each element. They are not ordered and allow for the fast retrieval
+and insertion of each element (constant time O(1)). To make them you use the
+following syntax:
+<code cpp>
 #include <unordered_set>
@@ Line 89: / Line 186: @@
 </code>
-==== Passing Yearbooks ====
+==== Unordered Sets of Pairs ====
-We are giving an array that represents the parth 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.
+Pairs need a special hashing function for them to work. Regular ordered sets work just fine too.
-==== 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.
+<code cpp>
+struct pair_hash
+{
+	template <class T1, class T2>
+	std::size_t operator () (std::pair<T1, T2> const &pair) const
+	{
+		std::size_t h1 = std::hash<T1>()(pair.first);
+		std::size_t h2 = std::hash<T2>()(pair.second);
-The minimum positive element is going to be anywhere between 1 and n+1. Here is why.
+		return h1 ^ h2;
-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:
+unordered_set<pair<int,int>, pair_hash> mySet;
+</code>
-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:
+===== Queue ====
-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:
+A queue is just a line man. First in fist out. You can only remove the element
-Look for the first non present negative number. If not found, handle the edge case and return n+1.
+in the front of the line of a queue. Remember that!
-YOU GO THIS!
+  - ''pop()'' - pops front of the queue, does NOT return the element!
+  - ''push()'' - pushes an element to the back of the queue.
+  - ''front()'' - reference to element in the front of the queue.
+  - ''back()'' - reference to the element in the back of the queue.
+  - ''size()''
+  - ''empty()'' - returns whether empty or not.
-==== Permutations and Combinations ====
+===== Priority Queue =====
-Theres like... all these different kinds of permutations and combinations with repetitions, with unique values, etc.
+A C++ ''priority_queue'' is a heap, which is by default a max heap as it uses
+the standard less comparator. Easy to get confused here, because the ''top()''
+function isn't getting the begin element of the container. Just remember, by
+default a prioirty queue is a max heap.
-=== Unique permutations with unique result ===
+<code cpp>
-https://www.youtube.com/watch?v=9lQnt4p7_nE
+priority_queue<int> max_heap;
-  - Sort input candidates.
+max_heap.push(10);
-  - Make a boolean flag array to track used elements.
+max_heap.push(1);
-  - Recurse over the canditations, choosing and building a solution, and then unchoosing.
-  - If the next option is the same, skip it.
+cout << "Top of max_heap: " << max_heap.top() << endl;
+// prints 10
-==== Power Function ====
+priority_queue<int, vector<int>, greater<int>> min_heap;
+min_heap.push(10);
+min_heap.push(1);
-Implement your own power function. The following is the naive algorithm and takes too much time:
+cout << "Top of min_heap: " << min_heap.top() << endl;
+// prints 1
+</code>
+==== Max Heap with Pairs ====
-<code c>
+By default, max heaps using type pair are ordered by the first element. You do not need to create a custom Compare class. See [[https://www.geeksforgeeks.org/priority-queue-of-pairs-in-c-ordered-by-first/|here]]
-class Solution {
+<code cpp>
-public:
+typedef pair<int,int> num_t;
-    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;
-    }
-};</code>
-{{::screen_shot_2020-07-08_at_11.55.31_am.png?400|}}
+priority_queue<num_t> maxHeap;
-<code c>
+maxHeap.push(make_pair(1,2));
-class Solution {
+maxHeap.push(make_pair(2,2));
+// This will be true
+assert_true(maxHeap.top().first == 2);
+</code>
+==== Using Custom Data With Priority Queues ====
+There are numerous was of doing this but here is the most elegant way:
+<code cpp>
+struct node{
+  node(int id, int value) : id(id), value(value){}
+  int id;
+  int value;
+};
+auto cmp = [](const node &a, const node &b){
+  //Max Heap:
+  //======================
+  //larger b will appear later in the container and therefore have a higher priority
+  return a.value < b.value;
+  //MIN Heap:
+  //if a is larger than b, it will appear before b, so smaller b will have higher priority
+  return a.value > b.value;
+};
+priority_queue<node, vector<node>, decltype(cmp)> maxHeap(cmp);
+</code>
+A less elegant way of overloading the default less than operator is as follows:
+<code cpp>
+struct node{
+  node(int _id, int _value) : id(_id), value(_value){}
+  int id;
+  int value;
+};
+bool operator<(const node& A, const node& B) {
+  // Priority look at the "last" element of their list as the one having
+  // the highest priority
+  /*--- FOR A MAX HEAP ---*/
+  // B will go after A and have a higher priority than A
+  return A.value < B.value;
+  /*--- FOR A MIN HEAP ---*/
+  // a GREATER THAN b means b will go before a. The smaller element a will have
+  // a higher priority than b.
+  return A.value > B.value;
+}
+// Now you initalize your priority queue normally, as it will call the
+// overloaded LESS THAN comparator
+priority_queue<node> pQ;
+</code>
+See [[https://stackoverflow.com/questions/9178083/priority-queue-for-user-defined-types|here]].
+Another option:
+<code cpp>
+typedef pair<string, int> p_d;
+class Compare{
 public:
-    double fastPow(double x, long long n)
+    bool operator() (const p_d& a, const p_d& b){
-    {
+        if(a.second == b.second){
-        if ( n == 0)
+            return a.first > b.first;
-            return 1.0;
+        }else {
-        double half = fastPow(x, n / 2);
+            return a.second < b.second;
-        if( n % 2 == 0)
-        {
-            return half * half;
-        }
-        else
-        {
-            return half * half * x;
         }
     }
+};
-    double myPow(double x, int n) {
-        long long N = n;
+// This is a max heap based on number of the int in the pair, and if numbers are the same, word thats lower on the alphabetical compare wins.
-        if(N < 0)
+priority_queue<p_d, vector<p_d>, Compare> heap;
-        {
+</code>
-            x = 1/x;
-            N = -N;
+[[https://stackoverflow.com/questions/16111337/declaring-a-priority-queue-in-c-with-a-custom-comparator|here]].
-        }
+===== Range Based Loops =====
-        return fastPow(x, N);
+Range based loops return copies unless a reference is requested. They return the
-    }
+pair, so no pointer member access required.
-};</code>
+<code cpp>
+unordered_map<int, int> counts;
+multimap<int,int, greater<int>> sorted;
+for(auto& i : counts)
+{
+    sorted.insert(make_pair(i.second, i.first));
+}
+vector<int> out;
+for(auto& i : sorted)
+{
+    out.push_back(i.second);
+    if(--k == 0)
+        break;
+}
+</code>
+===== Lists =====
+Lists are C++ implementations of doubly linked lists. They allow for
+manipulation of data from both ends of the list. The following functions allow
+you to control them:
+  * pop_back()
+  * push_back()
+  * pop_front()
+  * push_front()
+  * front()
+  * back()
+List iteartors are bidrectional! ''--myList.end()'' is a valid iterator that
+points the last element of the list (assuming the list has size greater than
+zero).
+We can also splice in elemnts into a position. For example, say we had a list
+like the following:
+<code cpp>
+myList.push_back(1);
+myList.push_back(2);
+myList.push_back(3);
+myList.push_back(4);
+</code>
+''1 <-> 2 <-> 3 <-> 4''
+And we want to place 4 in the front. We can do the following:
+''myList.splice(myList.begin(), myList, --myList.end());''