Si e projekton një strukturë të dhënash me kërkesa specifike O(1)/O(log n)?

Question

Accepted Answer

Projektimi i një strukture të personalizuar do të thotë **kombinimi i strukturave ekzistuese** në mënyrë që secila operacion i kërkuar të arrijë kompleksitetin e tij të synuar, duke lejuar që njëra strukturë të mbulojë dobësinë e tjetrës. Teknika klasike është çiftimi i një **harte hash** me një **varg, grumbull, ose listë të lidhur**.

## Një shembull praktik: insert, delete, getRandom — të gjitha O(1)

Kërkesa: `insert(x)`, `remove(x)` dhe `getRandom()` secila në O(1). Një hartë hash e vetme nuk mund të bëjë O(1) të rastësishëm; një varg vetëm nuk mund të bëjë O(1) fshirje. **Kombinoji ato**.

```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)
```

## Një recetë të përgjithshme projektimi

```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.
```

| Modeli | Strukturat e kombinuara | Lejon |
|---|---|---|
| Memoria e njëpasnjëshme LRU | hartë hash + listë dyfish e lidhur | O(1) get/put |
| Set i rastësishëm O(1) | hartë hash + varg | O(1) insert/remove/random |
| Min në O(1) në një stack | stack + min-stack ndihmës | O(1) getMin |

## Pse është i rëndësishëm

Sistemet reale rrallë kanë nevojë për një strukturë të vetme nga teksti — kanë nevojë për një përbërje të përshtatur me një model specifik të qasjes, i cili është pikërisht ajo që këta dizajne ofrojnë.

Intervistuesit përdorin këto probleme për të testuar nëse mund të arsyetosh nga **kostot e operacioneve në një përbërje**, aftësia themelore pas dizajnit të sistemeve me performancë të lartë.

Modeli	Strukturat e kombinuara	Lejon
Memoria e njëpasnjëshme LRU	hartë hash + listë dyfish e lidhur	O(1) get/put
Set i rastësishëm O(1)	hartë hash + varg	O(1) insert/remove/random
Min në O(1) në një stack	stack + min-stack ndihmës	O(1) getMin