Parse logs and generate NFT attributes
Company: Coinbase
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Quick Answer: This question evaluates parsing and log-processing skills alongside combinatorics and weighted-sampling competency, covering extraction and time-based grouping of timestamped records, handling malformed input policies, enumeration of Cartesian products, deduplication, and probabilistic generation.
Part 1: Parse and Group Log Lines by Thread ID
Constraints
- 0 <= len(log_lines) <= 100000
- Each log line has length at most 1000
- A well-formed line is exactly '<timestamp> thread=<threadId> msg=<message>'
- threadId is non-empty
- Malformed lines are skipped
- Timestamps are consistent in format across valid input lines
Examples
Input: (['2026-02-13T10:15:30Z thread=42 msg=Starting work', '2026-02-13T10:15:28Z thread=7 msg=Init', '2026-02-13T10:15:29Z thread=42 msg=Loading'],)
Expected Output: {'42': ['2026-02-13T10:15:29Z thread=42 msg=Loading', '2026-02-13T10:15:30Z thread=42 msg=Starting work'], '7': ['2026-02-13T10:15:28Z thread=7 msg=Init']}
Explanation: Logs are grouped by thread ID. Thread 42 has two entries sorted by timestamp.
Input: (['100 thread=A msg=first at 100', '99 thread=A msg=before', '100 thread=A msg=second at 100'],)
Expected Output: {'A': ['99 thread=A msg=before', '100 thread=A msg=first at 100', '100 thread=A msg=second at 100']}
Explanation: Integer timestamps are sorted numerically. The two timestamp-100 logs keep their input order.
Input: (['10 thread=1 msg=ok', 'bad line', '11 thread=2 nope', '9 thread=1 msg=old', '12 thread= msg=missing id'],)
Expected Output: {'1': ['9 thread=1 msg=old', '10 thread=1 msg=ok']}
Explanation: Malformed lines are skipped, including missing msg= and empty thread ID.
Input: ([],)
Expected Output: {}
Explanation: An empty input produces an empty grouping.
Hints
- Split each line into at most three pieces so the message can still contain spaces.
- Store the original index along with each parsed line to preserve order when timestamps tie.
Part 2: Generate All NFT Attribute Combinations
Constraints
- 0 <= len(categories) <= 12
- len(categories) == len(values)
- 0 <= len(values[i]) <= 100
- Within this problem, values in each category are assumed to be distinct
- The total number of generated combinations will not exceed 100000
Examples
Input: (['Background', 'Ears', 'Hat'], [['Red', 'Blue'], ['Pointy', 'Wide'], ['Cap', 'None']])
Expected Output: [['Red', 'Pointy', 'Cap'], ['Red', 'Pointy', 'None'], ['Red', 'Wide', 'Cap'], ['Red', 'Wide', 'None'], ['Blue', 'Pointy', 'Cap'], ['Blue', 'Pointy', 'None'], ['Blue', 'Wide', 'Cap'], ['Blue', 'Wide', 'None']]
Explanation: There are 2 * 2 * 2 = 8 possible NFTs.
Input: (['Hat'], [['Cap', 'None']])
Expected Output: [['Cap'], ['None']]
Explanation: With one category, each value forms one combination.
Input: ([], [])
Expected Output: [[]]
Explanation: The Cartesian product of zero categories contains one empty combination.
Input: (['Background', 'Hat'], [['Red'], []])
Expected Output: []
Explanation: If any category has no available values, no complete NFT can be formed.
Hints
- This is the Cartesian product of the value lists.
- Build combinations category by category by appending each possible value to existing partial combinations.
Part 3: Generate Unique NFT Attribute Combinations
Constraints
- 0 <= len(categories) <= 12
- len(categories) == len(values)
- 0 <= len(values[i]) <= 1000
- Values are strings
- The total number of unique generated combinations will not exceed 100000
Examples
Input: (['Background', 'Ears'], [['Red', 'Red', 'Blue'], ['Pointy', 'Pointy']])
Expected Output: [['Red', 'Pointy'], ['Blue', 'Pointy']]
Explanation: Duplicate Red and Pointy entries do not create duplicate NFTs.
Input: (['A', 'B'], [['x', 'x'], ['y', 'z', 'y']])
Expected Output: [['x', 'y'], ['x', 'z']]
Explanation: The unique values are A: x and B: y, z.
Input: (['Hat'], [['Cap', 'Cap', 'Cap']])
Expected Output: [['Cap']]
Explanation: All duplicate paths produce the same single combination.
Input: ([], [])
Expected Output: [[]]
Explanation: With no categories, there is one empty unique combination.
Input: (['A'], [[]])
Expected Output: []
Explanation: A category with no values makes it impossible to form an NFT.
Hints
- Duplicates inside one category can create duplicate final combinations.
- Deduplicate each category's value list while preserving first occurrence, then take the Cartesian product.
Part 4: Weighted NFT Generation with Optional Duplicate Avoidance
Constraints
- 0 <= len(categories) <= 20
- len(categories) == len(values) == len(weights)
- len(values[i]) == len(weights[i])
- Each non-empty category has total weight > 0
- Weights are non-negative numbers
- 0 <= random_numbers[i] < 1
- 0 <= count <= 100000
Examples
Input: (['Background', 'Eyes'], [['Blue', 'Red'], ['Open', 'Closed']], [[1, 3], [2, 2]], [0.0, 0.49, 0.25, 0.99], 2, False)
Expected Output: [['Blue', 'Open'], ['Red', 'Closed']]
Explanation: The first attempt chooses Blue then Open. The second attempt uses the next two random numbers; 0.25 lands exactly on the first category boundary, so strict greater-than selects Red, and 0.99 selects Closed.
Input: (['Type'], [['A', 'B']], [[1, 1]], [0.1, 0.1, 0.9], 3, False)
Expected Output: [['A'], ['A'], ['B']]
Explanation: Duplicates are allowed, so the two generated A NFTs are both accepted before B is generated.
Input: (['Type'], [['A', 'B']], [[1, 1]], [0.1, 0.1, 0.9, 0.2], 3, True)
Expected Output: [['A'], ['B']]
Explanation: The second A and final A are duplicates and are skipped. Only A and B are accepted before random numbers run out.
Input: (['Color', 'Shape'], [['Red', 'Blue'], ['Circle', 'Square']], [[1, 1], [1, 1]], [0.1, 0.1, 0.2, 0.3, 0.8, 0.1, 0.8, 0.9], 3, True)
Expected Output: [['Red', 'Circle'], ['Blue', 'Circle'], ['Blue', 'Square']]
Explanation: The second generated NFT is another Red-Circle, so it is skipped. Later unique NFTs are accepted until count reaches 3.
Input: ([], [], [], [], 3, True)
Expected Output: [[]]
Explanation: With no categories, the only possible unique NFT is the empty NFT. Duplicate avoidance allows it once.
Input: (['A', 'B', 'C'], [['x', 'y'], ['p', 'q'], ['m', 'n']], [[1, 1], [1, 1], [1, 1]], [0.6, 0.4, 0.9, 0.1, 0.2], 2, False)
Expected Output: [['y', 'p', 'n']]
Explanation: One full attempt needs 3 random numbers. After accepting the first NFT, only 2 random numbers remain, so generation stops.
Input: (['Type'], [['A', 'B']], [[1, 1]], [0.1, 0.9], 0, True)
Expected Output: []
Explanation: When count is 0, no NFTs should be generated.
Hints
- Convert each category's weights into prefix sums. A random number r selects the first prefix sum greater than r * total_weight.
- When avoiding duplicates, store accepted combinations as tuples in a set.