Conas a dhéanann tú struchtúr sonraí a dhearadh le ceanglais sonracha O(1)/O(log n)?

Question

Accepted Answer

Struchtúr saincheaptha a dhearadh ciallaíonn **struchtúir atá ann a chomhdhéanamh** ionas go mbuaileann gach oibríocht atá de dhíth an chomplíochtaí sprice aici, ag ligean do struchtúr amháin laighe struchtúir eile a chlúdach. Is é an teicníc clasaiceach **léarscáil hash** a phéireáil le **eagar, carnán, nó liosta nasctha**.

## Sampla oibrithe: insert, delete, getRandom — go léir O(1)

Ceanglais: `insert(x)`, `remove(x)` agus `getRandom()` gach ceann in O(1). Ní féidir le léarscáil hash amháin O(1) randamach a dhéanamh; ní féidir le heagar amháin O(1) remove a dhéanamh. **Comhcheangail iad**.

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

## Leagan amach dearaidh ginearálta

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

| Patrún | Struchtúir chomhcheangailte | Cumasaíonn |
|---|---|---|
| Taisce LRU | léarscáil hash + liosta dhúbailte nasctha | O(1) get/put |
| Tacar randamach O(1) | léarscáil hash + eagar | O(1) insert/remove/random |
| Min in O(1) ar stac | stac + stac cúnta min | O(1) getMin |

## Cén fáth a bhfuil sé tábhachtach

Is annamh a bhíonn gá ag córas fíor le struchtúr gealadáin amháin — bíonn gá aici a bheith comhdhéanta agus a bheith dírithe ar phatrún rochtana sonracha, ar tugann na dearaí seo duit go díreach é.

Baineann agallamhóirí úsáid as na fadhbanna seo chun a thástáil ar bhreith ar dhóchúlacht gur féidir leat a réasúnaigh ó **chostais oibríochtaí go comhdhéanamh**, an scil bhunúsach taobh thiar dhearadh corpsystem ard-fheidhmíochta.

Patrún	Struchtúir chomhcheangailte	Cumasaíonn
Taisce LRU	léarscáil hash + liosta dhúbailte nasctha	O(1) get/put
Tacar randamach O(1)	léarscáil hash + eagar	O(1) insert/remove/random
Min in O(1) ar stac	stac + stac cúnta min	O(1) getMin