ਤੁਸੀਂ ਖਾਸ O(1)/O(log n) ਲੋੜਾਂ ਦੇ ਨਾਲ ਡੇਟਾ ਸਟਰਕਚਰ ਨੂੰ ਕਿਵੇਂ ਡਿਜ਼ਾਈਨ ਕਰਦੇ ਹੋ?

Question

Accepted Answer

ਕਸਟਮ ਸਟਰਕਚਰ ਨੂੰ ਡਿਜ਼ਾਈਨ ਕਰਨਾ ਮਤਲਬ **ਮੌਜੂਦਾ ਸਟਰਕਚਰਾਂ ਨੂੰ ਜੋੜਨਾ** ਤਾਕਿ ਹਰੇਕ ਲੋੜੀਂਦਾ ਓਪਰੇਸ਼ਨ ਆਪਣੀ ਟਾਰਗਟ ਪੇਚੀਦਗੀ ਨੂੰ ਪੂਰਾ ਕਰੇ, ਜਿਸ ਨਾਲ ਇੱਕ ਸਟਰਕਚਰ ਦੂਸਰੇ ਦੀ ਕਮਜ਼ੋਰੀ ਨੂੰ ਕਵਰ ਕਰ ਸਕੇ। ਕਲਾਸਿਕ ਤਕਨੀਕ ਇੱਕ **hash map** ਨੂੰ ਇੱਕ **array, heap, ਜਾਂ linked list** ਦੇ ਨਾਲ ਜੋੜਨਾ ਹੈ।

## ਇੱਕ ਵਰਕ ਕੀਤੀ ਹੋਈ ਉਦਾਹਰਨ: insert, delete, getRandom — ਸਭ O(1)

ਲੋੜਾਂ: `insert(x)`, `remove(x)`, ਅਤੇ `getRandom()` ਹਰੇਕ O(1) ਵਿੱਚ। ਇੱਕ hash map ਇਕੱਲਾ O(1) ਰਿਡਮ ਨਹੀਂ ਕਰ ਸਕਦਾ; ਇੱਕ array ਇਕੱਲਾ O(1) remove ਨਹੀਂ ਕਰ ਸਕਦਾ। **ਉਹਨਾਂ ਨੂੰ ਜੋੜੋ**।

```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 + doubly linked list | O(1) get/put |
| O(1) randomized set | hash map + array | O(1) insert/remove/random |
| Min in O(1) on a stack | stack + auxiliary min-stack | O(1) getMin |

## ਇਹ ਮਾਇਨੇ ਕਿਉਂ ਰੱਖਦਾ ਹੈ

ਅਸਲ ਸਿਸਟਮ ਨੂੰ ਬਹੁਤ ਘੱਟ ਸਿਰਫ਼ ਇੱਕ ਪਾਠਾਭ ਸਟਰਕਚਰ ਦੀ ਲੋੜ ਹੋਵੇ — ਉਨ੍ਹਾਂ ਨੂੰ ਇੱਕ ਖਾਸ ਅ਼ਸੈਸ ਪੈਟਰਨ ਲਈ ਟਿਊਨ ਕੀਤੇ ਗਏ ਮਿਸ਼ਰਤ ਦੀ ਲੋੜ ਹੁੰਦੀ ਹੈ, ਜੋ ਬਿਲਕੁਲ ਇਹ ਹੈ ਜੋ ਇਹ ਡਿਜ਼ਾਈਨ ਪ੍ਰਦਾਨ ਕਰਦੇ ਹਨ।

ਇੰਟਰਵਿਊਅਰ ਇਹ ਸਮੱਸਿਆਵਾਂ ਵਰਤਦੇ ਹਨ ਤਾਂ ਜੋ ਪਰਖਿਆ ਜਾ ਸਕੇ ਕਿ ਕੀ ਤੁਸੀਂ **ਓਪਰੇਸ਼ਨ ਲਾਗਤਾਂ ਤੋਂ ਇੱਕ ਮਿਸ਼ਰਣ ਤੱਕ** ਦਲੀਲ ਕਰ ਸਕਦੇ ਹੋ, ਜੋ ਉੱਚ-ਪ੍ਰਦਰਸ਼ਨ ਸਿਸਟਮ ਡਿਜ਼ਾਈਨ ਦੇ ਪਿੱਛੇ ਮੂਲ ਕੌਸ਼ਲ ਹੈ।

ਪੈਟਰਨ	ਜੋੜੇ ਗਏ ਸਟਰਕਚਰ	ਸਮਰੱਥ ਬਣਾਉਂਦਾ ਹੈ
LRU cache	hash map + doubly linked list	O(1) get/put
O(1) randomized set	hash map + array	O(1) insert/remove/random
Min in O(1) on a stack	stack + auxiliary min-stack	O(1) getMin