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

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 findLeftMostIndexthen 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.

At a coding interview, talking about time complexity is extremely important, to verify understanding of fundamentals, and the ability to scale. It can be acceptable to not find the most optimal solution under stress, but the topic must be at least addressed.

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 .indexOf and .lastIndexOf. A hypothetical discussion over these things in the posted question would have been interesting too, demonstrating knowledge of what's available in the language out of the box.

Others have pointed out that you can use binary search for better time complexity. What I haven't seen mentioned yet is that two variations of binary search are needed, one to find the leftmost position and another to find the rightmost position. This is actually really the heart of this exercise, verifying that not only you understand time complexity, binary search, but also the added logical complexity of dealing with duplicate elements in the sorted collection. The wikipedia article has a section on this, it's very interesting, and not that complicated.

I think this would be a fine first iteration:

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 returned, 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, which will be a much smaller scope, easier for everyone to wrap their heads around. At that point it will be very natural to question the linear logic of checking elements one by one, and be reminded that the input is sorted and how we can benefit from it.

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.

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.

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.

Source Link
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. It can be acceptable to not find the most optimal solution under stress, but the topic must be at least addressed.

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 .indexOf and .lastIndexOf. A hypothetical discussion over these things in the posted question would have been interesting too, demonstrating knowledge of what's available in the language out of the box.

Binary search

Others have pointed out that you can use binary search for better time complexity. What I haven't seen mentioned yet is that two variations of binary search are needed, one to find the leftmost position and another to find the rightmost position. This is actually really the heart of this exercise, verifying that not only you understand time complexity, binary search, but also the added logical complexity of dealing with duplicate elements in the sorted collection. The wikipedia article has a section on this, it's very interesting, and not that complicated.

Solve from high level to lower levels

I think this would be a fine first iteration:

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 returned, 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, which will be a much smaller scope, easier for everyone to wrap their heads around. At that point it will be very natural to question the linear logic of checking elements one by one, and be reminded that the input is sorted and how we can benefit from it.