Google SWE New Guard 2021

One can apply for Google's SWE Guard either through LinkedIn or through their own site. After shortlisting you will be invited for the Google’s Online Challenge Round. Here you need to solve 2 questions. Time Limit is - 1 hr

The cost of a string

Your task is to create a string S consisting of lowercase English alphabets. You are given an array A of size 26 where A[i] denotes the cost of using the ith alphabet (consider 1-based indexing). Find the lexicographically largest string S that can be created such that the cost of building the line is exactly W.
Note: The cost of string S is equal to the sum of the cost of individual characters in it.
A string P is lexicographically smaller than string Q, if P is a prefix of Q and is not equal to Q or there exists an i such that Pi < Qi and for all j < i, Pj = Qj. For example, ‘abc’ is lexicographically smaller than ‘abcd’ and ‘abd’ is lexicographically smaller than ‘abec’ and ‘afa’ is not lexicographically smaller than ‘ab’ and ‘a’ is not lexicographically smaller than ‘a’.

• The first line contains an integer T denoting the number of test cases.
• The first line of each test case contains 26 space separated integers denoting the costs of characters from ‘a’ to ‘z’.
• The second line of each test case contains an integer W.

• For each test case, print the required string S in new line.

• 1<=T<=5
• 1<=A[i]<=10^5
• 1<=W<=10^4

      
Sample Input 1:
1
1 1 2 33 4 6 9 7 36 12 58 32 28 994 22 255 47 69 558 544 21
36 48 85 48 58
236

Sample Output 1:
zzzze

Cost of ‘z’ = 58, Cost of ‘e’ = 4
Cost of ‘zzzze’ = 4*58 + 4 = 236
Note: ‘zzzze’ is the lexicographically largest possible string with cost = 236

Sample Input 2:
1
81 149 907 611 114 730 867 529 50 890 981 777 418 659 374
106 614 526 826 158 510 240 971 573 727 513
5449

Sample Output 2:
zzzzzzzzzvtteaa

      

    
        #include<bits/stdc++.h>
        using namespace std;
        
        int main(){
            int tcs;
            cin>>tcs;
            while(tcs--){
                vector <int> value(26);
                set <int> s;
                vector <int> uni;
                for(int i=0;i<26;i++){
                    cin>>value[i];
                    if(!s.count(value[i])){
                        uni.push_back(value[i]);
                        s.insert(value[i]);
                    }
                }
                s.clear();
                sort(uni.begin(),uni.end());
                int weight;
                cin>>weight;
                vector <int> occ(26);
                for(int i=0;i<26;i++){
                    occ[i] = weight/value[i];
                }
                vector <int> table(weight+1,0);
                table[0] = 1;
                
                for(int i=0; i<uni.size(); i++) 
                for(int j=uni[i];j<=weight; j++) 
                    table[j] += table[j-uni[i]];
                
                vector <pair<char,int>> ans;
                for(int i=25;i>=0;i--){
                    if(weight==0)break;
                    if(weight%value[i]==0){
                          ans.push_back({i+'a',weight/value[i]});
                          weight = 0;
                          break;
                        }
                    for(int j=occ[i];j>=1;j--){
                        if(table[weight-(j*value[i])] && weight-(j*value[i])>=0){
                            ans.push_back({i+'a',j});
                            weight = weight - (j*value[i]);
                            break;
                        }
                    }
                }
                for(int i=0;i<ans.size();i++){
                    for(int j=0;j<ans[i].second;j++){
                        cout<<ans[i].first;
                    }
                }
                cout<<"\n";
            }
        }
    

Finding sum of Integers

You are given an integer A. Consider two integers A and A+1. Print the sum of the numbers that cannot be formed using any combination of A and A+1. Since the answer can be large, print the sum modulo 10^9 + 7. A combination of A and A+1 is represented as integer Z that can be denoted as x*A + y*(A+1) where both x and y are integers and x,y >= 0.

Input format

• The first line contains T denoting the number of test cases.
• Each of the T lines contains a single integer A.

• For each test case, print the sum of the numbers that cannot be formed using any combination of A and A+1 in a new line. Since the answer can be large, print the sum modulo 10^9+7.

• 1<=T<=10^3
• 1<=A<=10^4

      
      Sample Input 1:
      3
      2
      3
      4

      Sample Output 1:
      1
      8
      30

      Explanation:
      For A = 2, we can generate all numbers with combinations of A and A+1 except 1. So, the answer is 1.
      For A = 4, we can generate all numbers with combinations of A and A+1 except 1,2,3,6,7,11. So, the answer is 30.

      

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

int main(){
    int tcs;
    cin>>tcs;
    while(tcs--){
        int n;
        cin>>n;
        int limit = (n*(n-1))-1;
        int left = n;
        int right = n+1;
        long sum = 0;
        int mod = 1e9+7;
        
        for(int i=n;i<=limit;i+=left){
            int j = i;
            while(j<=right){
                sum = sum + j;
                j++;
            }
            right += n+1;
        }
        long long value= (long long)limit*(limit+1);
        value /= 2;
        
        cout<<(value-sum)%mod<<endl;
    }
}