gRPC and REST API

gRPC : 

gRPC (gRPC Remote Procedure Call) is a modern, open-source framework developed by Google for making remote procedure calls. It uses Protocol Buffers (protobuf) as its interface definition language and data serialization format, allowing for efficient communication between services.
gRPC uses HTTP/2, which allows for multiplexing, reducing the latency and improving the performance compared to traditional HTTP/1.1 used by REST APIs. It also uses Protocol Buffers (protobuf) for data serialization, which is more efficient than JSON.

Pros:

• Performance and Efficiency: gRPC uses HTTP/2, which allows for multiplexing, reducing the latency and improving the performance compared to traditional HTTP/1.1 used by REST APIs. It also uses Protocol Buffers (protobuf) for data serialization, which is more efficient than JSON
• Bi-directional Streaming: gRPC supports client, server, and bi-directional streaming, enabling real-time communication and more efficient handling of large data transfers.
• Cross-platform and Multi-Language Support
• Built-in Error Handling and Metadata: gRPC has standardized mechanisms for handling errors and sending metadata

Cons:

• Complexity: gRPC can be more complex to set up and understand, particularly for developers who are not familiar with Protocol Buffers and HTTP/2.
• Limited Browser Support:
• Less Human-Readable: Protocol Buffers are binary, which makes them less human-readable compared to the JSON format commonly used with REST APIs.

Use Cases:

• High performance and efficiency are crucial, such as in microservices communication.
• You need real-time communication features like streaming.
• You have a polyglot environment where multiple programming languages are used.
• You prefer a strongly typed schema and strict contract between client and server.

Factorization with prime Sieve

1. vector <int> prime; char sieve[1000009]; int N=1000009; void primeSieve ( ) { sieve[0] = sieve[1] = 1; prime.push_back(2); for ( int i = 4; i <= N; i += 2 ) sieve[i] = 1; int sqrtn = sqrt ( N ); for ( int i = 3; i <= sqrtn; i += 2 ) { if ( sieve[i] == 0 ) { for ( int j = i * i; j <= N; j += 2 * i ) sieve[j] = 1; } } for ( int i = 3; i <= N; i += 2 ) if ( sieve[i] == 0 ) prime.push_back(i); }
2. vector <int> factors; void factorize( ll n ) { ll sqrtn = sqrt ( n ); for ( ll i = 0; i < prime.size() && prime[i] <= sqrtn; i++ ) { if ( n % prime[i] == 0 ) { while ( n % prime[i] == 0 ) { n /= prime[i]; factors.push_back(prime[i]); } sqrtn = sqrt ( n ); } } if ( n != 1 ) { factors.push_back(n); } }

Longest Increasing Subsequence & Path Print (LIS)

class Solution {

public:

    int lengthOfLIS(vector<int>& nums) {

        int n = nums.size();

        vector<int> sub, subIndex; 

        vector<int> path(n, -1); 

        for (int i = 0; i < n; ++i) {

            if (sub.empty() || sub[sub.size() - 1] < nums[i]) {

                path[i] = sub.empty() ? -1 : subIndex[sub.size() - 1];

                sub.push_back(nums[i]);

                subIndex.push_back(i);

            } else {

                int idx = lower_bound(sub.begin(), sub.end(), nums[i]) - sub.begin();

                path[i] = idx == 0 ? -1 : subIndex[idx - 1];

                sub[idx] = nums[i];

                subIndex[idx] = i;

            }

        }

        vector<int> ans;

        int t = subIndex[subIndex.size() - 1];

        while (t != -1) {

            ans.push_back(nums[t]);

            t = path[t];

        }

        reverse(ans.begin(), ans.end());

        for(int i=0;i<ans.size();i++){

            cout<<ans[i]<<" ";

        }

        cout<<endl;

        return ans.size();

    }

};

Longest non-decreasing subsequence - TC: O(nlogn)

int longestNonDecresingSubsequenceLength(vector<int> a) {

    vector<int> s;

    s.push_back(a[0]);

    int n = a.size();

    int len = 1;

    for (int i = 1; i < n; i++) {

        int idx = upper_bound(s.begin(), s.end(), a[i]) - s.begin();

        int m = s.size();

        if (m > idx) {

            s[idx] = a[i];

        } else {

            s.push_back(a[i]);

        }

    }

    return s.size();

}

Mobius Inversion (Mobius Precalculate)

 const ll N=1e6+5;

ll lp[N];

ll mob[N];

void mobiusPreCalc(){

    mob[1] = 1;

    for (ll i = 2; i < N; ++i) {

        if (!lp[i]) for (ll j = i; j < N; j += i)

            if (!lp[j]) lp[j] = i;

        mob[i] = [](ll x) {

            ll cnt = 0;

            while (x > 1) {

                ll k = 0, d = lp[x];

                while (x % d == 0) {

                    x /= d;

                    ++k;

                    if (k > 1) return 0;

                }

                ++cnt;

            }

            if (cnt & 1) return -1;

            return 1;

        }(i);

    }

}

Detect Cycle and Print Cycle in an directed Graph

Problem :

https://leetcode.com/problems/course-schedule-ii/ 

class Solution {

public:

    vector<int>vis;

    vector<int>vec[5005];

    vector<int> ans;

    bool dfsAndReturnCycle(int src)

    {

        if(vis[src] == 1) 

            return true;

        if(vis[src] == 2) 

            return false;

        vis[src] = 1; 

        for (const auto& nextNode: vec[src])

        {

if(dfsAndReturnCycle(nextNode))

                return true;

        }

        vis[src] = 2;

        ans.push_back(src);

        return false;

        

    }

    vector<int> findOrder(int numCourses, vector<vector<int>>& ar) {

        int n=ar.size();

        for(int i=0;i<n;i++){

            int v=ar[i][0];

            int u=ar[i][1];

            vec[u].push_back(v);

        }

        int flag=0;

        vis = vector<int>(numCourses+2,0);

        for(int i=0;i<numCourses;i++)

        {

            if(vis[i]==0){

                if(dfsAndReturnCycle(i))

                {

                    return {};

                }

            }

        }

        reverse(ans.begin(),ans.end());

        return ans;

    }

};

FREQ2 - Most Frequent Value- Using Mo's Algorithm

You are given a sequence of n integers a0, a1, ..., an-1. You are also given several queries consisting of indices i and j (0 ≤ i ≤ j ≤ n-1). For each query, determine the number of occurrences of the most frequent value among the integers ai, ..., aj.

Mo's Algorithm Related Problem:

1) DQUERY - D-query , 2) FREQ2 - Most Frequent Value , 3) D. Cut and Stick  , 4) D. Powerful array , 5) Chef and Graph Queries 6) D. Tree and Queries 7) Sherlock and Inversions

   

 

///...................SUBHASHIS MOLLICK...................///

///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///

///.............ISLAMIC UNIVERSITY,BANGLADESH.............///

///....................SESSION-(14-15)....................///

#include<bits/stdc++.h>

using namespace std;

#pragma GCC target ("avx2")

#pragma GCC optimization ("O3")

#pragma GCC optimization ("unroll-loops")

#define sf(a) scanf("%d",&a)

#define sf2(a,b) scanf("%d %d",&a,&b)

#define sf3(a,b,c) scanf("%d %d %d",&a,&b,&c)

#define pf(a) printf("%d",a)

#define pf2(a,b) printf("%d %d",a,b)

#define pf3(a,b,c) printf("%d %d %d",a,b,c)

#define sfl(a) scanf("%lld",&a)

#define sfl2(a,b) scanf("%lld %lld",&a,&b)

#define sfl3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)

#define pfl(a) printf("%lld",a)

#define pfl2(a,b) printf("%lld %lld",a,b)

#define pfl3(a,b,c) printf("%lld %lld %lld",a,b,c)

#define nl printf("\n")

#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define ll long long

#define pb push_back

#define MPI map<int,int>mp;

#define fr(i,n) for(i=0;i<n;i++)

#define fr1(i,n) for(i=1;i<=n;i++)

#define frl(i,a,b) for(i=a;i<=b;i++)

#define tz 100005

#define clr0(a) memset(a,0,sizeof(a))

#define clr1(a) memset(a,-1,sizeof(a))

#define space " "

#define yesp cout<<"YES"<<endl;

#define nop cout<<"NO"<<endl;

/*primes in range 1 - n

1 - 100(1e2) -> 25 pimes

1 - 1000(1e3) -> 168 primes

1 - 10000(1e4) -> 1229 primes

1 - 100000(1e5) -> 9592 primes

1 - 1000000(1e6) -> 78498 primes

1 - 10000000(1e7) -> 664579 primes

large primes ->

104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697

*/

//freopen("Input.txt","r",stdin);

//freopen("Output.txt","w",stdout);

//const int fx[]={+1,-1,+0,+0};

//const int fy[]={+0,+0,+1,-1};

//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move

//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move

//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move

//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move

#define flagone(f) cout<<(f?"YES":"NO")<<endl;

#define flagzero(f) cout<<(f?"NO":"YES")<<endl;

int ar[tz],cnt[tz],ans[tz],freq[tz];

struct node

{

    int lft,right,index;

};

int mx=0;

node query[tz];

int blockSize=317;

bool cmp(node fst,node scnd)

{

    if(fst.lft/blockSize == scnd.lft/blockSize)

    {

        return fst.right/blockSize < scnd.right/blockSize;

    }

    return fst.lft<scnd.lft;

}

void addValue(int pos)

{

    cnt[ar[pos]]++;

    freq[cnt[ar[pos]]]++;

    mx=max(mx,cnt[ar[pos]]);

}

void removeValue(int pos)

{

    freq[cnt[ar[pos]]]--;

    if(freq[cnt[ar[pos]]]==0)

        mx--;

    cnt[ar[pos]]--;

}

main()

{

    timesave;

    //freopen("Input.txt","r",stdin);

    //freopen("Output.txt","w",stdout);

    int n,q,a,b;

    sf2(n,q);

    for(int i=0; i<n; i++)

    {

        sf(ar[i]);

    }

    for(int i=0; i<q; i++)

    {

        sf2(a,b);

        query[i].lft=a;

        query[i].right=b;

        query[i].index=i;

    }

    sort(query,query+q,cmp);

    int leftPointer = 0,rightPointer=0;

    for(int i=0; i<q; i++)

    {

        int leftValue = query[i].lft;

        int rightValue = query[i].right;

        int queryIndex = query[i].index;

        while(leftPointer<leftValue)

        {

            removeValue(leftPointer);

            leftPointer++;

        }

        while(leftPointer>leftValue)

        {

            addValue(leftPointer-1);

            leftPointer--;

        }

        while(rightPointer<=rightValue)

        {

            addValue(rightPointer);

            rightPointer++;

        }

        while(rightPointer>rightValue+1)

        {

            removeValue(rightPointer-1);

            rightPointer--;

        }

        ans[query[i].index]=mx;

        //cout<<leftValue<<" "<<rightValue<<" "<<mx<<endl;

    }

    for(int i=0; i<q; i++)

    {

        printf("%d\n",ans[i]);

    }

}