Πώς σχεδιάζετε μια δομή δεδομένων με συγκεκριμένες απαιτήσεις O(1)/O(log n);

Question

Accepted Answer

Το σχεδιασμό μιας προσαρμοσμένης δομής σημαίνει συνδυασμό υπαρχουσών δομών έτσι ώστε κάθε απαιτούμενη λειτουργία να φτάνει την στοχευμένη πολυπλοκότητά της, επιτρέποντας σε μια δομή να καλύψει την αδυναμία μιας άλλης. Η κλασική τεχνική είναι ο συνδυασμός ενός hash map με ένα array, heap ή linked list.

Ένα πρακτικό παράδειγμα: insert, delete, getRandom — όλα O(1)

Απαιτήσεις: , και καθεμία σε O(1). Ένα hash map μόνο δεν μπορεί να κάνει O(1) τυχαίο; ένα array μόνο δεν μπορεί να κάνει O(1) διαγραφή. .

## Ένα πρακτικό παράδειγμα: insert, delete, getRandom — όλα O(1)

Απαιτήσεις: `insert(x)`, `remove(x)` και `getRandom()` καθεμία σε O(1). Ένα hash map μόνο δεν μπορεί να κάνει O(1) τυχαίο; ένα array μόνο δεν μπορεί να κάνει O(1) διαγραφή. **Συνδυάστε τις**.

```python
import random
class RandomizedSet:
    def __init__(self):
        self.idx = {}      # value -> index in list
        self.vals = []     # values for O(1) random pick
    def insert(self, x):                    # O(1)
        if x in self.idx: return False
        self.idx[x] = len(self.vals)
        self.vals.append(x)
        return True
    def remove(self, x):                    # O(1): swap with last, pop
        if x not in self.idx: return False
        i, last = self.idx[x], self.vals[-1]
        self.vals[i] = last                 # move last into the hole
        self.idx[last] = i
        self.vals.pop()
        del self.idx[x]
        return True
    def getRandom(self):                    # O(1)
        return random.choice(self.vals)
```

## Μια γενική συνταγή σχεδιασμού

```text
1. List every required operation + its target complexity.
2. For each, name a structure that hits it:
     by key O(1)      -> hash map
     by index O(1)    -> array
     min/max O(log n) -> heap
     ordered O(log n) -> balanced tree / skip list
     O(1) splice      -> doubly linked list
3. COMBINE them; use the hash map to map keys -> positions/nodes
   in the other structure so updates stay O(1).
4. Verify each operation against its target.
```

| Μοτίβο | Συνδυασμένες δομές | Ενεργοποιεί |
|---|---|---|
| LRU cache | hash map + διπλά συνδεδεμένη λίστα | O(1) get/put |
| O(1) τυχαιοποιημένο σύνολο | hash map + array | O(1) insert/remove/random |
| Min σε O(1) σε ένα stack | stack + βοηθητικό min-stack | O(1) getMin |

## Γιατί έχει σημασία

Τα πραγματικά συστήματα σπάνια χρειάζονται μια μόνο δομή εγχειριδίου — χρειάζονται έναν συνδυασμό που έχει συντονιστεί σε ένα συγκεκριμένο μοτίβο πρόσβασης, το οποίο είναι ακριβώς αυτό που παρέχουν αυτά τα σχέδια.

Οι συνεντευκτάζοντες χρησιμοποιούν αυτά τα προβλήματα για να ελέγξουν εάν μπορείτε να συλλογιστείτε από **κόστη λειτουργιών σε συνδυασμό**, την κεντρική δεξιότητα πίσω από το σχεδιασμό συστημάτων υψηλής απόδοσης.

Μοτίβο	Συνδυασμένες δομές	Ενεργοποιεί
LRU cache	hash map + διπλά συνδεδεμένη λίστα	O(1) get/put
O(1) τυχαιοποιημένο σύνολο	hash map + array	O(1) insert/remove/random
Min σε O(1) σε ένα stack	stack + βοηθητικό min-stack	O(1) getMin