def profitable_project_pairs(profit, implementationCost):
    n = len(profit)
    net_profit = [profit[i] - implementationCost[i] for i in range(n)]
   
    net_profit.sort()
   
    count = 0
    left = 0
    right = n - 1
   
    while left < right:
        if net_profit[left] + net_profit[right] > 0:
            count += (right - left)
            right -= 1
        else:
            left += 1
   
    return count

Profitable project pairs ✅
Workspan

Mitsogo Hiring Software Engineer
Freshers can apply ❤

Link 🔗
https://boards.greenhouse.io/mitsogoinc/jobs/4045384008?gh_src=eacea7cc8us

#include <iostream>
#include <vector>
using namespace std;
const int MOD = 10000007;
#define ll long long
#define vvll vector<vector<ll>>

vvll multiply(vvll& A, vvll& B ) {
    int n = A.size();
    vvll C(n, vector<ll>(n, 0));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k < n; ++k) {
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
            }
        }
    }
    return C;
}

vvll matrixExpo(vvll A, int power) {
    int n = A.size();
    vvll result(n, vector<ll>(n, 0));
    for (int i = 0; i < n; ++i) {
        result[i][i] = 1;
    }
    while (power > 0) {
        if (power % 2 == 1) {
            result = multiply(result, A);
        }
        A = multiply(A, A);
        power /= 2;
    }
    return result;
}

int solve(vector<int>& input) {
    int a = input[0], b = input[1], c = input[2], d = input[3], e = input[4], f = input[5], N = input[6];
   
    if (N <= 1) return 1;

    vvll T = {
        {a, b, 0, 0, 0, 0},
        {1, 0, 0, 0, 0, 0},
        {0, 0, c, d, 0, 0},
        {0, 0, 1, 0, 0, 0},
        {0, 0, 0, 0, e, f},
        {0, 0, 0, 1, 0, 0}
    };

  
    vector<ll> F = {1, 1, 1, 1, 1, 1};
   
    vvll T_power = matrixExpo(T, N - 1);

    ll result = 0;
    for (int i = 0; i < 6; ++i) {
        result = (result + T_power[0][i] * F[i]) % MOD;
    }

    return result;
}

int main() {
    vector<int> input = {1, 1, 1, 1, 1, 1, 3};
    cout << solve(input) << endl;
    return 0;
}


//linear recurrence ivp

int balloonGame(int n, int input2[])
{
  int64_t dp[(1 << n)];
  memset(dp, 0x3f, sizeof(dp));
  dp[0] = 0;
  for (int i = 1; i < (1 << n); i++) {
    int x = __builtin_popcount(i);
    for (int j = 0; j < n; j++) {
      if (i & (1 << j)) {
int pv = i ^ (1 << j);
int64_t nx = dp[pv] + (input2[j] + (x-1)) / x;
dp[i] = min(dp[i], nx);
      }
    }
  }
  return dp[(1 << n) - 1];
}

Balloon Game ✅

Swiggy ✅

class Solution {
public:
    int mod = 1e9 + 7;
    int solve(int i,string &s,char fr,char sec,int len, vector<vector<vector<vector<int>>>> &dp){
        if(len == 5) return 1;
        if(i == s.size()) return 0;
        if(dp[fr-'0'][sec - '0'][len][i] != -1) return dp[fr-'0'][sec - '0'][len][i];
       
        long long op1 = 0, op2 = 0, op3 = 0, op4 = 0,op5 = 0;
        if(len == 0) op1 = solve(i+1,s,s[i],sec,len+1,dp);
        if(len == 1) op2 = solve(i+1,s,fr,s[i],len+1,dp);
        if(len == 2) op3 = solve(i+1,s,fr,sec,len+1,dp);
        if(len == 3 and s[i] == sec) op4 = solve(i+1,s,fr,sec,len+1,dp);
        if(len == 4 and s[i] == fr) op5 = solve(i+1,s,fr,sec,len+1,dp);
        long long op6 = solve(i+1,s,fr,sec,len,dp);
       
        return dp[fr-'0'][sec - '0'][len][i] = (op1 + op2 + op3 + op4 + op5 + op6) % mod;
    }
    int countPalindromes(string s) {
        vector<vector<vector<vector<int>>>> dp(10, vector<vector<vector<int>>> (10, vector<vector<int>> (5,vector<int>(s.size(),-1))));
        return solve(0,s,'1','1',0,dp);
    }
};  

special Subsequences✅
Salesforce

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

int getmaxnum(string s) {
    int val[] = {1, 10, 100, 1000, 10000};
    for (char &c : s) c -= 'A';
    reverse(s.begin(), s.end());
    int an = -2e9;
    auto check = [&](int p) {
        if (p == -1) return;
        for (char v : {0, 1, 2, 3, 4}) {
            swap(v, s[p]);
            int lt = 0, now = 0;
            for (char c : s) now += c >= lt ? val[lt = c] : -val[c];
            an = max(an, now);
            swap(v, s[p]);
        }
    };
    for (int i : {0, 1, 2, 3, 4}) check(s.find_first_of(i)), check(s.find_last_of(i));
    return an;
}

Astro and number system ✅
Salesforce

int solve(vector<string>& words) 
{   
    int n=words.size();
    vector<string>ans(n);
    int i = 0, j = n - 1;
    unordered_map<string, int> pm, npm;
    for (int k = 0; k < n; k++) {
        string s1 = words[k];
        string s2 = string(s1.rbegin(), s1.rend());
        if (s1 == s2) {
            pm[s1]++;
        }
        else {
            int f = npm[s2];
            if (f == 0) {
                npm[s1]++;
            }
            else {
                ans[i] = s1;
                ans[j] = s2;
                i++;
                j--;
                npm[s2]--;
            }
        }
    }
    string o;
    for (auto& p : pm) {
        string ps = p.first;
        int f = p.second;
        if (f % 2 == 1) {
            while (f > 1) {
                ans[i++] = ps;
                ans[j--] = ps;
                f -= 2;
            }
            if (o.empty()) {
                o = ps;
            }
        }
        else {
            while (f > 0) {
                ans[i++] = ps;
                ans[j--] = ps;
                f -= 2;
            }
        }
    }
    if (!o.empty()) {
        ans[i++] = o;
    }
    string res;
    for (auto& tmp : ans) {
        if (!tmp.empty()) {
            res += tmp;
        }
    }
    return res.size();
}

Astro and bunch of words ✅
Salesforce

#include <iostream>
#include <vector>
#include <unordered_map>
#include <cmath>
#include <algorithm>
using namespace std;
class UnionFind {
public:
    UnionFind(int n) : parent(n), size(n, 1) {
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }
    int find(int x) {
        if (x != parent[x]) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    void unionSet(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (size[rootX] < size[rootY]) {
                swap(rootX, rootY);
            }
            parent[rootY] = rootX;
            size[rootX] += size[rootY];
        }
    }
    int getSize(int x) {
        return size[find(x)];
    }
private:
    vector<int> parent;
    vector<int> size;
};
vector<int> primeFactors(int x) {
    vector<int> factors;
    for (int i = 2; i <= sqrt(x); ++i) {
        if (x % i == 0) {
            factors.push_back(i);
            while (x % i == 0) {
                x /= i;
            }
        }
    }
    if (x > 1) {
        factors.push_back(x);
    }
    return factors;
}
int largestMagicalGroup(int N, vector<int>& A) {
    UnionFind uf(*max_element(A.begin(), A.end()) + 1);
    unordered_map<int, int> value_to_index;
    for (int i = 0; i < N; ++i) {
        value_to_index[A[i]] = i;
        for (int prime : primeFactors(A[i])) {
            uf.unionSet(A[i], prime);
        }
    }
    unordered_map<int, int> group_sizes;
    int max_group_size = 1;
    for (int i = 0; i < N; ++i) {
        int root = uf.find(A[i]);
        group_sizes[root]++;
        max_group_size = max(max_group_size, group_sizes[root]);
    }
    return max_group_size;
}

Magical Group ✅

Who have Intuit, Microsoft, Morgan Stanley exam guys??
Send questions here solutions will provide

How many people got this

T* extendT(T* node) {
    if (!node) return node;

    if (!node->l && !node->r) {
        node->l = new T(node->x,nullptr,nullptr);
        node->r = new T(node->x,nullptr,nullptr);
    } else {
        extendT(node->l);
        extendT(node->r);
    }
    return node;
}

Microsoft ✅