So I recently gave an online interview for a job. Although my expertise are networks and cyber security.
I came across this question:
Write a function which takes an array of integers and returns the first covering prefix of that array. The "first covering prefix" of an array, A, of length N is the smallest index P such that 0 <= P <= N and each element in A also appears in the list of elements A[0] through A[P]. For example, the first covering prefix of the following array: A = [5, 3, 19, 7, 3, 5, 7, 3] is 3, because the elements from A[0] to A[3] (equal to [5, 3, 19, 7]) contains all values that occur in array A.
Although I am not a programmer (chose python3 for the interview),
I would like someone to explain the logic behind this.
Just wanting to learn, its been bugging me for a day now.
You can iterate all elements, if not already seen (use a set to keep track efficiently), update P:
A = [5, 3, 19, 7, 3, 5, 7, 3]
S = set()
P = 0 # you could set -1/None as default to account for empty lists?
for i, item in enumerate(A): # iterate elements together with indices
if item not in S: # if we haven't seen this element yet
P = i # update P as the current index
S.add(item) # add the element to the set
print(P)
output: 3