Skip to content

Latest commit

 

History

History
660 lines (530 loc) · 49 KB

README-el.md

File metadata and controls

660 lines (530 loc) · 49 KB
Raw

#Coding Interview University

Επίσημη έκδοση: Αγγλικά

Τι είναι

Είναi το πλάνο διαβάσματός μου για να γίνω από web developer (αυτοδίδακτος, χωρίς πτυχίο στην Επιστήμη των Υπολογιστών), μηχανικός λογισμικού για μία μεγάλη εταιρία.

Coding at the whiteboard - from HBO's Silicon Valley

Αυτό το έργο προορίζεται για νέους μηχανικούς λογισμικού ή για αυτούς που μεταβαίνουν από την ανάπτυξη λογισμικού/ιστοσελίδων στην τεχνολογία λογισμικού(εκεί που η γνώση για την επιστήμη των υπολογιστών ειναι προαπαιτούμενο). Αν έχεις αρκετά χρόνια εμπειρίας και αξιώνεις πολλά χρόνια εμπερίας στην τεχνολογία λογισμικού, πρέπει να περιμένεις μία δυσκολότερη συνέντευξη.

Εάν έχεις αρκετά χρόνια εμπειρίας στην ανάπτυξη λογισμικού/ιστοσελίδων, σημείωσε ότι οι μεγάλες εταιρίες λογισμικού όπως οι Google, Amazon, Facebook και Microsoft βλέπουν την τεχνολογία λογισμικού ως ενα διαφορετικό κομμάτι από την ανάπτυξη λογισμικού/ιστοσελίδων, και απαιτούν γνώσεις πάνω στην επιστήμη υπολογιστών.

Εάν θέλεις να είσαι ένας αξιόπιστος μηχανικός ή μηχανικός συστημάτων, διάβασε περισσότερο απο την προεραιτική λίστα(δίκτυα, ασφάλεια).

Πίνακας περιεχομένων

---------------- Everything below this point is optional ----------------

Γιατί να το χρησιμοποιήσεις

Όταν άρχισα αυτό το πρότζεκτ, δεν ήξερα τη διαφορά μίας στοίβας από μία ουρά, δεν ήξερα τίποτα σχετικά με τον συμβολισμό Big-Ο, τίποτα σχετικά με τα δέντρα ή πως να διασχίσω ένα δέντρο. Εάν έπρεπε να γράψω σε κώδικα έναν αλγόριθμο ταξινόμησης, μπορώ να σου πω ότι δεν θα ήταν πολύ καλός. Κάθε δομή δεδομένων που είχα χρησιμοποιήσει ήταν πακέτο της γλώσσας, και δεν ήξερα καθόλου πως δούλευαν "κάτω από το καπό". Ποτέ δεν είχα να διαχειριστώ τη μνήμη εκτός εάν μία διεργασία που έτρεχα, μου επέστρεφε ένα σφάλμα του τύπου: "out of memory", και μετά έπρεπε να βρώ μία λύση. Έχω χρησιμοποιήσει μερικούς πολυδιάστατους πίνακες στη ζωή μου και χιλιάδες συναφείς πίνακες, αλλά δεν είχα δημιουργήσει δομές δεδομένων από το 0.

Είναι ένα μακροπρόθεσμο πλάνο. Μπορεί να σου πάρει μήνες. Εάν είσαι οικείος με πολλά από αυτά ήδη, θα σου πάρει πολύ λιγότερο χρόνο.

Πώς να το χρησιμοποιήσεις

Οτιδήποτε παρακάτω είναι μία συνοπτική περιγραφή, και πρέπει να τα καταλάβεις από την αρχή μέχρι το τέλος.

Χρησιμοποιώ τη χαρακτηρηστική markdown γλώσσα του Github, σεμπεριλαμβανομένων και των tasks lists για να ελέγχω την εξέλιξη του πρότζεκτ.

Δημιούργησε ένα καινούργιο branch [x]

Κάνε fork το branch και ακολούθησε τις παρακάτω εντολές

git checkout -b progress

git remote add jwasham https://github.com/jwasham/coding-interview-university

git fetch --all

Μάρκαρε όλα τα κουτιά με X αφού ολοκληρώσεις τις αλλαγές

git add .

git commit -m "Marked x"

git rebase jwasham/master

git push --force

Περισσότερα σχετικά με την Github-flavored markdown

Μη νιώθεις ανίκανος

Σχετικά με τα βίντεο

Μερικά βίντεο είναι διαθέσιμα μόνο κάνοντας εγγραφή σε μία Coursera, EdX, or Lynda.com τάξη. Αυτές καλούνται MOOCs. Μερικές φορές οι τάξεις δεν είναι διαθέσιμες, έτσι πρέπει να περιμένεις 1-2 μήνες, έτσι ώστε να αποκτήσεις πρόσβαση. Τα μαθήματα του Lynada.com δεν είναι δωρεάν.

Θα εκτιμούσα τη βοήθεια σου να προσθέσεις δωρεάν και πάντοτε-διαθέσιμες ανοικτές πηγές, όπως βίντεο από το Youtube να συνοδεύσουν τα online μαθήματα βίντεο. 
Μου αρέσει να χρησιμοποιώ πανεπιστημιακές διαλέξεις.

Διαδικασία Συνέντευξης & Γενική προετοιμασία συνέντευξης

Διάλεξε μία γλώσσα για τη συνέντευξη

Μπορείς να χρησιμοποιήσεις μία γλώσσα με την οποία είσαι άνετος για να κάνεις το προγραμματιστικό κομμάτι της συνέντευξης, αλλά για τις μεγάλες εταιρίες, υπάρχουν ατόφιες επιλογές:

  • C++
  • Java
  • Python

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

  • Javascript
  • Ruby

Πρέπει να είσαι πολύ εξοικιωμένος με τη γλώσσα και γνώστης.

Διάβασε περισσότερα σχετικά με τις παραπάνω επιλογές:

Βρες πόρους για τη γλώσσα εδώ

Θα δείς λίγη γνώση σχετικά με τις C, C++ και Python να περιέχεται παρακάτω, επείδη μαθαίνω. Υπάρχουν μερικά εμπλεκόμενα βιβλία, δες το κάτω μέρος.

Λίστα βιβλίων

Εάν έχεις αρκετό ελεύθερο χρόνο:

Αρχιτεκτονική Υπολογιστών

Αν έχεις λίγο χρόνο:

  • Write Great Code: Volume 1: Understanding the Machine
    • Το βιβλίο δημοσιεύτηκε το 2004, και είναι λίγο απαρχεωμένο, αλλά είναι ένας υπέροχος πόρος για να κατανοήσεις έναν υπολογιστή εν συντομία.
    • Ο συγγραφέας εφηύρε το HLA, έτσι μην παίρνεις τις αναφορές του και παραδείγματά του για το HLA, τοις μετρητοίς.
    • Αυτά τα κεφάλαια αξίζουν το διάβασμα για να σου δώσουν ισχυρά θεμέλια:
      • Chapter 2 - Numeric Representation
      • Chapter 3 - Binary Arithmetic and Bit Operations
      • Chapter 4 - Floating-Point Representation
      • Chapter 5 - Character Representation
      • Chapter 6 - Memory Organization and Access
      • Chapter 7 - Composite Data Types and Memory Objects
      • Chapter 9 - CPU Architecture
      • Chapter 10 - Instruction Set Architecture
      • Chapter 11 - Memory Architecture and Organization

Αν έχεις αρκετό χρόνο (Το θέλω αυτό το βιβλίο):

Συγκεκριμένη γλώσσα

Θα πρέπει να επιλέξεις μία γλώσσα για τη συνέντευξη (δες παραπάνω). Εδώ είναι οι προτάσεις μου ανά γλώσσα. Δεν έχω τους πόρους για όλες τις γλώσσες. Καλοδεχούμενες οι προσθήκες.

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

Επιπρόσθετοι πόροι που αφορούν συγκεκριμένες γλώσσες εδώ.

C++

Δεν έχω διαβάσει αυτά τα δύο, αλλά έχουν λάβει υψηλές αξιολογήσεις και έχουν γραφτεί από τον Sedgewick. Είναι φοβερός.

Εάν έχεις μία καλύτερη πρόταση για τη C++, παρακαλώ ενημέρωσέ με. Ψάχνοντας για έναν περιεκτικό πόρο.

Java

Ή:

  • Data Structures and Algorithms in Java
    • by Goodrich, Tamassia, Goldwasser
    • used as optional text for CS intro course at UC Berkeley
    • see my book report on the Python version below. This book covers the same topics.

Python

Προαιρετικά Βιβλία

Ορισμένοι συστήνουν αυτά, αλλά το παρακάνουν, εκτός εάν έχεις πολλά χρόνια εμπειρίας και περιμένεις μία δυσκολότερη συνέντευξη:

  • Algorithm Design Manual (Skiena)

    • As a review and problem recognition
    • The algorithm catalog portion is well beyond the scope of difficulty you'll get in an interview.
    • This book has 2 parts:
      • class textbook on data structures and algorithms
        • pros:
          • is a good review as any algorithms textbook would be
          • nice stories from his experiences solving problems in industry and academia
          • code examples in C
        • cons:
          • can be as dense or impenetrable as CLRS, and in some cases, CLRS may be a better alternative for some subjects
          • chapters 7, 8, 9 can be painful to try to follow, as some items are not explained well or require more brain than I have
          • don't get me wrong: I like Skiena, his teaching style, and mannerisms, but I may not be Stony Brook material.
      • algorithm catalog:
        • this is the real reason you buy this book.
        • about to get to this part. Will update here once I've made my way through it.
    • Can rent it on kindle
    • Half.com is a great resource for textbooks at good prices.
    • Answers:
    • Errata

  • Introduction to Algorithms

    • Important: Reading this book will only have limited value. This book is a great review of algorithms and data structures, but won't teach you how to write good code. You have to be able to code a decent solution efficiently.
    • Half.com is a great resource for textbooks at good prices.
    • aka CLR, sometimes CLRS, because Stein was late to the game

  • Programming Pearls

    • The first couple of chapters present clever solutions to programming problems (some very old using data tape) but that is just an intro. This a guidebook on program design and architecture, much like Code Complete, but much shorter.

  • "Algorithms and Programming: Problems and Solutions" by Shen

    • A fine book, but after working through problems on several pages I got frustrated with the Pascal, do while loops, 1-indexed arrays, and unclear post-condition satisfaction results.
    • Would rather spend time on coding problems from another book or online coding problems.

Πριν αρχίσεις

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

Εδώ βρίσκονται κάποια λάθη που έκανα για να έχεις μία καλύτερη εμπειρία.

1. Δε θα το θυμάσαι καθόλου

Είδα αρκετές ώρες βίντεο και πήρα άφθονες σημειώσεις, κα μήνες μετά υπήρχαν πολλά τα οποία δεν θυμόμουν. Ξόδεψα 3 μέρες εξετάζοντας λεπτομερώς τις σημειώσεις μου και έκανα καρτέλες για να μπορούσα να τις αξιολογήσω.

Σε παρακαλώ διάβασε τα για να μην κανεις τα ίδια λάθη με τα δικά μου:

Retaining Computer Science Knowledge

2. Χρησιμοποιήσε κάρτες σημειώσεων

Να λύνεις το πρόβλημα, Εγώ έκανα μία μικρή ιστοσελίδα με κάρτες σημειώσεων 2 τύπων: γενικές και κώδικα. Κάθε μία κάρτα έχει διαφορετικό φορμάτ.

Έκανα ένα mobile-first website για να μπορούσα να τις αξιολογήσω στο κινητό μου και στο tablet μου, όπου κι αν είμαι.

Φτιάξε το δικό σου δωρεάν:

Θυμήσου ότι ξεπέρασα τα όρια και είχα κάρτες που κάλυπταν τα πάντα, από assembly και Python trivia έως και μηχανική μάθηση και στατιστική. Ήταν κάπως υπερβολικό από αυτό που χρειαζόταν.

Σημείωσε στα flashcards: Τον πρώτο καιρό θα αναγνωρίζεις ότι γνωρίζεις την απάντηση, μην την μαρκάρεις ως γνωστή. Έχεις να δεις την ίδια κάρτα και να την απαντήσεις αρκετές φορές σωστά πριν την κατανοήσεις πλήρως. Η επανάληψις είναι μήτηρ πάσης μαθήσεως!-Πλάτωνας.

Η εναλλακτική είναι να χρησιμοποιήσεις το δικό μου flashcard site: Anki, το οποίο έχει προταθεί σε εμένα αρκετές φορές. Χρησιμοποιεί ένα επαναληπτικό σύστημα για να σε βοηθήσει να θυμηθείς. Είναι φιλικό προς τον χρήστη, διαθέσιμο σε όλες τις πλατφόρμες και διαθέτει συγχρονισμό με το cloud. Κοστίζει 25$ για iOS αλλά είναι δωρεάν στις άλλες πλατφόρμες.

Η flashcard βάση δεδομένων μου σε φορμάτ Anki: https://ankiweb.net/shared/info/25173560 (thanks @xiewenya)

3. Αναθεώρησε, αναθεώρησε, αναθεώρησε

Διατηρώ το σετ μου απο σκονάκια σε ASCII, στοίβα OSI, σχηματισμούς Big-O, και άλλα. Τα μελετώ όταν έχω λίγο χρόνο.

Κάνε ένα διάλειμμα από τα προβλήματα προγραμματισμού για μισή ώρα και δούλεψε με τα flashcards.

4. Συγκεντρώσου

Υπάρχουν πολλοί αντιπερισπασμοί που μπορούν να κοστίσουν πολύτιμο χρόνο. Η συγκέντρωση είναι ένα αρκετά δύσκολο κομμάτι.

Τι δε θα δεις να καλύπτετε

Υπάρχουν επικρατέστερες τεχνολογίες αλλά δεν είναι κομμάτι αυτού του πλάνου διαβάσματος:

  • SQL
  • Javascript
  • HTML, CSS, και άλλες front-end τεχνολογίες

Το καθημερινό πλάνο

Μερικά θέματα παίρνουν μία ολόκληρη μέρα, και μερικά θα κοστίσουν μερικές μέρες. Μερικά είναι μόνο γνώση χωρίς να χρειαστεί να υλοποιήσεις οτιδήποτε.

Κάθε μέρα παίρνω ένα θέμα από την παρακάτω λίστα, βλέπω βίντεο για το συγκεκριμένο θέμα, και γρράφω μία υλοποίηση σε:

  • C - χρησιμοποιώντας structs και functions που παίρνουν struct * και κάτι άλλο σαν ορίσματα.
  • C++ - χωρίς να χρησιμοποιώ built-in τύπους
  • C++ - χρησιμοποιώντας built-in τύπους, όπως τα std::list της STL για μία συνδεδεμένη λίστα
  • Python - χρησιμοποιώντας built-in τύπους (για να εξασκούμε στην Python)
  • και γράφω tests για να σιγουρευτώ ότι το κάνω καλά, μερικές φορές χρησιμοποιώντας μόνο assert() δηλώσεις
  • Μπορεί να κάνεις Java ή κάτι άλλο, αυτό είναι μόνο αυτό που κάνω.

Δεν χρειάζεσαι όλα αυτά. Χρειάζεσαι μόνο μία γλώσσα για τη συνέντευξη.

Γιατί γράφω κώδικα σε όλα αυτά;

  • Εξάσκηση, εξάσκηση, εξάσκηση, μέχρι να γίνω άρρωστος από αυτό, και να μπορώ να το κάνω χωρίς κανένα πρόβλημα (μερικά έχουν πολλές ακραίες περιπτώσεις και και τήρηση των λεπτομερειών του βιβλίου να θυμηθείς)
  • Δουλέυω με τα εμπόδια (allocating/freeing memory χωρίς την βοήθεια του garbage collection (εκτός της Python))
  • Κάνω χρήση των built-in τύπων έτσι έχω λίγη εμπειρία στη χρήση built-in εργαλείων για χρήση στον πραγματικό κόσμο (δεν πάω να γράψω τη δικιά μου υλοποίηση για τη συνδεδεμένη λίστα στην παραγωγή)

Μπορεί να μην έχω χρόνο να τα κάνω αυτά για όλα τα θέματα, αλλά θα προσπαθήσω.

Μπορείς να δεις τον κώδικα μου εδώ:

Δε χρειάζεται να απομνημονεύσεις κάθε κομμάτι ενός αλγόριθμου.

Γράψε κώδικα σε ένα πίνακα ή σε ένα χαρτί, όχι σε υπολογιστή. Τέσταρε τον με μερικές απλές εισόδους. Μετά τέσταρε τον και σε έναν υπολογιστή.

Προαπαιτούμενη γνώση

Αλγοριθμική πολυπλοκότητα / Big-O / Ασυμπτωτική ανάλυση

Δομές Δεδομένων

  • Πίνακες

    • Υλοποίησε μία λίστα, η οποία αλλάζει αυτόματα μέγεθος.
    • Περιγραφή:
    • Υλοποίησε μία συλλογή (ευμετάβλητο πίνακα με αυτόματη αλλαγή μεγέθους):
      • Κάνε πρακτική σε κώδικα χρησιμοποιώντας πίνακες και δείκτες, και pointer math για να πας σε ένα δείκτη από το να χρησιμοποιήσεις ευρετηρίαση.
      • new raw data array with allocated memory
        • can allocate int array under the hood, just not use its features
        • start with 16, or if starting number is greater, use power of 2 - 16, 32, 64, 128
      • size() - αριθμός των στοιχείων
      • capacity() - αριθμός στοιχείων που μπορεί να περιέχει
      • is_empty()
      • at(index) - επιστρέφει που υπάρχει στη θέση index, εκρύγνειται αν ο δείκτης είναι εκτός συνόρων του πίνακα
      • push(item)
      • insert(index, item) - εισάγει ένα σημείο στη θέση index, μετακινεί την τιμή του index και σύρει όλα τα στοιχεία στα δεξιά
      • prepend(item) - εισάγει το αντικείμενο στην αρχή της συλλογής(insert(0,item))
      • pop() - αφαιρεί από το τέλος, επιστρέφει την τιμή
      • delete(index) - διγράφη το στοιχείο στη θέση index, σύρει όλα τα στοιχεία στα αριστερά
      • remove(item) - ψάχνει για την τιμή και διαγράφει το δείκτη που την έχει (ακόμα και αν είναι σε περισσότερες από 1 θέσεις)
      • find(item) - ψάχνει για την τιμή και επιστρέφει τον πρώτο δείκτη με αυτή την τιμή, -1 έαν δε βρεθεί
      • resize(new_capacity) // private function
        • όταν φτάνεις στη χωρητικώτητα, άλλαξε το μέγεθος του πίνακα κατά το διπλάσιο
        • όταν αφαιρείς ένα στοιχείο, εάν το μέγεθος είναι 1/4 της χωρητικότητας, άλλαξε το μέγεθος κατά το μισό
    • Χρόνος
      • O(1) για πρόσθεση/αφαίρεση στο τέλος (απελευθέρωση των δεσμευμένων θέσεων για περισσότερο χώρο)
      • O(n) για πρόσθεση/αφαίρεση αλλού
    • Χώρος
      • συνεχόμενος στη μνήμη, έτσι η μικρή απόσταση βοηθάει στην απόδοση
      • απαιτούμενος χώρος = (χωρητικότητα πίνακα, η οποία είναι >= n) * μέγεθος του στοιχείου, αλλά ακόμα και αν είναι 2n => O(n)

  • Συνδεδεμένες λίστες

    untill here

      - [ ] size() - returns number of data elements in list
  - [ ] empty() - bool returns true if empty
  - [ ] value_at(index) - returns the value of the nth item (starting at 0 for first)
  - [ ] push_front(value) - adds an item to the front of the list
  - [ ] pop_front() - remove front item and return its value
  - [ ] push_back(value) - adds an item at the end
  - [ ] pop_back() - removes end item and returns its value
  - [ ] front() - get value of front item
  - [ ] back() - get value of end item
  - [ ] insert(index, value) - insert value at index, so current item at that index is pointed to by new item at index
  - [ ] erase(index) - removes node at given index
  - [ ] value_n_from_end(n) - returns the value of the node at nth position from the end of the list
  - [ ] reverse() - reverses the list
  - [ ] remove_value(value) - removes the first item in the list with this value

  • Stack

  • Queue

    • Using Queues First-In First-Out(video)
    • Queue (video)
    • Circular buffer/FIFO
    • Priority Queues (video)
    • [Review] Queues in 3 minutes (video)
    • Implement using linked-list, with tail pointer:
      • enqueue(value) - adds value at position at tail
      • dequeue() - returns value and removes least recently added element (front)
      • empty()
    • Implement using fixed-sized array:
      • enqueue(value) - adds item at end of available storage
      • dequeue() - returns value and removes least recently added element
      • empty()
      • full()
    • Cost:
      • a bad implementation using linked list where you enqueue at head and dequeue at tail would be O(n) because you'd need the next to last element, causing a full traversal each dequeue
      • enqueue: O(1) (amortized, linked list and array [probing])
      • dequeue: O(1) (linked list and array)
      • empty: O(1) (linked list and array)

  • Hash table

More Knowledge

Trees