In a technical interview, whiteboard problems can take you by surprise. Sometimes it can be difficult to follow the solution you envision in your mind and reach the finish line, especially if somebody is trying to direct you to do it a different way.

When under pressure, if we cannot come up with the best answer, at least we can come up with a working solution.

Let’s take this age old problem of merging sets of ranges:

Combine [1..5, 10..15, 35..40] with [5..20, 38..48]

The first conundrum here is whether the ends of your ranges are inclusive or exclusive. An easy way to see past this problem is to define your ranges according to start and length instead of start and end. The end of a range is a vague notion (potentially inclusive or exclusive), but length is obvious.

Now that we have a way to express our data precisely, let’s go to work.

The input, therefore, is an array of range objects, where a range object can denoted quite literally:

{
  start: 35,
  length: 5
}

We can describe our function as follows:

function mergeRanges(arr, arr2) {
  let result = [];
  // compute something
  return result;
}

We know as a given that in each of the original arrays, nothing is overlapping. But we know that the merged result could be anywhere from 1 element in size to the sum total of each of the original elements.

Since any element could overlap with any other element, I think it’s fair to go through each element one by one to check if they overlap with something else, and to walk each array so that our indexes are lined up.

1..5   10..15        35...40
   5..........20       38.......48

But alas, I’m getting ahead of myself. The idea of walking both arrays in theory sounds straightforward, but implementing could get tricky real fast.

So let’s jump into the brute force solution. Simply try to mash every element with every other element, and repeat until nothing collides. We’ll use nested loops, very similar to the implementation of a bubble sort.

function mergeRanges(arr1, arr2) {
  let result = arr1.concat(arr2);
  let goAgain = true;
  while (goAgain) {
    goAgain = false;
    for (let i = 0; i < result.length — 1; i++) {
      for (let j = i + 1; j < result.length; j++) {
        if (overlaps(result[i], result[j])) {
          result[i] = merge(result[i], result[j]);
          result.splice(j, 1);
          j--; // since the element at j got trashed, walk backwards
          goAgain = true;
        }
      }
    }
  }
  return result;
}

Notice that I made some new functions on-the-fly, overlaps and merge? Let’s fill those in. Now, what is overlap? Overlap means that leftmost OR rightmost element of one range is present in the other range.

[....]        [....]       [....]      [..........]
   [....]  [....]       [..........]      [....]

First, I’ll make a helper function to get the exclusive end. I know I said length was more intuitive, and it is, but this saves us some busywork.

const getEnd = a => {
  return a.start + a.length;
}

Now, the overlap function:

const overlaps = (a, b) => {
  let leftAinB = a.start >= b.start && a.start < getEnd(b);
  let rightAinB = getEnd(a) > b.start && getEnd(a) <= getEnd(b);
  return leftAinB || rightAinB;
}

And finally, the merge function:

const merge = (a, b) => {
  // assume a and b overlap
  let start = Math.min(a.start, b.start);
  let length = Math.max(getEnd(a), getEnd(b)) — start;
  return { start, length };
}

Now let’s say for all intents and purposes that this solution works and there are no bugs. How fast is it? Because we have concentric loops, and the algorithm could be re-run every time elements are merged, the runtime is going to be O(n³) where n represents the average size of each of the arrays. This is a decent solution for a small data set, but I think we can do better. Can we create a solution that is O(m + n)?

function mergeRanges(arr1, arr2) {
  let index1 = 0;
  let index2 = 0;
  let result = [];
  while (index1 < arr1.length && index2 < arr2.length) {
    // case 1: range 1 comes before range 2 and does not overlap
    if (getEnd(arr1[index1]) < arr2[index2]) {
      result.push(arr1[index1]);
      index1++;
    }
    // case 2: range 2 comes before range 1 and does not overlap
    if (getEnd(arr2[index2]) < arr1[index1]) {
      result.push(arr2[index2]);
      index2++;
    }
    // case 3: they overlap
    result.push(merge(arr1[index1], arr2[index2]));
    index1++;
    index2++;

    // Wait a minute, I’m going to have to run through the list
    // of results again to see if they merge.

    // Ugh, I think it’s time to pull my hair out. All of it.
  }
  return result;
}

Regrettably, my brain has turned to stew. The caffeine buzz I was on that got me through the brute force solution is no longer working. I’m feeling flustered. I’m embarrassed. I’m thinking to myself, “am I just dumb?”

If only I had more practice. If only I was better at these kinds of problems. I can already imagine that engineer interviewing me looking down on me because he knows the answer. Is he smarter than me? Does he have the solution memorized? Am I a complete failure? Should I just plow through like a moron, fully realizing that I am a moron with no chance for improvement? As I ask for help along the way will they realize that I am a magical unicorn and pamper me with fairy dust? I think I’ll take up another profession.

Seriously, these are the thoughts going through my head. The pressure is real here, folks. What to do? I think I am going to talk it through, bracing myself for the worst but hoping for the best.

Because here’s the reality: In a supportive environment, the people around us will help us. In an unsupportive environment, they won’t. If someone is unwilling to help you at your most vulnerable state, then your glow is not shining upon them. That’s not because you don’t have a glow but it’s because their darkness is repelling it.

Yes, go through the ringer, but no, don’t feel like less of a person because you got bruised and beaten down. Ask any expert, and they will tell you persistence pays. You might be reduced to your most humble, but it is at your most humble that your true strengths will emerge.

Until then, go with the brute force solution. As you can see, it was quite a roundabout way of solving this problem, but it required only 1 fork in the road, not 10. The optimized solution is certainly something in my capacity, but it’s going to take a 3rd cup of coffee, and thanks but I could really use my beauty rest tonight.

When faced with an impossible compromise, take the easy way out. When you’re your own boss, sure, be ambitious, but as long as you’re working for somebody else, just get things done. You’ll naturally float to a place where you are valued for the magical unicorn you really are inside, and there will be plenty of smart people dousing you with buckets of fairy dust.

So go out there, be you, and save the perfection for your self-care routine.