Cheat sheet Question List

Below are the must-known data structures with all basic functions of any programming language given. Here I am currently listing the c++ based functions for below mentioned Data Structures.

Topics Mentioned below
A.) String
B.) XOR operations
C.) Topological Sort
D.) Buy & Sell
E.) Binary Search
F.) Maximum Sum in Array/Tress: Not Adjacent indexes
G.) Interval
H.) Coin Change
I.) Reverse Linked List
J.) Trees

String Functions Code Block

 

string a = "123";
string b = "123 456";
string c= " 123 ";
string d = "  123 a23";
string e = " a 5432";
        
cout<

 

int a = 123;
char b = 'A';
cout<

 

 

char a = 'T';
cout<< std:string(1,a) ;  // "T"

 

 

//istringstream (use for input stream), ostringstream (use for output stream), stringstream(use for input/output both)

string str = "     bitsofjarvis  ! #  #$%   blog is gooood     ";
istringstream ss(str);
string word;
    while(ss >> word){
    cout< whereas you where waiting a write only object, you will not be happy ;-)
source : stackoverflow

 

string A = "I AM GOOD" , B = "YES I AM";
istringstream combined(A + " " + B);
string word;
 while (getline(combined, word, ' ')){
    cout<

 

 

tolower(c);
OR
for(auto &c : str) c = tolower(c);

 

 

str.substr(startIndex , length);

 

 

str.find("@gmail.com");

OR

 std::string str ("There are two needles in this haystack with needles.");
  std::string str2 ("needle");

  // different member versions of find in the same order as above:
  std::size_t found = str.find(str2);
  if (found!=std::string::npos)
    std::cout << "first 'needle' found at: " << found << '\n';

found=str.find("needles are small",found+1,6);
  if (found!=std::string::npos)
    std::cout << "second 'needle' found at: " << found << '\n';

  found=str.find("haystack");
  if (found!=std::string::npos)
    std::cout << "'haystack' also found at: " << found << '\n';

  found=str.find('.');
  if (found!=std::string::npos)
    std::cout << "Period found at: " << found << '\n';

  // let's replace the first needle:
  str.replace(str.find(str2),str2.length(),"preposition");
  std::cout << str << '\n';

//output : to be, or not to be: that is the question...

 

 

str.erase (10,8);   
OR
str.erase (str.begin()+5, str.end()-9);

 

 

std::string str="to be question";
  std::string str2="the ";
  std::string str3="or not to be";
  std::string::iterator it;

  // used in the same order as described above:
  str.insert(6,str2);                 // to be (the )question
  str.insert(6,str3,3,4);             // to be (not )the question
  str.insert(10,"that is cool",8);    // to be not (that is )the question
  str.insert(10,"to be ");            // to be not (to be )that is the question
  str.insert(15,1,':');               // to be not to be(:) that is the question
  it = str.insert(str.begin()+5,','); // to be(,) not to be: that is the question
  str.insert (str.end(),3,'.');       // to be, not to be: that is the question(...)
  str.insert (it+2,str3.begin(),str3.begin()+3); // (or )
  std::cout << str << '\n';
//output:to be, or not to be: that is the question...

 

 

sort(s.begin() , s.end());

 

 

string sentence = "    This   site  is Awsm     GOOOD     ";
stringstream ss(sentence);
string words;
while(ss >> words){
cout<

 

Stack Functions

 

#include <iostream>       // std::cout
#include <stack>          // std::stack

int main ()
{
  std::stack<int> mystack;

  for (int i=0; i<5; ++i){ 
   mystack.push(i);
 }

  std::cout << "Popping out elements...";
  while (!mystack.empty())
  {
     std::cout << ' ' << mystack.top();
     mystack.pop();
  }
  std::cout << '\n';

  return 0;
}

 

 

// stack::push/pop
#include <iostream>       // std::cout
#include <stack>          // std::stack

int main ()
{
  std::stack<int> mystack;

  for (int i=0; i<5; ++i) mystack.push(i);

  std::cout << "Popping out elements...";
  while (!mystack.empty())
  {
     std::cout << ' ' << mystack.top();
     mystack.pop();
  }
  std::cout << '\n';

  return 0;
}

 

Queue Functions

 

// queue::push/pop
#include        // std::cin, std::cout
#include           // std::queue

int main ()
{
  std::queue myqueue;
  int myint;

  std::cout << "Please enter some integers (enter 0 to end):\n";

  do {
    std::cin >> myint;
    myqueue.push (myint);
  } while (myint);

  std::cout << "myqueue contains: ";
  while (!myqueue.empty())
  {
    std::cout << ' ' << myqueue.front();
    myqueue.pop();
  }
  std::cout << '\n';

  return 0;
}

 

 

// queue::push/pop
#include        // std::cin, std::cout
#include           // std::queue

int main ()
{
  std::queue myqueue;
  int myint;

  std::cout << "Please enter some integers (enter 0 to end):\n";

  do {
    std::cin >> myint;
    myqueue.push (myint);
  } while (myint);

  std::cout << "myqueue contains: ";
  while (!myqueue.empty())
  {
    std::cout << ' ' << myqueue.front();
    myqueue.pop();
  }
  std::cout << '\n';

  return 0;
}

 

 

// queue::front
#include        // std::cout
#include           // std::queue

int main ()
{
  std::queue myqueue;

  myqueue.push(77);
  myqueue.push(16);

  myqueue.front() -= myqueue.back();    // 77-16=61

  std::cout << "myqueue.front() is now " << myqueue.front() << '\n';

  return 0;
}

 

 

// queue::back
#include        // std::cout
#include           // std::queue

int main ()
{
  std::queue myqueue;

  myqueue.push(12);
  myqueue.push(75);   // this is now the back

  myqueue.back() -= myqueue.front();

  std::cout << "myqueue.back() is now " << myqueue.back() << '\n';

  return 0;
}

 

Map Functions

 

map<string , int> phoneNum; 

phoneNum.insert( pair<string , int>("zunglee", 530-7972));

 

 

map<string , int> phoneNum;

phoneNum.insert( pair<string , int>("zunglee", 530-7972));

for(pair<string , int> p : phoneNum){
     cout<<"Contact Name :" <<p.first;
     cout<<"Contact number :" <<p.second;
}

 

 

//1.) COPY to vector and sort;
map<string , int> phoneNum;
..
..
..
vector<pair<string , int>> vecData;

for(auto &it : phoneNum){
      vecData.push_back(it);
}

sort(vecData.begin() ,  vecData.end() , []( pair<string,int> a , pair<string,int> b ){
   return a.second  < b.second;
});

 

 

map<string , int> phoneNum;
..
..
..
struct comp {
    template <typename T>
  
    // Comparator function
    bool operator()(const T& l,
                    const T& r) const
    {
        if (l.second != r.second) {
            return l.second < r.second;
        }
        return l.first < r.first;
    }
};

set<pair<string , int> , comp> setData(phoneNum.begin() , phoneNum.end());

 

 

map<string , int> phoneNum;
..
..
..
sortMap(phoneNum);

void sortMap(map<string , int> &M){

multimap<int, string> MM;

for (auto& it : M) {
        MM.insert({ it.second, it.first });
    }

}

 

Set Functions

 

set<int> myset;

myset.insert(7);

int arr[]= {5,10,15};
myset.insert(arr , arr+2);

//final : 7 , 5 , 10  (****15 is not included)

 

//1.) Advance

eg : set<string> s ;

s.insert("zunglee");
s.insert("bits");
s.insert("of");
s.insert("jarvis");

auto first = s.begin(); // get iterator to 1st element
std::advance(first, 1);     // advance by 1
std::cout << *first;        // first element

//2.) std::next

auto it = std::next(myset.begin(), 5);
std::cout << *it;



std::advance

modifies its argument
returns nothing
works on input iterators or better (or bi-directional iterators if a negative distance is given)
std::next

leaves its argument unmodified
returns a copy of the argument, advanced by the specified amount
works on forward iterators or better (or bi-directional iterators if a negative distance is given))

 

Heap Function

 

struct comparator
{
    bool operator()(int a, int b)
    {
        return a > b;
    }
};

priority_queue<int, vector<int>, comp> minHeap;

 minHeap.push(12);
    minHeap.push(8);
    minHeap.push(15);

  while (!minHeap.empty())
    {
        cout<<minHeap.top()<<" ";
        minHeap.pop();
    }

 

 

priority_queue <int> pq;

    pq.push(5);
    pq.push(1);
    pq.push(10);

while (pq.empty() == false)
    {
        cout << pq.top() << " ";
        pq.pop();
    }

 

Here I am going to List by Topic wise:

A.) String :
1446. Consecutive Characters: https://leetcode.com/problems/consecutive-characters/submissions/
459.  Repeated Substring Pattern
1759. Count Number of Homogenous Substrings
884. Uncommon Words from Two Sentences
890. Find and Replace Pattern (idea to normalize sol1 )

To-do :
1763. Longest Nice Substring


B.) XOR operations

  1. Missing Number: https://leetcode.com/problems/missing-number/
  2. Bitwise ORs of Subarrays: https://leetcode.com/problems/bitwise-ors-of-subarrays/
  3. XOR Queries of a Subarray: https://leetcode.com/problems/xor-queries-of-a-subarray/
  4. Minimum Flips to Make a OR b Equal to c: https://leetcode.com/problems/minimum-flips-to-make-a-or-b-equal-to-c/
  5. Count Triplets That Can Form Two Arrays of Equal XOR: https://leetcode.com/problems/count-triplets-that-can-form-two-arrays-of-equal-xor/
  6. Bitwise AND of Numbers Range: https://leetcode.com/problems/bitwise-and-of-numbers-range/
  7. Decode XORed Permutation: https://leetcode.com/problems/decode-xored-permutation/

1. (a|b) = (a+b) - (a&b)     This is helpful when we want to related AND/OR operations with sum.
2. (a+b) = (a^b) + 2*(a&b)   This one is a very special relation which can be used to solve some seemingly very tough questions.
3. The popcount function is a C++ 20 standard builtin function that counts set bits. LeetCode uses g++ compiler with the C++17 standard so we can use __builtin_popcount instead
    popcount(6) => 2
4. Setting K-th Bit: n | 1 ≪ (K – 1)
5. Clearing K-th Bit : n & ~(1 ≪ K – 1)
6. Toggling K-th Bit : n ^(1 ≪ K – 1)
7. Toggling Rightmost One Bit : n & n – 1
8. Isolating Rightmost Zero Bit : ~n & n + 1
9. Checking Whether Number is Power of 2 or Not : if(n & n – 1 == 0)
10. Multiplying by 2 : n ≪ 1
11. Divinding by 2: n >> 1  

source : https://leetcode.com/discuss/general-discussion/1073221/All-about-Bitwise-Operations-Beginner-Intermediate


C,) Topological Sort

D.) Buy & Sell
E.)Binary Search

F.) Maximum Sum in Array/Tress: Not Adjacent indexes

G.) Interval

56. Merge Intervals (sol1 , sol2 )
252 Meeting Rooms
253 Meeting Rooms II
435 Non-overlapping Intervals (sol1 , sol2)
452. Minimum Number of Arrows to Burst Balloons ()
https://leetcode.com/problems/insert-interval/
436. Find Right Interval (sol1)
986. Interval List Intersections

H,) Coin Change

518. Coin Change 2
377. Combination Sum IV

I.) Reverse Linked List
206. Reverse Linked List
92. Reverse Linked List II
25. Reverse Nodes in k-Group
** Alternate K-group reverse

J.) Tree
Preorder , Inorder , Postoder traversal
https://leetcode.com/problems/binary-tree-right-side-view/

J.) Tree
Preorder , Inorder , Postoder traversal
https://leetcode.com/problems/binary-tree-right-side-view/

J.) Tree
Preorder , Inorder , Postoder traversal
https://leetcode.com/problems/binary-tree-right-side-view/
https://leetcode.com/problems/boundary-of-binary-tree/

Stack

Sliding Window

Binary Search

Bonus (Monotone Stack)

Linked List: [8]
https://leetcode.com/problems/add-two-numbers/
https://leetcode.com/problems/merge-two-sorted-lists/
https://leetcode.com/problems/reverse-nodes-in-k-group/
https://leetcode.com/problems/copy-list-with-random-pointer/
https://leetcode.com/problems/sort-list/
https://leetcode.com/problems/palindrome-linked-list/
https://leetcode.com/problems/linked-list-cycle-ii/
https://leetcode.com/problems/intersection-of-two-linked-lists/

Array: [8]
https://leetcode.com/problems/two-sum/
https://leetcode.com/problems/search-insert-position/
https://leetcode.com/problems/spiral-matrix/
https://leetcode.com/problems/sort-colors/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
https://leetcode.com/problems/majority-element-ii/
https://leetcode.com/problems/insert-delete-getrandom-o1/
https://leetcode.com/problems/task-scheduler/

HashMap: [9]
https://leetcode.com/problems/longest-substring-without-repeating-characters/
https://leetcode.com/problems/group-anagrams/
https://leetcode.com/problems/bulls-and-cows/
https://leetcode.com/problems/sort-characters-by-frequency/
https://leetcode.com/problems/subarray-sum-equals-k/
https://leetcode.com/problems/valid-sudoku/
https://leetcode.com/problems/subarray-sums-divisible-by-k/

Ordered Map:
https://leetcode.com/problems/my-calendar-ii/
https://leetcode.com/problems/my-calendar-iii/

String: [5]
https://leetcode.com/problems/longest-palindromic-substring/
https://leetcode.com/problems/reverse-words-in-a-string/
https://leetcode.com/problems/compare-version-numbers/
https://leetcode.com/problems/longest-common-prefix/
https://leetcode.com/problems/long-pressed-name/

Stack: [5]
https://leetcode.com/problems/valid-parentheses/
https://leetcode.com/problems/simplify-path/
https://leetcode.com/problems/implement-stack-using-queues/
https://leetcode.com/problems/next-greater-element-i/
https://leetcode.com/problems/min-stack/

Queue: [3]
https://leetcode.com/problems/number-of-recent-calls/
https://leetcode.com/problems/design-circular-queue/
https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/

Heap: [3]
https://leetcode.com/problems/top-k-frequent-elements/
https://leetcode.com/problems/find-median-from-data-stream/
https://leetcode.com/problems/last-stone-weight/

Two Pointers: [3]
https://leetcode.com/problems/3sum/
https://leetcode.com/problems/boats-to-save-people/
https://leetcode.com/problems/container-with-most-water/

Binary Search: [4]
https://leetcode.com/problems/first-bad-version/
https://leetcode.com/problems/search-in-rotated-sorted-array/
https://leetcode.com/problems/powx-n/
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

Bit Manipulation: [5]
https://leetcode.com/problems/single-number-ii/
https://leetcode.com/problems/power-of-two/
https://leetcode.com/problems/single-number-iii/
https://leetcode.com/problems/sum-of-two-integers/
https://leetcode.com/problems/counting-bits/

Tree: [12]
https://leetcode.com/problems/binary-tree-inorder-traversal/
https://leetcode.com/problems/validate-binary-search-tree/
https://leetcode.com/problems/binary-tree-level-order-traversal/
https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
https://leetcode.com/problems/balanced-binary-tree/
https://leetcode.com/problems/binary-tree-right-side-view/
https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
https://leetcode.com/problems/find-largest-value-in-each-tree-row/
https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/
https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/

Graph: [8]
Topological Sort:
https://leetcode.com/problems/course-schedule-ii/

DFS:
https://leetcode.com/problems/number-of-islands/
https://leetcode.com/problems/number-of-closed-islands/
https://leetcode.com/problems/number-of-enclaves/

BFS:
https://leetcode.com/problems/rotting-oranges/
https://leetcode.com/problems/01-matrix/

Union Find:
https://leetcode.com/problems/redundant-connection/
https://leetcode.com/problems/friend-circles/

Trie: [2]
https://leetcode.com/problems/implement-trie-prefix-tree/
https://leetcode.com/problems/design-add-and-search-words-data-structure/

Sort: [2]
https://leetcode.com/problems/merge-intervals/
https://leetcode.com/problems/rank-teams-by-votes/

Divide and Conquer: [1]
https://leetcode.com/problems/median-of-two-sorted-arrays/

Dynamic Programming: [8]
https://leetcode.com/problems/climbing-stairs/
https://leetcode.com/problems/house-robber/
https://leetcode.com/problems/perfect-squares/
https://leetcode.com/problems/coin-change/
https://leetcode.com/problems/longest-increasing-subsequence/
https://leetcode.com/problems/russian-doll-envelopes/
https://leetcode.com/problems/ugly-number-ii/
https://leetcode.com/problems/range-sum-query-2d-immutable/

Greedy: [4]
https://leetcode.com/problems/gas-station/
https://leetcode.com/problems/assign-cookies/
https://leetcode.com/problems/lemonade-change/
https://leetcode.com/problems/jump-game/

Design: [4]
https://leetcode.com/problems/lru-cache/
https://leetcode.com/problems/implement-queue-using-stacks/
https://leetcode.com/problems/design-twitter/
https://leetcode.com/problems/kth-largest-element-in-a-stream/

Math: [2]
https://leetcode.com/problems/rectangle-area/
https://leetcode.com/problems/excel-sheet-column-title/

Sliding window: [3]
https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/
https://leetcode.com/problems/sliding-window-maximum/
https://leetcode.com/problems/max-consecutive-ones-iii/



0 0 votes
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
error

Enjoy this blog? Please spread the word :)

0
Would love your thoughts, please comment.x
()
x