Find Every Three-Card Set Among Cards With Four Attributes
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
A card game uses cards that each have four attributes: color, shape, number and shading. As in the standard version of the game, each attribute takes one of three values, so a card is encoded as four integers, each `0`, `1` or `2`.
Three cards form a **set** when, for each attribute separately, the three cards' values are either all the same or all different. For example, three cards with the same color, three different shapes, the same number and three different shadings form a set. Three cards where two share a color and the third has another color are not a set, whatever their other attributes are.
The interview first asked whether three given cards form a set. The follow-up gave any number of cards and asked which groups of three form a set. Implement the follow-up; given exactly three cards, it answers the original question. Checking every group of three is a reasonable first answer, after which the interviewer appeared to want an approach whose running time is quadratic in the number of cards.
### Function Signature
```python
def find_sets(cards: list[list[int]]) -> list[list[int]]:
```
`cards[i]` is `[color, shape, number, shading]` for card `i`.
### Rules
- Indices `i < j < k` form a set when, for every attribute `a` in `0..3`, the values `cards[i][a]`, `cards[j][a]` and `cards[k][a]` are all equal or pairwise different.
- Return every set as a list `[i, j, k]` with `i < j < k`.
- Sort the returned list in ascending lexicographic order: by `i`, then by `j`, then by `k`.
- Return an empty list when no set exists, including when there are fewer than three cards.
### Constraints
- `1 <= len(cards) <= 81`
- `len(cards[i]) == 4`, and every value is `0`, `1` or `2`.
- All cards are distinct, as in a real deck, which has exactly 81 different cards.
### Examples
**Example 1**
```text
Input: cards = [[0, 1, 2, 0], [0, 2, 2, 1], [0, 0, 2, 2]]
Output: [[0, 1, 2]]
```
Color is 0, 0, 0 (all the same), shape is 1, 2, 0 (all different), number is 2, 2, 2 (all the same) and shading is 0, 1, 2 (all different). Every attribute passes, so the three cards form a set.
**Example 2**
```text
Input: cards = [[0, 0, 0, 0], [0, 0, 0, 1], [1, 0, 0, 2]]
Output: []
```
The colors are 0, 0, 1: two match and one differs. These three cards are therefore not a set, even though their shapes and numbers are all the same and their shadings are all different.
**Example 3**
```text
Input: cards = [[0, 0, 0, 0], [1, 1, 1, 1], [2, 2, 2, 2], [0, 1, 2, 0], [0, 2, 1, 0], [1, 0, 0, 0]]
Output: [[0, 1, 2], [0, 3, 4]]
```
Cards 0, 1 and 2 differ in every attribute. Cards 0, 3 and 4 share color 0 and shading 0, and have all-different shapes (0, 1, 2) and numbers (0, 2, 1). No other group of three is a set, and card 5 belongs to none.
Overview: A coding problem based on a card game in which each card has four attributes with three values each, and three cards form a set when every attribute is all the same or all different. It asks for every set among a group of distinct cards, testing the validity rule, canonical output ordering and improving on a cubic brute force.
Read the full Snowflake Software Engineer interview experience this question came from
A card game uses cards that each have four attributes: color, shape, number and shading. Each attribute takes one of three values, so card `i` is encoded as `cards[i] = [color, shape, number, shading]`, four integers that are each `0`, `1` or `2`.
Three cards form a **set** when, for each attribute separately, the three cards' values are either all the same or all different. For example, three cards with the same color, three different shapes, the same number and three different shadings form a set. Three cards where two share a color and the third has another color are not a set, whatever their other attributes are.
Given any number of distinct cards, return every group of three cards that forms a set. Given exactly three cards, this answers whether those three cards form a set. Checking every group of three is a reasonable first answer; the interviewer was looking for an approach whose running time is quadratic in the number of cards.
### Rules
- Indices `i < j < k` form a set when, for every attribute `a` in `0..3`, the values `cards[i][a]`, `cards[j][a]` and `cards[k][a]` are all equal or pairwise different.
- Return every set as a list `[i, j, k]` of 0-based card indices with `i < j < k`.
- Sort the returned list in ascending lexicographic order: by `i`, then by `j`, then by `k`.
- Return an empty list when no set exists, including when there are fewer than three cards.
Every index is at most 80 and there are at most 1080 sets, so every value fits in a 32-bit integer.
### Example 1
```text
Input: cards = [[0, 1, 2, 0], [0, 2, 2, 1], [0, 0, 2, 2]]
Output: [[0, 1, 2]]
```
Color is 0, 0, 0 (all the same), shape is 1, 2, 0 (all different), number is 2, 2, 2 (all the same) and shading is 0, 1, 2 (all different). Every attribute passes, so the three cards form a set.
### Example 2
```text
Input: cards = [[0, 0, 0, 0], [1, 1, 1, 1], [2, 2, 2, 2], [0, 1, 2, 0], [0, 2, 1, 0], [1, 0, 0, 0]]
Output: [[0, 1, 2], [0, 3, 4]]
```
Cards 0, 1 and 2 differ in every attribute. Cards 0, 3 and 4 share color 0 and shading 0, and have all-different shapes (0, 1, 2) and numbers (0, 2, 1). No other group of three is a set, and card 5 belongs to none.
### Constraints
- `1 <= len(cards) <= 81`
- `len(cards[i]) == 4`, and every value is `0`, `1` or `2`.
- All cards are distinct, as in a real deck, which has exactly 81 different cards.
Constraints
- 1 <= len(cards) <= 81
- len(cards[i]) == 4, and every value is 0, 1 or 2
- All cards are distinct, as in a real deck, which has exactly 81 different cards
Examples
Input: ([[2, 2, 2, 2]],)
Expected Output: []
Explanation: Minimum valid: a single card (every value at the bound 2) is fewer than three cards, so the result is empty.
Input: ([[1, 2, 0, 1], [2, 2, 0, 1]],)
Expected Output: []
Explanation: Two cards are fewer than three, so no set exists.
Hints
- Judge each of the four attributes on its own: a group of three fails as soon as any single attribute shows exactly two equal values.
- Report positions in the input rather than card values, and make sure each qualifying group appears once, as i < j < k, in lexicographic order.
- The follow-up asks for a running time quadratic in the number of cards: consider how much freedom a third card has once two cards are fixed.