bool isp(string s){
    int n=s.length();
    for(int i=0;i<n/2;i++){
        if(s[i]!=s[n-i-1]){
            return false;
        }
    }
    return true;
}

int longestString(vector<string>v){
    unordered_map<string,int>mp;
    for(auto x:v){
        mp[x]++;
    }
    int ans=0;
    for(auto x:mp){
      if(x.second>1){
        int k=(x.second)/2;
          ans+=k*(x.first.length()); 
      }
      if(x.second%2!=0){
         mp[x.first]=1;
      }
      else
      mp.erase(x.first);
    }
    int maxi=0;
    for(auto x:mp){
        if(isp(x.first)){
            maxi=max(maxi,(int)x.first.length());
        }
    }
    return ans+maxi;
}

Max palindrome
Infosys ✅

#include <bits/stdc++.h>
#define int long long
using namespace std;
#define ll long long
vector<vector<ll>> solve(ll n,ll k,vector<ll>&a,vector<ll>&b) 
{
    priority_queue<pair<double,pair<ll,ll>>> pq;
    for(int i=0;i<n;i++)
    {
        double x=a[i];
        double y=b[i];
        double dis=sqrt(x+y);
        pq.push({dis,{x,y}});
        if(pq.size()>k)  pq.pop();
    }
    vector<vector<ll>>ans;
    while(!pq.empty())
    {
        ans.push_back({pq.top().second.first,pq.top().second.second});
        pq.pop();
    }
    sort(begin(ans),end(ans));
    return ans;
}
signed main() 
{        
        ll n,k; cin>>n>>k;
        vector<ll>a(n),b(n);
        for(ll i=0;i<n;i++) cin>>a[i];
        for(ll i=0;i<n;i++) cin>>b[i];
        vector<vector<ll>>ans=solve(n,k,a,b);
        for(auto it:ans) cout<<it[0]<<" "<<it[1]<<endl;
            
    return 0;
}

Closet k points to origin

#include <iostream>
#include <unordered_set>
#include <string>
using namespace std;
void generateSubstrings(const string &s, int len, unordered_set<string> &substrings) {
    for (int i = 0; i <= s.size() - len; ++i) {
        substrings.insert(s.substr(i, len));
    }
}

string findMinimalString(const string &s) {
    unordered_set<string> substrings;
    for (int len = 1; ; ++len) {
        substrings.clear();
        generateSubstrings(s, len, substrings);
        string candidate(len, 'a');
        while (true) {
            if (substrings.find(candidate) == substrings.end()) {
                return candidate;
            }
            int pos = len - 1;
            while (pos >= 0 && candidate[pos] == 'z') {
                candidate[pos] = 'a';
                --pos;
            }
            if (pos < 0) break;
            ++candidate[pos];
        }
    }
}

int main() {
    string S;
    cin >> S;
    cout << findMinimalString(S) << endl;
    return 0;
}. 

Minimal string ✅

Longest palindrome concatenation ✅

#include <bits/stdc++.h>
#define int long long
using namespace std;
#define ll long long
ll solve(ll n,ll k,vector<ll>&a) 
{   
    k++;
    unordered_map<ll,ll>freq;
    map<ll,vector<ll>>mpp;
    for (ll i=0;i<n;i++) 
    {   
        freq[a[i]]++;
        mpp[freq[a[i]]].push_back(a[i]);
    }
    ll ans=0;
    for (auto it:mpp) ans+=it.second.size();
    return ans;
}
signed main() 
{        
        ll n,k; cin>>n>>k;
        vector<ll>a(n);
        for(ll i=0;i<n;i++) cin>>a[i];
        cout<<solve(n,k,a);
            
    return 0;
}

Sequence split ✅

const int MOD = 1000000007;

int subsetSumCount(const vector<int>& A, int L, int R, int K) {
    vector<int> dp(K + 1, 0);
    dp[0] = 1;

    for (int i = L; i <= R; ++i) {
        for (int j = K; j >= A[i]; --j) {
            dp[j] = (dp[j] + dp[j - A[i]]) % MOD;
        }
    }

    return dp[K];
}

int findXOR(int n, int Q, const vector<int>& A, const vector<vector<int>>& B ) {
    int result = 0;
    for (const auto& query : B ) {
        int L = query[0] - 1;
        int R = query[1] - 1;
        int K = query[2];
        int P = subsetSumCount(A, L, R, K);
        result ^= P;
    }
    return result;
}


//subarray subset sum✅

import java.util.*;

public class PrimeSumOptimal {
   
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
        }
        System.out.println(maxNonPrimeSumSubset(A, N));
        sc.close();
    }
    private static boolean[] isPrime;
    private static void sieve(int maxLimit) {
        isPrime = new boolean[maxLimit + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int p = 2; p * p <= maxLimit; p++) {
            if (isPrime[p]) {
                for (int i = p * p; i <= maxLimit; i += p) {
                    isPrime[i] = false;
                }
            }
        }
    }
   
    private static boolean isPrime(int num) {
        return isPrime[num];
    }
    private static int maxNonPrimeSumSubset(int[] A, int N) {
        sieve(1000);
        int maxSubsetSize = 0;
        for (int bitmask = 0; bitmask < (1 << N); bitmask++) {
            List<Integer> subset = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                if ((bitmask & (1 << i)) != 0) {
                    subset.add(A[i]);
                }
            }
            boolean validSubset = true;
            int subsetSize = subset.size();
            for (int i = 0; i < subsetSize && validSubset; i++) {
                for (int j = i + 1; j < subsetSize; j++) {
                    if (isPrime(subset.get(i) + subset.get(j))) {
                        validSubset = false;
                        break;
                    }
                }
            }
            if (validSubset) {
                maxSubsetSize = Math.max(maxSubsetSize, subsetSize);
            }
        }
       
        return maxSubsetSize;
    }
}. 

pair sum

Google Referral Post This could be your next office...

Fill out the referral form and I'll refer the top 10 candidates. Form link:

https://docs.google.com/forms/d/e/1FAIpQLScpODCpJUqiEme9zbjdWDJedqaGz3xjpaz8hothdx0KbS21tw/viewform

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

int maxPartitions(vector<int>& nums) {
    int n = nums.size();
    unordered_map<long long, int> map, rmap;
    long long total = 0;

    for (int num : nums) {
        total += num;
    }

    long long left = 0, right = total;

    for (int i = 0; i < n - 1; ++i) {
        right -= nums[i];
        left += nums[i];
        long long diff = right - left;
        rmap[diff]++;
    }

    int result = rmap[0];

    left = 0;
    right = total;

    for (int i = 0; i < n; ++i) {
        result = max(result, map[nums[i]] + rmap[-nums[i]]);

        right -= nums[i];
        left += nums[i];

        long long diff = right - left;
        rmap[diff]--;
        map[diff]++;
    }

    return result;
}

int main() {
    int t;
    cin >> t;
   
    while (t--) {
        int n;
        cin >> n;
       
        vector<int> nums(n);
        for (int i = 0; i < n; ++i) {
            cin >> nums[i];
        }

        int result = maxPartitions(nums);
       
        cout << result << endl;
    }

    return 0;
}

Number of Partition ✅
Google

#include <iostream>
#include <vector>
#include <string>

using namespace std;


void precompute(const string& S, vector<vector<bool>>& isPalindrome) {
    int n = S.size();
    for (int i = 0; i < n; ++i) {
        isPalindrome[i][i] = true;
    }
    for (int len = 2; len <= n; ++len) {
        for (int i = 0; i <= n - len; ++i) {
            int j = i + len - 1;
            if (S[i] == S[j]) {
                if (len == 2) {
                    isPalindrome[i][j] = true;
                } else {
                    isPalindrome[i][j] = isPalindrome[i + 1][j - 1];
                }
            }
        }
    }
}


int countGoodTriplets(const string& S) {
    int n = S.size();
    vector<vector<bool>> isPalindrome(n, vector<bool>(n, false));
    precompute(S, isPalindrome);
   
 
    vector<int> dpLeft(n, 0);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= i; ++j) {
            if (isPalindrome[j][i]) {
                dpLeft[i]++;
            }
        }
        if (i > 0) {
            dpLeft[i] += dpLeft[i - 1];
        }
    }
   
  
    vector<int> dpRight(n, 0);
    for (int i = n - 1; i >= 0; --i) {
        for (int j = i; j < n; ++j) {
            if (isPalindrome[i][j]) {
                dpRight[i]++;
            }
        }
        if (i < n - 1) {
            dpRight[i] += dpRight[i + 1];
        }
    }
   
    int goodTriplets = 0;
  
    for (int i = 1; i < n - 1; ++i) {
        for (int j = i; j < n - 1; ++j) {
            if (isPalindrome[i][j]) {
                goodTriplets += dpLeft[i - 1] * dpRight[j + 1];
            }
        }
    }
   
    return goodTriplets;
}

int main() {
    int t;
    cint >> t;
    while(t--){
        string S;
        cin >> S;
        cout << countGoodTriplets(S) << endl;
    }
    return 0;
}

Palindromic triplet
Google ✅
Source :Hola

#include<bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;

const int mod = 1e9+7;
const int K = 18;

int solve(int n, int m, vector<vector<int> > arr){
    vector<pair<int, int> > a(n);
    for(int i = 0; i < n; i++){
        a[i].first = arr[i][1];
        a[i].second = arr[i][0];
    }
    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());


    int ans = 0;
    priority_queue<int> pq;
    int e = 0, price = 0;
    for(int i = 0; i < n; i++){
        price += a[i].second;
        pq.push(-a[i].second);
        e++;

        if(e < m) continue;
        if(e == m+1){
            e--;
            price += pq.top();
            pq.pop();
        }

        ans = max(ans, price + a[i].first * m);
    }

    return ans;
}

int32_t main(){
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);
    int n, m;
    cin>>n>>m;
    vector<vector<int> > arr(n, vector<int>(2));
    for(int i = 0; i < n; i++){
        cin>>arr[i][0]>>arr[i][1];
    }

    cout<<solve(n, m, arr)<<endl;
    return 0;
}

Maximizing Profit
Google ✅

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

void Sieve(ll n, vector<ll>& primes) { 
    vector<bool> prime(n + 1, true); 
    for (ll p = 2; p * p <= n; p++) { 
        if (!prime[p]) continue; 
        for (ll i = p * p; i <= n; i += p) { 
            prime[i] = false; 
        } 
    } 
    for (ll i = 2; i <= n; i++) { 
        if (prime[i]) { 
            primes.push_back(i); 
        } 
    } 
} 

bool isPrime(ll n, vector<ll>& primes) { 
    auto it = find(primes.begin(), primes.end(), n); 
    return it != primes.end(); 
} 

void dfs(ll s, ll p, ll mod, vector<vector<ll>>& adj, vector<vector<ll>>& dp, vector<ll>& primes) { 
    for (ll i = 0; i < 25; i++) { 
        dp[s][i] = 1; 
    } 
    for (auto u : adj[s]) { 
        if (u != p) { 
            dfs(u, s, mod, adj, dp, primes); 
            for (ll i = 0; i < 25; i++) { 
                ll pos = 0; 
                for (ll j = 0; j < 25; j++) { 
                    if (!isPrime(primes[i] + primes[j], primes)) { 
                        pos = (pos + dp[u][j]) % mod; 
                    } 
                } 
                dp[s][i] = (dp[s][i] * pos) % mod; 
            } 
        } 
    } 
} 

long long Validasignment(int n, vector<vector<int>>& edges) { 
    ll mod = 1000000007; 
    vector<ll> primes; 
    Sieve(200, primes); 
    vector<vector<ll>> dp(n + 1, vector<ll>(25, 0)); 
    vector<vector<ll>> adj(n + 1); 
    for (int i = 0; i < n - 1; i++) { 
        adj[edges[i][0]].push_back(edges[i][1]); 
        adj[edges[i][1]].push_back(edges[i][0]); 
    } 
    dfs(1, -1, mod, adj, dp, primes); 
    ll ans = 0; 
    for (ll i = 0; i < 25; i++) { 
        ans = (ans + dp[1][i]) % mod; 
    } 
    return ans; 
}

Google ✅

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

int equalzeroandone(vector<int>v){
    int n=v.size();
    for(int i=0;i<n;i++){
        if(v[i]==0){
            v[i]=-1;
        }
    }
    int sum=0;
    int ans=-1;
   map<int,int>mp;
    for(int i=0;i<n;i++){
        sum+=v[i];
        if(sum==0){
            ans=i+1;
        }
        if(mp.find(sum)!=mp.end()){
            ans=max(ans,i-mp[sum]);
        }
        else{
            mp[sum]=i;
        }
    }
    return ans;
}

int main() {
    int n;
    cin>>n;
    vector<int>v(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    cout<<equalzeroandone(v);
}

Equal number of zero
Infosys

largest subarray equal number
Infosys ✅

public static int findLargestSquareSize(List<List<Integer>> samples) {
   // Write your code here
      int R = samples.size();
        if (R == 0) return 0;
        int C = samples.get(0).size();
       
        int[][] S = new int[R][C];
        int[][] M = new int[R][C];
       
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                M[i][j] = samples.get(i).get(j);
            }
        }
       
        for (int i = 0; i < R; i++)
            S[i][0] = M[i][0];
        for (int j = 0; j < C; j++)
            S[0][j] = M[0][j];
       
        for (int i = 1; i < R; i++) {
            for (int j = 1; j < C; j++) {
                if (M[i][j] == 1) {
                    S[i][j] = Math.min(S[i][j - 1], Math.min(S[i - 1][j], S[i - 1][j - 1])) + 1;
                } else {
                    S[i][j] = 0;
                }
            }
        }
       
        int max_of_s = S[0][0];
        int max_i = 0;
        int max_j = 0;
       
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (max_of_s < S[i][j]) {
                    max_of_s = S[i][j];
                    max_i = i;
                    max_j = j;
                }
            }
        }
       
        return Math.abs((max_i - max_of_s) - max_i);
    }.

findLargestSquareSize

Linkdin ✅

vector<int>findSubsequence(vector<int>arr){
    map<int,int>m;
    vector<int>ans;
    int maxi=0;
    int n=arr.size();
    for(int i=0;i<n;i++){
        if(m[arr[i]]>0){
            if(arr[i]<maxi){
                return {-1};
            }
            else{
                maxi=max(maxi,arr[i]);
                ans.push_back(arr[i]);
            }
        }
        m[arr[i]]++;
    }
    return ans;
}

Find sequence✅