Google | OA Coding Questions and Solutions | 2022 | Application Engineer | India

Question

All past online assesments of Google can be found using the tag "google_oa" in the search bar.

Here is the link :  https://www.desiqna.in/tag/google_oa

Answer 1

Profile: Application Engineer (CTC 22.72LPA)
So basically there was two questions in this test carrying 30 marks each.

 

Q1. Attached:

 

Q2. Attached:

 

Comments

Question 1: Greedy + Stack

Here's my C++ Implementation
```cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;

int const INF = 1e8;
int const MOD = 1e9 + 7;

inline void init_code(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
}

ll infPowers[100001] = {1};

void build(){
    for(int i = 1; i < 100001; i++){
        infPowers[i] = (1ll * infPowers[i - 1] * INF)%MOD;
    }
}

vector<ll> findNearestGreaterOnLeft(vector<ll> &arr){
    int n = arr.size();
    
    stack<ll> stack;
    vector<ll> nearestGreaterLeft(n);

    for(int i = 0; i < n; i++){
        while(stack.size() && arr[stack.top()] <= arr[i]) stack.pop();
        
        if(stack.empty()) nearestGreaterLeft[i] = -1;
        else nearestGreaterLeft[i] = stack.top();

        stack.push(i);
    }
    return nearestGreaterLeft;
}

ll getAwesomeness(vector<ll> &arr, ll i, ll j){
    return (arr[i] - arr[j]) * infPowers[arr.size() - j + i];
}

void solve(){
    ll n;
    cin >> n;

    vector<ll> arr(n);

    for(auto &i: arr) cin >> i;

    vector<ll> nearestGreaterOnLeft = findNearestGreaterOnLeft(arr);

    ll maximumAwesomeness = 0;
    for(int i = 1; i < n; i++){
        if(nearestGreaterOnLeft[i]!= -1){
            ll currentAwesomeness = getAwesomeness(arr, nearestGreaterOnLeft[i], i);
            maximumAwesomeness = max(maximumAwesomeness, currentAwesomeness);
        }
    }
    cout << maximumAwesomeness << endl;
}

int main()
{
    // init_code();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    build();

    int t;
    cin >> t;

    while(t--){
        solve();
    }
    return 0;
}
```

---

The second Question Pic is not clear, can you please re-upload it in better quality?