Google L3 Interview Experience - 1.5 YOE
Anonymous User
1565
GoogleInterview

Phone Screen:

Problem: Number of ways to make a mobile lock pattern with an n x n grid.
Approach: DFS + Backtracking

Onsite Interviews:

1st Onsite – Binary Search + DFS

Problem: Smallest Rectangle Enclosing Black Pixels
Approach: Used binary search and DFS to efficiently find the smallest rectangle enclosing the black pixels.

2nd Onsite – Implementation (Ad Server)

Problem: Design an Ad Server that supports two operations:

  1. insertAd(content, score) – Inserts an ad with given content and score.
  2. serveAd() – Serves the best ad (highest score) while ensuring the same ad is not served consecutively.
    Approach: Used priority queues for ad retrieval and a cache to track previously served ads.

3rd Onsite – Max Sum Subarray with Constraints

Problem: Given an array of integers nums, find two indices i and j such that i ≤ j, nums[i] = nums[j], and the sum of nums[i] to nums[j] is maximized.
Approach: Used prefix sums and a hashmap to track indices of repeating elements while maintaining the maximum sum.

Here’s my solution for this problem:


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

int pr(vector<int>&pref,int i,int j){
    if(i>0)
    return pref[j]-pref[i-1];
    return pref[j];
}
int main(){
    int t;
    cin>>t;
    while(t--){
        int n ;
        cin>>n;
        vector<int>v(n);
        int maxVal = INT_MIN;
        int maxi = -1;
        int maxj = -1;
        for(int i=0;i<n;i++)cin>>v[i];
        vector<int>prefix(n);
        unordered_map<int,vector<int>>mp;
        for(int i=0;i<n;i++){
            if(i>0)prefix[i]=prefix[i-1];
            prefix[i]+=v[i];
            mp[v[i]].push_back(i);
        }
        for(auto k:mp){
            int key = k.first;
            vector<int> val = k.second;
            int ci = val[0], cj = val[0],cm = v[val[0]];
            for(int i=0;i<val.size();i++){
                 if(i){
                    int sums =pr(prefix,val[i-1],val[i]);
                    if(sums<v[val[i]]){
                        ci = val[i];
                        cj = val[i];
                        cm = v[val[i]];
                    }else{
                        cm = sums;
                        cj = val[i];
                    }
                 }
                 if(maxVal<cm){
                    maxVal=cm;
                    maxi = ci;
                    maxj = cj;
                 }
            }
        
        }

        cout<<maxi<<" "<<maxj<<" "<<maxVal<<endl;
    }

    return 0;

}

Timeline:
November 12: Initial Call with Recruiter
November 28: Phone screening
January 14: 1st Onsite
January 16: 2nd Onsite
(Initially all Onsites interviews were planned in the same week. Rescheduled around 5 times)
February 4: 3rd Onsite
February 6: Googlyness round
February 19: team matching
March 5: 4th Onsite round

Comments (7)