तुम विशिष्ट 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) 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)
```

## एक सामान्य डिजाइन रेसिपी

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