Note: This content has been reviewed and formatted using ChatGPT to correct grammatical issues and improve clarity.

Background

• Experience: 2 years in Full-Stack Development
• Competitive Programming: Master on Codeforces
• Application: Applied via the Google Careers portal (no referral)

Recruiter Call

I received a call in the first week of April. The recruiter inquired about my background, experience, and salary expectations. I was asked to share five available dates for interviews, with a maximum of two weeks' preparation time. However, the actual interviews were scheduled for later dates than initially discussed. Each round was set for 45 minutes.

Elimination Round (45 mins)

Timezone: US
Problem: A MEX-like problem involving sequence numbers (long long int) and an initial sequence number x. Two types of queries were involved:

1. Add a sequence number y
2. Fetch the minimum missing sequence number from the current set

Solution:
I used a HashSet to store the incoming sequence numbers and a variable to track the current missing sequence. With each insertion, the tracker increments until it hits the next missing value. For query type 2, we return this number. I also discussed time complexity in detail.

Follow-up Questions:

• Why not trigger the increment in the "get minimum" call?
  I explained that placing the increment depends on the query pattern. If query type-2 is less frequent, it’s more efficient to place it during the insertion step.

• Real-world application and the role of the initial sequence number?
  I related it to a video loading use case, where the initial sequence number represents the starting frame. Missing frames indicate a need for retransmission.

• How to detect unprocessed (corrupted) frames?
  By inserting each received frame into a HashSet and removing it upon processing.

• How to distinguish between corrupted and unprocessed frames?
  Through timestamp-based invalidation.

Timeline:

• Question & clarification: 5–10 mins
• Approach: 8 mins
• Implementation: 8 mins
• Follow-up: 10 mins
• Interviewer questions: 5 mins
• Ended early

Result: Advanced to next rounds — 3 Technical + 1 Googleyness & Leadership (G&L)

Technical Interview 1 (45 mins)

Timezone: India
Problem: An array (garland) contains d diamonds and r rubies (both even). You are allowed up to 2 cuts to divide it into two parts such that both parts contain the same number of diamonds and rubies.

Approach:

• For 1 cut: Only the middle position works.
• For 2 cuts: First and last segments form one group; use a sliding window of fixed length n/2.
  Achieved an O(n) time solution using O(1) space.

Follow-up:

• What if there's a third type of stone and up to 3 cuts allowed?
  I used the same logic for up to 2 cuts. For 3 cuts, fixed the first segment and iterated possible joins for a rough O(n²) solution. Did not implement.

Timeline:

• Question & clarification: 5–10 mins
• Approach: 5–10 mins
• Implementation: 20–25 mins
• Follow-up: 2–3 mins
• Interviewer questions: 2 mins

Technical Interview 2 (50–55 mins)

Timezone: India
Problem: In an undirected graph where nodes represent homes, two persons (nodes a and b) must reach a destination node c. They may travel independently or meet up on the way and then travel together. Joint travel on an edge counts as a single unit of cost.

Approach:
Precomputed all shortest paths between node pairs. For each node, considered it as a meeting point for a and b, then both travel together to c. Computed the minimum total cost.

Time Complexity: O(n²)

Follow-up:

• Now suppose there are 3 friends: a, b, and d—how would all of them reach c?
  I considered 3 possible groupings: (a & b), (b & d), (d & a), with each pair meeting before the third joins. For each, iterated over potential join points to compute the best path. Did not implement.

Timeline:

• Question & clarification: 5–10 mins
• Approach explanation: 15–20 mins
• Implementation: 15–20 mins
• Follow-up: 5 mins
• Interviewer questions: 5 mins

Technical Interview 3 (45 mins)

Timezone: Australia

Problem 1: Remove a node with a given value from a linked list
Response: Implemented quickly

Problem 2: Create an n × m maze such that there is exactly one valid path between every two cells.
Initial Idea:
Start from cell (1,1), go straight if possible, else turn left—creates a spiral path. Explained this for ~10 mins before self-correcting.

Final Idea:
A simpler method—draw all horizontal lines, but skip one column per row to maintain a unique path between all cells.

Timeline:

• Problem 1: 20 mins
• Problem 2: Question & clarification (5 mins), Idea 1 (10–15 mins), Idea 2 (2 mins)
• Interviewer questions: 5 mins

Technical Interview 4 (45 mins)

Timezone: US
Note: This was supposed to be a G&L round, but the interviewer decided to conduct a technical interview.

Problem: Inside an n × m rectangle with a set of horizontal and vertical lines, find how many squares can be formed.

Approach:
Used preprocessing to store the maximum length of consecutive horizontal/vertical lines ending at each point. For each potential square, checked if it could be formed using these precomputed values.

Timeline:

• Interviewer joined late (~5–10 mins delay); I created and shared a Google Doc
• Question & clarification: 5–10 mins
• Solution explanation + pseudocode: 25–30 mins
• Interviewer questions: 5 mins

Final Result

Rejected. The recruiter shared that the last two rounds received negative feedback. Surprisingly, during the final interview, the interviewer actively followed my approach, asked relevant questions, and signaled understanding throughout the session. The rejection note cited that the interviewer was “not able to understand the solution,” which was inconsistent with the actual interaction.