#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;
vector<int> applyRule(const vector<int>& P) {
    int n = P.size();
    vector<int> newP(n);
    for (int i = 0; i < n; ++i) {
        newP[i] = P[P[i] - 1];
    }
    return newP;
}
bool isStable(const vector<int>& P) {
    for (int i = 0; i < P.size(); ++i) {
        if (P[i] != i + 1) return false;
    }
    return true;
}
int solve(vector<int>& P) {
    unordered_set<string> seen;
    int time = 0;
    while (true) {
        if (isStable(P)) return time;
        string key = "";
        for (int x : P) key += to_string(x) + ",";
        if (seen.count(key)) return -1;
        seen.insert(key);
        P = applyRule(P);
        ++time;
    }
    return -1;
}

#include <vector>
#include <unordered_map>
#include <iostream>

using namespace std;

int getMinTransactions(int n, vector<vector<int>>& debt) {
    unordered_map<int, int> balance
    for (const auto& d : debt) {
        balance[d[0]] -= d[2];
        balance[d[1]] += d[2];
    }
   
    vector<int> transactions;
    for (const auto& entry : balance) {
        if (entry.second != 0) {
            transactions.push_back(entry.second);
        }
    }

    int count = 0;
    int i = 0, j = transactions.size() - 1;
    while (i < j) {
        if (transactions[i] + transactions[j] == 0) {
            count++;
            i++;
            j--;
        } else if (transactions[i] + transactions[j] > 0) {
            transactions[i] += transactions[j];
            j--;
            count++;
        } else {
            transactions[j] += transactions[i];
            i++;
            count++;
        }
    }
    return count;
}

Meesho ✅

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int MOD = 1e9 + 7;
const int MAXN = 400;
int grid[MAXN][MAXN];
int dp[MAXN][MAXN][2];
int n, m;
int dfs(int row, int col, bool doubled) {
    if (row >= n || col >= m) return 0;
    if (dp[row][col][doubled] != -1) return dp[row][col][doubled];
   
    int qr = grid[row][col];
    int maxQR = qr + max(dfs(row + 1, col, doubled), dfs(row, col + 1, doubled));

    if (!doubled) {
        maxQR = max(maxQR, qr * 2 + max(dfs(row + 1, col, true), dfs(row, col + 1, true)));
    }
    return dp[row][col][doubled] = maxQR;
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> grid[i][j];
        }
    }
    memset(dp, -1, sizeof(dp));
    int result = dfs(0, 0, false);
    cout << result << endl;
   
    return 0;
}.  

//PHONE PE 2 ✅

Company Name: Nutanix

🛄 Job Title: Member of Technical Staff
✍🏻 YOE: 2022, 2023 and 2024 grads

➡️ Apply: https://nutanix.eightfold.ai/careers/job/23778110

Please do share in your college grps and in case you are applying please react on this post:) 😇❤️

import java.util.HashMap;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            String str = sc.next();
            String s = "";
            HashMap<Character, Character> map = new HashMap<>();
            int c = 0;

            for (int i = 0; i < n; i++) {
                if (map.containsKey(str.charAt(i))) {
                    s += map.get(str.charAt(i));
                } else {
                    s += (char) (c + '0');
                    map.put(str.charAt(i), (char) (c + '0'));
                    c++;
                }
            }

            int ans1=helper(s, 1, "0", map.size());
            int ans2=helper(s, 1, "1", map.size());
            System.out.println(ans1+ans2);
    }

    public static int helper(String s, int i, String tmp, int val) {
        if (i == val) {
            if (check(s, tmp)) return 1;
            return 0;
        }
        int ans=0;
        ans+=helper(s, i + 1, tmp + "0", val);
        ans+=helper(s, i + 1, tmp + "1", val);
        return ans;
    }

    public static boolean check(String a, String b) {
        int n = a.length();
        int tmp = 0;
        for (int i = 0; i < n; i++) {
            int c = a.charAt(i) - '0';
            tmp += (b.charAt(c) == '0') ? -1 : 1;
            if (tmp < 0) return false;
        }
        return (tmp == 0);
    }
}
VALID SEQUENCES IVP

Phone Pay 3rd -> #include "bits/stdc++.h"
using namespace std;
const int N=2e5+10;
vector<bool> vis(N);
vector<vector<int>>v(N);
// vector<int>sub(N);

void bfs(int n, vector<int>&par){
    par[n]=n;
    vis[n]=1;
    queue<int>q;
    q.push(n);
   
    while(q.size()){
        auto curr=q.front();
        q.pop();
        for(auto x:v[curr]){
            if(!vis[x]){
                vis[x]=1;
                q.push(x);
                par[x]=curr;
            }
        }
    }
}

int main(){
   
    int t;
    cin>>t;
   
    while(t--){
       
        int n;
        cin>>n;
       
        for(int i=0;i<=n;i++){
            v[i].clear();
            vis[i]=0;
        }
       
        int m;
        cin>>m;
       
        int a,b,c;
        cin>>a>>b>>c;
       
        vector<int>costs(m);
        for(int i=0;i<m;i++){
            cin>>costs[i];
        }
       
        for(int i=0;i<m;i++){
            int x,y;
            cin>>x>>y;
            v[x].push_back(y);
            v[y].push_back(x);
        }
       
        sort(costs.begin(),costs.end());
       
        vis.assign(n+1,0);
        vector<int>par1(n+1,0);
        bfs(a,par1);
       
        if(!par1[a] !par1[b] !par1[c]){
            cout<<-1<<endl;
            continue;
        }
       
        int val=b;
        vector<vector<int>>cnt(n+1,vector<int>(n+1,0));
       
        while(val!=a){
            int ik=par1[val];
            cnt[ik][val]++;
            cnt[val][ik]++;
            val=ik;
        }
       
        vis.assign(n+1,0);
        vector<int>par2(n+1,0);
        bfs(b,par2);
       
        val=c;
        while(val!=b){
            int ik=par2[val];
            cnt[ik][val]++;
            cnt[val][ik]++;
            val=ik;
        }
       
        vector<int>app;
       
        for(int i=1;i<=n;i++){
            for(int j=1;j<=i;j++){
                if(cnt[i][j]){
                    app.push_back(cnt[i][j]);
                }
            }
        }
       
        sort(app.rbegin(),app.rend());
       
        int ans=0;
       
        for(int i=0;i<app.size();i++){
            ans+=app[i]*costs[i];
        }
       
        cout<<ans<<endl;
       
    }
   
   
    return 0;
}

#include <iostream>
#include <cstring>
using namespace std;

typedef long long ll;
const int mod = 1e9 + 7;
int dp[1000001][2][4];

ll F(int i, int ok, int zlen) {
    if (i < 0 || ok > 1) return (ok + (zlen == 2)) % mod;
    if (dp[i][ok][zlen] != -1) return dp[i][ok][zlen];
   
    ll z = F(i - 1, ok, min(3, zlen + 1));
    ll nz = F(i - 1, ok + (zlen == 2), 0);
   
    return dp[i][ok][zlen] = (nz + z) % mod;
}

int main() {
    memset(dp, -1, sizeof(dp));
   
    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;
        cout << F(N - 1, 0, 0) << endl;
    }
   
    return 0;
}.

LIGHT PHONEPE

function getSumOfFactors(num) {
    let sum = 0;
    for (let i = 1; i <= Math.sqrt(num); i++) {
        if (num % i === 0) {
            sum += i;
            if (i !== num / i) {
                sum += num / i;
            }
        }
    }
    return sum;
}

function maxSubsetSum(arr) {
    return arr.map(num => getSumOfFactors(num));
}

Factset
Largest Subset Sum ✅

Who have Google and Goldman Sachs exam guys?
Send questions here solutions will be provide

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 200001;
vector<int> tree[MAXN];
char C[MAXN];
int result[MAXN];
bool isPalindrome[MAXN];
bool visited[MAXN];
bool checkPalindrome(const string& s) {
    int n = s.size();
    for (int i = 0; i < n / 2; ++i) {
        if (s[i] != s[n - i - 1]) {
            return false;
        }
    }
    return true;
}
string dfs(int u) {
    visited[u] = true;
    string S = "";

    for (int v : tree[u]) {
        if (!visited[v]) {
            S += dfs(v);
        }
    }

    S += C[u];
    isPalindrome[u] = checkPalindrome(S);
    return S;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
   
    int N;
    cin >> N;

    for (int i = 1; i < N; ++i) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    for (int i = 1; i <= N; ++i) {
        cin >> C[i];
    }

    memset(visited, false, sizeof(visited));
    dfs(1);

    int Q;
    cin >> Q;
    while (Q--) {
        int u;
        cin >> u;
        cout << (isPalindrome[u] ? 1 : 0) << "\n";
    }

    return 0;
}.

// FIND PALIDROME
Google ✅

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int T;
    cin >> T;

    while (T--) {
        int N;
        cin >> N;
        vector<int> weights(N);
        for (int i = 0; i < N; ++i) {
            cin >> weights[i];
        }

        int B;
        cin >> B;
        int totalWeight = 0;
        for (int i = 0; i < N; ++i) {
            totalWeight += weights[i];
        }

        int totalCapacity = B * 10;
        if (totalWeight <= totalCapacity) {
            cout << "True" << endl;
        } else {
            cout << "False" << endl;
        }
    }

    return 0;
}

Goldman Sachs ✅

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
long clinicShed(vector<long> patients, int k) {
    sort(patients.begin(), patients.end());
 
    long minShedLength = LONG_MAX;
    int n = patients.size();
        for (int start = 0; start <= n - k; ++start) {
        int end = start + k - 1;
        long length = patients[end] - patients[start] + 1;
        minShedLength = min(minShedLength, length);
    }
   
    return minShedLength;
}.

Vaccination Drive ✅
GOLDMAN

String machine try this
Google✅

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int f(int id, int taken, int t1, int t2, int k, vector<int> &a, vector<vector<int>> &dp) {
    if (taken == 2 * k) {
        return t1 ^ t2;
    }
    if (id >= a.size()) {
        return INT_MIN;
    }
    if (dp[id][taken] != -1) {
        return dp[id][taken];
    }
   
    int take = INT_MIN, ntake = INT_MIN;
   
    if (taken >= k) {
        take = f(id + 1, taken + 1, t1, t2|a[id], k, a, dp);
    } else {
        take = f(id + 1, taken + 1, t1|a[id],t2, k, a, dp);
    }
   
    ntake = f(id + 1, taken, t1, t2, k, a, dp);
   
    return dp[id][taken] = max(take, ntake);
}

OR XOR ✅
Google