Skip to main content

Interval cheatsheet for coding interviews

Introduction

Interval questions are a subset of array questions where you are given an array of two-element arrays (an interval) and the two values represent a start and an end value. Interval questions are considered part of the array family but they involve some common techniques hence they are extracted out to this special section of their own.

An example interval array: [[1, 2], [4, 7]].

Interval questions can be tricky to those who have not tried them before because of the sheer number of cases to consider when they overlap.

Things to look out for during interviews

  • Clarify with the interviewer whether [1, 2] and [2, 3] are considered overlapping intervals as it affects how you will write your equality checks.
  • Clarify whether an interval of [a, b] will strictly follow a < b (a is smaller than b)

Corner cases

  • No intervals
  • Single interval
  • Two intervals
  • Non-overlapping intervals
  • An interval totally consumed within another interval
  • Duplicate intervals (exactly the same start and end)
  • Intervals which start right where another interval ends - [[1, 2], [2, 3]]

Techniques

Sort the array of intervals by its starting point

A common routine for interval questions is to sort the array of intervals by each interval's starting value. This step is crucial to solving the Merge Intervals question.

Checking if two intervals overlap

Be familiar with writing code to check if two intervals overlap.

def is_overlap(a, b):
return a[0] < b[1] and b[0] < a[1]

Merging two intervals

def merge_overlapping_intervals(a, b):
return [min(a[0], b[0]), max(a[1], b[1])]

Essential questions

These are essential questions to practice if you're studying for this topic.

These are recommended questions to practice after you have studied for the topic and have practiced the essential questions.

AlgoMonster

AlgoMonster aims to help you ace the technical interview in the shortest time possible. By Google engineers, AlgoMonster uses a data-driven approach to teach you the most useful key question patterns and has contents to help you quickly revise basic data structures and algorithms. Best of all, AlgoMonster is not subscription-based - pay a one-time fee and get lifetime access. Join today for a 70% discount →

Grokking the Coding Interview: Patterns for Coding Questions

This course on Educative expands upon the questions on the recommended practice questions but approaches the practicing from a questions pattern perspective, which is an approach I also agree with for learning and have personally used to get better at coding interviews. The course allows you to practice selected questions in Java, Python, C++, JavaScript and also provides sample solutions in those languages along with step-by-step visualizations. Learn and understand patterns, not memorize answers! Join today for a 10% discount →

Master the Coding Interview: Data Structures + Algorithms

This Udemy bestseller is one of the highest-rated interview preparation course (4.6 stars, 21.5k ratings, 135k students) and packs 19 hours worth of contents into it. Like Tech Interview Handbook, it goes beyond coding interviews and covers resume, non-technical interviews, negotiations. It's an all-in-one package! Note that JavaScript is being used for the coding demos. Check it out →