როგორ აირჩიეთ სწორი მონაცემთა სტრუქტურა პრობლემისთვის?

Question

Accepted Answer

აირჩიეთ სტრუქტურა, რომლის **ყველაზე ხშირი ოპერაციები ყველაზე იაფია** თქვენი წვდომის ნიმუშისთვის. დაიწყეთ იმ ოპერაციების ჩამოთვლით, რომელსაც შესრულებთ, შეაფასეთ მათი სიხშირე, შემდეგ მათ მიუთითეთ სტრუქტურის ძლევამოსილების მიხედვით.

## გადაწყვეტის შემოწმების სია

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

## ოპერაციების შესაბამისობა რთულობასთან

| საჭირო | საუკეთესო სტრუქტურა | ძირითადი ოპ ღირებულება |
|---|---|---|
| შემთხვევითი წვდომა ინდექსით | დინამიური მასივი | O(1) |
| ძიება გასაღებით | hash map | O(1) საშ. |
| დალაგებული + დიაპაზონის მოთხოვნა | დაბალანსებული BST | O(log n) |
| Min/max განმეორებით | heap | O(log n) pop |
| FIFO / LIFO | რიგი / სტეკი | O(1) |
| პრეფიქსის ძიება | 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²) ამოხსნებს შორის — ერთი ყველაზე დიდი ბერკეტი ღირებულებაზე.

ინტერვიউზე გამოკითხვის მიზანი მხოლოდ ეს მსჯელობაა: გინდათ იხილოთ, როგორ აბრუნებთ მოთხოვნილებებს ოპერაციული ღირებულებების მიმართ, არ დაიმახსოვროთ სტრუქტურა.

საჭირო	საუკეთესო სტრუქტურა	ძირითადი ოპ ღირებულება
შემთხვევითი წვდომა ინდექსით	დინამიური მასივი	O(1)
ძიება გასაღებით	hash map	O(1) საშ.
დალაგებული + დიაპაზონის მოთხოვნა	დაბალანსებული BST	O(log n)
Min/max განმეორებით	heap	O(log n) pop
FIFO / LIFO	რიგი / სტეკი	O(1)
პრეფიქსის ძიება	trie	O(L)