anshu2002's blog

By anshu2002, history, 16 months ago, In English

for this leetcode problem

this is my solution which gave tle

class Solution {
public:
    vector<vector<int>>dp;
    int solve(int i,vector<vector<int>>&ne,int prev){
        if(i==ne.size()){
            return 0;
        }
        if(prev!=-1 && dp[i][prev]!=-1)
            return dp[i][prev];
        int ans = INT_MIN;
        ans = max(ans,solve(i+1,ne,prev));
        if(prev==-1||ne[prev][1]<=ne[i][0])
            ans = max(ans,solve(i+1,ne,i)+ne[i][2]);
        if(prev!=-1)
            dp[i][prev]=ans;
        return ans;
    }
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        dp = vector<vector<int>>(profit.size(),vector<int>(profit.size(),-1));
        vector<vector<int>>ne;
        for(int i=0;i<profit.size();i++){
            ne.push_back({startTime[i],endTime[i],profit[i]});
        }
        sort(begin(ne),end(ne));
        return solve(0,ne,-1);      
    }
};

and this is my friend's solution which gave AC

class Solution {
public:
    int solve(int ind,int &n,int prevEnd,vector<int> &dp,vector<vector<int>> &v){
        //base case
        if(ind == n){
            return 0;
        }
        if(v[ind][0]<prevEnd){
            return solve(ind+1,n,prevEnd,dp,v);
        }
        //cache
        if(dp[ind] != -1)return dp[ind];
        
        int pick = v[ind][2]+solve(ind+1,n,v[ind][1],dp,v);
        int notPick = 0 + solve(ind+1,n,prevEnd,dp,v);
        
        return dp[ind] = max(pick,notPick);
    }
    
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        vector<vector<int>> v;
        int i,n = endTime.size();
        for(i = 0; i < n; i++){
            v.push_back({startTime[i],endTime[i],profit[i]});
        }
        sort(v.begin(),v.end());
        vector<int> dp(n,-1);
        return solve(0,n,0,dp,v);
    }
};

Full text and comments »

  • Vote: I like it
  • -23
  • Vote: I do not like it

By anshu2002, history, 21 month(s) ago, In English

This is was my implementation for previous weekly fourth question what's wrong in my code ?

class Solution {
public:
    vector<vector<int>>dp;
    int solve(int i,vector<vector<int>>&num,int sum){
        if(sum==0)
        {
            return 1;
        }
        if(i==num.size()||sum<0)
            return 0;
        if(dp[i][sum]!=-1)
            return dp[i][sum];
        int ans = 0;
        if(num[i][0]>0)
        {
            num[i][0]--;
            ans+=solve(i,num,sum-num[i][1]);
            ans%=1000000007; 
            num[i][0]++;
        }
        ans+=solve(i+1,num,sum);
        ans%=1000000007;
        return dp[i][sum]=ans;
    }
    int waysToReachTarget(int target, vector<vector<int>>& types) {
        dp = vector<vector<int>>(types.size(),vector<int>(target+1,-1));
        return solve(0,types,target);
    }
};

Full text and comments »

  • Vote: I like it
  • -16
  • Vote: I do not like it

By anshu2002, history, 2 years ago, In English
// there is a unrooted unweighted tree with n nodes numbered from 1 to n . You have to travel from 1 to n via some special nodes,
// so find the length of shortest path from 1 to n
// you can visit any node any number of times
// you have to visit special nodes atleast once
vector<int>edges = {{1,2},{1,3},{3,4},{3,5}};
vector<int>special_nodes = {2,4};
// ans : 6 (1->2->1->3->4->3->5)

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By anshu2002, history, 2 years ago, In English

Fogive me if I offend someone . But I wanted to ask is leetcode enough to clear OA and interviews or codechef and codeforces is a must ? I am a 2024 grad and practiced over 500+ questions in leetcode , given 27 contest and rating is 1700+(I don't know how good or bad it is)

Full text and comments »

  • Vote: I like it
  • -16
  • Vote: I do not like it

By anshu2002, history, 2 years ago, In English

Anyone here does leetcode ?? Please review my leetcode profile with respect to job perspectives .

My leetcode profile

Full text and comments »

  • Vote: I like it
  • -18
  • Vote: I do not like it

By anshu2002, history, 2 years ago, In English

There is an array consisting of numbers from 0 to 9 You have to divide the array into buckets such that every occurance of each number falls in only one bucket So find the maximum number of buckets you can form Example arr = {0,0,1,1,2,1,7,8,7,9,9}

ans = 4

({0,0},{1,1,2,1},{7,8,7},{9,9})

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By anshu2002, history, 2 years ago, In English

There is a tree of N nodes and a integer k.In one operation you can do the following . Choose a node X other than the root node. If the distance between root and the parent of X is less than that of X ( where 1<=X<=N ) . Then X will be disconnected from it's original parent and X will be directly get connected to root. Height of the tree is the maximum distance from root to any node of tree . So find the minimum height of the tree after applying the above operation at most K times

EDIT 1 : THIS TREE IS ROOTED AT 1 AND EDGES ARE UNDIRECTED INPUT FORMAT: First line contains N and K . Next N-1 line contains two integers u and v denoting that there is an edge between u and v

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By anshu2002, history, 2 years ago, In English

the question is , two strings are given s1 and s2 . You have to find minimum number of insertions to be done at the end of s1 so that s2 becomes a subsequence of s1

test #1 s1: armaze s2: amazon ans : 2

test #2 s1: armazen s2: amazon ans : 2

Full text and comments »

  • Vote: I like it
  • +2
  • Vote: I do not like it

By anshu2002, history, 2 years ago, In English

Though I may sound noob . But I want to learn

class FoodRatings {
public:
    map<string,set<pair<int,string>>> s;
    unordered_map<string,string> abcd;
    unordered_map<string,int> rat;
    FoodRatings(vector<string>& ff, vector<string>& str, vector<int>& rate) {
        int i=0;
        while(i<ff.size())
        {
            s[str[i]].insert({-rate[i],ff[i]});
            abcd[ff[i]]=str[i];
            rat[ff[i]]=-rate[i];
            i++;
        }
    }
    void change(string food, int newRating){
        int r=rat[food];
        string c=abcd[food];
        s[c].erase({r,food});
        s[c].insert({-newRating,food});
        rat[food]=-newRating;
    }
    void changeRating(string food, int newRating) {
        change(food,newRating);
    }
    
    string highestRated(string cuisine) {
        pair<int,string> p= *(s[cuisine].begin());
        return p.second;
    }
};

It was one of the submission of todays weekly contest ( number 303 ) . So I want to know that how the 's' map , when that encounter a food of a cuisine with already the highest rating . How it ensures that it finally excepts the lexicographically smaller

Full text and comments »

  • Vote: I like it
  • -5
  • Vote: I do not like it

By anshu2002, history, 2 years ago, In English
void solve(int N,int P){
	if(N==0)
	{
		cout<<"yes\n";
		return;
	}
	if(N-2>=0){
		solve(N-2,P);
	}
	if(N-3>=0){
		solve(N-3,P);
	}
}

It's showing runtime error for N = 200000(Ignore P) . Why ??

Full text and comments »

  • Vote: I like it
  • -5
  • Vote: I do not like it

By anshu2002, history, 2 years ago, In English
class Solution {
public:
    vector<vector<long long>>dp;
    void solve(int m, int n){
        for(int i=1;i<=m/2;i++){
            solve(i,n);
            solve(m-i,n);
            dp[m][n]=max(dp[m][n],dp[i][n]+dp[m-i][n]);
        }
        for(int i=1;i<=n/2;i++){
            solve(m,i);
            solve(m,n-i);
            dp[m][n]=max(dp[m][n],dp[m][i]+dp[m][n-i]);
        }
    }
    long long sellingWood(int m, int n, vector<vector<int>>& prices) {
        dp = vector<vector<long long>>(m+1,vector<long long>(n+1,0));
        for(auto it:prices){
            dp[it[0]][it[1]]=it[2];
        }
        solve(m,n);
        return dp[m][n];
    }
};

this was my approach , showing tle . Why ?? link to the problem

Please somebody correct my mistake

Full text and comments »

  • Vote: I like it
  • +4
  • Vote: I do not like it

By anshu2002, history, 3 years ago, In English
class Solution{
  public:
    int solve(int i,int arr[],vector<int>& dp)
    {
        //cout<<i<<"\n";
        if(i==1)
            return 0;
        if(dp[i]!=-1)
            return dp[i];
        int ans=1000001;
        for(int k=1;k<=arr[i-1] && i-k>=1;k++)
        {
            ans=min(ans,solve(i-k,arr,dp)+1);
        }
        return dp[i]=ans;
    }
    int minJumps(int arr[], int n){
        vector<int>dp(n+1,-1);
        reverse(arr,arr+n);
        int ans=solve(n,arr,dp);
        if(ans==1000001)
            ans=-1;
        return ans;
    }
};

I was solving the problem of minimum number of jumps to reach to the end of an array in geeksforgeeks Problem link

And this was my solution to it is right at the top

At worst , this should show TLE , but showing Segmentation fault . Can someone identify where am I wrong

Full text and comments »

  • Vote: I like it
  • +7
  • Vote: I do not like it