[Hard] interview questions #18

[rygh4775]

[RoyMoon]

Solution 1 : Brute Force

def findShortestSequence(numbers, elements) :
    shortest = -1
    shortestStart = -1
    shortestEnd = -1
    for idx in range(len(numbers)) :
        end = getAllMatchedIdx(numbers, elements, idx)

        if end == -1 : continue

        if shortest == -1 or end - idx < shortest :
            shortest = end - idx
            shortestStart = idx
            shortestEnd = end

    return [shortestStart, shortestEnd]

def getAllMatchedIdx(numbers, elements, idx):
    last = -1
    for e in elements:
        match = getMatchIdx(numbers, e,idx)
        if match == -1 : return -1

        last = max(match,last)

    return last

def getMatchIdx(numbers, element, idx) :
    for i in range(idx, len(numbers)) :
        if numbers[i] == element :
            return i
    return -1

elements =[1,5,9]
numbers=[7,5,9,0,2,1,3,5,7,9,1,1,5,8,8,9,7]

print(findShortestSequence(numbers, elements))

output :

[7, 10] Time Complexity O(N^2 * M) M = elements size N = numbers size

Solution 2 : Optimizer

def findShortestSequence(numbers, elements) :
    nextElements = getNextElementsMulti(numbers, elements)
    closures = getClosure(nextElements)
    for i in range(0,len(elements)):
        printVal = ""
        for j in range(0,len(numbers)):
            if j == 0 :
                printVal = str(nextElements[i][j])
            else :
                printVal = printVal + ", " + str(nextElements[i][j])
        print(printVal)

    printVal = ""
    shortest = -1
    closuresIdx = -1
    for i in range(0,len(numbers)):
        if closures[i] == -1 : break
        if i == 0 :
            printVal = str(closures[i])
        else :
            printVal = printVal + ", " + str(closures[i])
                           if shortest == -1 or closures[i] - i < shortest:
            print ("closures : ", closures[i]," idx : ", i )
            closuresIdx = i
            shortest = closures[i] - i
            print (shortest)

    print(printVal)

    return [closureIdx, closures[closuresIdx] ]

def getClosure(nextElements) :
    closures =[ -1 for x in range(0, len(nextElements[0]) )]

    for i in range(0, len(nextElements[0])) :
        for s in range(0, len(nextElements)) :

            if nextElements[s][i] == -1 : break;
            if nextElements[s][i] > closures[i] :
                  closures[i] = nextElements[s][i]
    return closures

def getNextElementsMulti(numbers, elements):
    nextElementsMulti =[[ -1 for x in range(len(numbers))] for y in range(len(elements))]
    for i in range(0,len(elements)) :
        nextElementsMulti[i] = getNextElements(numbers, elements[i])

    return nextElementsMulti

def getNextElements(numbers, element) :
    matchedIdx = -1
    nextElements =  [ -1 for x in range(0,len(numbers))]
    for i in reversed(range(0,len(numbers))) :
        if numbers[i] == element :
            matchedIdx = i

        nextElements[i] = matchedIdx
    return nextElements

elements =[1,5,9]
numbers=[7,5,9,0,2,1,3,5,7,9,1,1,5,8,8,9,7]

print(findShortestSequence(numbers,elements))
                                                              68,40         Bot

output : [7, 10] Time Complexity O(N * M)

M = elements size N = numbers size Space Complexity

Solution 3 : Optimizer

Time Complexity O(N * M) Space Complexity