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 most optimal solution under stress, but the topic of complexity must be at least addressedraised 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
.
A hypothetical discussion over these things in the posted question would have been interesting too,
demonstratingwhich would be a good demonstration of knowledge of what's available in the language out,
sending good signals.
The discussion about the use of continue
and break
in the boxloop are minor compared to the conversation on complexity and the main algorithm.
Others have pointed out that you can use binary search for better time complexity. What II haven't seen mentioned yet is that two variations of binary search are needed here, one to find the leftmost position and another to find the rightmost position. ThisI believe this is actually really the heart of this exercise, verifying that not only you understandthe understanding of time complexity, but also binary search, but also and going a little bit beyond its most basic use case. That is, considering the added logical complexity of dealing with duplicate elements in the sorted collection, and how to deal with them. TheSee the dedicated section on this topic in wikipedia article has a section on this, it's very interesting, and not that complicated.
IAt the highest level, finding a range comes down to finding the start and the end of the range. I think this would beit's a finegood 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 indexes to be returnedboundaries of the range (inclusive vs exclusive), and potential corner cases. All fantastic interview topics, demonstrating a structured approach to problem solving, and not diving into the middle of code without understanding what is expected.
After clarifying the above details and the intended behavior,
the conversation can focus on implementing findLeftMostIndex
then of course the next step is to implement one or both of the helper functions, depending on the interviewer and the time available.
which will beBut that's a much smaller scope than the original problem,
easier for everyone to wrap their heads around.
At that point itwhich will be very naturalhelp the conversation to questiongo in the direction of questioning whether a linear logic of checking elements one by one,
and be reminded that the input is sorted
and howgood enough to find the correct index, and if we can benefit somehow from itthe fact that the list is sorted.