Largest Range in an Array

Problem:

Given an array of integers, return the largest range, inclusive, of integers that are all included in the array.

Approach:

You should start by asking relevant questions, and scoping the problem:

  1. How should we handle empty lists? I am assuming empty list returns "()". Even here, most interviewers let you choose a suitable default
  2. How about repeated integers in the list? Let’s assume a repeated number is only counted once, so, the longest range in [8, 8, 8, 9, 1, 2, 3] is [1, 2, 3] even though 8 appears three times.
  1. A max_count variable to store the length of the longest sub-array found so far.
  2. l_bound and u_bound integers to keep track of lower and upper bound of the longest sub-array.

Efficient Algorithm:

What is the complexity of the algorithm above? The complexity is dominated by that of std::sort - the rest of the loop is a single pass through the sorted array. The total complexity is therefore O(NlogN), where N is the size of the array.

Testing:

Like always, we are going to use Gunit testing framework for writing tests. Let’s start with a few simple test cases: An empty list, and a list with a single element.

Solutions to programming interview questions at some of the top companies in the world: cppcodingzen.com