Cos'è un set e quali problemi risolve?

Question

IT Interview Practice · Accepted Answer

Un **set** è una collezione non ordinata di elementi **unici**. La sua forza principale è rispondere alla domanda "X è qui?" in **O(1) medio**, e rifiuta automaticamente i duplicati.

## Esempio

```python
seen = set()
seen.add('a')
seen.add('a')          # ignored — already present
print(len(seen))       # 1
'a' in seen            # O(1) average membership test

# Set algebra
a = {1, 2, 3}
b = {2, 3, 4}
a & b                  # intersection -> {2, 3}
a | b                  # union        -> {1, 2, 3, 4}
a - b                  # difference   -> {1}
```

La maggior parte dei set sono implementati come **hash set** (una hash table che memorizza solo le chiavi), quindi:

| Operazione | Media |
|---|---|
| add | O(1) |
| remove | O(1) |
| membership (`in`) | O(1) |

## Usi comuni

- **Deduplicazione** — rimuovere i duplicati da una lista in una riga.
- **Membership veloce** — "ho già visto questo?"
- **Relazioni** — intersezione/unione/differenza tra gruppi.

## Perché è importante

I set rendono l'"unicità" e l'"appartenenza" banali e veloci, sostituendo i cicli annidati lenti sulle liste.

Un trucco comune nei colloqui — rilevare duplicati o nodi visitati — si riduce a poche operazioni su set.

Esempio

Usi comuni

Perché è importante

Domande correlate