Python ~ First Covering Prefix in Array

Question

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.

mozway · Accepted Answer · 2022-09-09 14:45:03Z

2

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

answered Sep 9, 2022 at 14:45

mozway

267k13 gold badges56 silver badges106 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Python ~ First Covering Prefix in Array

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related