There is a interview question from AirBNB:

You have a sorted array, and you want get the first index and the last index of the matching occurrence of an element by a function in python. If there is no match, return [-1.-1]. If there is a match, return [first_index,last_index].

This is my newbie solution, can anyone come up with a better one?

By the way, this question is from TechLead DailyInterviewPro.

def solution(array,key):
    start_index = -1
    ending_index = -1
    if key not in array:
        return [start_index,ending_index]
    else:
        for i in range(len(array)):
            if array[i]==key:
                if start_index == -1:
                
                    start_index = i
                    ending_index = i
                else:
                    ending_index = i
                    
        return [start_index,ending_index]        

CodePudding user response：

with one liner, using list.index function you can use

[-1, -1] if key not in array else [arrary.index(key),len(array)-array[::-1].index(key)-1 ]

little efficient code, if memory is not a concern, else need to use two pointer apprach

def solution(array, key):
    store_index = {}
    for index, value in enumarate(array):
         if value not in store_index:
              store_index[value] = []
         store_index[value].append(index)

    if key not in store_index:
       return [-1, -1]
    return [store_index[key][0], store_index[key][-1]]

CodePudding user response：

Just for fun, an optimized solution that:

1. Uses index to push the work of confirming at least one value exists, and retrieving its index, to the C layer
2. Avoids scanning a single element more than needed, and doesn't make any copies (it doesn't access elements between the start_index and end_index at all):

def solution(array,key):
    try:
        return [array.index(key),
                len(array) - next(i for i, x in enumerate(reversed(array), 1) if x == key)]
    except ValueError:
        return [-1, -1]

It relies on array.index either computing the first element's index or raising ValueError (in which case no such element exists), then follows up by retrieving a single value from a genexpr running over the list in reverse order to get the index (the genexpr is guaranteed to find something, at worst it runs until it finds the same element the index call found). Technically, this does mean that if the element occurs only once, we test it for equality twice (coming from either end), but avoiding said "cost", while possible via itertools.islice, it hardly worth the bother.

If you really love one-liners, you could always do:

def solution(array,key):
    return [next((i for i, x in enumerate(array) if x == key), -1)
            next((len(array) - i for i, x in enumerate(reversed(array), 1) if x == key), -1)]

though that solution does involve scanning the whole of array twice (once forward, once backward) when the element is not found (if the element exists though, the minimal number of elements are scanned).