Python Interview with a Google engineer

Interview Summary

Problem type: Seat Allocation
Interview question: A cinema has n rows of seats, numbered from 1 to n and there are ten seats in each row, labelled from 1 to 10.
Given the array reservedSeats containing the numbers of seats already reserved, for example, reservedSeats[i] = [3,8] means the seat located in row 3 and labelled with 8 is already reserved.
Return the maximum number of four-person groups you can assign on the cinema seats. A four-person group occupies four adjacent seats in one single row. Seats across an aisle are not considered to be adjacent, but there is an exceptional case on which an aisle split a four-person group, in that case, the aisle split a four-person group in the middle, which means to have two people on each side.

Example 1:

Input: n = 3, reservedSeats = [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]
Output: 4
Explanation: The figure above shows the optimal allocation for four groups, where seats marked with blue are already reserved and contiguous seats marked with orange are for one group.

Example 2:

Input: n = 2, reservedSeats = [[2,1],[1,8],[2,6]]
Output: 2

Example 3:

Input: n = 4, reservedSeats = [[4,3],[1,4],[4,6],[1,7]]
Output: 4

Interview Feedback

Feedback about Meta Slide Rule (the interviewee)
Advance this person to the next round? Yes
How were their technical skills? 4/4
How was their problem-solving ability? 3/4
What about their communication ability? 4/4

Strengths:

• Fast coder
• Concise coder
• Knows how to capture, how to store, and how to evolve computational state
• Good typing and problem-visualizing skills: I could follow the visual understandings of the cinema seat allocation
• Code looks to be in a mostly working state - 3 minutes of tweaking and I can get it to pass test cases on Leetcode
• Needed hints or nudges here-and-there, but with the hints, worked their way to an effective solution.
• Technical persistency: they did not give up on their solutioning.
• Big-O Time-Space Complexity Reasoning Correct and Well-Justified to Optimal Complexity

Areas for Refinement:

• Really think of edge case scenarios. Minimal inputs/edge case scenario thinking will help you solution faster and catch issues ahead of time
• With edge case scenario, really think about reviewing your code across different scenarios. We really dived into the scenario of a single person in the middle which could break your rules engine
• Think of case decomposition: we talked about the cases of seats with index groupings - (2,5); (4,7); and (6,9)
• Remember if we can leverage nested expressions/nested conditionals

Other:

• Mention or think about modularizing code ahead of time
• We talked about logging posture or how to extend code in a production setting. If you can highlight your past experiences, or mention to interviewers "Here's what I'd do in a production setting", you get more kudos points :-)
• Not all interviewers know this, but mention both explicit stack space and implicit stack space. Your approach is iterative - not recursive, meaning that you use only O(1) call stack space

I'd pass this person for Google L3 or Google L4 positions (Strong Hire).
For Google L5 leveling or higher, I'd place at (Hire).

Feedback about Purple Brontosaurus (the interviewer)
Would you want to work with this person? Yes
How excited would you be to work with them? 3/4
How good were the questions? 3/4
How helpful was your interviewer in guiding you to the solution(s)? 4/4

Strengths:

• Thanks for guiding me to edge cases and to think more deeply about my approach
• Responsive, provided redirection

Improvements:

• Nothing, the sound was cut off in the middle of the call, but that's probably a technical issue

Interview Transcript

Purple Brontosaurus: So I won't disclose my name, but I've been working as a software engineer for almost like six years so far. I spent some time working for Google and other companies out here in the Bay Area. I'm your mock interviewer for today, so I just want to give a bit of an intro and. Yeah, can you tell me a bit more about yourself?

Meta Slide Rule: Yep, sure. So I am a software engineer. I have been working for a year and a half, almost two years, fresh out of college and I'm working at a series B startup. But I have a Google interview lined up for the on site. So I'm just prepping for that particular round.

Purple Brontosaurus: All right. I'm definitely wishing you best of luck. I've done on sites for Google. They are rigorous, but they are also passable.

Detailed feedback on the interview process and example coding problems were discussed but omitted for brevity.

Images

Example Interview Videos:

• Seat Allocation at Scale: Coding Interview with a Google Engineer (Python)
• Additional interviews related to data structures and problem-solving scenarios.