Quick Overview

This question evaluates understanding of combinatorics, deterministic pseudo-random generation, and efficient enumeration for producing unique NFT metadata, measuring competency in algorithm design, state-space management, and handling large-scale outputs.

Generate NFT metadata and ensure uniqueness

Company: Coinbase

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

You are implementing an **NFT metadata generator**. Each NFT is defined by selecting exactly one trait value from each trait category. You must generate a requested number of NFTs, ensure they are unique (no repeated trait combinations), and output JSON metadata. ## Input A single JSON object with: - `collectionName` (string) - `traits`: an array of trait categories. Each category is: - `name` (string) - `values` (array of strings, non-empty) - `n` (integer): number of NFTs to generate - `seed` (integer): seed for deterministic pseudo-random generation Example: ```json { "collectionName": "MyCollection", "traits": [ {"name": "Background", "values": ["Blue", "Red"]}, {"name": "Eyes", "values": ["Normal", "Laser"]} ], "n": 3, "seed": 42 } ``` ## Required behavior 1. Each generated NFT must have exactly one value for each trait category. 2. Two NFTs are considered the same if they have the **same value for every trait category**. 3. Use `seed` to make generation deterministic: - Using the same input must produce the same outputs in the same order. 4. If `n` exceeds the number of possible unique combinations, output `ERROR`. ## Output Output a JSON array of length `n`. Each element is an object: - `name`: `"<collectionName> #<index>"` where `index` starts at 1 - `attributes`: array of `{ "trait_type": <categoryName>, "value": <selectedValue> }` Example output element: ```json { "name": "MyCollection #1", "attributes": [ {"trait_type": "Background", "value": "Red"}, {"trait_type": "Eyes", "value": "Laser"} ] } ``` ## Constraints - Up to 10 trait categories. - Each category has up to 200 values. - `n` can be up to 100,000. ## Notes You must define your own approach for generating unique combinations efficiently (not by repeatedly sampling and retrying until unique).

Overview: This question evaluates understanding of combinatorics, deterministic pseudo-random generation, and efficient enumeration for producing unique NFT metadata, measuring competency in algorithm design, state-space management, and handling large-scale outputs.

Read the full Coinbase Software Engineer interview experience this question came from

You are implementing an NFT metadata generator. Each NFT must choose exactly one value from every trait category and produce metadata for that combination. Generate exactly n NFTs in a deterministic seed-based order, making sure no two generated NFTs use the same value for every category. If a category contains duplicate equal strings, they count as the same trait value and must not create duplicate NFTs. If n is larger than the number of possible unique combinations, return 'ERROR'. Your solution must generate unique combinations directly, not by repeatedly sampling and retrying until you find an unused one.

Constraints

  • 0 <= number of trait categories <= 10
  • Each category has 1 to 200 provided values
  • 0 <= n <= 100000
  • Trait value strings inside the same category may repeat; repeated equal strings do not increase the number of unique combinations
  • The total number of unique combinations can be extremely large, so generating all combinations up front is not required

Examples

Input: ({'collectionName': 'MyCollection', 'traits': [{'name': 'Background', 'values': ['Blue', 'Red']}, {'name': 'Eyes', 'values': ['Normal', 'Laser']}], 'n': 3, 'seed': 42},)

Expected Output: [{'name': 'MyCollection #1', 'attributes': [{'trait_type': 'Background', 'value': 'Blue'}, {'trait_type': 'Eyes', 'value': 'Laser'}]}, {'name': 'MyCollection #2', 'attributes': [{'trait_type': 'Background', 'value': 'Red'}, {'trait_type': 'Eyes', 'value': 'Laser'}]}, {'name': 'MyCollection #3', 'attributes': [{'trait_type': 'Background', 'value': 'Blue'}, {'trait_type': 'Eyes', 'value': 'Normal'}]}]

Explanation: There are 4 unique combinations. With seed 42, the deterministic index sequence produced by the reference solution is 2, 3, 0, which decodes to the three metadata objects shown.

Input: ({'collectionName': 'Dupes', 'traits': [{'name': 'Color', 'values': ['Gold', 'Gold', 'Silver']}, {'name': 'Hat', 'values': ['Cap', 'None']}], 'n': 4, 'seed': 1},)

Expected Output: [{'name': 'Dupes #1', 'attributes': [{'trait_type': 'Color', 'value': 'Silver'}, {'trait_type': 'Hat', 'value': 'Cap'}]}, {'name': 'Dupes #2', 'attributes': [{'trait_type': 'Color', 'value': 'Gold'}, {'trait_type': 'Hat', 'value': 'Cap'}]}, {'name': 'Dupes #3', 'attributes': [{'trait_type': 'Color', 'value': 'Silver'}, {'trait_type': 'Hat', 'value': 'None'}]}, {'name': 'Dupes #4', 'attributes': [{'trait_type': 'Color', 'value': 'Gold'}, {'trait_type': 'Hat', 'value': 'None'}]}]

Explanation: The duplicate 'Gold' value does not create extra uniqueness. After deduplication there are 2 x 2 = 4 unique combinations, and all 4 are generated exactly once.

Hints

  1. Think of one NFT as one point in the Cartesian product of all trait value lists. A single integer can represent one combination if you decode it using mixed radix.
  2. To avoid retrying until unique, generate distinct combination indices directly. An arithmetic progression modulo total_combinations visits every index exactly once when the step and the modulus are coprime.

Loading coding console...