TikTok Coding OA

Question

Given an integer array nums, handle multiple queries of the following 2 types:

 

1. Given a value x, update all elements inside nums that are less than x to x
2. Given an index i and a value v , modify nums[i] to v

 

Return nums after running through all queries.

 

Example
Input
nums:

 

[1,2,3,4,5]

 

queries:

 

[[1,3,-1],[2,0,1],[1,4,-1]]

 

After first query, nums become : [3,3,3,4,5]
Explanation : [1,3,-1] refers to type 1 so update all numbers in nums that are less than 3 to 3

 

After second query, nums become : [1,3,3,4,5]
Explanation : [2,0,1] refers to type 2 so modify nums[0] to 1

 

After third query, nums become : [4,4,4,4,5]
Explanation : [1,4,-1] refers to type 1 so update all numbers in nums that are less than 4 to 4

 

Output

 

Return

 

[4,4,4,4,5]

 

Constraints
1 <= n <= 10^6, n = length of nums
1 <= m <= 10^6, m = length of queries

Answer 1

#include <bits/stdc++.h>

using namespace std;
typedef long long int ll ; 
int main() {
    ll n ; 
    cin>>n ; 
    ll b[n+5] = {0} ; 
    ll g[n+5];
    ll i = 0 ; 
    while(i<=n-1){
        cin>>b[i] ; 
        g[i] = -1; 
        i++;
    }
    ll t ; 
    cin>>t ; 
    ll w[n+5][5] ; 
    i = 1 ; 
    while(i<=t){
        cin>>w[i][1];
        cin>>w[i][2];
        cin>>w[i][3];
        i++;
    }
    
    
    
    
    unordered_map <ll,ll> kk ; 
    
    ll vv = 0 ; // keeps track of maximum suffix value of operation of type 1 for < 
    i = 3 ; 
    while(i>=1){
        
        if(w[i][1]==2){
            
            ll y = w[i][2] ; 
            if(kk.find(y)==kk.end()){
                
                g[y] = w[i][3] ; 
                
                g[y] = max(g[y],vv);
                
                
                
            }
            kk[y]++;
            
        }
        
        if(w[i][1]==1){
            //cout<<w[i][2]<<"\n";
            vv = max(vv,w[i][2]);
            
        }
        i--;
    }
    //cout<<vv<<"\n";
    
    i = 0 ; 
    while(i<=n-1){
        if(g[i]==-1){
            g[i] = max(b[i],vv);
        }
        cout<<g[i]<<" ";
        i++;
    }
    return 0 ; 
}

Answer 2

Vid solution by Kumar K :