Interview Cheat Sheets | Intervals Cheat Sheet

December 29th, 2023

Introduction to Intervals

This article will serve to further summarize the excellent overview of intervals from the tech interview handbook.

Overview of Intervals

Interval questions are a specialized subset within array questions, focusing on two-element arrays representing start and end values. They pose unique challenges, requiring distinct techniques and considerations.

Example Interval Array

[[1, 2], [4, 7]]

Interval questions often involve complexities, especially when dealing with overlapping cases.

Things to Look Out for During Interviews

  • Clarification:
    • Verify with the interviewer the treatment of overlapping intervals ([1, 2] vs. [2, 3]) for proper equality checks.
    • Confirm whether [a, b] strictly follows a < b (a is smaller than b).

Corner Cases

Consider the following scenarios:

  • No intervals
  • Single interval
  • Two intervals
  • Non-overlapping intervals
  • Interval totally consumed within another
  • Duplicate intervals
  • Intervals starting right where another ends: [[1, 2], [2, 3]]

Techniques

Sort the Array of Intervals

Sorting intervals by starting points is a crucial step, especially for solving the Merge Intervals question.

Checking Overlapping Intervals

Understand how to write code to check if two intervals overlap.

// Checking if two intervals overlap
function isOverlap(a: [number, number], b: [number, number]): boolean {
  return a[0] < b[1] && b[0] < a[1];
}

Merging Overlapping Intervals

Implement the merging of two overlapping intervals.

// Merging two overlapping intervals
function mergeOverlappingIntervals(
  a: [number, number],
  b: [number, number]
): [number, number] {
  return [Math.min(a[0], b[0]), Math.max(a[1], b[1])];
}

Essential Questions

  • Non-overlapping Intervals