آپ کسی مسئلے کے لیے صحیح data structure کا انتخاب کیسے کرتے ہیں؟

Question

Accepted Answer

اس structure کو منتخب کریں جس کی **سب سے زیادہ استعمال ہونے والی operations سب سے سستی** ہوں آپ کے access pattern کے لیے۔ ان operations کی فہرست بنا کر شروع کریں جو آپ انجام دیں گے، ان کی تعداد کا اندازہ لگائیں، پھر انہیں structure کی طاقتوں سے ملائیں۔

## فیصلے کی فہرست

```text
1. How do you access data?  by index -> array
                            by key   -> hash map
                            by order -> tree / heap
2. Need ordering?           sorted   -> balanced BST / sorted array
                            FIFO     -> queue
                            LIFO     -> stack
3. Frequent middle inserts? -> linked list
4. Need fast "seen it?"     -> set / hash map
5. Need "best/min/max next" -> heap (priority queue)
```

## Operations کو complexity سے ملائیں

| ضرورت | بہترین structure | اہم op cost |
|---|---|---|
| Index سے Random access | dynamic array | O(1) |
| Key سے Lookup | hash map | O(1) avg |
| Sorted + range queries | balanced BST | O(log n) |
| Min/max بار بار | heap | O(log n) pop |
| FIFO / LIFO | queue / stack | O(1) |
| Prefix search | trie | O(L) |

## مثال کی وجہ

```text
"Find the 10 most frequent words in a huge file."
 - count frequencies  -> hash map (O(1) updates)
 - keep top 10        -> min-heap of size 10 (O(log 10) per word)
```

## اہمیت

صحیح انتخاب اکثر O(n) اور O(n²) حل کے درمیان فرق ہوتا ہے — کارکردگی پر سب سے بڑا اثر ڈالنے والا عامل۔

Interviewers بالکل یہی reasoning test کرتے ہیں: وہ یہ دیکھنا چاہتے ہیں کہ آپ requirements کو operation costs سے کیسے ملاتے ہیں، نہ کہ structures کو یاد کرتے ہیں۔

ضرورت	بہترین structure	اہم op cost
Index سے Random access	dynamic array	O(1)
Key سے Lookup	hash map	O(1) avg
Sorted + range queries	balanced BST	O(log n)
Min/max بار بار	heap	O(log n) pop
FIFO / LIFO	queue / stack	O(1)
Prefix search	trie	O(L)