int solution(int N, vector<int>& A, vector<int>& B) {
    vector<vector<int>> graph(N);
    vector<int> edgesCount(N, 0);

    for (int i = 0; i < A.size(); i++) {
        edgesCount[A[i]]++;
        edgesCount[B[i]]++;
        graph[A[i]].push_back(B[i]);
        graph[B[i]].push_back(A[i]);
    }

    queue<int> q;
    for (int i = 0; i < N; i++) {
        if (edgesCount[i] <= 1) {
            q.push(i);
        }
    }

    int seconds = 0;
    while (!q.empty()) {
        int size = q.size();
        while (size > 0) {
            int vertex = q.front();
            q.pop();
            for (int neighbor : graph[vertex]) {
                if (edgesCount[neighbor] > 0) {
                    edgesCount[neighbor]--;
                    if (edgesCount[neighbor] == 1) {
                        q.push(neighbor);
                    }
                }
            }
            edgesCount[vertex] = 0;
            size--;
        }
        seconds++;
    }

    return seconds;
}

minimum time Microsoft

https://t.me/oadiscussion

Join here for question and free help of oa

Ttl Genpact make sure to remove plag

Genpact code are repeating so make sure to save it somewhere and mcq too

https://t.me/oahelp

Make sure to share the channel phir yahi se utha kar ye scammers bech dete ha dusre grp mai...also will motivate me too post more solutions❤️

#define ll long long

int mod = 1e9 + 7;

ll calcpower(ll x, ll n)
{
    if (n == 1)
    {
        return x;
    }
    ll temp = calcpower(x, n / 2);
    if (n & 1)
    {
        return ((((x * temp) % mod) * temp) % mod);
    }
    return (temp * temp) % mod;
}

// Fermat's Little Theorem : a^p=a mod(p)  =>   a^(p-2)=(a^-1)mod(p)
ll modinv(ll num)
{
    return calcpower(num, mod - 2);
}

// Z-Algorithm
vector<int> calculateZ(string &s)
{
    vector<int> z(s.size(), 0);
    int l = 0;
    int r = 0;
    for (int k = 1; k < s.size(); k++)
    {
        if (k > r)
        {
            l = r = k;
            while (r < s.size() && s[r] == s[r - l])
            {
                r++;
            }
            z[k] = r - l;
            r--;
        }
        else
        {
            int k1 = k - l;
            if (z[k1] < r - k + 1)
            {
                z[k] = z[k1];
            }
            else
            {
                l = k;
                while (r < s.size() && s[r] == s[r - l])
                {
                    r++;
                }
                z[k] = r - l;
                r--;
            }
        }
    }
    return z;
}

int numberOfWays(string s, string t, long long k)
{
    if (s.size() != t.size())
    {
        return 0;
    }
    string temp = t;
    temp += '$';
    temp += s;
    temp += s;

    vector<int> z = calculateZ(temp);
    vector<long long> v;
    int n = s.size();
    if (k % 2 == 0)
    {
        v.resize(n, (((calcpower(n - 1, k) - 1) * modinv(n)) % mod));
        v[0] += 1;
        v[0] %= mod;
    }
    else
    {
        v.resize(n, (((calcpower(n - 1, k) + 1) * modinv(n)) % mod));
        v[0] -= 1;
        v[0] += mod;
        v[0] %= mod;
    }

    int ans = 0;
    for (int i = 0; i < z.size(); i++)
    {
        if (z[i] == t.size())
        {
            if (i - t.size() - 1 >= 0 && i - t.size() - 1 < n)
            {
                ans += v[i - t.size() - 1];
            }
            ans %= mod;
        }
    }

    return ans % mod;
}

int getNumWays(string src, string target, int k)
{
    return numberOfWays(src, target, k);
}

NLP atlassian

int countAnalogousArrays(vector<int>& arr, int lower, int higher) { 
    int max = std::numeric_limits<int>::min();  
    int n = lower; 
    for (int i = 0; i < arr.size(); i++) { 
        int k = arr[i]; 
        int k1 = n - k; 
 
        if (k1 > higher || k1 < lower) { 
            return 0; 
        } 
 
        n = k1; 
        max = std::max(max, n); 
    } 
 
    max = higher - max + 1; 
 
    return max; 
}

analogus array atlassian

long getMaximumScore(vector<int> v)
{
    int n=v.size();
    map<int,vector<int>> mp; 
    for(int i=0;i<n;i++)
    {
       mp[v[i]-i].push_back(v[i]);
    }
    long ans=0;
    for(auto v:mp)
    {
        long sum=0;
        for(auto it: v.second)
        {
            sum+=it;
        }
        ans=max(sum,ans);
    }
    return ans;

}

max score atlassian

int n = a.size();
sort(a.begin(),a.end());
int s = 0;
int e = a[n-1]-a[0];
int ans = 0;
while(s<=e){
int mid = s+(e-s)/2;
int mi = a[0];
int count = 1;
bool f = true;
for(int i=1; i<n; i++){
if((a[i]-mi)<=mid){
count++;
}
else{
if(count<m) f = false;
else{
count = 1;
mi = a[i];
}
}
}
if(count<m) f = false;
if(f==false){
s = mid+1;
}
else{
ans = mid;
e = mid-1;
}
}
return ans;

array division Deshaw
9/15

ll solve(vector<int> &arr){
    int n=arr.size();
    vector<ll> pf(n),sf(n);
    pf[0]=arr[0];
    sf[n-1]=arr[n-1];
    for(int i=1;i<n;i++) pf[i]=arr[i]+pf[i-1];
    for(int i=n-2;i>=0;i--) sf[i]=arr[i]+sf[i+1];
    ll sm=0,mn=0;
    ll mx=-1e18;
    for(int i=0;i<n;i++){
        sm+=arr[i];
        if(sm>0) sm=0;
        mn=min(mn,sm);
        mx=max(mx,pf[i]-2*mn-(i<n-1?sf[i+1]:0));
    }
    return mx;
}

subarrays Deshaw

    int l=0,r=1e14;
    while(l<r){
        int mid=(l+r+1)>>1;
        int ans=1;
        int pr=0;
        for(int i=0;i<n;i++){
            if(pr>starts[i]+d){
                ans=0;
            }else{
                pr=max(pr+mid,starts[i]);
            }
        }
        if(ans){
            l=mid;
        }else{
            r=mid-1;
        }
    }
    return l;

Range selection deshaw

2/15

15/15
Deshaw range selection

long getMaxDist(std::vector<long> starts, long d) {
int n = starts.size();
sort(starts.begin(), starts.end()); // Sort the starting points in ascending order
long l = 0, r = 1e14;

while (l < r) {
long mid = (l + r + 1) / 2;
int ans = 1;
long pr = 0;

for (int i = 0; i < n; i++) {
if (pr > starts[i] + d) {
ans = 0;
} else {
pr = std::max(pr + mid, starts[i]);
}
}

if (ans) {
l = mid;
} else {
r = mid - 1;
}
}

return l;
}
c++ Deshaw range queries

Deshaw questions