Python Interview with a FAANG engineer

Interview Summary

Problem type

Insert Interval

Interview question

You are given an array of non-overlapping intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti.

You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Note that you don't need to modify intervals in-place. You can make a new array and return it.

Interview Feedback

Feedback about Magnetic Buffalo (the interviewee)

• Excellent communication, easy to follow and understand
• Good work with clarification questions. Your immediate intuition to use binary search is spot on and shows experience with algorithmic problems
• Normally I absolutely encourage the use of pseudocode but given the time constraints meta imposes, be mindful of spending too much on it so it does not cost you down the line.
• I absolutely love your sense of humor, highly encourage you to bring this spirit in the interview, it makes you a fun candidate to interview and also showcases a semblance of confidence which biases the interview into trusting your expertise.
• Excellent work to do your complexity analysis right at the start. This saves you time and checks a big box in the interview process which is invaluable.
• Kept a good pace but we should have ideally have had a solution at 7:22. This is a problem commonly encountered with Java usage given its constraints on data structures. Feel free to experiment interviewing with different languages you are comfortable with.
• Good understanding of traversals overall, you were spot on with in order here.
• Good technical understanding of the CBV and CBA nuances which end up influencing the complexity. I tend to prefer the use of encapsulation or using a class level map structure which is accessible to all methods of the class. You can then insert values to the map/list.

Feedback about The Legendary Avenger (the interviewer)

• Interesting set of questions. One thing I didn't mention is that I've received contradictory advice about Meta interviews. Yours was that the code can be "good enough" to enable me to move to the next problem. Other feedback I've received has been that the code needs to be basically flawless on the first try. It might be worth discussing this with candidates to calibrate their expectations (perfection is a terrifying standard).

Interview Transcript

The Legendary Avenger: Awesome. All right, so maybe just before we get started, maybe give me a quick run through of what you're prepping for as well as what you're looking to get out of this that we can calibrate it for.

Magnetic Buffalo: Sure. So I'm preparing for a full loop with Meta next week. I'm basically just practicing until things become boring.

The Legendary Avenger: I like that philosophy.

Magnetic Buffalo: Yeah, I tend to get nervous. I've been pretty hit and miss on coding mock interviews. It's my weakest area out of the three, so we'll see what happens.

The Legendary Avenger: All right, I have some good news for you. So I actually work at Meta and they do conduct interviews there. So if you'll like, I can give you a META formatted interview right now. All right, so just before we even start there, I'm hoping you know the general format of how Meta does things.

Magnetic Buffalo: Yes. So I have the notes here. One was that you'll see an easy medium or medium medium or maybe medium hard. So two problems in each interview and that you're looking for problem solving, code quality, edge cases, bug finding, and communication.

The Legendary Avenger: All right, that's exactly it. And so I'll even add a further bit of tip there. Don't practice outside of Leetcode. I tell my candidates for Meta, 9 out of 10 questions they'll ask you will come from the Leetcode list.

Technical Discussion

Magnetic Buffalo: Okay, so let me see if I understand. Given an array of non-overlapping intervals. Okay, so I imagine that's like an int array. Array represents start and end of the ith interval and intervals are sorted in ascending order according to start. You're also given a interval new interval start and end that represents the start and end of another interval. Certain new interval intervals. Such intervals are still assorted in. So in ascending order. And intervals does not have any overlapping intervals. Merge overlapping. That's. That's the key.

The Legendary Avenger: Exactly.

Magnetic Buffalo: Inserting necessary turn intervals after insertion. You don't need to modify internals intervals and places. You can make a new array and return it. That's. That's convenient.

The Legendary Avenger: Yes, and to your point, that's actually a language nuance. I feel like with Java there's a clear distinguishment between lists and arrays, and so sometimes properties get miscommunicated because with the likes of Python, Rust and such, you just make them mutable or just at least by default, so they're automatically extensible.

Code Implementation

Magnetic Buffalo: So public int[] insert(int[][] intervals, int[] newInterval) { List<int[]> result = new ArrayList<>(); int i = 0; while (i < intervals.length && intervals[i][1] < newInterval[0]) { result.add(intervals[i]); i++; } while (i < intervals.length && intervals[i][0] <= newInterval[1]) { newInterval[0] = Math.min(newInterval[0], intervals[i][0]); newInterval[1] = Math.max(newInterval[1], intervals[i][1]); i++; } result.add(newInterval); while (i < intervals.length) { result.add(intervals[i]); i++; } return result.toArray(new int[result.size()][]); }