← Grammarly Interview Insights

Grammarly·Software Engineer·Onsite - Coding / Algorithms·Intermediate

Intermediate
Jun 2026

Summary

Coding round at Grammarly for a software engineer role. One algorithm question, interval scheduling flavor, pretty standard if you've seen it before.

Questions Asked (1)

Q1

Given an array of intervals, what is the minimum number of intervals you must remove so that no two remaining intervals overlap?

Algorithms & Data Structures
Author's notes

I knew the greedy approach here: sort by end time, walk through and count removals whenever the current start is before the last recorded end.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Reframe the problem as finding the maximum number of non-overlapping intervals, then subtract that from the total. Sort intervals by end time and greedily select intervals that start after the last selected end time. The minimum removals equals total intervals minus the maximum non-overlapping count.

Pro tip: Mention that sorting by end time is optimal for interval scheduling, and briefly explain why sorting by start time fails with a counterexample. This shows deeper understanding and avoids a common pitfall.

1. Clarify and Reframe

Confirm that intervals are closed and that overlapping means sharing any point. Reframe the problem: minimum removals = total intervals - maximum non-overlapping intervals.

2. Choose Greedy Strategy

Explain that to maximize non-overlapping intervals, we should always pick the interval that ends earliest and is compatible with previous choices. This is the classic interval scheduling greedy algorithm.

3. Sort by End Time

Sort all intervals in ascending order of their end times. This ordering ensures that we consider intervals that finish sooner first, leaving more room for subsequent intervals.

4. Iterate and Count

Initialize a variable to track the end time of the last selected interval (e.g., -infinity) and a count of selected intervals. For each interval in sorted order, if its start time is >= last end time, select it, update last end time, and increment count.

5. Compute Removals

After iterating, the maximum number of non-overlapping intervals is the count. The minimum removals is total intervals minus this count. Return that value.

Key Points to Mention

  • Greedy algorithm for interval scheduling: always pick the interval with the earliest end time.
  • Proof of optimality: exchange argument showing that choosing the earliest finishing interval is always safe.
  • Time complexity: O(n log n) due to sorting, then O(n) for the greedy pass.
  • Space complexity: O(1) extra space if sorting in place, or O(n) if creating a sorted copy.
  • Edge cases: empty array, single interval, intervals with same end times, touching intervals (e.g., [1,2] and [2,3] are considered non-overlapping if endpoints are allowed to touch).
  • Counterexample for sorting by start time: intervals [1,10], [2,3], [4,5] – sorting by start picks [1,10] and yields 1 non-overlapping, but optimal is 2.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.