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).
Quick Answer: 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.
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.