Problem
This problem was asked by Amazon.
You are given a sorted array and a value i. Find the last index where the value appears.
For example, given
arr=[1,1,1,3,3,4,5,5,5]
and i= 1
your solution should return 2. Don’t use any external library functions.
HINT/Spoiler: This problem has a lot of nuances that you should think about
Step 1: Clarifying Constraints
This is an overlooked first step in coding interviews. Remember the hint? You will see why I chose to give that here instead of in a “harder” question. Questions like this seem obvious on the surface, which can make it easy to overlook the nuances.
Some questions/observations that you verbalize to the interviewers:
Seems the arrays have repeating values. Is there an upper limit to the number of repetitions?
What do I do if the array is empty? Should I return -1/something special?
What if the value doesn’t exist in the array?
None of these questions are strictly game-changing. But it is good practice to help you ask good questions in your interviews.
Step 1.5
This question is interesting because there is a clear way to split this question into separate parts and solve them. We can break this question into two parts:
Find an index where the value exists.
Using this, find the last index.
Since the array is sorted, we know that all the identical values will be bunched up together.
Step 2: Solution to part 1
I will not mention linear search as a solution. You should immediately be able to identify binary search as a valid way to find the value and its index in the array. With questions involving finding values in sorted arrays, binary search is your go-to. Following is a quick refresher on how binary search looks.
With it, we can discover an index of i. Now that we have one index of i, how do we do part 2 of our solution?
Step 3: Solution to part 2
How can we find the last index, being given a starting point? Easy we traverse using the current index. But how do we traverse the array?
This is where the nuance of the questions comes in. If the repetitions are guaranteed to be logarithmic or a constant number, we can traverse the array linearly from our current starting point. This would still not increase our logarithmic run time.
However, if the upper bound on repetitions is a linear function of n (it can’t be more than n), then our solution becomes O(n). And all the hard work of implementing binary search will go to waste. So what do we do?
Step 4: Getting Creative
How do we work through this challenge? We need a solution that is at most logarithmic. We have a sorted array. If we could find a value to search for, we can binary search.
Keep reading with a 7-day free trial
Subscribe to Technology Made Simple to keep reading this post and get 7 days of free access to the full post archives.