I had a chance to give interviews for Google L4. It consited 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 vis array, and then push adjacent values and contonue until q is empty and return false if q becomes empty or true if target is reached then i said i will code, to which interviewer said that the approach is 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 (aka Manhattan) distance measure, i.e., the sum of the horizontal and vertical distances.
I told him i will use bfs function i wud have written in previous part and use binary search to find the value, he asked why binary search, i explained bcs we need min value at max distance then, i took references from first question and at last gave him a fully working code,which is below:
int maximinPath(vector<vector<int>>& grid, vector<int>& source,
vector<int>& target, vector<int>& 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<vector<bool>> visited(n, vector<bool>(n, false));
queue<pair<int,int>> 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
}then i gave him n^2log n, as tc, then i said lets take example he said not needed as we are out of time and it looks gud,
--------------------------------Round 2------------------------------
Second round was googlyness i gave very candid answers then she asked why google i said we are conditioned like this only that google is ultimate goal then i said if not this time i will try again then many
questions like this i was completely real. i was asked what wuld i do if i am manager, i said i have manager i expect things from manager i will try to inculcate some, then work related i said delivery is important, then i gave many answers which kind of justifid managers sometimes sometimes employees, mentioned putting extra effort if needed.
**Result:**recruiter earlier told me while scheduling that since ur first 2 irtual rounds are quite positive and she want to close loop soon. So the process moved to onsite rounds.
On-Site Rounds
-----------------------------Round 3--------------------------------
I was asked the question given coordinates, find max rectangle area. axis can be any, need not be parallel to axis.The question was similar to https://leetcode.com/problems/minimum-area-rectangle-ii/description/
I told her for rectangle. we have a side, each side has slope which is y2-y1/x2-x1, for rectangle it should have third point at slope perendicular, which is reciprocal, so what i will do is store coordinates in set/map, then use this set to find third
point at reverse slope, then we have 3 points, so we can find fourth one.
she asked TC i said n^3 to find 3 points and using set to find 4th point.
Then i said i will take a map<vector,vector<vector>> where first key will have x1,y1 and slope and second will have points x2,y2, she said arent there too many keys, i said yes then she said how about slope only i said we can try and push both x1,y1 and x2 y2. then she said how will u make sure combinations are not duplicated i said i will take outer loop 0 to n then inner loop i+1 to n, then i said we can code she said yes, so while coding rather than map<double,vector<vector>, as it is better if i store it like map<vector<int,int>,map<double,vector<vector>>,
i said for each coord i will take slope as second key and second coord is pushed in vector to make sure that we get correct points. this is how i will compute, then i will use for loop from 0 to n for each point then i will find the map for this coord, and for each slope if reverse slope is not present i will continue, else i will look for coordinate to get second point. then she said you can comment as only 2-3 mins are left and i said i can use reverseslope for third loop inside and then we have 3 we can find fourth. she said it is n4 no? i said yes in worst case, but code is not complete, could write below code:
class Solution {
public:
double minAreaFreeRect(vector<vector<int>>& points) {
int n=points.size();
if(n<4)return 0.0;
double ans=1e18;
map<vector<int>,map<double,vector<vector<int>>>>mp;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(i==j)continue;
int x1=points[i][0];
int y1=points[i][1];
int x2=points[j][0];
int y2=points[j][1];
double slope=((double)(y1-y2))/((double)(x1-x2));
mp[{x1,y1}][slope].push_back({x2,y2});
}
}
for(int i=0;i<n;i++)
{
int x1=points[i][0];
int y1=points[i][1];
for(auto &[slope,vectorc]:mp[{x1,y1}])
{
for(auto it:vectorc)
{
int x2=it[0];
int y2=it[1];
double revers=((double)(x2-x1))/((double)(y1-y2));
if(mp[{x1,y1}].count(revers)==0)continue;
//Incomplete code
}
}
}
}
};then she said any question i said i am gud.
-----------------------------Round 4--------------------------------
The interviewer came, he said if i want to rest for a little and have water.I said no we can continue. He asked if i need a glass of water or need to freshen up i said no i am gud we can continue, then he gave me question,
where start end times are given along with profits, we need to find the max profit considering no overlapping intervals are to be selected. This was same as https://leetcode.com/problems/maximum-profit-in-job-scheduling/description/
I started thinking then he asked if any brute force approach is there in my mind, i said we can sort by start time and then we can either
take current value or skip it, then we continue to do this until end and thus we can store the max, he said yes and what is tc, i said since 2 branching so at worst exponential, he said yes then how you will u optimise it i said recusrion calls should be cut. He asked how to do that, i said i will use DP to memoize, then he said what will u do i said i will condense all 3 arrays into a vector of vector where start is first value then sort them, then i create a dp vector where it stores -1 for each index then i run memoization recursive solution then i pass dp,0, n and condensed data structure, then i said i can use set of vector but since i need index, so i will keep vector of vector only, then he said how many arrays i said i can do it with 2, one dp and other vector of vector, then he said,alright fine u can take it like all 3 arrays are such that the given interval is sorted by starttime and then endtime and profit are such that they are also sorted according to start time then i passed all 3 along with dp and index and n and in code i wrote if dp[idx] is not -1 then return the value if idx>=n, return 0; then take skip where idx is incremented and also have take which is curent value then for end time at given index i, find the lowerbound start time, from begin plus idx +1 to end to make sure theat it is always forward he said ok, then i calculated idx as it-start.begin(), then in take i had take+=recu where i pass nextindex found using lowerbound. then make max of both in the dp[idx]=max(take,skip).
Below was complete code:
int jobSchedulingInternal(vector<int>& startTime, vector<vector<int>>& p,vector<int>&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<int>& startTime, vector<int>& endTime, vector<int>& profit) {
int n=endTime.size();
vector<int>dp(n,-1);
vector<vector<int>>p;
for(int i=0;i<n;i++)
{
p.push_back({startTime[i],endTime[i],profit[i]});
}
sort(p.begin(),p.end());
sort(startTime.begin(),startTime.end());
return jobSchedulingInternal(startTime,p,dp,n,0);
}He asked TC, i said nlogn, n for loop and log n for lower bound and SC is n because of dp array and n for recursion stack but he said it can be discounted.
10 minutes were left, then he said lets move to second question. He asked
if we have array and a range of index how to check if it has unique value.
I told him i will take set, better to use unordered set as its fetching is O(1) while it is O(logn) for set then in for loop range, if unordered_set contains value return false, else put it in unordered_set. he said tc i said n and sc is n then he said if many ranges, i said, I have read somewhere that variable ranges involves generally segment tree, then he said we can do it simple way as well, i said how abt taking a map storing last index, and in vector -1 for first and last index for next values, and changing map value to find its values, this is precomputation and then traversing if for any range,we check if value is not beyond lower bound it is false.
He said still O(n),as traversing is needed. So,it will optimise but not that much, i said he was right then i said how abt taking prefix sum thing, where value 0 can be first value , if we do something like this, then he said how about going backward till what index subarray is unique ending at current index.
I said i will take map and vector then in precomputation i will use l and r for each r add freq by 1 in map. Yhen while this freq is greater than 1, i will do mp[nums[l]]--; l++;,
then outside the while loop res[r]=l;
then for each range if res[end]<=start return true;
I gave below code:
map<int,int>mp;
vector<int>res;
void precomputation(vector<int>nums)
{
int l=0;
int n=nums.size();
for(int r=0;r<n;r++)
{
mp[nums[r]]++;
while(mp[nums[r]]>1)
{
mp[nums[l]]--;
l++;
}
res.push_back(l);
}
}
bool isUnique(int start,int end)
{
return res[end]<=start;
}When asked TC, i said O(n) for precomputation, and O(1) for each range.
He said might need some change,then himself said looks good.
This is my whole process. Can anyone please tell what are chances.
Update-Got call from recruiter, she told me 3 rounds are highly positive, 1 round is not positive. Lets see what happens now.
