Verifying Authenticity - codepath/compsci_guides GitHub Wiki

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q
  • What is the desired outcome?
    • To determine if the given array art_pieces is an authentic collection based on the base[n] array.
  • What input is provided?
    • An array of integers art_pieces.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Check if the array matches the structure of base[n] which contains the integers from 1 to n - 1 exactly once, and n twice.

1) Find `n`, the maximum value in `art_pieces`.
2) Check if the length of `art_pieces` is `n + 1`.
3) Count the occurrences of each piece in `art_pieces`.
4) Verify that the counts match the structure of `base[n]`.
   - Each number from `1` to `n - 1` should appear exactly once.
   - The number `n` should appear exactly twice.
5) Return `True` if the array is authentic, otherwise return `False`.

⚠️ Common Mistakes

• Not correctly counting the occurrences of each piece in art_pieces.

I-mplement

def is_authentic_collection(art_pieces):
    n = max(art_pieces)

    # The correct base art_pieces should have exactly n + 1 elements
    if len(art_pieces) != n + 1:
        return False

    # Count the occurrences of each piece in the art_pieces
    counts = {}
    for piece in art_pieces:
        if piece in counts:
            counts[piece] += 1
        else:
            counts[piece] = 1

    # Check the counts against the required base art_pieces structure
    for i in range(1, n):
        if counts.get(i, 0) != 1:
            return False

    return counts.get(n, 0) == 2