كيف تصمم بنية بيانات بمتطلبات O(1)/O(log n) محددة؟

Question

Accepted Answer

تصميم بنية مخصصة يعني **دمج البنى الموجودة** بحيث تحقق كل عملية مطلوبة تعقيد زمني محدد، مما يسمح ببنية واحدة بتغطية ضعف بنية أخرى. الأسلوب الكلاسيكي هو جمع **خريطة hash** مع **مصفوفة، كومة، أو قائمة مرتبطة**.

## مثال عملي: insert و delete و getRandom — جميعها O(1)

المتطلبات: `insert(x)` و `remove(x)` و `getRandom()` كل منها في O(1). خريطة hash وحدها لا تستطيع O(1) عشوائي؛ مصفوفة وحدها لا تستطيع O(1) حذف. **ادمجهما**.

```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 + قائمة مرتبطة ثنائية الاتجاه | O(1) get/put |
| مجموعة عشوائية O(1) | خريطة hash + مصفوفة | O(1) insert/remove/random |
| Min في O(1) على stack | stack + min-stack مساعد | O(1) getMin |

## لماذا يهم

الأنظمة الحقيقية نادراً ما تحتاج بنية نصية واحدة — فهي تحتاج إلى مركب معدّل لنمط وصول محدد، وهذا بالضبط ما يوفره هذا التصميم.

يستخدم المقابلون هذه المسائل لاختبار ما إذا كان بإمكانك الاستدلال من **تكاليف العمليات إلى تركيب**، وهي المهارة الأساسية وراء تصميم الأنظمة عالية الأداء.