Fix the invariant checker for a dedupe function
Your task
An assistant's property test for dedupe(arr) compared its output with [...new Set(arr)]. That oracle is a second copy of the algorithm, and it only accepts the first copy of each value. The team is replacing it with checks that hold for any correct dedupe.
An assistant wrote dedupe_violations(original, candidate). It is in the editor. It has a bug. Find it and fix it.
Input and output:
original: the list of integers passed todedupe. It can be empty and can hold repeats and negative numbers.candidate: the list of integersdedupereturned.- Return the names of the checks
candidatebreaks, as a list of strings.
Rules the tests check:
"has_duplicates": some value appears more than once incandidate."not_subsequence":candidateis not a subsequence oforiginal. A subsequence is what you get by deleting zero or more items from a list and keeping the rest in order. Any choice of items to delete counts, so an output that keeps the last copy of a value is as valid as one that keeps the first."missing_element": some value inoriginaldoes not appear anywhere incandidate."extra_element": some value incandidatedoes not appear anywhere inoriginal.- Report each name at most once, sorted alphabetically. When nothing is broken, return an empty list.
Examples
dedupe_violations(original: list[int], candidate: list[int]) -> list[str]Example 1
Input
dedupe_violations([3, 1, 3, 2], [3, 1, 2])Output
[]Example 2
Input
dedupe_violations([3, 1, 3, 2], [3, 2, 1])Output
["not_subsequence"]Example 3
Input
dedupe_violations([1, 1, 2], [1, 1, 2])Output
["has_duplicates"]