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

int solve(vector<int>& v) {
    int n = v.size();
    vector<int> dp(n, INT_MAX);
    dp[0] = 0;
    for(int i = 0; i < n; i++) {
        for(int j = i+1; j <= min(i+3, n-1); j++) {
            dp[j] = min(dp[j], dp[i] + abs(v[i] - v[j]));
        }
    }
    return dp[n-1];
}

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


Three jump ✅
Service Now

bool check(vector<int>&v,int mid,int t){
    int trip=0,curr=0;
    for(auto it : v){
        if(it>mid)return false;
        if(curr+it>mid){
            trip++;
            curr=it;
        }
        else curr+=it;
    }
    if(curr>0)trip++;
    return trip<=t;
}

void diamondBoxes(){
    int n;
    cin>>n;
    vector<int>v(n);
    int l=0,r=0;
    for(int i=0;i<n;i++){
        cin>>v[i];
        l=max(l,v[i]);
        r+=v[i];
    }
    int t;
    cin>>t;
    while(l<r){
        int mid=l+(r-l)/2;
        if(check(v,mid,t))r=mid;
        else l=mid+1;
    }
    cout<<l<<endl;
   
}

Diamond Boxes ✅

#include<bits/stdc++.h>
using namespace std;
int main(){

     long long i,j,n,m,a,b,cnt;
     while(cin>>n)
     {
         long long f[10000],a[1000];
         memset(f,0,sizeof(f));
         for(i=0;i<n;i++)
         {
             cin>>a[i];
             f[i]=0;
         }
         sort(a,a+n);
          cnt=0;
         for(i=0;i<n;i++){
            for(j=i+1;j<n;j++){
                if(f[j]==0&&a[i]<a[j])
                {
                        cnt++;
                        f[j]=1;
                        break;
                }
            }
         }
         cout<<cnt<<endl;
     }
     return 0;
}

Art ✅
Service Now

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

int solve(vector<int>& arr, int k) {
    int n = arr.size();
    sort(arr.begin(), arr.end());
    vector<int> dp(n+1, INT_MAX);
    dp[0] = 0;
    for(int i = 1; i <= n; i++) {
        int maxVul = arr[i-1];
        for(int j = i-1; j >= max(0, i-k); j--) {
            maxVul = max(maxVul, arr[j]);
            dp[i] = min(dp[i], dp[j] + maxVul);
        }
    }
    return dp[n];
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> arr(n);
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << solve(arr, k) << endl;
    return 0;
}

IT department✅

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

int main() {
    int n;
    cin >> n;
    vector<int> powOf2;
    long long val = 1;
    for(int i = 0; i <= n; i++) {
        powOf2.push_back(val);
        val = (val * 2) % MOD;
    }
    long long ans = 0;
    for(int i = n - 1; i > 0; i-= 2)
        ans = (ans + powOf2[i]) % MOD;
    cout << ans << endl;
}

Lucky Strings ✅

public static void main (String[] args) throws java.lang.Exception
  {
        int tes=1;
        StringBuilder sb=new StringBuilder();
      lable:for(int fuck=1;fuck<=tes;fuck++)
      {
           int n=sc.nextInt(),i;
           ArrayList<ArrayList<Integer>> arr=new ArrayList<>();
           for(i=0;i<=n;i++) arr.add(new ArrayList<>());
           for(i=2;i<=n;i++){
            int x=sc.nextInt();
            arr.get(x).add(i);
            arr.get(i).add(x);
           }
           int dp[]=new int[n+1];
           int okk=dfs(1,0,dp,arr);
           for(i=1;i<=n;i++) System.out.print(dp[i]+" ");
        }
    }
    public static int dfs(int u,int p,int dp[],ArrayList<ArrayList<Integer>> arr){
        for(int it:arr.get(u)){
            if(it==p) continue;
            dp[u]=dp[u]+dfs(it,u,dp,arr)+1;
        }
        return dp[u];
    }


//Organisation
Service Now ✅

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

vector<int> solve(int V, vector<int>& bosses) {
    vector<int> h(V, 0);
    for(int i = 0; i < V-1; i++) {
        int b = bosses[i];
        while(b != -1) {
            h[b-1]++;
            b = (b-1 > 0 ? bosses[b-2] : -1);
        }
    }
    return h;
}

int main() {
    int V;
    cin >> V;
    vector<int> b(V-1);
    for(int i = 0; i < V-1; i++) {
        cin >> b[i];
    }
    vector<int> h = solve(V, b);
    for(int i = 0; i < V; i++) {
        cout << h[i] << " ";
    }
    cout << endl;
    return 0;
}


Find Hierarchy✅

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

void twiceIsEnough(string &s){
    int n=s.length();
    int i=0,j=0,ans=0;
    unordered_map<char,int>mp;
    while(i<n){
        while(j<i && mp[s[i]]==2){
            mp[s[j]]--;
            if(mp[s[j]]==0)mp.erase(s[j]);
            j++;
        }
        mp[s[i]]++;
        ans=max(ans,i-j+1);
        i++;
    }
    cout<<ans<<endl;
}

int main(){
    string s;
    cin>>s;
    twiceIsEnough(s);
}

first non repeating and twice is enough✅

int a,b,c;
    cin>>a>>b>>c;
    int d=a&b;
    int ans=0;
    for(int i=0;i<32;i++)
    {
        if((c&(1<<i)))
        {
        if(!(d&(1<<i)))
           ans=ans|(1<<i);
        }
        else if((d&(1<<i)))
        {
            cout<<-1<<endl;
            return 0;
        }
        
    }
    cout<<ans<<endl;
    return 0;



Bit expression ✅

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

int maxDiff(vector<int>& a) {
    int n = a.size();
    vector<int> ng(n), mr(n);
    stack<int> s;
    for(int i = n-1; i >= 0; i--) {
        while(!s.empty() && s.top() <= a[i]) {
            s.pop();
        }
        ng[i] = s.empty() ? 0 : s.top();
        s.push(a[i]);
    }
    mr[n-1] = a[n-1];
    for(int i = n-2; i >= 0; i--) {
        mr[i] = max(mr[i+1], a[i]);
    }
    int res = 0;
    for(int i = 0; i < n; i++) {
        if(ng[i] > 0) {
            res = max(res, abs(ng[i] - mr[i]));
        }
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    cout << maxDiff(a) << endl;
    return 0;
}


maximum difference ✅

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

void twiceIsEnough(string &s){
    int n=s.length();
    int i=0,j=0,ans=0;
    unordered_map<char,int>mp;
    while(i<n){
        while(j<i && mp[s[i]]==2){
            mp[s[j]]--;
            if(mp[s[j]]==0)mp.erase(s[j]);
            j++;
        }
        mp[s[i]]++;
        ans=max(ans,i-j+1);
        i++;
    }
    cout<<ans<<endl;
}

int main(){
    string s;
    cin>>s;
    twiceIsEnough(s);
}

Twice is enough ✅

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int dp[100001];
int solve(int n,vector<int>& ar,int ci){
    if(ci>=n) return INT_MAX;
    if(ci==n-1){
        return 0;
    }
    if(dp[ci]!=-1) return dp[ci];
    int a=INT_MAX,b=INT_MAX,c=INT_MAX;
    if(ci+1<n){
        int a1=0;
        a1+=abs(ar[ci]-ar[ci+1])+solve(n,ar,ci+1);
        a=min(a1,a);
    }
    if(ci+2<n){
        int b1=0;
        b1+=abs(ar[ci]-ar[ci+2])+solve(n,ar,ci+2);
        b=min(b1,b);
    }
    if(ci+3<n){
        int c1=0;
        c1+=abs(ar[ci]-ar[ci+3])+solve(n,ar,ci+3);
        c=min(c1,c);
    }
    return dp[ci]=min(a,min(b,c));
}
int main(){
    int n;
    cin>>n;
    vector<int>ar;
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        ar.push_back(a);
    }
    if(n==1) return ar[0];
    memset(dp,-1,sizeof(dp));
    cout<<solve(n,ar,0);
}


3 jumps ✅

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

vector<pair<int, int>> solve(vector<pair<int, int>>& p, int K) {
    priority_queue<pair<int, pair<int, int>>> mh;
    for(auto& i : p) {
        int d = i.first * i.first + i.second * i.second;
        mh.push({d, i});
        if(mh.size() > K) {
            mh.pop();
        }
    }
    vector<pair<int, int>> res;
    while(!mh.empty()) {
        res.push_back(mh.top().second);
        mh.pop();
    }
    return res;
}

int main() {
    int N, K;
    cin >> N;
    vector<pair<int, int>> p(N);
    for(int i = 0; i < N; i++) {
        cin >> p[i].first >> p[i].second;
    }
    cin >> K;
    vector<pair<int, int>> np = solve(p, K);
    for(auto& i : np) {
        cout << i.first << " " << i.second << endl;
    }
    return 0;
}

At the center ✅

#include <iostream>
#include <vector>

using namespace std;

void solve(vector<int>& a, int n) {
    int ans = a[0];
    for (int i = 1; i < n; i++) {
        ans &= a[i];
    }
    cout << ans << " ";
}

int main() {

        int n;
        cin >> n;

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

        solve(v, n);

    return 0;
}

Minimum integer✅

Element on right ✅

longest common substring - Alpha set

Book shelf ✅

Company Name: SmartReach.io
Role: SDE 1
Batch eligible: 2023 and 2024 passouts

Apply: https://smartreach.freshteam.com/jobs/C8Ti_0q7_Qu4/software-development-engineer-1-sde-1-j6

def longest_beautiful_prefix(S, substrings):
    dp = {len(S): 0}

    for i in range(len(S) - 1, -1, -1):
        longest_prefix = 0

        for s in substrings:
            possible_end = i + len(s)

            if possible_end <= len(S) and S[i:possible_end] == s[::-1] and possible_end in dp:
                longest_prefix = max(longest_prefix, dp[possible_end] + len(s))

        dp[i] = longest_prefix

    return dp[0]

Longest Prefix ✅
Infosys