Fix the invariant checker for a dedupe function

Review the AI's codeMedium15 min

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 to dedupe. It can be empty and can hold repeats and negative numbers.
  • candidate: the list of integers dedupe returned.
  • Return the names of the checks candidate breaks, as a list of strings.

Rules the tests check:

  • "has_duplicates": some value appears more than once in candidate.
  • "not_subsequence": candidate is not a subsequence of original. 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 in original does not appear anywhere in candidate.
  • "extra_element": some value in candidate does not appear anywhere in original.
  • 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
Inputdedupe_violations([3, 1, 3, 2], [3, 1, 2])
Output[]
Example 2
Inputdedupe_violations([3, 1, 3, 2], [3, 2, 1])
Output["not_subsequence"]
Example 3
Inputdedupe_violations([1, 1, 2], [1, 1, 2])
Output["has_duplicates"]