TikTok || OA (2 Questions) ( 🥵 Hard )
Anonymous User
6735
TikTokAlgorithmData StructureInterview

First Question

image

image

image

image

2nd Question

image

image

UPDATE

First question is solved and i tried out second question and this is my code
it passes 50% test cases and giving wrong answer in other 50%.

idea : i am storing all elements of matrix with its row number and applying sliding window and keep an lock variable if it 0 then window include at least m/2 elements from all row.

now i can't figure out why it is not working for all inputs is there any error in logic?

Thank You.

long getMaxProduct(vector<vector<int>> arr) {
    
    int n=arr.size(),m=arr[0].size();
    
    vector<pair<int,int>> v;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            v.push_back({arr[i][j],i});
        }
    }
    sort(v.begin(),v.end());
    int i=0,j=0;
    long long ans=0;
    int lock=n;
    long long diff=INT_MAX;
    
    // for(int i=0;i<v.size();i++)
    // {
    //     cout<<"{"<<v[i].first<<" "<<v[i].second<<"} ";
    // }
    vector<int> mp(n,0);
    while(j<v.size())
    {
        if(++mp[v[j].second]==(m+1)/2)
        {
            lock--;
        }
        if(j<m-1&&v[j].first==v[j+1].first)
        {
            j++;//expand window
            continue;
        }
        while(lock==0)//m/2 elements taken from all rows
        {
            int tempdiff=v[j].first-v[i].first;
            if(diff>tempdiff)
            {
                diff=tempdiff;
                ans=diff*(j-i+1);
                // cout<<diff<<" "<<i<<" " <<j<<" "<<v.size()<<endl;
            }
            if(mp[v[i].second]==(m+1)/2)
            {
                lock++;
            }
            mp[v[i].second]--;
            i++; //srinking window
            // cout<<lock<<" "<<i<<" "<<mp[v[i].second]<<endl;
        }
        j++;
    }
    return ans;
}

1st Question Code (Topological sort) credit: @leetcode_dafu

int getMinCost(vector<int> val, int t_nodes, vector<int> f, vector<int> t) {
    
    vector<int> deg(t_nodes+1,0);
    
    for(int z=0;z<t_nodes;z++)
    {
        deg[f[z]]++;
        deg[t[z]]++;
    }
    
    vector<vector<int>> adj(t_nodes+1);
    
    for(int z=0;z<t_nodes;z++)
    {
        adj[f[z]].push_back(t[z]);
        adj[t[z]].push_back(f[z]);
    }
    vector<bool>vis(t_nodes+1,0);
    
    queue<int> q;
    for(int z=1;z<=t_nodes;z++)
    {
        if(deg[z]==1)
        {
            q.push(z);
        }
    }
    int ans=0;
    while(!q.empty())
    {
        int curr=q.front();
        q.pop();
        vis[curr]=1;

        for(int i:adj[curr])
        {
            if(!vis[i])
            {
                deg[i]--;
                if(val[curr-1]&1)
                {
                    ans++;
                    val[i-1]--;
                }
                val[curr-1]=0;
                if(deg[i]==1)
                    q.push(i);
            }
        }

    }
    return ans;
}
Comments (9)