SHARE
TWEET

Untitled

a guest Apr 18th, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. bool customEqualsFunction (const obj a, const obj b)
  2. {
  3.     /// implementation here
  4. }
  5.  
  6. bool cmp (const obj a, const obj b)
  7. {
  8.     // implementation here
  9. }
  10.  
  11.  
  12. std::next_permuation(something.begin(), something.end(), &customEqualsFunction)
  13.     modifies something to the next available permutation
  14.     returns true if there is a permutatin greater than the last one, false if not
  15.     worst case : last-first / 2 swaps
  16.     avg: 3 comparisions and 1.5 swaps per call
  17.  
  18.  
  19. std::is_permutation (required.begin(),required.end(),sample.begin(), &customEqualsFunction)
  20.     yes, just the beginning of the text to be compared to is required
  21.  
  22.  
  23.  
  24. sort( values.begin( ), values.end( ), [ ]( const auto& lhs, const auto& rhs )
  25. {
  26.     return <do comparision here>
  27. });
  28.  
  29.  
  30. intersection points of two rectangles:
  31.     int x5 = max(x1, x3);
  32.     int y5 = max(y1, y3);
  33.     int x6 = min(x2, x4);
  34.     int y6 = min(y2, y4);
  35.  
  36.     where x1y1 x2y2 are bottom left and top right resply for the first rectangle
  37.  
  38.  
  39. unordered_set:
  40.     find(key)
  41.         returns an iterator to the element or returns an end iterator  
  42.             set.find(something) != set.end() => means the element exists
  43.         O(constant) average
  44.     count(key)
  45.         returns number of elements with required key
  46.             kind of useless because unordered set does not allowe duplicates so the only possible answers are 0 and 1
  47.        
  48.     so instead of using set.find(key) != set.end() for comparision, you can use if(set.count(key)) which is the same thing
  49.  
  50.  
  51.  
  52. https://leetcode.com/problems/flood-fill/
  53.  
  54.     floodfill ( r, c, color) {
  55.         adj_values = {all the adjacent values}
  56.         for ( auto i : adj_values )
  57.         {
  58.             if ( i is within bounds )
  59.             {
  60.                 floodfill(i.x, i.y, color)
  61.             }
  62.         }
  63.  
  64.         this.color = color;
  65.     }
  66.  
  67.  
  68.  
  69. subarray with given sum:
  70.                     int subArraySum(int arr[], int n, int sum)
  71.                 {
  72.                     int curr_sum = arr[0], start = 0, i;
  73.                  
  74.                     for (i = 1; i <= n; i++)
  75.                     {
  76.                         while (curr_sum > sum && start < i-1)
  77.                         {
  78.                             curr_sum = curr_sum - arr[start];
  79.                             start++;
  80.                         }
  81.                
  82.                         if (curr_sum == sum)
  83.                         {
  84.                             printf ("Sum found between indexes %d and %d", start, i-1);
  85.                             return 1;
  86.                         }
  87.                
  88.                         if (i < n)
  89.                         curr_sum = curr_sum + arr[i];
  90.                     }
  91.                
  92.                     printf("No subarray found");
  93.                     return 0;
  94.                 }
  95.     the logic here is to assign the first element as cur, and keep adding elements to it by iterating over the array
  96.     if cur exceeds sum, then start a while loop which runs while cur > sum, and while it is, remove the elements from the back side
  97.     keep track of which element from the back youve removed so far by using a variable called start which tells you where the start of the current summed up sub array is
  98.  
  99.  
  100. pairs with given sum:
  101.     unordered_set set1(vec1.begin(),vec1.end())
  102.     unordered_set set2(vec2.begin(),vec2.end())
  103.  
  104.     for ( auto i : set1 )
  105.     {
  106.         if ( set2.count(sum-i) )
  107.         {
  108.             cout << i << sum-i
  109.         }
  110.     }
  111.  
  112. std::lower_bound(vec.begin(), vec.end(), value, comparisionFunction) returns first element that is greater than value
  113. std::uper_bound(vec.begin(),vec.end(),value, comparisionFunction) returns first element that is lesser than value
  114.  
  115. unordered_set uses hashing to store the keys in no particular order, only unique keys
  116. set does not use hashing, keys are stored in ascending order, only unique keys
  117. multiset does not using hashing, keys are stored in ascending order, duplicate keys allowed
  118.  
  119.  
  120. iterating over a set/multiset/unordered_set
  121. for (std::multiset<T>::const_iterator i(mlt.begin()), end(mlt.end()); i != end; ++i)
  122.     std::cout << *i << "\n";
  123.  
  124. find median of a stream of integers as they arrive:
  125.  
  126.     std::multiset<int> stream;
  127.     int middle;
  128.  
  129.     int x;
  130.     int n;
  131.     while ( cin >> x )
  132.     {
  133.         stream.insert(x);
  134.         n = n + 1;
  135.  
  136.         std::multiset<int>::const_iterator it(stream.begin());
  137.         if ( n%2 == 0)
  138.         {
  139.             calcs
  140.         } else {
  141.             calcs
  142.         }
  143.     }
  144.    
  145.  
  146. minimum depth in a tree:
  147.  
  148.     int minimum(node* root, int level)
  149.     {
  150.         if ( root == null )
  151.         {
  152.             return level
  153.         }
  154.         level++;
  155.  
  156.         return min(minimum(root.lefbool startsWith(string given, string searchTerm) {
  157.   return (given.rfind(searchTerm, 0) == 0);
  158. }
  159. t,level),(root.right,level))
  160.     }
  161.  
  162. program to multiply two integers stored as large integers :
  163.  
  164.     string multiply ( string s1, string s2)
  165.     {
  166.         std::reverse(s1.begin(), s1.end())
  167.         std::reverse(s2.begin(), s2.end())
  168.         vector<string> levels;
  169.  
  170.         for ( auto j : s2)
  171.         {
  172.             stringstream ss;
  173.             int multiplier = j - '0'
  174.             int carry = 0 ;
  175.             for ( auto i : s1 )
  176.             {
  177.                 int thisnumber = multiplier * (int)(i - '0');
  178.                 if ( carry != 0 )
  179.                 {
  180.                     thisnumber += carry
  181.                     carry = 0  
  182.                 }
  183.  
  184.                 if ( thisnumber > 9 )
  185.                 {
  186.                     carry = thisnumber/10;
  187.                     thisnumber = thisnumber%10
  188.                 }
  189.  
  190.                 ss << thisnumber%10;
  191.             }
  192.  
  193.             if ( carry != 0 )
  194.             {
  195.                 ss << carry
  196.             }
  197.             string str = ss.str();
  198.             std::reverse(str);
  199.             levels.push_back(str)
  200.             ss.str("");
  201.             ss.clear();
  202.         }
  203.  
  204.         vector<string> tobeadded
  205.         for (int i = 0 ; i < levels.size(); ++i)
  206.         {
  207.             stringstream ss;
  208.             ss << levels[i]
  209.  
  210.             for ( int j = 0 ; j < i ; ++j)
  211.             {
  212.                 ss << '0'
  213.             }            
  214.             string sth = ss.str();
  215.             std::reverse(sth.begin(),sth.end())
  216.             tobeadded.push_back(sth);
  217.         }
  218.  
  219.         int i = 0 ;
  220.         int max = s1.size() + s2.size()
  221.         int carry = 0 ;
  222.         stringstream final;  
  223.         while(i < max )
  224.         {
  225.             int tempsum = 0 ;
  226.  
  227.             for ( auto j : tobeadded )
  228.             {
  229.                 tempsum += (int)(j[i]-'0')
  230.             }
  231.  
  232.             tempsum += carry
  233.             carry = 0  
  234.  
  235.             if ( tempsum > 9 )
  236.             {
  237.                 carry = tempsum/10
  238.                 tempsum = tempsum%10
  239.             }
  240.  
  241.             final << tempsum%10
  242.             i++;
  243.  
  244.         }
  245.  
  246.         string answer = final.str();
  247.         std::reverse(answer.begin(),answer.end());
  248.     }
  249.  
  250.  
  251.  
  252.  
  253. gcd of two numbers:
  254.     recursive solution, euclidean algorithm:
  255.  
  256.     int func( int a , int b )
  257.     {
  258.         if b == 0
  259.             return a
  260.         return gcd( b, a%b )
  261.     }
  262.  
  263. sorting elements of a map by value using a vector:
  264.  
  265.     map<T,T> freq;
  266.     vector<std::pair<T,T>> vec;  
  267.     for ( auto &it = freq.begin(), it != freq.end(), it++)
  268.     {
  269.         vec.push_back(*it)
  270.     }
  271.  
  272.     std::sort(vec.begin(),vec.end(), [](std::pair<T,T> lhs, std::pair<T,T> rhs) {
  273.         return lhs.second > rhs.second;
  274.     });
  275.  
  276.     //OR JUST USE A MULTIMAP
  277.  
  278.  
  279. Multimaps:
  280.     multimaps store in ascending order of keys
  281.     duplicate keys are allowed
  282.         if there are duplicate keys then the they are stored in ascending order of the values
  283.     to access elements in multimaps, you will have to use m.find(key) which will return an iterator to the pair, so dereference it like this (*x).first or whatever
  284.  
  285. integer to binary :
  286.     std::string binary = std::bitset<8>(128).to_string();
  287.  
  288. stepping number:
  289.     Given N and M find all stepping numbers in range N to M
  290.  
  291.                
  292.                 vector<int> Ans;
  293.                 void dfs(int len, int N, int M, int num = 0) {
  294.                     if(num >= N && num <= M) {
  295.                             Ans.push_back(num);
  296.                     }
  297.                     if(len == 0)
  298.                         return;
  299.                    
  300.  
  301.                     if(num == 0) {
  302.                         for(int i = 1; i <= 9; ++i) {
  303.                             dfs(len - 1, N, M, i);
  304.                         }
  305.                         return;
  306.                     }
  307.  
  308.                     int last_dig = num%10;
  309.                     if(last_dig == 0) {
  310.                    
  311.                         dfs(len - 1, N, M, (num * 10) + (last_dig + 1));
  312.                    
  313.                     } else if(last_dig == 9) {
  314.                    
  315.                         dfs(len - 1, N, M, (num * 10) + (last_dig - 1));
  316.                    
  317.                     } else {
  318.                         dfs(len - 1, N, M, (num * 10) + (last_dig - 1));
  319.                         dfs(len - 1, N, M, (num * 10) + (last_dig + 1));
  320.                     }
  321.                 }
  322.  
  323.                 vector<int> stepnum(int N, int M) {
  324.                     int len = 0;
  325.                     int temp = M;
  326.                     while(temp) {
  327.                         temp /= 10;
  328.                         len++;
  329.                     }
  330.  
  331.                     Ans.clear();
  332.                     dfs(len, N, M);
  333.                     sort(Ans.begin(), Ans.end());
  334.                     return Ans;
  335.                 }
  336.  
  337. putting horses into K stables such that the product of black and white horses is minimum
  338.  
  339.             vector<vector<int> > dp;
  340.  
  341.             int rec(int start, int stables, string str, int K) {
  342.                 int N = str.size();
  343.                 if(start == N) {
  344.                     if(stables == K)
  345.                             return 0;
  346.                     return INT_MAX;
  347.                 }
  348.  
  349.                 if(stables == K)
  350.                         return INT_MAX;
  351.  
  352.                 if(dp[start][stables] != -1)
  353.                         return dp[start][stables];
  354.  
  355.                 int W = 0;
  356.                 int B = 0;
  357.                 int ans = INT_MAX;
  358.  
  359.                 for(int i = start; i < N; ++i) {
  360.                     W += str[i] == 'W';
  361.                     B += str[i] == 'B';
  362.                     if (W * B > ans) break;
  363.                     int Temp = rec(i + 1, stables + 1, str, K);
  364.                     if(Temp != INT_MAX) {
  365.                         ans = min(ans, Temp + (W * B));
  366.                     }
  367.                 }
  368.                
  369.                 return dp[start][stables] =  ans;
  370.             }
  371.  
  372.             int arrange(string str, int K) {
  373.                 int N = str.size();
  374.                 dp.clear();
  375.                 dp.resize(N, vector<int>(K, -1));
  376.  
  377.                 int ans = rec(0, 0, str, K);
  378.                 return ans == INT_MAX ? -1 : ans;
  379.             }
  380.  
  381. divide an array into two parts such that the average of both the parts is the same (subarrays)
  382.         Lets try to simplify the problem.
  383.         Lets assume the two sets are set1 and set2.
  384.         Assume sum of set1 = Sum_of_Set1, with size = size_of_set1.
  385.         Assume sum of set2 = Sum_of_Set2, with size = size_of_set2
  386.  
  387.             SUM_of_Set1 / size_of_set1 = SUM_of_Set2 / size_of_set2
  388.             SUM_of_Set1 = SUM_of_Set2 * (size_of_set1 / size_of_set2)
  389.        
  390.             total_sum = Sum_of_Set1 + Sum_of_Set2
  391.             AND size_of_set2 = total_size - size_of_set1
  392.        
  393.             Sum_of_Set1 = (total_sum - Sum_of_Set1) * (size_of_set1 / (total_size - size_of_set1))
  394.             OR on simplifying,
  395.            
  396.             total_sum / Sum_of_Set1 - 1 = (total_size - size_of_set1) / size_of_set1
  397.             total_sum / Sum_of_Set1 = total_size / size_of_set1
  398.             Sum_of_Set1 / size_of_set1 = total_sum / total_size
  399.        
  400.  
  401.                         vector<vector<vector<bool> > > dp;
  402.                         vector<int> res;
  403.                         vector<int> original;
  404.                         int total_size;
  405.  
  406.                         bool possible(int index, int sum, int sz) {
  407.                             if (sz == 0) return (sum == 0);
  408.                             if (index >= total_size) return false;
  409.  
  410.                             if (dp[index][sum][sz] == false) return false;
  411.  
  412.                             if (sum >= original[index]) {
  413.                                 res.push_back(original[index]);
  414.                                 if (possible(index + 1, sum - original[index], sz - 1)) return true;
  415.                                 res.pop_back();
  416.                             }
  417.                            
  418.                             if (possible(index + 1, sum, sz)) return true;
  419.  
  420.                             return dp[index][sum][sz] = false;
  421.                         }
  422.                    
  423.                         vector<vector<int> > avgset(vector<int> &Vec) {
  424.  
  425.                             sort(Vec.begin(), Vec.end());
  426.                             original.clear();
  427.                             original = Vec;
  428.                             dp.clear();
  429.                             res.clear();
  430.  
  431.                             int total_sum = 0;
  432.                             total_size = Vec.size();
  433.  
  434.                             for(int i = 0; i < total_size; ++i)
  435.                                 total_sum += Vec[i];
  436.                            
  437.                             dp.resize(original.size(), vector<vector<bool> > (total_sum + 1, vector<bool> (total_size, true)));
  438.  
  439.                             // We need to minimize size_of_set1. So, lets search for the first size_of_set1 which is possible.
  440.                             for (int i = 1; i < total_size; i++) {
  441.                                 // Sum_of_Set1 has to be an integer
  442.                                 if ((total_sum * i) % total_size != 0) continue;
  443.                                 int Sum_of_Set1 = (total_sum * i) / total_size;
  444.                                 if (possible(0, Sum_of_Set1, i)) {
  445.  
  446.                                     // Ok. Lets find out the elements in Vec, not in res, and return the result.
  447.                                     int ptr1 = 0, ptr2 = 0;
  448.                                     vector<int> res1 = res;
  449.                                     vector<int> res2;
  450.                                     while (ptr1 < Vec.size() || ptr2 < res.size()) {
  451.                                         if (ptr2 < res.size() && res[ptr2] == Vec[ptr1]) {
  452.                                             ptr1++;
  453.                                             ptr2++;
  454.                                             continue;
  455.                                         }
  456.                                         res2.push_back(Vec[ptr1]);
  457.                                         ptr1++;
  458.                                     }
  459.  
  460.                                     vector<vector<int> > ans;
  461.                                     ans.push_back(res1);
  462.                                     ans.push_back(res2);
  463.                                     return ans;
  464.                                 }
  465.                             }
  466.                             // Not possible.
  467.                             vector<vector<int> > ans;
  468.                             return ans;
  469.                         }
  470.  
  471.  
  472. bfs traversal of tree:
  473.     q.add(root)
  474.     while ( q not empty )
  475.     {
  476.         head = q.pop()
  477.         head.visited = true
  478.         cout << head
  479.  
  480.             for ( auto i : head.adjacent or for auto i : head.children)
  481.             {
  482.                 q.add(i)
  483.             }
  484.  
  485.         OR
  486.  
  487.             if head.left != NULL : q.add(head.left)
  488.             if head.right != NULL : q.add(head.right)
  489.     }
  490.  
  491.  
  492. dfs traversal of tree: (pre order)
  493.  
  494.     dfs(root):
  495.         root.visited = true;
  496.         cout << root
  497.             for ( auto i : root.adjacent )
  498.             {
  499.                 if i.visited == false:
  500.                     dfs(i)
  501.             }
  502.        
  503.         OR
  504.  
  505.             if ( root.left != null )
  506.                 dfs(root.left)
  507.             if ( root.right != null )
  508.                 dfs(root.right)
  509.  
  510.  
  511. creating a binary tree from an array
  512.  
  513.     node* driverFunction(int[] arr, int n)
  514.     {
  515.         node* root = helperFunction(arr,n,0,root)
  516.         return root
  517.     }        
  518.  
  519.     node* helperFunction( int[] arr, int i, int n, node* root)
  520.     {
  521.         if ( i < n )
  522.         {
  523.             node* temp = node(arr[i])
  524.             root = temp
  525.  
  526.             root->left = helperFunction(arr,2i+1,n,root->left)
  527.             root->right = helperFunction(arr,2i+2,n, root->right)
  528.         }
  529.  
  530.         return root
  531.     }
  532.  
  533. merge sort:
  534.                 void Merge(int *a, int low, int high, int mid)
  535.                 {
  536.                     // We have low to mid and mid+1 to high already sorted.
  537.                     int i, j, k, temp[high-low+1];
  538.                     i = low;
  539.                     k = 0;
  540.                     j = mid + 1;
  541.                
  542.                     // Merge the two parts into temp[].
  543.                     while (i <= mid && j <= high)
  544.                     {
  545.                         if (a[i] < a[j])
  546.                         {
  547.                             temp[k] = a[i];
  548.                             k++;
  549.                             i++;
  550.                         }
  551.                         else
  552.                         {
  553.                             temp[k] = a[j];
  554.                             k++;
  555.                             j++;
  556.                         }
  557.                     }
  558.                
  559.                     // Insert all the remaining values from i to mid into temp[].
  560.                     while (i <= mid)
  561.                     {
  562.                         temp[k] = a[i];
  563.                         k++;
  564.                         i++;
  565.                     }
  566.                
  567.                     // Insert all the remaining values from j to high into temp[].
  568.                     while (j <= high)
  569.                     {
  570.                         temp[k] = a[j];
  571.                         k++;
  572.                         j++;
  573.                     }
  574.                
  575.                
  576.                     // Assign sorted data stored in temp[] to a[].
  577.                     for (i = low; i <= high; i++)
  578.                     {
  579.                         a[i] = temp[i-low];
  580.                     }
  581.                 }
  582.                
  583.                 // A function to split array into two parts.
  584.                 void MergeSort(int *a, int low, int high)
  585.                 {
  586.                     int mid;
  587.                     if (low < high)
  588.                     {
  589.                         mid=(low+high)/2;
  590.                         // Split the data into two half.
  591.                         MergeSort(a, low, mid);
  592.                         MergeSort(a, mid+1, high);
  593.                
  594.                         // Merge them to get sorted output.
  595.                         Merge(a, low, high, mid);
  596.                     }
  597.                 }
  598.  
  599.  
  600. swapping two numbers with xor:
  601.     x,y
  602.         x = x xor y
  603.         y = y xor x
  604.         x = x xor y
  605.  
  606.  
  607. bool startsWith(string given, string searchTerm) {
  608.   return (given.rfind(searchTerm, 0) == 0);
  609. }
  610.  
  611.  
  612.  
  613. LRU CACHE implementation
  614.                     class entry {
  615.                         int key ;
  616.                         int value ;
  617.                         entry left;
  618.                         entry right;
  619.                     };
  620.  
  621.  
  622.                     unordered_map<int,entry> map;
  623.                     entry start, end;
  624.  
  625.  
  626.                     int size = // variable size  ;
  627.  
  628.                     void addAtTop (Entry node) {
  629.                         node.right = start;
  630.                         node.left = null
  631.  
  632.                         if ( start != null ) {
  633.                             start.left = node
  634.                         }
  635.  
  636.                         start = node
  637.  
  638.                         if ( end == null ) {
  639.                             end = start
  640.                         }
  641.  
  642.                     }
  643.  
  644.                     void removeNode(Entry node) {
  645.                         if ( node.left != null ) {
  646.                             node.left.right = node.right
  647.                         } else {
  648.                             start = node.right
  649.                         }
  650.  
  651.                         if ( node.right != null ) {
  652.                             node.right.left = node.left
  653.                         } else {
  654.                             end = node.left
  655.                         }
  656.                     }
  657.  
  658.                     int getValue ( int key ) {
  659.                         if ( map.contains(key)) {
  660.                             entry e = map.get(key);
  661.                             removeNode(e)
  662.                             addAtTop(e)
  663.                             return entry.value
  664.                         }
  665.                     }
  666.  
  667.                     void addEntry ( int key, int value ) {
  668.                         if (map.contains(key)) {
  669.                             Entry e = map.get(key)
  670.                             e.value = value
  671.                             addAtTop(e);
  672.                         } else {
  673.                             entry newnode;
  674.                             newnode.left = null
  675.                             newnode.right = null
  676.                             newnode.key = key ;
  677.                             newnode.value = value
  678.                             if ( map.size() > size ) {
  679.                                 map.remove(end.key)
  680.                                 removeNode(end)
  681.                                 addAtTop(newnode)
  682.                             } else {
  683.                                 addAtTop(newnode)
  684.                             }
  685.  
  686.                             map.put(key,newnode)
  687.                         }
  688.                     }
  689.    
  690.                     int lookup_entry(int key) { // key of the entry
  691.                         if map.contains(key) { // key is found in cache
  692.                             entry e = map.get(key);
  693.  
  694.                         }
  695.  
  696.                     }
  697.  
  698. to check if there are overlapping times in a list of given time intervals
  699.  
  700.                 bool isThereAnOverlap(vector<pair<int,int>> listOfTimes) {
  701.                    
  702.                     std::sort(listOfTimes.begin(),listOfTimes.end(), [] ( const auto &lhs, const auto&rhs) {
  703.                         return lhs.first <= rhs.first;
  704.                     });
  705.                        
  706.                        
  707.                     for ( auto i : listOfTimes) {
  708.                         cout << i.first << " " << i.second ;
  709.                     }
  710.                     std::vector<pair<int,int>>::iterator i;
  711.                    
  712.                     bool truth = false;
  713.                     for (i = listOfTimes.begin(); i < listOfTimes.end()-1 ; i++) {
  714.                        
  715.                         auto p1 = *i ;
  716.                        
  717.                         auto p2 = *(i+1);
  718.                         // 12 26
  719.                        
  720.                         if ( p1.second > p2.first ) {
  721.                             truth = true;
  722.                             break;
  723.                         }
  724.                        
  725.                     }
  726.                    
  727.                     return truth;
  728.                        
  729.                 }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top