#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

def calculateF(B, K):
    orPart = 0
    xorPart = 0
    for i in range(K):
        orPart |= B[i]
    for i in range(K, 2 * K):
        xorPart ^= B[i]
    return orPart + xorPart

def findMaxF(N, K, A):
    maxF = 0
    from itertools import combinations
    for subset in combinations(A, 2 * K):
        currentF = calculateF(subset, K)
        maxF = max(maxF, currentF)
    return maxF

def main():
    T = int(input())
    for _ in range(T):
        N, K = map(int, input().split())
        A = list(map(int, input().split()))
        print(findMaxF(N, K, A))

if name == "main":
    main()                  

// COMPLEX ✅
Google

String Machine ✅
Google

Range Function ✅
Google

using ll = long long;

class SegTree {
    vector<ll> tree;
    vector<ll> A;
    ll n;

public:
    SegTree(const vector<int>& arr) {
        n = arr.size();
        A = vector<ll>(arr.begin(), arr.end());
        tree.resize(4 * n, 0);
        build(0, 0, n - 1);
    }

    void build(ll node, ll start, ll end) {
        if (start == end) {
            tree[node] = A[start];
        } else {
            ll mid = (start + end) / 2;
            build(2 * node + 1, start, mid);
            build(2 * node + 2, mid + 1, end);
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
        }
    }

    void upd(ll idx, ll val, ll node, ll start, ll end) {
        if (start == end) {
            A[idx] = val;
            tree[node] = val;
        } else {
            ll mid = (start + end) / 2;
            if (idx <= mid) {
                upd(idx, val, 2 * node + 1, start, mid);
            } else {
                upd(idx, val, 2 * node + 2, mid + 1, end);
            }
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
        }
    }

    ll qry(ll L, ll R, ll node, ll start, ll end) {
        if (R < start || end < L) {
            return 0;
        }
        if (L <= start && end <= R) {
            return tree[node];
        }
        ll mid = (start + end) / 2;
        ll left = qry(L, R, 2 * node + 1, start, mid);
        ll right = qry(L, R, 2 * node + 2, mid + 1, end);
        return left + right;
    }

    void upd(ll idx, ll val) {
        upd(idx, val, 0, 0, n - 1);
    }

    ll qry(ll L, ll R) {
        return qry(L, R, 0, 0, n - 1);
    }
};

vector<ll> solve(int N, int l, vector<int> A, vector<vector<int>> query) {
    SegTree segTree(A);
    vector<ll> results;

    for (const auto& q : query) {
        if (q[0] == 1) {
            int idx = q[1];
            int val = q[2];
            segTree.upd(idx - 1, val);
        } else if (q[0] == 2) {
            int L = q[1];
            int R = q[2];
            ll sum = 0;
            for (int i = L - 1; i < R; ++i) {
                for (int j = i; j < R; ++j) {
                    sum += segTree.qry(i, j);
                }
            }
            results.push_back(sum);
        }
    }

    return results;
}

Source : Hola