Skip to main content
2 of 2
added 411 characters in body
janos
  • 111.7k
  • 15
  • 152
  • 391

Time complexity

At a coding interview, talking about time complexity is extremely important, to verify understanding of fundamentals, and the ability to scale. Finding the optimal algorithm and implementing it is the typical target of a coding interview. It can be acceptable to not find the optimal solution under stress, but the topic of complexity must be at least raised and discussed.

The posted code, as well as the youtuber reference code are both linear. A solution exists with logarithmic time and it's an interesting topic during a coding interview, as well as contrasting with using the native functions .indexOf and .lastIndexOf, which would be a good demonstration of knowledge of the language, sending good signals.

The discussion about the use of continue and break in the loop are minor compared to the conversation on complexity and the main algorithm.

Binary search

Others have pointed out that you can use binary search for better time complexity. I haven't seen mentioned yet that two variations of binary search are needed here, one to find the leftmost position and another to find the rightmost position. I believe this is actually the heart of this exercise, verifying not only the understanding of time complexity, but also binary search, and going a little bit beyond its most basic use case. That is, considering the added logical complexity of duplicate elements in the sorted collection, and how to deal with them. See the dedicated section on this topic in wikipedia.

Solve from high level to lower levels

At the highest level, finding a range comes down to finding the start and the end of the range. I think it's a good start to split the problem into two smaller sub-problems like this, and go from there. Then the first iteration of the solution could look something like this:

// returns an array of [start, end],
// where start is the index of the first element that has the target value,
// and end is the index after the last element that has the target value,
// or [-1, -1] when the target value is not in the array
function findRange(arr, target) {
  return [
    findLeftMostIndex(arr, target),
    findAfterRightMostIndex(arr, target)
  ];
}

The referenced functions don't exist (yet), and that's ok. This is a good opportunity to have a conversation with the interviewer about the function name, the parameters, their types, the return value, the precise meaning of the boundaries of the range (inclusive vs exclusive), and potential corner cases.

After clarifying the above details and the intended behavior, then of course the next step is to implement one or both of the helper functions, depending on the interviewer and the time available. But that's a smaller scope than the original problem, which will help the conversation to go in the direction of questioning whether a linear logic is good enough to find the correct index, and if we can benefit somehow from the fact that the list is sorted.

janos
  • 111.7k
  • 15
  • 152
  • 391