Πώς επιλέγετε τη σωστή δομή δεδομένων για ένα πρόβλημα;

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

## Αντιστοίχιση λειτουργιών με πολυπλοκότητα

| Ανάγκη | Καλύτερη δομή | Κόστος κύριας λειτουργίας |
|---|---|---|
| Τυχαία πρόσβαση ανά ευρετήριο | dynamic array | O(1) |
| Αναζήτηση κατά κλειδί | hash map | O(1) avg |
| Ταξινομημένο + ερωτήματα εύρους | balanced BST | O(log n) |
| Min/max επανειλημμένα | heap | O(log n) pop |
| FIFO / LIFO | queue / stack | 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²) — το μεγαλύτερο μοχλό στην απόδοση.

Οι συνεντευξιαστές δοκιμάζουν ακριβώς αυτό το συλλογισμό: θέλουν να δουν πώς αντιστοιχίζετε τις απαιτήσεις στα κόστη λειτουργιών, όχι απλώς να απομνημονεύετε δομές.

Ανάγκη	Καλύτερη δομή	Κόστος κύριας λειτουργίας
Τυχαία πρόσβαση ανά ευρετήριο	dynamic array	O(1)
Αναζήτηση κατά κλειδί	hash map	O(1) avg
Ταξινομημένο + ερωτήματα εύρους	balanced BST	O(log n)
Min/max επανειλημμένα	heap	O(log n) pop
FIFO / LIFO	queue / stack	O(1)
Αναζήτηση προθέματος	trie	O(L)