Islands After K Days of Erosion

Watch someone solve the islands after k days of erosion problem in an interview with a Google engineer and see the feedback their interviewer left them.

Interview Summary

Problem type
Islands After K Days of Erosion
Interview question
Given a 2D grid where 1 represents land and 0 represents water, find the number of islands remaining after K days of erosion. Each day, any land cell adjacent to water becomes water. The challenge involves efficiently calculating how long each land cell survives before being eroded, then counting connected components of cells that survive past K days.

Interview Feedback

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

Technical: 3 out of 4. I think it’s very important for you to finish writing the code for a working solution, and I think it’s possible you could’ve done this if I accommodate another 10-15 minutes for you to finish writing code, so I don’t think I can rate you any lower 2/4 or higher 4/4 today. For the same reason, I would advance you.
Problem solving: 4 out of 4. You have quite strong problem solving, and pretty much came across a working and optimal solution yourself. You’re very structured in your process, and considered runtime up front. Communication: 4 out of 4. I understood what you were thinking the entire time, with a couple pretty minor stumbles that I don’t think are worth rating you lower at 3/4: once when discussing the innerness solution and I misunderstood, and the second when I think you actually meant BFS since that’s what you talked through but actually meant DFS. I think the latter might be a technical point where you acknowledged you might have overlooked if you were going too fast.

Things you did well:

• You seem to be quite prepared, and you were able to talk through the Number of Islands problem, solution and complexity analysis easily.
• As mentioned, your problem solving strategy is strong, where you talked through an initial brute force option with simulation, then came across an optimal and correct solution yourself without much strong direction. You immediately recognized the perimeter/distance search solution after briefly talking about simulation, then refined this solution over 15 minutes.
• You considered concrete examples yourself, which was very clear and useful to do.
• You were organized in writing out notes in comments as needed.
• You balanced working with your interviewer to stay on track while driving appropriately for the level you're targeting.
• You were very careful in your C++ syntax to make sure it was readable, idiomatic and correct. Your naming was helpful and you used code modularization when needed. You stubbed out an uninteresting method with sound reasoning. You also mentioned you had good reasoning to spend time writing out types for readability, which makes sense.

Areas of improvement:

• As you know, the biggest area of improvement is pacing. You spent 16 minutes planning today and 19 minutes writing code and pseudo-code, which is right up against the default time limit for an interview.
• You took quite a bit of time to write readable, idiomatic and efficient C++.

My advice:

• You're quite self-aware, which is good. You mentioned your feedback is now quite consistent across interviews, which means you have a strong signal to go faster. Your time accommodation is very helpful. If your timing today is consistent with your other interviews, then I think you can spend ~3 minutes going faster in planning and most of the time going faster when writing pseudo-code and code while maintaining correctness. It's possible with an accommodation of +15 minutes and if your estimate is right that you could finish writing code within that time, then that would bring you right to your time limit, so to be safe, you definitely have room to save ~5 minutes going faster, or ~10 minutes going faster to have buffer time to go through tests and talk about runtime again.
• It would be nice if you didn’t have to write C++ :) You had very sound reasoning about correctness and writing readable, idiomatic, correct, and efficient C++ code. You have good reasoning to go slowly here, and I agree that this is important that there’s some balance with correctness and readability and pacing, so I think this is the best opportunity to improve on time. Maybe more practice would help you write readable, idiomatic, correct C++ faster. You had quite a few points where you mentioned you would write C++ a different way, but sacrificed on readability for the sake of time -- you could probably do this more without mentioning it every time.

Interview Transcript

Verdant Gazelle: Hello.
Immutable Lightning: Hi, pretty good. So we have about an hour, so we'll spend 45 minutes working on an interview question or two together. We'll save the last 15 minutes or so to share feedback, and we'll just use the next 5 minutes for setup. Verdant Gazelle: Yeah, yeah. I am currently— I've been working in robotics and mostly a lot of platform type stuff. Also, I've done a good bit of motion planning as well. I'm targeting a bunch of C++ roles at self-driving car companies. There's a very famous one that everyone's heard of that was spun out of a FAANG company, and they've asked me to do the interview in C++. It's for an L5 role. However, you know, they have a reputation for kind of down-leveling. So I'm hoping to give a little bit of an L6 signal during the interview as well. Um, and yeah, I've got 10 years of experience.

Problem solution approach

1. Exploration of the problem using concepts:

   • Simulation of erosion in a grid while tracking visited land.
   • Usage of BFS or DFS for exploring islands.
   • Adjusting calculations based on adjacent cells.

2. Pseudocode structure:

   // Code Initialization  
   struct Cell {  
       bool isLand;  
       bool isVisited;  
       int distanceFromShore;  
   };  
   
   // Function to calculate remaining islands after K days of erosion  
   int countIslandsAfterErosion(vector<vector<int>>& grid, int K) {  
       // Logic for counting islands  
   }  
   

3. Main takeaways from coding practice:

• Balance between speed and correctness needs improvement.
• Practicing with C++ structures can enhance code readability and efficiency.
• Continuous self-assessment during coding helps in identifying pressure points.