Skip to content

all_programs_list.md

Latest commit

 

History

History
1458 lines (1151 loc) · 87 KB

all_programs_list.md

File metadata and controls

1458 lines (1151 loc) · 87 KB

program list

  1. maximum sum problem
  2. kth smallest element
  3. minimum jump required
  4. count bits 11 making a meal
  5. count bit difference
  6. swap two nibbles in a byte
  7. Please do it, count no ofoccurance of digit in a range
  8. [tree ] count no of unique binary tree
  1. https://www.geeksforgeeks.org/combinational-sum/
  2. https://www.geeksforgeeks.org/find-all-combinations-that-adds-upto-given-number-2/

New Session Geeks

Linked List

interview Bit:

Reference:

  1. [Algo Advances])(https://www.cs.rit.edu/~ib/#teach)(https://www.cs.rit.edu/~ib/Classes/CSCI261_01_Fall17-18/assignments.html)
  2. Algo Lecture MIT
  3. Analysis Algo
  4. Design Algo Good

Puzzles:

CodeChef:

Contribution in month of june

contribution on 1-7-19

contribution on 2-7-19 :

contribution on 3-7-19 :

contribution on 4-7-19

contribution on 5-7-19

contribution on 6-7-19

contribution 7-7-17

contribution on 8-7-19

contribution on 11-7-19

Contribution on 14-7-19

Contribution on 15-7-19

Contribution on 18-7-19

contribution on 18-7-19

contribution on 21-7-19

contribution 22-7-19

contribution on 23-7-19

contribution on 26-7-19

Contribution on 27-7-19

contribution on 29-7-19

Contribution on 30-7-19

contribution on 31-7-19

contribution on 1-8-19

contribution on 2-8-19

contribution on 3-8-19 (very imp day)

contribution on 5-8-19

contribution on 12-8-19

Contribution on 13-8-19

Contribution on 14-8-19

Contribution on 15-8-19

Contribution on 16-8-19

Contribution on 17-8-19

Contribution on 19-8-17

Contribution on 20-8-19

Contribution on 22-8-19

Contribution on 23-8-19

Contribution on 24-8-19

Contribution on 26-8-19

Contribution on 31-8-19

Contribution on 2-9-19

Contribution on 3-9-19

Contribution on 6-9-19

Contribution on 17-9-19

Contribution on 18-9-19

Contribution on 19-9-19

Contribution on 20-9-19

Contribution on 21-9-19

Contribution on 24-9-19

Contribution on 25-9-19

Contribution on 30-9-19

Contribution on 1-10-19

Contribution on 2-10-19

Contribution on 4-10-19

Contribution on 7-10-19

Contribution on 8-10-19

Contribution on 9-10-19

Contribution on 10-10-19

Contribution on 11-10-19

Contribution on 12-10-19

Contribution on 15-10-19

Contribution on 16-10-19

Contribution on 17-10-19

Contribution on 18-10-19

Contribution on 19-10-19

Contribution on 20-10-19

Contribution on 21-10-19

Contribution on 22-10-19

Contribution on 23-10-19

Contribution on 24-10-19

Contribution on 25-10-19

Contribution on 26-10-19

Contribution on 27-10-19

Contribution on 28-10-19

Contribution on 29-10-19

Contribution on 30-10-19

Contribution on 31-10-19

Contribution on 1-11-19

Contribution on 4-11-19

Contribution on 10-11-19

Contribution on Jan, 2020

Random Day contribution

undone

https://leetcode.com/articles/sum-of-distances-in-tree/# https://www.hackerrank.com/contests/test-contest-27/challenges/paintwall/problem https://www.geeksforgeeks.org/painting-fence-algorithm/ https://www.geeksforgeeks.org/painters-partition-problem/ https://www.geeksforgeeks.org/m-coloring-problem-backtracking-5/

Undone

https://leetcode.com/problems/largest-plus-sign/ https://leetcode.com/problems/coloring-a-border/ https://www.geeksforgeeks.org/given-matrix-o-x-find-largest-subsquare-surrounded-x/ https://leetcode.com/problems/largest-1-bordered-square/ https://leetcode.com/problems/minimum-area-rectangle-ii/ https://www.geeksforgeeks.org/maximum-size-rectangle-binary-sub-matrix-1s/ https://leetcode.com/problems/construct-the-rectangle https://leetcode.com/problems/minimum-area-rectangle/

Very good references (premium problem from leetcode)

Database

  1. https://www.youtube.com/playlist?list=PLyvBGMFYV3auVdxQ1-88ivNFpmUEy-U3M
  2. https://www.youtube.com/playlist?list=PLRFPL_aa_SLVjQn93cUGZaKZVGr_80vYv
  3. https://www.youtube.com/playlist?list=PL9426FE14B809CC41
  4. https://www.youtube.com/playlist?list=PL52484DF04A264E59

Important Stuff

Custom comparators

struct myData{
    string key, value;
};

struct compare{
    bool operator()(const myData &lhs, const myData &rhs) const{
        return lhs.key < rhs.key;
    }
};
set<myData, compare> mySet;
mySet.insert(myData{"Hii"})

Sorting (customize at same place):

sort(begin(cs), end(cs), [](vector<int> &v1, vector<int> &v2) {
    return (v1[0] - v1[1] < v2[0] - v2[1]);
  });
  1. Modulo Operator for output ((a-b)%m = (a%m - b%m + m)%m)
consider this: (14-1)%7. If you just do ((14%7 - 1%7)%7), you will get -1(considering implementation in C/C++). That's why add divisor before final division. (14%7 - 1%7 + 7)%7 = 6 which is the expected answer. And when the result of first two modular divions is non-negative adding divisor won't affect the result which is easy to prove. Hope you get the logic.
  1. Init struct
struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };

Break and Convert a string into integer and string

Input: logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]
struct Log {
    int id;
    string status;
    int timestamp;
};

for(string log: logs) {
    stringstream ss(log);
    string temp, temp2, temp3;
    getline(ss, temp, ':');
    getline(ss, temp2, ':');
    getline(ss, temp3, ':');

    Log item = {stoi(temp), temp2, stoi(temp3)};
  1. Pass Struct Node as reference
void call_func(TreeNode* &root){
    root->left = new TreeNode(10); // we access orig node, which is passed as pointer in call_func function.
}

void main()
{
    TreeNode* root = NULL;
    call_func(root);
}
  1. Class Constructor in one line
Rectangle (int x, int y) : width(x), height(y) { }
  1. String to int (STL):
1. Use C++ standard library std::stringstream.

#include <sstream>
#include <string>

std::string text = "123";
int number;
std::istringstream iss (text);
iss >> number;
if (iss.fail()) {
  // something wrong happened
}

2. Use std::stoi() function from C++ standard library since C++11.

#include <iostream>
#include <string>

int main ()
{
  std::string str("123");
  int n = std::stoi(str);
  std::cout << str << " --> " << n << std::endl;
  return 0;
}
  1. Easy method to return vector
    return vector<int> ({1,2});
or
    return {1,2};

Inline Function

  • No control tranfer
  • copy the function in the place where it is called at compile time.

bit manipulation

  • n & (n-1) drops lowest set bit
  • to count all set bit: use while (n) { n &= (n - 1); count++; }

sorting different method

A simple example using std::sort

struct MyStruct{
    int key;
    std::string stringValue;

    MyStruct(int k, const std::string& s) : key(k), stringValue(s) {}
};

struct less_than_key{
    inline bool operator() (const MyStruct& struct1, const MyStruct& struct2){
        return (struct1.key < struct2.key);
    }
};

std::vector < MyStruct > vec;

vec.push_back(MyStruct(4, "test"));
vec.push_back(MyStruct(3, "a"));
vec.push_back(MyStruct(2, "is"));
vec.push_back(MyStruct(1, "this"));

std::sort(vec.begin(), vec.end(), less_than_key());

Edit: As Kirill V. Lyadvinsky pointed out, instead of supplying a sort predicate, you can implement the operator< for MyStruct:

struct MyStruct
{
    int key;
    std::string stringValue;

    MyStruct(int k, const std::string& s) : key(k), stringValue(s) {}

    bool operator < (const MyStruct& str) const
    {
        return (key < str.key);
    }
};

Using this method means you can simply sort the vector as follows:

std::sort(vec.begin(), vec.end());

Edit2: As Kappa suggests you can also sort the vector in the descending order by overloading a > operator and changing call of sort a bit:

struct MyStruct
{
    int key;
    std::string stringValue;

    MyStruct(int k, const std::string& s) : key(k), stringValue(s) {}

    bool operator > (const MyStruct& str) const
    {
        return (key > str.key);
    }
};

And you should call sort as:

std::sort(vec.begin(), vec.end(),greater<MyStruct>());

map with key as pair:

Note: unordered_map is hash, that throw error with key as pair, there exist a method, by overloading size operator and redefine template using hash function. But simple is following Alterning:

    map<pair<int, int>, int> vis;
    for(int i=0; i<10; i++){
        vis[{i,i}] = i;
    }
    for(auto c : vis){
        cout<<c.first.first<<" "<<c.first.second<<" "<<c.second<<endl;
    }
    
    // if(Vis.count(mpa(x, y)))
    //      continue;
    // Vis[mpa(x, y)] = true;

definition of node for trees/linked-list:

class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node() {}

    Node(int _val, Node* _next, Node* _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};

priority queue init

class custom_pq{
public:
    int d, x, y;
    custom_pq(int d_, int x_, int y_):
    d(d_), x(x_), y(y_){}
};

bool operator<(const custom_pq &p1, const custom_pq &p2){
    return (p1.d > p2.d);
}

priority_queue<custom_pq> pq;
struct custom_pq{
    int d, x, y;
    custom_pq(int d_, int x_, int y_):
    d(d_), x(x_), y(y_){}
};

struct custom_sort{
    bool operator()(const custom_pq &p1, const custom_pq &p2){
        return (p1.d > p2.d);
    }
};

priority_queue<custom_pq, vector<custom_pq>, custom_sort> pq;

type define

#define ll long long int
#define mod 1000000007

typedef long long int ll;

Return dynamic array

  • use static keyword
int* topoSort(int V, vector<int> adj[]){
    static int ans[max_size];
    return ans;
}

find in multimap

#include<bits/stdc++.h>
using namespace std;

int main()
{
    multimap<int,int> map;
    map.insert({1,204});
    map.insert({1,202});
    map.insert({1,201});
    map.insert({2,200});
    map.insert({2,290});

    typedef std::multimap<int, int>::iterator MMAPIterator;
 
    // It returns a pair representing the range of elements with key equal to 'c'
    std::pair<MMAPIterator, MMAPIterator> result = map.equal_range(1);
 
    for (MMAPIterator it = result.first; it != result.second; it++)
        std::cout << it->second << std::endl;
 }

char to string

  • string s(1, ch);
  • string s; s.push_back(ch);
  • s = c;
  • string s; s += c;

stringstream

    istringstream ss(s);
    string word;
    while(ss >> word){
        cout<<word<<"\t";
    }

Careful with the usuage of set and unordered_set

char ch[] ={'a','b','a','e','d'};
set<char> vis;
unordered_set<char> visi;

Output:
a b d e  :: sorted and order maintain according to first unique value
d e a b  :: not sorted and order is maintained in reverse order

Fixed number of digit after decimal

#include <bits/stdc++.h>
using namespace std;
#define FIXED_FLOAT(x) std::fixed <<std::setprecision(2)<<(x)

int main()
{
    int a, b;
    a = 1000;
    b = 3;
    float c = a/(b*1.0);
    cout<<c<<endl;;
    // cout<<fixed<<setprecision(2)<<c<<endl;
    cout<<FIXED_FLOAT(c)<<endl;
    cout<<c<<endl;
    cout<<a<<endl;
    cout<<b<<endl;
    cout<<1.2345<<endl;

    // simple trick, convert it manually, using multiplication and division
    float ans = (int(c*10))*1.0/10.0;
    cout<<ans<<endl;

    return 0;
}

char array to string

char a[] = {'C','O','D','E' }; 
char b[] = "geeksforgeeks"; 

string sa = a; 
string sb = b;

char array to string

string s = "geeksforgeeks"; 
int n = s.length();  
char char_array[n + 1];  
strcpy(char_array, s.c_str());

2nd approach:

string s = "Hello World!";
char cstr[s.size() + 1];
copy(s.begin(), s.end(), cstr);
cstr[s.size()] = '\0';
cout << cstr << '\n';

Random number generation with equal probability

#include <ctime>

template<class T>
T *FindMRandom(T *array, int m){
    int m, n = array.size();
    T *temp = new T[m];
    srand((unsigned )time(0));

    for (int i=0; i<m; ++i ){
        m = rand() % (n-i);
        temp[i] = array[m];
        Swap(array[m], array[n-i-1]);
    }
    return temp;
}
/*
It seems to me that the second element's probability is not 1/n-1. It is the probability that it is *not* chosen the first time (n-1/n) times the probability that it *is* chosen the second time (1/n-1).

(n-1/n)*(1/n-1) = 1/n

For the third element:

(n-1/n)*(n-2/n-1)*(1/n-2) = 1/n

*/

Dynamic memory allocation to 3d matrix

    int M = 2, N = 3, O = 4;
    int* A = (int*)malloc(M * N * O * sizeof(int));
    // assign values to allocated memory
    for (int i = 0; i < M; i++)
        for (int j = 0; j < N; j++)
            for (int k = 0; k < O; k++)
                *(A + i*N*O + j*O + k) = rand() % 100;

    // to print, use: printf("%d ", *(A + i*N*O + j*O + k));
    // deallocate memory
    free(A);

Dynamic expand array

int *p;
p = new int[5];
for(int i=0;i<5;i++)
   *(p+i)=i;

// realloc
int* temp = new int[6];
std::copy(p, p + 5, temp); // Suggested by comments from Nick and Bojan
delete [] p;
p = temp;