Google Software Engineer Interview Experience — Mouse, Cheese and Cat Grid Path, a Googlyness Manager Question, and a Non-Axis-Aligned Max Rectangle

Phone Interview 1

Warmup Question:
Given an N x N grid with a start cell S and a target cell T, where some cells are impassable water. You can only move horizontally or vertically. Determine whether a path from S to T exists.

Main Question:
Given an N x N grid. A mouse starts at S and the goal is the cheese at T. The grid also has impassable water cells and a cat C. The mouse can only move horizontally or vertically on land cells. Find a path from S to T such that the minimum Manhattan distance from any point on the path to the cat C is as large as possible.

Phone Interview 2 (Googlyness)

Googlyness Questions:

1. Why Google? What will you do if you don't pass this time?
2. If you were a manager, what would you expect from a manager, and how would you live up to that yourself? How would you handle project delivery, balancing the interests of management and employees, and putting in extra effort when necessary?

Onsite Round 1

Coding Question:
Given a set of points on a 2D plane, find the largest rectangle area that can be formed from them. The sides of the rectangle do not need to be parallel to the axes.
(Similar to LeetCode 963, Minimum Area Rectangle II, but this one asks for the maximum area.)

Onsite Round 2

Question 1:
Given jobs with startTime, endTime and profit, find the maximum profit you can get without picking overlapping jobs.
(LeetCode 1235, Maximum Profit in Job Scheduling)

Question 2:
Given an array and a range, determine whether the elements in that range are unique.

1. Follow-up: if there will be many queries on different ranges, how would you optimize?
2. Requirement: do the precomputation in the best time complexity you can, so that each query takes O(1).