آپ مخصوص O(1)/O(log n) ضروریات کے ساتھ ایک ڈیٹا سٹرکچر کو کیسے ڈیزائن کرتے ہیں؟

Question

Accepted Answer

ایک custom structure کو ڈیزائن کرنے کا مطلب ہے **موجودہ structures کو compose کرنا** تاکہ ہر required operation اپنا target complexity حاصل کرے، ایک structure دوسرے کی کمزوری کو پورا کرتا ہے۔ یہ classical technique ایک **hash map** کو **array، heap، یا linked list** کے ساتھ جوڑنا ہے۔

## ایک کام کی گئی مثال: insert، delete، getRandom — سب O(1)

ضروریات: `insert(x)`، `remove(x)`، اور `getRandom()` ہر ایک O(1) میں۔ ایک hash map اکیلا O(1) random نہیں کر سکتا؛ ایک 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)
```

## ایک عمومی ڈیزائن recipe

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

| Pattern | Structures combined | Enables |
|---|---|---|
| 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 |

## یہ کیوں اہم ہے

حقیقی systems کو شاذ و نادر ایک single textbook structure کی ضرورت ہے — انہیں ایک مخصوص access pattern کے لیے tune کیے گئے composite کی ضرورت ہے، جو بالکل یہی ہے جو یہ designs فراہم کرتے ہیں۔

Interviewers ان مسائل کو یہ test کرنے کے لیے استعمال کرتے ہیں کہ آپ **operation costs سے composition تک** سوچ سکتے ہیں یا نہیں، جو high-performance system design کے پیچھے کی core skill ہے۔

Pattern	Structures combined	Enables
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