Google L4 Interview Experience

I had a chance to give interviews for Google L4. It consisted of 2 virtual rounds, followed by 2 in‑person rounds.

Virtual Rounds

Round 1

Warmup question: Given a grid of size (N × N), cells S and T, impassable cells with water, find if an S→T path exists, assuming we can only move horizontally/vertically.

I said I will use BFS and push start to queue along with a visited array, then push adjacent cells until the queue is empty. The interviewer said the approach was fine, so no need to code.

Main Question: A mouse is trying to get from its starting position S to a treat T, while moving only on land cells and staying as far away as possible from the cat C. Formally, assume again a square grid of size (N × N), allowing only horizontal and vertical moves, impassable cells with water, and cells S, T, and C. We want to find a path from S to T for which the minimal distance to C along the path is maximal. Use the L1 (Manhattan) distance measure.

I explained I would reuse the BFS from the first part and apply binary search on the distance value. I then wrote a full working code (shown below). The interviewer accepted the solution and the time complexity was given as O(n² log n).

int maximinPath(vector>& grid, vector& source,
                vector& target, vector& cat) {
    int n = grid.size();
    int dr[4] = {0, 0, 1, -1};
    int dc[4] = {1, -1, 0, 0};
    auto distToCat = [&](int x, int y) {
        return abs(x - cat[0]) + abs(y - cat[1]);
    };
    auto isPossible = [&](int value) -> bool {
        if (distToCat(source[0], source[1]) < value ||
            distToCat(target[0], target[1]) < value) return false;
        vector> visited(n, vector(n, false));
        queue> que;
        visited[source[0]][source[1]] = true;
        que.push({source[0], source[1]});
        while (!que.empty()) {
            auto [r, c] = que.front(); que.pop();
            if (r == target[0] && c == target[1]) return true;
            for (int k = 0; k < 4; k++) {
                int x = r + dr[k], y = c + dc[k];
                if (x < 0 || x >= n || y < 0 || y >= n) continue;
                if (visited[x][y]) continue;
                if (grid[x][y] == 0) continue; // water
                if (distToCat(x, y) < value) continue; // too close to cat
                visited[x][y] = true;
                que.push({x, y});
            }
        }
        return false;
    };
    int low = 0, high = 2 * (n - 1), ans = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (isPossible(mid)) { ans = mid; low = mid + 1; }
        else { high = mid - 1; }
    }
    return ans;   // -1 means T unreachable even with no restriction
}

Round 2

The second round focused on “googliness” and behavioral questions. I answered candidly about why I want to work at Google, how I would act as a manager, and the importance of delivery.

On‑Site Rounds

Round 3

I was asked: given a set of coordinates, find the maximum‑area rectangle. The rectangle’s sides can have any orientation (not necessarily axis‑parallel). The problem is similar to LeetCode "Minimum Area Rectangle II".

I described an approach using slopes to identify opposite sides, storing points in maps keyed by coordinates and slopes, and then enumerating triples of points to construct rectangles. I discussed time complexity (O(n³) to find three points, O(n⁴) in the worst case) and wrote partial code (shown below).

class Solution {
public:
    double minAreaFreeRect(vector>& points) {
        int n=points.size();
        if(n<4)return 0.0;
        double ans=1e18;
        map,map>>> mp;
        for(int i=0;i

int jobSchedulingInternal(vector& startTime, vector>& p,vector&dp,int n, int idx)
{
    if(idx>=n)return 0;
    if(dp[idx]!=-1) return dp[idx];
    int skip= jobSchedulingInternal(startTime,p,dp,n,idx+1);
    int take=p[idx][2];
    int nextIndex=n;
    auto it=lower_bound(startTime.begin()+idx+1,startTime.end(),p[idx][1]);
    if(it!=startTime.end())
        nextIndex=it-startTime.begin();
    take+=jobSchedulingInternal(startTime,p,dp,n,nextIndex);
    return dp[idx]=max(skip,take);
}
int jobScheduling(vector& startTime, vector& endTime, vector& profit) {
    int n=endTime.size();
    vectordp(n,-1);
    vector>p;
    for(int i=0;i

map mp;
vector res;
void precomputation(vector nums)
{
    int l=0;
    int n=nums.size();
    for(int r=0;r1)
        {
            mp[nums[l]]--;
            l++;
        }
        res.push_back(l);
    }
}
bool isUnique(int start,int end)
{
    return res[end]<=start;
}