Posts

Hashing

When we cannot use hashing -  when  order is important =>  Find key which is just smaller than the given key. COMPRESSION  MAP  => H(key) = key % M (M is prime number close to table size)  POLYNOMIAL  ACCUMULATION  =>  H(string) = [(s[0]*x^0) +  (s[1]*x^1) +  ....] % M   Requirements for hash function => H(key) = value No matter how many times you pass key => value should always be same If M is size of hash table => value must lie between 0 to M-1 Value should be uniformly distributed --> less collision UNIVERSAL  HASHING -  choose any hash function uniformly at random
Post a Comment
Read more

Policy based data structures (PBDS)

Implement set with the ability to know index of item  --> data structure order statistics tree, (unfortunately only available for the GNU C++) g++ compiler supports some data structures that are not part of standard C++ library ---> such structures are called policy-based data structures #include <ext/pb_ds/assoc_container.hpp> // Common file #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update using namespace __gnu_pbds ; template < typename Key , // Key type typename Mapped , // Mapped-policy --> USE null_type for sets (bcz no mapping) typename Cmp_Fn = less < Key >, // Key comparison functor typename Tag = rb_tree_tag , // Specifies which underlying data structure to use class Node_Update = null_node_update , // A policy for updating node invariants > Node_Update  — class denotes policy for updating node invariants. By default, set to  null_node_update , i.e, a...
Post a Comment
Read more

Graphs

Image
GRAPH  Modelling - Multi-Source BFS --> Use normal BFS but insert all the sources in queue and make their distance = 0 --> Update the distance for others as usual for normal BFS ( Link ) Transform existing Graph and use BFS (non-weighted) & Dijkstra (weighted) Hot (red)  -  Cold (blue)  problem => Update graph s.t. red & blue are alternate  make 2*n nodes as A => A' and A'' connect A' -> B'' (for hot) and A'' -> B' (for cold) Directed - weighted G + can remove k edges make G => k+1 times as A', A'', A''', ..... Add edge of weight 0 in between the k+1 graphs n city + m roads + max storage (c litre) => weighted road (consume w litre) + cost[i] (cost per litre to refuel at i-th point) => min. cost from s to t We have to move from A to B  capacity = 3. From A -> A' -- 1 litre needed at value in cost array. From A''' -> B' because loss of 2 litres (as shown in the below d...
Post a Comment
Read more

Basics

Comment -  for In-line comment (means comment in same line) --> Use //                          for multi-line comment --> Use /* ........ */ Array -  int arr[10] = {4, 5, 8} --> creates array of size 10 with first 3 elements known  Access - 10[arr] or arr[10]  --> both correct bcz *(10+arr) and *(arr+10) are same Pair -  pair<int,string> p  = {2 , "fsf"} How to access ? p.first and p.second Vector -  array with dynamic memory size =>  continuous memory allocation How to  initialize vector ? vector <double> v(10) => declares vector of size 10 with each value as 0 vector <double> v(7 , 3) => declares vector of size 7 with each value as 3 vector <double> v = {1, 3, 5, 10} => declares vector of with given values vector <double> v(st.begin(), st.end()) => declares vector from given set vector <int> v1 =v  ...
Post a Comment
Read more

File Handling

BENEFITS  OF  FILE  HANDLING give permanent storage facility can access huge chunk of data in instant (bcz RAM is of small size -> can't store huge data) easy to transfer data as files
Post a Comment
Read more

Stack + Queue + Priority queue

                                                                 STACK //while pushing top++ and while pop top-- in full stack TOP=Max-1 and empty stack ->top = -1 Stack is full and we are pushing => overflow Stack is empty and we are popping => underflow                                                              QUEUE empty queue -> front = - 1  and rear = - 1 if inserted ,i.e., enqueue => rear++ if deleted ,i.e., dequeue => front++ {NOTE:- front is index before first element} eg .- _523 =>front is 0 bcz 1st element '5' is at index 1              ...
Post a Comment
Read more