I found this question at codility.com, but I don’t understand the question. Can you help me figure out what do they want? I am more interested in the theory than a code.
A non-empty zero-indexed array A consisting of N integers is given. A prefix_suffix_set is a pair of indices (P, S) such that 0 ≤ P, S < N and such that:
- every value that occurs in the sequence A[0], A[1], …, A[P] also occurs in the sequence A[S], A[S + 1], …, A[N − 1],
- every value that occurs in the sequence A[S], A[S + 1], …, A[N − 1] also occurs in the sequence A[0], A[1], …, A[P].
The goal is to calculate the number of prefix_suffix_sets in the array. For example, consider array A such that:
- A[0] = 3
- A[1] = 5
- A[2] = 7
- A[3] = 3
- A[4] = 3
- A[5] = 5
There are exactly fourteen prefix_suffix_sets: (1, 4), (1, 3), (2, 2), (2, 1), (2, 0), (3, 2), (3, 1), (3, 0), (4, 2), (4, 1), (4, 0), (5, 2), (5, 1), (5, 0).
Write a function:
- function solution(A);
that, given a non-empty zero-indexed array A of N integers, returns the number of prefix_suffix_sets.
3
If I read things correctly:
(1,4) designates the portion of the array
i 0 1 2 3 4 5 A 3 5 7 3 3 5 p/s p p s s
In this set, everything that occurs in A[0..1] also occurs in A[4..5].
The set is not concerned with the multiplicity of a number (1,3) shows:
i 0 1 2 3 4 5 A 3 5 7 3 3 5 p/s p p s s s
3 occurs twice in the ‘s’ set and once in the ‘p’ set.
These can be overlapping (2,2)
i 0 1 2 3 4 5
A 3 5 7 3 3 5
p p p p
s s s s
and (2,1)
i 0 1 2 3 4 5
A 3 5 7 3 3 5
p p p p
s s s s s
The question is asking “how many of these pairings (suffix and prefix) exist where the set of numbers in the prefix part of the array matches the set of numbers in the suffix part of the array?”
0