+ green?
-red?- BigO cheat sheet
- c++ STL
- C++ tricks-codeforces
- ceil(x) //if x=6.79; cout=7
-
Print Divisors //O(sqrt(n))
-
Prime
- seive of Eratosthenes
- Miller-Rabin Primality Testing
if X*X = (Y*Y)modN && X != +-YmodN, then N is composite - Fermat's Little Theorem -
given a prime number P, and any number a (where 0<a<p0), then a^(p−1) = 1modp
-
Euclid's algo
-
GCD
public int GCD(int a, int b) { if (b==0) return a; return GCD(b,a%b); } -
lcm - use !...
public int LCM(int a, int b) { return b*a/GCD(a,b); // as a*b = gcd*lcm } -
solve linear Diophantine equations of type ax+by =d, d=GCD(a,b) find x,y:
extendedEuclid(int A, int B) { if(B == 0) { d = A; x = 1; y = 0; } else { extendedEuclid(B, A%B); int temp = x; x = y; y = temp - (A/B)*y; } * Naive: try for all the values of B in [1,M-1] // O(M) -
extendedEuclid: If A & M are coprime, Ax + My =1; then x is the answer. //O(log(Max(A,M)))
-
Fermat's Little Theorem- works only when M is prime: since A^(M-1) = 1(mod M) => A^(-1) = (A^(M-2))(mod M), which is the ans i.e.
int modInverse(int A,int M) { return modularExponentiation(A,M-2,M); } //O(logM) ``` } O(Log(max(A,B))``` -
Modular multiplicative inverse ** For given A, M find B such that (A.B)%M =1 **
-
Maths: * A.B = 1(mod M) * B is in range[1,M-1] {(A.B)%M = (A%M * B%M)%M and B=0 is invalid} * Existence of modular multiplicative inverse only when A and M are coprime i.e. GCD(A,M)=1
-
Methods:
-
-
Geometry
-
Pick’s Theorem for area of polynomials
Area = B/2 + I - 1B = number of lattice points on the boundary of the polygon I = number of lattice points in the interior of the polygon``` -
Euler’s Formula for polygonal nets
V - E + F = 2;V = number of vertices,E = number of edges,F = number of faces -
Line sweep technique
-
line-line intersection: orientation
-
-
Fractions/complex numbers- store num and denom in pairs
- adding 2 fractions(make denom same first)
public int[] addFractions(int[] a, int[] b) { int denom=LCM(a[1],b[1]); int[] c={denom/a[1]*a[0] + denom/b[1]*b[0], denom}; return c; }- reduce a fraction to its simplest form - when the GCD of the numerator and denominator is equal to 1
public void reduceFraction(int[] a) { int b=GCD(a[0],a[1]); a[0]/=b; a[1]/=b; } -
Modular arithmetic
- (a+-b)%c = (a%c +- b%c)%c
- (a*/b)%c = ((a%c)*/(b%c))%c
-
Exponantiation
- BinaryExponentiation //O(logN)
int binaryExponentiation(int x,int n) { if(n==0) return 1; else if(n%2 == 0) //n is even return binaryExponentiation(x*x,n/2); else //n is odd return x*binaryExponentiation(x*x,(n-1)/2); }- modularExponentiation
int modularExponentiation(int x,int n,int M) { if(n==0) return 1; else if(n%2 == 0) //n is even return modularExponentiation((x*x)%M,n/2,M); else //n is odd return (x*modularExponentiation((x*x)%M,(n-1)/2,M))%M; } ***
-
Arrays
- Dynamic alloaction of arrays: example
- C++ dynamic arrays = vectors
-
freqFuncs
- vectorv(5,5) //size 5 ; all elements 5
- vi (arr, arr+n);
- sort(v.begin(),v.end()) //sort
- sort(v.rbegin(),.rend()) //reverse sort
- random_shuffle(v.begin(),v.begin()+2, v.end()) //partial shuffle
- set_intersection(v1.begin(),v1.end(),v2.begin(),v2.end())
- vector:: iterator j;
- j= lower_bound(v.begin(),v.end(), key); if(j== v.end())cout<<"not found"; //binary search for lower bound
- next_permutation(v.begin(),v.end());
- v.size() - number of items
- v.is_empty() //retrurns 0-1
- v.at(index) - returns item at given index, blows up if index out of bounds
- v.push(item) | v.push_back(item) | v.push_front(item)
- v.insert(index, item)
- v.pop_back(); //Removes the last element in the vector, reducing size by one,destroys the removed element.
- v.find(key) //looks for value and returns first index with that value, -1 if not found
- v.resize(new_capacity)
-
Time
- O(1) to add/remove at end
- O(n) to insert/remove elsewhere
-
Space
- contiguous in memory, so proximity helps performance
- space needed = (array capacity, which is >= n) * size of item, but even if 2n, still O(n)
-
Problems
- Next Greater Element
- Rotate Array by 90 anti-clock - some weired rotation trick; see once
- Find duplicates in O(n) time - smarty art thou
- Print the array in spiral form
- Find the repeating and the missing -simple application of the duplictaes prob above
- Arrange given numbers to form the biggest number - make an bool compare function, based on result of appending
- Majority Element in unsorted Array
- Majority element in sorted array
- Number of shapes in Boolean Matrix
- Using DFS - create an equivalent array and keep increasing the count; the name DFS is just to scare the shit out of you
- Using Disjoint Set -lite lo na
- Union and Intersection of:
- Sorted Array - easy peasy, binary search
- Unsorted Array - same as above, either sort the smaller array or make a new one and do binary search
- Collect maximum points in an array with k moves
- Find an element in array such that sum of left array is equal to sum of right array
- Find minimum cost to buy all books
- Remove elements from array : 2 pointer
- Remove duplicate elements from sorted array : 2 pointer
- 2sum
- 3Sum
- 4sum : soln
- Power Set
- Merge 2 sorted arrays
- Maximum sum such that no two elements are adjacent
- Binary Heaps: insertion, deletion,removal, updation
- Find position of an element in a sorted array of infinite numbers
- Sort an array of 0s, 1s and 2s
- Search in a row wise and column wise sorted matrix
- Matrix traversal in diagonal form/Zigzag
- Find the rotation point in a rotated sorted array
- Rearrange positive and negative numbers in O(n) time and O(1) extra space
- Rearrange array in alternating positive & negative items
- To print nth row of Pascal's triangle CodePic
- Find ele that appear more than n/k times: CodePic
- Print the array in wave form :you can deduce the first method; look up here for second
- Find three closest elements from given three sorted arrays
- Container With Most Water
- Sort an array by given column
- find-three-closest-elements-from-given-three-sorted-arrays
- check for pair in A[] with sum as x
- farthest-co-prime
- Sorting an array:
-
Linked List
- Pointers - video '&' means 'address of' and '*' means 'value at'
- Creation and Traversal | Insertion | Deletion
-
-front() – Returns reference to the first element in the list -back() – Returns reference to the last element in the list -push_front(g) – Adds a new element ‘g’ at the beginning of the list -push_back(g) – Adds a new element ‘g’ at the end of the list -pop_front() – Removes the first element of the list, and reduces size of the list by 1 -pop_back() – Removes the last element of the list, and reduces size of the list by 1 -begin() – Returns an iterator pointing to the first element of the list -end() – Returns an iterator pointing to the theoretical last element which follows the last element -empty() – Returns whether the list is empty(1) or not(0) -insert() – Inserts new elements in the list before the element at a specified position -erase() – Removes a single element or a range of elements from the list -assign() – Assigns new elements to list by replacing current elements and resizes the list -remove() – Removes all the elements from the list, which are equal to given element -reverse() – Reverses the list -size() – Returns the number of elements in the list -sort() – Sorts the list in increasing order
Problems
- Adding with carry
- Clone a link list with next
- Reverse a link list
- Find Middle element
- Merge sort for doubly linked list
- Insertion Sort
- Add 1 to a number represented as linked list
- Segregate even and odd nodes
- Rearrange ll such that all even and odd positioned noes are together
- Merge two sorted linked lists such that merged list is in reverse order
-
Stacks
-
- s.push(val)
- s.pop()
- s.top()
- s.isEmpty(): Returns true if stack is empty, else false
-
-
Queues
- hE: heaps and PQs
- Implementation:
- Priority_queues - are implemented using heaps
priority_queue<pair<int, string>>pooh; pooh.push(make_pair(1,"tigger")); // O(logn) pair<int, string> rerult = pooh.top; // O(1) pooh.pop(); // O(logn)
- Dequeue STL c++ -> std::deque
-
- Generate binary numbers from 1 to n
- Implementing k queues in single array
- Implement a stack using single queue
- Trapping Rain Water
- Generate All Parenthesis
- Min Stack
- Redundant Braces
- Nearest Smalles element
- Largest Area under histogram: 1. Using Divide and Conquer: O(nlogn) 2. Using Stacks : O(n)
- Sliding Window Maximum (Maximum of all subarrays of size k)
- N Queens
-
Hash Table
-
Trees
-
All about BST's:source code -contains all the BST algos
-
Search:
-
Traversal :Preorder, Inorder, Postorder
-
Connect Nodes at same level :Asked by Microsoft
-
[Identical Binary Tree] (http://www.geeksforgeeks.org/write-c-code-to-determine-if-two-trees-are-identical/)
-
Sum:
-
Minimum no. of iterations to pass information to all nodes in the tree
-
Find height of a special binary tree whose leaf nodes are connected
-
Convert an arbitrary Binary Tree to a tree that holds Children Sum Property
-
Vertical Sum in a given Binary Tree A.HashMap B.Doubly Linked List
-
Convert a given Binary Tree to Doubly Linked List 1.Set1 2.Set2 3.Set3 4.Set4
-
Trie -for strings/dictionary/genome
- hackerEarht
- trie- a neglected DS
- Topcoder forget not the problems at bottom
- Sedgewick video lecture
-
Fenwick Tree - for sum till indices; prob with SumArray is that it requires full updation on a single change in number array
-
Segment Tree
-
Graphs | Graph compulsion :1 place to find BFS,DFS and what not
GraphEssential :My codes for all graph algo's from hackerearth
- Graph representation:
- Objects and Pointers
- Adjacency matrix
- Adjacency list
- Edge List
- for simplified understanding-no code 2.Adjacency matrix
int AdjMat[100][100];
// Adj Matrix
// for each line: |V| entries, 0 or the weight
/*
0 10 0 0 100 0
10 0 7 0 8 0
0 7 0 9 0 0
0 0 9 0 20 5
100 8 0 20 0 0
0 0 0 5 0 0
*/
Inputting: like 2-D matrix
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
scanf("%d", &AdjMat[i][j]);
Outputting:
printf("Neighbors of vertex 0:\n");
for (int j = 0; j < V; j++)
if (AdjMat[0][j])
printf("Edge 0-%d (weight = %d)\n", j, AdjMat[0][j]);- Adjacency List: vector of vector of pairs or array of linked list
typedef pair<int, int> ii;
typedef vector<ii> vii;
vector<vii> AdjList;
/*
2 2 10 5 100
3 1 10 3 7 5 8
2 2 7 4 9
3 3 9 5 20 6 5
3 1 100 2 8 4 20
1 4 5
*/
scanf("%d", &V);
AdjList.assign(V, vii()); // quick way to initialize AdjList with V entries of vii
for (int i = 0; i < V; i++) {
scanf("%d", &total_neighbors);
for (int j = 0; j < total_neighbors; j++) {
scanf("%d %d", &id, &weight);
AdjList[i].push_back(ii(id - 1, weight)); // some index adjustment
}
}
printf("Neighbors of vertex 0:\n");
for (vii::iterator j = AdjList[0].begin(); j != AdjList[0].end(); j++)
// AdjList[0] contains the required information
// O(k), where k is the number of neighbors
printf("Edge 0-%d (weight = %d)\n", j->first, j->second);
3.Edge List
priority_queue< pair<int, ii> > EdgeList; // one way to store Edge List
scanf("%d", &E);
for (int i = 0; i < E; i++) {
scanf("%d %d %d", &a, &b, &weight);
EdgeList.push(make_pair(-weight, ii(a, b))); // trick to reverse sort order
}
// edges sorted by weight (smallest->largest)
for (int i = 0; i < E; i++) {
pair<int, ii> edge = EdgeList.top(); EdgeList.pop();
// negate the weight again
printf("weight: %d (%d-%d)\n", -edge.first, edge.second.first, edge.second.second);
}
* 2.Adjacency matrix
```cpp
int AdjMat[100][100];
/*
0 10 0 0 100 0
10 0 7 0 8 0
0 7 0 9 0 0
0 0 9 0 20 5
100 8 0 20 0 0
0 0 0 5 0 0
*/
Inputting: like 2-D matrix
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
scanf("%d", &AdjMat[i][j]);
Outputting:
printf("Neighbors of vertex 0:\n");
for (int j = 0; j < V; j++)
if (AdjMat[0][j])
printf("Edge 0-%d (weight = %d)\n", j, AdjMat[0][j]);
```
* 3. Adjacency List
```cpp
typedef pair<int, int> ii;
typedef vector<ii> vii;
vector<vii> AdjList;
/*
2 2 10 5 100
3 1 10 3 7 5 8
2 2 7 4 9
3 3 9 5 20 6 5
3 1 100 2 8 4 20
1 4 5
*/
scanf("%d", &V);
AdjList.assign(V, vii()); // quick way to initialize AdjList with V entries of vii
for (int i = 0; i < V; i++) {
scanf("%d", &total_neighbors);
for (int j = 0; j < total_neighbors; j++) {
scanf("%d %d", &id, &weight);
AdjList[i].push_back(ii(id - 1, weight)); // some index adjustment
}
}
printf("Neighbors of vertex 0:\n");
for (vii::iterator j = AdjList[0].begin(); j != AdjList[0].end(); j++)
// AdjList[0] contains the required information
// O(k), where k is the number of neighbors
printf("Edge 0-%d (weight = %d)\n", j->first, j->second);
- 4.Edge List
priority_queue< pair<int, ii> > EdgeList; // one way to store Edge List
scanf("%d", &E);
for (int i = 0; i < E; i++) {
scanf("%d %d %d", &a, &b, &weight);
EdgeList.push(make_pair(-weight, ii(a, b))); // trick to reverse sort order
}
// edges sorted by weight (smallest->largest)
for (int i = 0; i < E; i++) {
pair<int, ii> edge = EdgeList.top(); EdgeList.pop();
// negate the weight again
printf("weight: %d (%d-%d)\n", -edge.first, edge.second.first, edge.second.second);
}
vedio link:https://www.youtube.com/watch?v=5pNIul92cj0&list=PLTZbNwgO5eboNKSj5qUbXnmuGQb86PuQf&t=2
- When asked a question, look for a graph-based solution first, then move on if none.
- BFS in graph
- DFS in graph
- Graph Algorithms:
-
Single source shortest path: 1.Dijkstra's algo 2. Bellman-Ford
-
All pair shortest path Floyd Warshell
-
MSP: 1.Kruskal's algo 2. Prim's algo
-
Strongly connected components: Kosaraju's algo
-
Max Flow Ford Fulkerson/Edmonds Karp
-
Detecting cycles: * in unidirected graphs * in directed gaphs * all simple cycles in directed graphs: Johnson's algo
-
- hE: the real power of binary search
- recursive implementation
- iterative implementation
- problems:
int NoPowMod( int x, int y, int z ) { int a = x % z; int t = 1; while( y > 0 ) { // Y is odd if( y & 1 ) { t = (t * a) % z; } y >>= 1; a = (a * a) % z; } return(t); }
-
-
Bits Cheat Sheet ghot from 2^1 to 2^16 & 2^32
-
counting number of set bits in a number:
cout<< __builtin_popcount (4);//11.__builtin_popcount = int 2.__builtin_popcountl = long int 3.__builtin_popcountll = long long -
[video] to understand &, |, ^, ~, >>, << {(1 << n = 2^n), (1 >> n = 2^-n)}
-
set a given bit to 1:( it's like multiplying with 2^position )
def set_bit(x,position): // x 00000110 mask = 1 << position //position 00000101 i.e.set 5th bit to 1 return x | mask //mask 00100000 1 got r. shifted by 5 //returned value 00100110
-
clear a bit- make it 0 :( it's like dividing with 2^position )
def clear_bit(x, position): // x 00000110 mask = 1 << position //position 00000010 return x & ~mask //mask 00000100 //~mask 11111011 //returned value 00000010
-
flip bit:
def flip_bit(x, postion): // x 01100110 maks = 1 << position //position 00000010 return x ^ mask //mask 00000100 //returned value 01100010
-
is bit at given position set or not(boolean return)
def is_bit_set(x, position): // x 01100110 shifted = x >> position //position 00000101 return shifted & 1 //shifted 00000011 //returned value 00000001
- modifying bit at given position(state=1 ->set_bit; state=0 ->clear_bit )
def modify_bit(x, position, state): //state 00000001 mask = 1 << position //-state 11111111 return (x & ~mask) | (-state & mask)
-
-
1's Complement : reverse the bit
-
2's complement : reverse and add 1 from last bit
-
- Check_if_even :
if((x & 1)==0)even - check_if_power_of_2 :(means only 1 bit will be set)
if((x & x-1)==0)return true //x 1000 //x-1 0111 //& 0000
- Count the number of ones in the binary representation of the given number
while( n ){ n = n&(n-1);count++; } //O(k), k is no of one's in bin form - find the largest power of 2, which is <= x :Change all the bits which are at the right side of the most significant digit, to 1
int highestPowerof2(unsigned int n) { // Invalid input if (n < 1) return 0; int res = 1; // Try all powers starting from 2^1 for (int i=0; i<8*sizeof(unsigned int); i++) { int curr = 1 << i; // If current power is more than n, break if (curr > n) break; res = curr; } return res; }-
compute the sign of an integer:
int sign = -(x < 0) // if v < 0 then -1, else 0. -
Detect if two integers have opposite signs
bool f = ((x ^ y) < 0); // true iff x and y have opposite signs -
Compute the minimum (min) or maximum (max) of two integers without branching:
result = y ^ ((x ^ y) & -(x < y)); // min(x, y) result = x ^ ((x ^ y) & -(x < y)); // max(x, y) -
Counting bits set
for (count = 0; x; x >>= 1) { count += x & 1; } ``` -
Computing parity in given number(Parity of a number refers to whether it contains an odd or even number of 1-bits. )
unsigned int v; // word value to compute the parity of bool parity = false; // parity will be the parity of v while (v) { parity = !parity; v = v & (v - 1); }-
Swapping
#define SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b))) -
Returns the rightmost 1 in binary representation of x
x ^ ( x & (x-1)) -
Compute modulus division by 1 << s without a division operator
const unsigned int n; // numerator const unsigned int s; const unsigned int d = 1U << s; // So d will be one of: 1, 2, 4, 8, 16, 32, ... unsigned int m; // m will be n % d m = n & (d - 1);
- find log base 2 of given interger
int resulg t=0; while(x >>= 1){result++;} - [-] Add one to a number : CodePic
- Check_if_even :
-
Problems:
- check-binary-representation-number-palindrome
- Reverse bits
- Single Number
- Divide without dividing
- nth magic number
- Single Number 1
- single Number 2
- Count set bits in an integer
- Count total set bits in all numbers from 1 to n
- Swap bits in a given number
- Count number of bits to be flipped to convert A to B
- n-th number whose binary representation is a palindrome
- Check whether all the bits are set in the given range
- Find the Maximum of Two Integers without Comparison Logic: if(a-b >=0, max(a,b)=a;else max(a,b) = a-(a-b)
-
-
- CS50 :
- Visual Representation : pure gold
- Sorting algo: - Bubble sort - Insertion - Selection - Merge - Quick - Heap - Radix || hE
- Merged Sort For Linked list
- Median of stream of running integers
- FUN- visual representation of 15 sorting algorithms
-
- Orientation
- To see if 2 lines intersect or not.Find all the 4 slopes and check of opposite orientation of both the pairs.
- Convex Hull
-
Jarvis Algorithm. Time Complexity: n^2
- Pick the leftmost point P
- Repeat until P is reached:
- Next point Q is such that pair (p,q,r) is in anticlock orientataion.
- next[P] = Q
- P = Q
-
Graham's Algorithm. Time Complexity: nlogn
- Initialize bottom-most(leftmost, if multiple) point P.
- Sort all points w.r.t P to find the closed path.
- Move on the path and pick a point if counter-clock rotation found.
-
- Orientation
-
- hE: DP for beginners
- DP:Novice to Advanced-Topcoder Awesome thou art.
- everythingOnDP-codeforces-Noobs don't try
-
Here's a short video to understand how to form a DP table.Implementation:
int knapsack(int n, int wmax, int val[], int wt[]){ if(n==0 || wmax ==0){ return 0; } else if(wt[n-1] > wmax) return knapsack(n-1, wmax, val, wt); else return max(val[n-1]+ knapsack(n-1, wmax- wt[n-1],val, wt), knapsack(n-1, wmax,val, wt)); }
-
Matrix Chain Multiplication
lite
-
Video link Just see this and move on.
if(j<set[i-1]) subset[i][j] = subset[i-1][j]; if (j >= set[i-1]) subset[i][j] = subset[i-1][j] || subset[i - 1][j-set[i-1]];
-
- TBDL
-
Coin Change Simple shit
-
Longest Increasing Subsequence
- n^2
- nlogn
- Examples:
- ZigZag : if(a[i].a[j]<0) z[i] = 1+max(d[i],d[j]);
- Bad Neighbours
- Flower Garden
-
Egg Dropping Problem Intresting one! This video is alone enough.
-
That blow(sigh!)
- Examples:
- Chess Metric
- Avoid Road
- top->bottom->top MiniPaint
- Examples:
-
Maximum Sum Rectangular Submatrix in Matrix Uses kadane's algorithm for 2D array.
-
Standard Problems should be really familiar with these types
-
State Space Reduction
- [ ]
-
- hE:Exact string matching algorithms
- Print all permutations of a string 1.w/o STL 2.with STL 3.see this
- smallest window in a string containing all characters of another string
- Minimum number of bracket reversals needed to make an expression balanced
- Given a string, find its first non-repeating character
- Minimum number of deletions to make a string palindrome
- Multiply strings
- Text Justification
-
- Gas station My code
- stock buy and sell
- Activity Selection Problem
- Kruskal’s Minimum Spanning Tree Algorithm
- Prim's MST
- Huffman Coding
- KMP
- Rearrange characters in a string such that no two adjacent are same
- Rearrange a string so that all same characters become d distance away
- Fitting Shelves Problem
- Egyptian Fraction
- Find if two rectangles overlap
-
- NP complete
- halting problem
- Turing Machine
- P, NP complete, NP hard:
- Near optimal solution for tavelling salesman problem
- NP complete
Puzzles: | technical interview puzzles set | GfG puzzles set : must do
- Daughters age
- cross the bridge
- Divide the cake
- 2 Eggs and 100 Floors
- Ratio of Boys and Girls in a Country where people want only boys
Math
- [Nth Fibonaccii no.s] (http://practice.geeksforgeeks.org/problems/nth-fibonacci-number/0) my soln
- Find the median- my soln- my diff soln
- Count the squares- my soln
- Trailing zeros in Factorial- my soln
Sorting
Binary Search
- Rotated Sorted Array SearchBookmark Suggest Edit
- Cout Squares
- Find the Median
- comparing the time in linear search and binary search soln
Arrays
String
- Reverse a string word by word
- Implement strstr()
- Integer to Roman
- Length of last word
- Search in an array of strings where non-empty strings are sorted
linkedlist
- Find middle element in a linked list my soln
- n'th node from end of the linked list my soln
- Occurence of an integer in a linked list my soln
- Remove duplicate from sorted linked list- my soln -my diff soln
- Pairwise swap elements of a linked list by swaping data- my soln
- linked list insertion - my soln
- Swap linked list nodes in pairs
- Count nodes of linked list my soln
- node at a given index of linked list my soln
Tree
- Level order traversal- my sol
- k distancefrom root- my soln
- Lowest common ancestor in binary tree- my soln
- LevelOrderTraversal using queue lib and vector stl in c++
- Level Order traversal lineby line
- Lowestcommon ancester in BST- my soln
Graph
Greedy
Dyanamic Programming
- Kadane's Algorithm my soln
- Longest increasing subsequence my soln
- Edit distance- my soln
- Longest Common Subsequence- my soln
Stacks
** Computer Network video link** https://www.youtube.com/channel/UCJjC1hn78yZqTf0vdTC6wAQ/playlists
Bit Manipulation
Graphs