[Powered by Google Translate] [Σεμινάριο: Τεχνικές Συνεντεύξεις]
[Kenny Yu, Πανεπιστήμιο Χάρβαρντ]
[Αυτό είναι CS50.] [CS50.TV]
Γεια σε όλους, είμαι Kenny. Είμαι σήμερα ένας κατώτερος επιστήμη μελετά τον υπολογιστή.
Είμαι ένας πρώην CS TF, και εύχομαι να είχα αυτό όταν ήμουν underclassman,
και γι 'αυτό δίνω αυτό το σεμινάριο.
Έτσι, ελπίζω να το απολαύσετε.
Αυτό το σεμινάριο είναι σχετικά με τις τεχνικές συνεντεύξεων,
και όλους τους πόρους μου, μπορείτε να βρείτε σε αυτό το σύνδεσμο,
αυτό το σύνδεσμο εδώ, ένα ζευγάρι των πόρων.
Έτσι, έκανα μια λίστα με τα προβλήματα, στην πραγματικότητα, αρκετά προβλήματα.
Επίσης, μια γενική σελίδα πόρους όπου μπορούμε να βρούμε άκρες
σχετικά με το πώς να προετοιμαστούν για μια συνέντευξη,
συμβουλές για το τι πρέπει να κάνετε κατά τη διάρκεια μιας πραγματικής συνέντευξης,
καθώς και το πώς να προσεγγίσουν τα προβλήματα και τους πόρους για μελλοντική αναφορά.
Είναι όλα σε απευθείας σύνδεση.
Και ακριβώς για να πρόλογο αυτό το σεμινάριο, παραίτηση από κάθε ευθύνη,
όπως αυτό δεν θα πρέπει - προετοιμασία για την συνέντευξη σας
δεν πρέπει να περιορίζεται σε αυτόν τον κατάλογο.
Αυτό είναι μόνο για να είναι ένας οδηγός,
και θα πρέπει να πάρετε σίγουρα ό, τι λέω με ένα σπυρί αλατιού,
αλλά επίσης να χρησιμοποιήσετε ό, τι χρησιμοποιείται για να σας βοηθήσει στην προετοιμασία για την συνέντευξη σας.
>> Πάω να επιταχύνει μέσα στις επόμενες διαφάνειες
έτσι μπορούμε να πάρουμε με τις πραγματικές μελέτες περιπτώσεων.
Η δομή μιας συνέντευξης για postion τεχνολογία λογισμικού,
τυπικά είναι 30 έως 45 λεπτά,
πολλαπλούς γύρους, ανάλογα με την εταιρεία.
Συχνά θα σας κωδικοποίησης σε ένα λευκό του σκάφους.
Έτσι, ένα λευκό του σκάφους, όπως αυτό, αλλά συχνά σε μικρότερη κλίμακα.
Αν έχετε μια τηλεφωνική συνέντευξη, θα πρέπει πιθανώς να χρησιμοποιούν
είτε collabedit ή ένα Google Doc, έτσι ώστε να μπορούν να δουν ζείτε κωδικοποίησης
ενώ είστε σε συνέντευξη από το τηλέφωνο.
Μια συνέντευξη ίδια είναι συνήθως 2 ή 3 προβλήματα
τον έλεγχο του υπολογιστή σας τις γνώσεις της επιστήμης.
Και αυτό θα είναι σχεδόν σίγουρα απαιτεί την κωδικοποίηση.
Τα είδη των ερωτήσεων που θα δείτε είναι συνήθως δομών δεδομένων και αλγορίθμων.
Και σε κάνει αυτά τα είδη των προβλημάτων,
θα σας ζητήσω, όπως, τι είναι ο χρόνος και η πολυπλοκότητα χώρου, μεγάλη O;
Συχνά ζητούν επίσης υψηλότερου επιπέδου ερωτήματα,
έτσι, το σχεδιασμό ενός συστήματος,
πώς θα απλώστε τον κωδικό σας;
Τι διασυνδέσεις, τι τάξεις, τι ενότητες έχετε στο σύστημά σας,
και πώς αυτές αλληλεπιδρούν μεταξύ τους;
Έτσι, δομές δεδομένων και αλγορίθμων, καθώς και το σχεδιασμό συστημάτων.
>> Μερικές γενικές συμβουλές πριν βουτήξει για να περιπτωσιολογικές μελέτες μας.
Νομίζω ότι ο πιο σημαντικός κανόνας είναι πάντα να σκέφτεται φωναχτά.
Η συνέντευξη υποτίθεται ότι είναι η ευκαιρία σας για να αναδείξουν τη διαδικασία σκέψης σας.
Το σημείο της συνέντευξης είναι ο ερευνητής να μετρήσει
πώς σκέφτονται και πώς θα περάσει μέσα από ένα πρόβλημα.
Το χειρότερο πράγμα που μπορείτε να κάνετε είναι να είναι σιωπηλός καθ 'όλη τη συνέντευξη.
Αυτό είναι απλά δεν είναι καλό.
Όταν δίνεται μια ερώτηση, μπορείτε επίσης να θέλετε να βεβαιωθείτε ότι έχετε κατανοήσει το θέμα.
Έτσι, επαναλαμβάνω την ερώτηση πίσω με δικά σας λόγια
και προσπαθούν να εργαστούν σε βάθος μερικές απλές περιπτώσεις δοκιμής
για να βεβαιωθείτε ότι έχετε κατανοήσει το θέμα.
Εργασίας μέσα σε λίγες περιπτώσεις δοκιμή θα σας δώσει επίσης μια διαίσθηση για το πώς να λύσουμε αυτό το πρόβλημα.
Ίσως ακόμη και να ανακαλύψετε μερικά σχέδια για να σας βοηθήσει να λύσετε το πρόβλημα.
Μεγάλη μύτη τους είναι να μην απογοητευτείτε.
Μην απογοητευτείτε.
Συνεντεύξεις είναι δύσκολο, αλλά το χειρότερο πράγμα που μπορείτε να κάνετε,
εκτός του ότι είναι σιωπηλή, είναι εμφανώς να ανατραπεί.
Δεν θέλουμε να δώσουμε την εντύπωση σε μια συνέντευξη.
Ένα πράγμα που - έτσι, πολλοί άνθρωποι, όταν πηγαίνουν σε μια συνέντευξη,
προσπαθούν να προσπαθήσουμε να βρούμε την καλύτερη λύση κατ 'αρχάς,
όταν πραγματικά, υπάρχει συνήθως μια λύση ολοφάνερες.
Θα μπορούσε να είναι αργή, θα μπορούσε να είναι αναποτελεσματική, αλλά θα πρέπει να αναφέρει ακριβώς,
ακριβώς έτσι ώστε να έχετε ένα σημείο εκκίνησης από το οποίο να λειτουργεί καλύτερα.
Επίσης, επισημαίνοντας το διάλυμα είναι αργή, από την άποψη της
μεγάλη χρονική πολυπλοκότητα O ή την πολυπλοκότητα χώρου,
θα αποδείξει στην συνέντευξη ότι καταλαβαίνετε
αυτά τα ζητήματα κατά τη σύνταξη κώδικα.
Γι 'αυτό μην φοβάστε να καταλήξει με τον απλούστερο αλγόριθμο πρώτη
και στη συνέχεια να λειτουργήσει καλύτερα από εκεί.
Οποιεσδήποτε ερωτήσεις μέχρι τώρα; Εντάξει.
>> Έτσι, ας βουτήξει πρώτο πρόβλημα μας.
"Λαμβάνοντας υπόψη μια σειρά από n ακέραιους αριθμούς, γράφοντας μια λειτουργία που ανακατεύει τη σειρά
σε θέση τέτοια ώστε όλες οι παραλλαγές των ακεραίων η είναι εξίσου πιθανό. "
Και υποθέσουμε ότι έχετε διαθέσιμη μια γεννήτρια τυχαίων ακέραιο
που δημιουργεί έναν ακέραιο σε μια περιοχή από 0 έως i, ένα δεύτερο εύρος.
Μήπως όλοι κατανοούν αυτή την ερώτηση;
Σας δίνω μια σειρά από n ακέραιους αριθμούς, και θέλω να το ανακατέψετε.
Στον κατάλογο μου, έγραψα μερικά προγράμματα για να αποδείξουν τι εννοώ.
Πάω να ανακατέψετε μια σειρά από 20 στοιχεία,
-10 έως 9,
και θέλω να εξαγάγετε μια λίστα σαν αυτή.
Έτσι, αυτό είναι ταξινομημένο πίνακα εισόδου μου, και θέλω να το ανακατέψετε.
Θα το κάνουμε και πάλι.
Μήπως όλοι καταλαβαίνουν την ερώτηση; Εντάξει.
Έτσι είναι στο χέρι σας.
Ποιες είναι μερικές ιδέες; Μπορείτε να το κάνετε ως n ^ 2, n log n, n;
Ανοικτό σε προτάσεις.
Εντάξει. Έτσι, μια ιδέα, που προτείνεται από Emmy,
είναι το πρώτο υπολογίσουμε ένα τυχαίο αριθμό, τυχαίο ακέραιο αριθμό, σε μία περιοχή από 0 έως 20.
Έτσι αναλάβει σειρά μας έχει μήκος 20.
Στο διάγραμμα μας από 20 στοιχεία,
αυτό είναι σειρά εισόδου μας.
Και τώρα, η πρότασή της είναι να δημιουργήσει μια νέα σειρά,
έτσι ώστε αυτή θα είναι η συστοιχία εξόδου.
Και με βάση το i επέστρεψε από ραντ -
οπότε αν ήμουν, ας πούμε, 17,
αντιγραφή του στοιχείου 17α στην πρώτη θέση.
Τώρα πρέπει να διαγράψετε - θα πρέπει να στραφούν όλα τα στοιχεία εδώ
πάνω έτσι ώστε να έχουμε ένα διάκενο στο τέλος και χωρίς τρύπες στη μέση.
Και τώρα μπορούμε να επαναλάβετε τη διαδικασία.
Τώρα έχουμε πάρει ένα νέο τυχαίο ακέραιο μεταξύ 0 και 19.
Έχουμε ένα νέο i εδώ, και εμείς αντιγράψετε αυτό το στοιχείο σε αυτή τη θέση.
Στη συνέχεια, τα στοιχεία στροφή πάνω και επαναλαμβάνουμε τη διαδικασία μέχρι να έχουμε πλήρη νέα σειρά μας.
Ποιος είναι ο χρόνος εκτέλεσης του αλγορίθμου;
Λοιπόν, ας εξετάσει τον αντίκτυπο αυτής.
Είμαστε μετατόπιση κάθε στοιχείο.
Όταν αφαιρούμε ί αυτό, είμαστε μετατόπιση όλα τα στοιχεία, μετά την προς τα αριστερά.
Και αυτό είναι ένα O (n) κόστος
γιατί ό, τι αν αφαιρέσετε το πρώτο στοιχείο;
Έτσι, για κάθε αφαίρεση, αφαιρούμε -
κάθε αφαίρεση πραγματοποιεί ένα O (n) λειτουργία,
και από τότε έχουμε n μετακομίσεις, αυτό οδηγεί σε O (n ^ 2) shuffle.
Εντάξει. Έτσι, καλή αρχή. Καλή αρχή.
>> Μια άλλη πρόταση είναι να χρησιμοποιήσετε κάτι που είναι γνωστό ως το shuffle Knuth,
ή το Fisher-Yates shuffle.
Και αυτό είναι στην πραγματικότητα μια γραμμική μετάθεση του χρόνου.
Και η ιδέα είναι πολύ παρόμοια.
Και πάλι, έχουμε σειρά εισόδου μας,
αλλά αντί να χρησιμοποιεί δύο συστοιχίες για είσοδο / έξοδο μας,
χρησιμοποιούμε το πρώτο μέρος του πίνακα για να παρακολουθείτε ανακατεύονται τμήμα μας,
και να παρακολουθείτε, και στη συνέχεια αφήνουμε το υπόλοιπο της σειράς μας για την unshuffled τμήμα.
Έτσι, εδώ είναι ό, τι θέλω να πω. Ξεκινάμε με - επιλέγουμε ένα i,
μία συστοιχία 0-20.
Τρέχουσα δείκτης μας δείχνει με την πρώτη δείκτη.
Επιλέγουμε κάποια i εδώ
και τώρα έχουμε ανταλλάξει.
Έτσι, αν αυτό ήταν 5 και αυτή ήταν 4,
η προκύπτουσα σειρά θα έχουν 5 εδώ και 4 εδώ.
Και τώρα παρατηρούμε εδώ ένα δείκτη.
Τα πάντα για την αριστερά είναι ανακατεύονται,
και τα πάντα προς τα δεξιά είναι unshuffled.
Και τώρα μπορούμε να επαναλάβετε τη διαδικασία.
Επιλέγουμε ένα τυχαίο δείκτη μεταξύ 1 και 20 τώρα.
Έτσι, ας υποθέσουμε νέα μας i είναι εδώ.
Τώρα έχουμε ανταλλάξει αυτό το i με την τρέχουσα νέα θέση μας εδώ.
Γι 'αυτό και μια εναλλαγή πέρα ​​δώθε σαν αυτό.
Επιτρέψτε μου να φέρει το κωδικό για να γίνουν πιο συγκεκριμένες.
Ξεκινάμε με την επιλογή μας για i -
αρχίσουμε με το i ισούται με 0, έχουμε πάρει μια τυχαία τοποθεσία j
στην unshuffled τμήματος της συστοιχίας, i έως n-1.
Έτσι, αν είμαι εδώ, να επιλέξουν ένα τυχαίο δείκτη μεταξύ εδώ και το υπόλοιπο του πίνακα,
και έχουμε ανταλλάξει.
Αυτό είναι όλος ο κώδικας για να ανακατέψετε σειρά σας.
Οποιεσδήποτε ερωτήσεις;
>> Λοιπόν, το ένα έπρεπε ερώτημα είναι, γιατί είναι αυτό σωστό;
Γιατί είναι κάθε μετάθεση εξίσου πιθανό;
Και δεν θα περάσουν από την απόδειξη γι 'αυτό,
αλλά πολλά προβλήματα στην επιστήμη των υπολογιστών μπορεί να αποδειχθεί μέσω της επαγωγής.
Πόσοι από εσάς είναι εξοικειωμένοι με επαγωγή;
Εντάξει. Cool.
Έτσι, μπορείτε να αποδείξει την ορθότητα αυτού του αλγορίθμου με απλή επαγωγή,
όπου επαγωγική υπόθεση σας θα είναι, ας υποθέσουμε ότι
Shuffle μου επιστρέφει κάθε μετάθεση εξίσου πιθανό
μέχρι τα πρώτα στοιχεία i.
Τώρα, θεωρούν i + 1.
Και από τον τρόπο που έχουμε επιλέξει j δείκτη μας για να ανταλλάξουν,
αυτό οδηγεί σε - και στη συνέχεια να επεξεργαστεί τις λεπτομέρειες,
τουλάχιστον μία πλήρη απόδειξη του γιατί αυτός ο αλγόριθμος επιστρέφει
κάθε μετάθεση με εξίσου πιθανό πιθανότητα.
>> Εντάξει, το επόμενο πρόβλημα.
Έτσι, "δίνεται μια σειρά από ακέραιους αριθμούς, postive, μηδέν, αρνητικός,
γράψει μια λειτουργία που υπολογίζει το μέγιστο ποσό
οποιασδήποτε continueous subarray της διάταξης εισαγωγής. "
Ένα παράδειγμα εδώ είναι, στην περίπτωση όπου όλοι οι αριθμοί είναι θετικοί,
τότε το παρόν η καλύτερη επιλογή είναι να πάρετε το σύνολο της διάταξης.
1, 2, 3, 4, 10 ισούται.
Όταν έχετε κάποια αρνητικά εκεί,
σε αυτή την περίπτωση θέλουμε μόνο τις δύο πρώτες
επειδή την επιλογή -1 και / ή -3 θα φέρει άθροισμα μας κάτω.
Μερικές φορές μπορεί να χρειαστεί να ξεκινήσει στη μέση του πίνακα.
Μερικές φορές θέλουμε να επιλέξετε τίποτα? Είναι καλύτερο να μην πάρει τίποτα.
Και μερικές φορές είναι καλύτερα να λάβει η πτώση,
επειδή το πράγμα, αφού είναι εξαιρετικά μεγάλο. Έτσι, οποιεσδήποτε ιδέες;
(Φοιτητής, ακατάληπτο) >> Ναι.
Ας υποθέσουμε ότι εγώ δεν λαμβάνουν -1.
Στη συνέχεια, είτε θα επιλέξουν 1.000 και 20.000,
ή μπορώ να επιλέξω μόνο τα 3 δισ. ευρώ.
Λοιπόν, η καλύτερη επιλογή είναι να λάβει όλα τα νούμερα.
Αυτό -1, παρά το γεγονός ότι αρνητικά,
ολόκληρο το ποσό είναι καλύτερη από ό, τι ήταν Ι να μην λάβει -1.
Έτσι, μία από τις συμβουλές που ανέφερα προηγουμένως ήταν να αναφέρει σαφώς το προφανές
και η ωμή δύναμη λύση πρώτα.
Ποια είναι η ωμή δύναμη λύση σε αυτό το πρόβλημα; Ναι;
[Jane] Λοιπόν, νομίζω ότι η ωμή βία λύση
θα ήταν να προσθέσουμε όλους τους δυνατούς συνδυασμούς (ακατάληπτο).
[Yu] Εντάξει. Έτσι, η ιδέα της Jane είναι να λάβει κάθε δυνατό -
Είμαι παραφράζοντας - είναι να αναλάβουν κάθε δυνατή συνεχή subarray,
υπολογίζει άθροισμα του, και στη συνέχεια να λάβει το μέγιστο από όλες τις πιθανές συνεχή subarrays.
Τι προσδιορίζει μοναδικά μια σειρά subarray στην είσοδο μου;
Όπως, τι δύο πράγματα πρέπει να κάνω; Ναι;
(Φοιτητής, ακατάληπτο) >> Δεξιά.
Ένα κατώτερο όριο για το δείκτη και ένα άνω όριο δείκτη
μοναδικά προσδιορίζει μια συνεχή subarray.
[Γυναίκα φοιτητής] Είμαστε εκτίμηση είναι μια σειρά από μοναδικούς αριθμούς;
[Yu] Όχι λοιπόν ερώτησή της, είμαστε υποθέτοντας σειρά μας -
είναι η σειρά μας όλα μοναδικούς αριθμούς, και η απάντηση είναι όχι.
>> Αν χρησιμοποιήσουμε ωμή δύναμη μας λύση, τότε οι έναρξης / λήξης δείκτες
μοναδικά καθορίζει συνεχές subarray μας.
Έτσι, αν έχουμε επαναλάβει για όλες τις πιθανές εγγραφές εκκίνησης,
και για όλες τις καταχωρήσεις τέλος> ή = για να ξεκινήσει, και <n,
θα υπολογίσετε το άθροισμα και στη συνέχεια παίρνουμε το μέγιστο ποσό που έχουμε δει μέχρι τώρα.
Είναι σαφές αυτό;
Ποια είναι η μεγάλη O αυτής της λύσης;
Χρονικά την περίοδο.
Δεν n αρκετά ^ 2.
Σημειώστε ότι έχουμε επαναλάβει από 0 έως n,
έτσι ώστε να είναι ένα για βρόχο.
Έχουμε επαναλάβει ξανά από σχεδόν την αρχή μέχρι το τέλος, για μια άλλη θηλιά.
Και τώρα, στο πλαίσιο αυτό, θα πρέπει να συνοψίσουμε σε κάθε είσοδο,
έτσι αυτό είναι ένα άλλο για βρόχο. Έτσι έχουμε τρεις ένθετα για βρόχους, n ^ 3.
Εντάξει. Αυτό πηγαίνει ως σημείο εκκίνησης.
Η λύση μας δεν είναι χειρότερη από ό, τι ν ^ 3.
Μήπως όλοι κατανοούν την ωμή δύναμη λύση;
>> Εντάξει. Μια καλύτερη λύση είναι η χρήση μια ιδέα που ονομάζεται δυναμικός προγραμματισμός.
Εάν πάρετε CS124, που είναι Αλγόριθμοι και Δομές Δεδομένων,
θα γίνει πολύ εξοικειωμένοι με αυτήν την τεχνική.
Και η ιδέα είναι, να προσπαθήσουμε να δημιουργήσουν λύσεις σε μικρότερα προβλήματα πρώτα.
Τι εννοώ με αυτό είναι, αυτή τη στιγμή χρειάζεται να ανησυχείτε για δύο πράγματα: αρχή και τέλος.
Και αυτό είναι ενοχλητικό. Τι θα συμβεί αν θα μπορούσαμε να απαλλαγούμε από μία από αυτές τις παραμέτρους;
Μια ιδέα είναι να - we're δοθεί αρχικό μας πρόβλημα,
βρει το μέγιστο άθροισμα οποιασδήποτε subarray σε μία περιοχή [O, n-1].
Και τώρα έχουμε ένα νέο υποπρόβλημα, όπου γνωρίζουμε ότι, στη σημερινή μας δείκτη i,
ξέρουμε ότι πρέπει να ολοκληρώσω εκεί. Subarray μας πρέπει να σταματήσει στην τρέχουσα δείκτη.
Έτσι, το υπόλοιπο είναι πρόβλημα, όπου θα πρέπει να αρχίσουμε subarray μας;
Μήπως αυτό έχει νόημα; Εντάξει.
Έτσι έχω κωδικοποιημένες αυτό επάνω, και ας δούμε τι σημαίνει αυτό.
Στο codirectory, υπάρχει ένα πρόγραμμα που ονομάζεται subarray,
και παίρνει τον αριθμό των τεμαχίων,
και επιστρέφει το μέγιστο ποσό subarray ανακατεύονται στην λίστα μου.
Έτσι σε αυτή την περίπτωση, η μέγιστη subarray μας είναι 3.
Και αυτό είναι που λαμβάνονται από απλά χρησιμοποιώντας 2 και 1.
Ας τρέξει ξανά. Είναι επίσης 3.
Αλλά αυτή τη φορά, σημειώστε πως πήραμε την 3.
Πήραμε το - εμείς απλά να πάρουν το ίδιο το 3
επειδή είναι περιτριγυρισμένο από τα αρνητικά και από τις δύο πλευρές,
το οποίο θα φέρει ένα ποσό <3.
Ας τρέξει σε 10 αντικείμενα.
Αυτή τη φορά είναι 7, παίρνουμε την ηγετική 3 και 4.
Αυτή τη φορά είναι 8, και παίρνουμε ότι με τη λήψη 1, 4 και 3.
Έτσι για να σας δώσει μια διαίσθηση για το πώς μπορούμε να λύσουμε αυτό το πρόβλημα μετατρέπεται,
ας ρίξουμε μια ματιά σε αυτό το subarray.
Είμαστε δοθεί αυτή η σειρά εισόδου, και γνωρίζουμε ότι η απάντηση είναι 8.
Παίρνουμε το 1, 4, και 3.
Αλλά ας δούμε πώς φτάσαμε στην πραγματικότητα την απάντηση.
Ας δούμε την μέγιστη subarray που έληξε σε κάθε ένα από αυτούς τους δείκτες.
Ποια είναι η μέγιστη subarray που πρέπει να καταλήξει στην πρώτη θέση;
[Φοιτητικό] Zero. >> Zero. Απλά δεν λαμβάνουν το -5.
Εδώ πρόκειται να είναι 0, καθώς και. Ναι;
(Φοιτητής, ακατάληπτο)
[Yu] Ω, συγγνώμη, αυτό είναι ένα -3.
Έτσι, αυτό είναι ένα 2, αυτό είναι ένα -3.
Εντάξει. Έτσι, -4, ποια είναι η μέγιστη subarray να τερματίσει αυτή τη θέση
όπου στο -4 είναι; Μηδέν.
Ένα; 1, 5, 8.
Τώρα, πρέπει να σταματήσει στο σημείο όπου είναι -2.
Έτσι 6, 5, 7, και η τελευταία είναι 4.
Γνωρίζοντας ότι αυτά είναι καταχωρήσεις μου
για το μετασχηματισμένο πρόβλημα όπου πρέπει να σταματήσει σε κάθε ένα από αυτούς τους δείκτες,
τότε τελική απάντηση μου είναι απλά, να λάβει ένα σκούπισμα όλη,
και να πάρει το μέγιστο αριθμό.
Έτσι, σε αυτή την περίπτωση είναι 8.
Αυτό σημαίνει ότι η μέγιστη subarray καταλήγει σε αυτό το δείκτη,
και ξεκίνησε κάπου πριν.
Μήπως όλοι καταλαβαίνουν αυτό μετατρέπεται subarray;
>> Εντάξει. Λοιπόν, ας καταλάβουμε την επανάληψη για αυτό.
Ας εξετάσουμε μόνο τις πρώτες εγγραφές.
Έτσι, εδώ ήταν 0, 0, 0, 1, 5, 8.
Και τότε υπήρχε μια -2 εδώ, και αυτό έφερε σε 6.
Έτσι, αν Καλώ την είσοδο στη θέση i υποπρόβλημα (i),
πώς μπορώ να χρησιμοποιήσω την απάντηση σε προηγούμενη υποπρόβλημα
να απαντήσει σε αυτό το υποπρόβλημα;
Αν δούμε, ας πούμε, η καταχώρηση αυτή.
Πώς μπορώ να υπολογίσει την απάντηση 6 κοιτάζοντας
ένας συνδυασμός αυτού του πίνακα και τις απαντήσεις στα προηγούμενα υποπροβλήματα σε αυτόν τον πίνακα; Ναι;
[Γυναίκα φοιτητής] Παίρνετε τον πίνακα των ποσών που
στην θέση αμέσως πριν, επομένως ο 8,
και στη συνέχεια, μπορείτε να προσθέσετε την τρέχουσα υποπρόβλημα.
[Yu] Έτσι η πρότασή της είναι να εξετάσουμε αυτά τα δύο αριθμούς,
αυτός ο αριθμός και ο αριθμός αυτός.
Έτσι, αυτό το 8 αναφέρεται στην απάντηση για το υποπρόβλημα (i - 1).
Και ας την ονομάσουμε εισόδου Α. σειρά μου
Για να βρείτε μια μέγιστη subarray που καταλήγει στη θέση i,
Έχω δύο επιλογές: μπορώ να συνεχίσω είτε το subarray
που έληξε την προηγούμενη δείκτη, ή να ξεκινήσετε μια νέα σειρά.
Εάν επρόκειτο να συνεχίσει την subarray που ξεκίνησε στο προηγούμενο δείκτη,
τότε το μέγιστο ποσό που μπορεί να επιτύχει είναι η απάντηση στο προηγούμενο υποπρόβλημα
καθώς και η τρέχουσα καταχώρηση πίνακα.
Αλλά, έχω επίσης την επιλογή της έναρξης μιας νέας subarray,
στην οποία περίπτωση το άθροισμα είναι 0.
Έτσι, η απάντηση είναι max 0, υποπρόβλημα i - 1, καθώς και η τρέχουσα καταχώρηση πίνακα.
Μήπως αυτή η επανάληψη νόημα;
Επανάληψης μας, όπως εμείς μόλις ανακαλύψαμε, είναι υποπρόβλημα i
είναι ίσο με το ανώτατο όριο του προηγούμενου υποπρόβλημα συν τρέχουσα καταχώρηση σειρά μου,
πράγμα που σημαίνει συνέχιση της προηγούμενης subarray,
ή 0, ξεκινήστε μια νέα subarray στο σημερινό δείκτη μου.
Και από τη στιγμή που έχουμε δημιουργήσει αυτό το τραπέζι των λύσεων, τότε η τελική μας απάντηση,
απλά κάνει μια γραμμική σάρωση σε όλη την σειρά υποπρόβλημα
και να πάρει το μέγιστο αριθμό.
Αυτή είναι μια ακριβής εφαρμογή των όσων μόλις είπα.
Έτσι δημιουργούμε μια νέα σειρά υποπρόβλημα, υποπροβλήματα.
Η πρώτη καταχώρηση είναι είτε 0 ή η πρώτη θέση, το μέγιστο των δύο αυτών.
Και για το υπόλοιπο των υποπροβλήματα
χρησιμοποιούμε την ακριβή επανάληψη που μόλις ανακαλύφθηκαν.
Τώρα έχουμε υπολογίσει το μέγιστο των υποπροβλήματα σειρά μας, και αυτό είναι η τελική μας απάντηση.
>> Έτσι, πόσο χώρο είμαστε χρησιμοποιώντας σε αυτόν τον αλγόριθμο;
Εάν έχετε λάβει μόνο CS50, τότε ίσως να μην έχουν συζητηθεί πάρα πολύ χώρο.
Λοιπόν, ένα πράγμα που πρέπει να σημειωθεί είναι ότι κάλεσα εδώ malloc με μέγεθος n.
Τι σημαίνει ότι προτείνουμε για εσάς;
Αυτός ο αλγόριθμος χρησιμοποιεί γραμμικό χώρο.
Μπορούμε να το κάνουμε καλύτερα;
Υπάρχει κάτι που θα παρατηρήσετε ότι είναι περιττό να υπολογιστεί η τελική απάντηση;
Υποθέτω ότι μια καλύτερη ερώτηση είναι, τι είδους πληροφορίες
δεν πρέπει να μεταφέρουν σε όλη τη διαδρομή μέχρι το τέλος;
Τώρα, αν κοιτάξουμε αυτές τις δύο γραμμές,
εμείς μόνο νοιάζονται για την προηγούμενη υποπρόβλημα,
και μόνο νοιάζονται για το μέγιστο που έχουμε δει ποτέ μέχρι τώρα.
Για τον υπολογισμό τελική απάντηση μας, δεν χρειαζόμαστε το σύνολο του πίνακα.
Το μόνο που χρειάζεται τον τελευταίο αριθμό, δύο τελευταίοι αριθμοί.
Τελευταία αριθμός για το υποπρόβλημα σειρά, και τελευταίο αριθμό για το μέγιστο.
Έτσι, στην πραγματικότητα, μπορούμε να συντήκονται μαζί αυτά βρόχους
και να πάει από γραμμικό χώρο σε συνεχή χώρο.
Τρέχουσα ποσό μέχρι σήμερα, εδώ, αντικαθιστά το ρόλο του υποπρόβλημα, σειρά υποπρόβλημα μας.
Έτσι τρέχον ποσό, μέχρι στιγμής, είναι η απάντηση στο προηγούμενο υποπρόβλημα.
Και το ποσό αυτό, μέχρι στιγμής, παίρνει τη θέση της μέγιστης μας.
Θα υπολογίσουμε το μέγιστο όσο προχωράμε.
Και έτσι πάμε από γραμμικό χώρο σε συνεχή χώρο,
και έχουμε επίσης μια γραμμική λύση στο πρόβλημα subarray μας.
>> Αυτά τα είδη των ερωτήσεων που θα πάρετε κατά τη διάρκεια μιας συνέντευξης.
Ποια είναι η χρονική πολυπλοκότητα? Ποια είναι η πολυπλοκότητα χώρου;
Μπορείς να το κάνεις καλύτερα; Υπάρχουν πράγματα που δεν είναι απαραίτητες για να κρατήσει εκεί γύρω;
Το έκανα αυτό για να τονίσει ότι οι αναλύσεις θα πρέπει να πάρετε τη δική σας
όπως εργάζεστε μέσω αυτών των προβλημάτων.
Πάντα να αναρωτιέστε, "Μπορώ να κάνω καλύτερα;"
Στην πραγματικότητα, μπορούμε να κάνουμε κάτι καλύτερο από αυτό;
Ταξινόμηση των ερώτηση τέχνασμα. Δεν μπορείς, γιατί θα πρέπει να
τουλάχιστον να διαβάσει την είσοδο στο πρόβλημα.
Έτσι, το γεγονός ότι θα πρέπει να διαβάσει τουλάχιστον την είσοδο στο πρόβλημα
σημαίνει ότι δεν μπορείτε να κάνετε καλύτερα από ό, τι γραμμικό χρόνο,
και δεν μπορείτε να κάνετε καλύτερα από σταθερό χώρο.
Έτσι, αυτό είναι, στην πραγματικότητα, η καλύτερη λύση στο πρόβλημα αυτό.
Ερωτήσεις; Εντάξει.
>> Χρηματιστήριο πρόβλημα της αγοράς:
"Λαμβάνοντας υπόψη μια σειρά από n ακέραιοι, θετική, μηδενική ή αρνητική,
που αντιπροσωπεύουν την τιμή μιας μετοχής πάνω από n ημέρες,
γράψετε μια λειτουργία για τον υπολογισμό του μέγιστου κέρδους που μπορείτε να κάνετε
δεδομένου ότι θα αγοράζουν και να πωλούν ακριβώς 1 μετοχή μέσα σε αυτές τις n ημέρες. "
Ουσιαστικά, θέλουμε να αγοράσουμε χαμηλό, πωλεί υψηλό.
Και θέλουμε να καταλάβουμε το καλύτερο κέρδος που μπορούμε να κάνουμε.
Πηγαίνοντας πίσω στην άκρη μου, ποια είναι η αμέσως σαφής, απλή απάντηση, αλλά η διαδικασία είναι αργή;
Ναι; (Φοιτητής, ακατάληπτο) >> Ναι.
>> Έτσι θα πήγαινε όμως και να δούμε τις τιμές των μετοχών
σε κάθε χρονική στιγμή, (ακατάληπτο).
[Yu] Εντάξει, έτσι λύση της - πρόταση της των υπολογιστών
η χαμηλότερη και την υψηλότερη υπολογισμό δεν λειτουργεί απαραιτήτως
διότι η υψηλότερη θα μπορούσε να συμβεί πριν από το χαμηλότερο.
Έτσι ποια είναι η ωμή δύναμη λύση σε αυτό το πρόβλημα;
Ποια είναι τα δύο πράγματα που θα πρέπει να προσδιοριστεί μοναδικά το κέρδος μπορώ να κάνω; Δεξιά.
Η ωμή δύναμη λύση είναι - ω, έτσι, την πρόταση του Γιώργου είναι ότι το μόνο που χρειάζεται δύο ημέρες
να προσδιορίσει μοναδικά το κέρδος των δύο αυτών ημερών.
Έτσι, υπολογίζουμε κάθε ζευγάρι, όπως αγοράς / πώλησης,
υπολογίσουμε το κέρδος, το οποίο μπορεί να είναι θετικές ή αρνητικές ή μηδέν.
Υπολογίστε το μέγιστο κέρδος που κάνουμε μετά από επανάληψη σε όλα τα ζεύγη των ημερών.
Αυτό θα είναι η τελική μας απάντηση.
Και ότι η λύση θα είναι O (n ^ 2), επειδή δεν υπάρχει n επιλέξουν δύο ζεύγη -
των ημερών που μπορείτε να επιλέξετε ανάμεσα ημέρες στο τέλος του.
Εντάξει, έτσι είμαι δεν πρόκειται να πάει πέρα ​​από την ωμή δύναμη λύση εδώ.
Πάω να σας πω ότι υπάρχει μια λύση n log n.
Αλγόριθμος όποια στιγμή εσείς ξέρετε ότι είναι n log n;
Δεν είναι μια ερώτηση παγίδα.
>> Συγχώνευση είδος. Συγχώνευση είδος είναι n log n,
και στην πραγματικότητα, ένας τρόπος επίλυσης αυτού του προβλήματος είναι η χρήση
ένα είδος είδος συγχώνευση της ιδέας που ονομάζεται, σε γενικές γραμμές, διαίρει και βασίλευε.
Και η ιδέα είναι ως ακολούθως.
Θέλετε να υπολογίσει την καλύτερη αγοράς / πώλησης ζευγάρι στο αριστερό μισό.
Βρείτε το καλύτερο κέρδος που μπορείτε να κάνετε, απλά με την πρώτη ν πάνω από δύο ημέρες.
Στη συνέχεια, θέλετε να oompute το καλύτερο αγοράς / πώλησης ζευγάρι στο δεξιό μισό,
έτσι ώστε η τελευταία ν πάνω από δύο ημέρες.
Και τώρα το ερώτημα είναι, πώς μπορούμε να συγχωνεύσει αυτές τις λύσεις πίσω μαζί;
Ναι; (Φοιτητής, ακατάληπτο)
Εντάξει >>. Επιτρέψτε μου λοιπόν να σχεδιάσετε μια εικόνα.
Ναι; (Γιώργος, ακατάληπτο)
Ακριβώς >>. Γιώργος λύση είναι ακριβώς σωστό.
Έτσι η πρότασή του είναι, υπολογίζει πρώτα το best buy / sell ζευγάρι,
και αυτό συμβαίνει στο αριστερό μισό, οπότε ας το ονομάσουμε ότι αριστερά, αριστερά.
Καλύτερη αγοράς / πώλησης ζευγάρι που εμφανίζεται στο δεξιό μισό.
Αλλά αν σε σύγκριση με μόνο αυτούς τους δύο αριθμούς, χάνουμε την υπόθεση
όπου αγοράζουμε εδώ και να πωλούν κάπου στο δεξιό μισό.
Αγοράζουμε το αριστερό μισό, να πωλήσει στο δεξιό μισό.
Και ο καλύτερος τρόπος για να υπολογίσουμε το καλύτερο Αγορά / Πώληση ζευγάρι που εκτείνεται σε δύο ημίχρονα
είναι να υπολογιστεί το ελάχιστο εδώ και υπολογίστε τη μέγιστη εδώ
και να τους διαφορά.
Έτσι, οι δύο περιπτώσεις στις οποίες η Αγορά / Πώληση ζευγάρι συμβαίνει μόνο εδώ,
μόνον εδώ, ή και στα δύο μισά ορίζεται από αυτούς τους τρεις αριθμούς.
Έτσι, ο αλγόριθμος μας να συγχωνεύσει τις λύσεις μας πίσω μαζί,
θέλουμε να υπολογίσουμε το καλύτερο Αγορά / Πώληση ζευγάρι
όπου αγοράζουμε στο αριστερό μισό και να πωλούν στο δεξιό μισό.
Και ο καλύτερος τρόπος για να το κάνουμε αυτό είναι να υπολογίσουμε τη χαμηλότερη τιμή κατά το πρώτο εξάμηνο,
η υψηλότερη τιμή στο δεξιό μισό, και να τους διαφορά.
Οι προκύπτουσες τρεις κέρδη, αυτά τα τρία νούμερα, παίρνετε το μέγιστο των τριών,
και αυτό είναι το καλύτερο κέρδος που μπορείτε να κάνετε σε αυτά τα πρώτα και τέλος ημέρες.
Εδώ οι σημαντικές γραμμές είναι στο κόκκινο.
Πρόκειται για μια αναδρομική κλήση για να υπολογίσει την απάντηση στο αριστερό μισό.
Πρόκειται για μια αναδρομική κλήση για να υπολογίσει την απάντηση στο δεξιό μισό.
Αυτές οι δύο για βρόχους υπολογίζουμε την min και το max στο αριστερό και δεξιό ήμισυ, αντίστοιχα.
Τώρα θα υπολογίσουμε το κέρδος που εκτείνεται σε δύο μισά,
και η τελική απάντηση είναι το μέγιστο από αυτά τα τρία.
Εντάξει.
>> Έτσι, σίγουρα, έχουμε έναν αλγόριθμο, αλλά το μεγαλύτερο ερώτημα είναι,
Ποια είναι η χρονική πολυπλοκότητα του αυτό;
Και ο λόγος για τον οποίο ανέφερα είδος συγχώνευσης είναι ότι αυτή η μορφή του διαιρούν την απάντηση
σε δύο και στη συνέχεια συγχώνευση λύσεις μας πίσω μαζί
είναι ακριβώς η μορφή του είδους συγχώνευσης.
Επιτρέψτε μου λοιπόν να περάσουν από τη διάρκεια.
Εάν ορίζεται μια συνάρτηση τ (n) είναι ο αριθμός των βημάτων
για ν ημερών,
δύο αναδρομικές κλήσεις μας
Οι κάθε πρόκειται να κοστίσει t (n / 2),
και υπάρχει σε δύο από αυτές τις κλήσεις.
Τώρα πρέπει να υπολογίσουμε το ελάχιστο αριστερό μισό,
που μπορώ να κάνω σε n / 2 ώρα, καθώς και το ανώτατο όριο του δικαιώματος μισό.
Έτσι, αυτό είναι ακριβώς n.
Και στη συνέχεια, συν κάποια σταθερή δουλειά.
Και αυτή η εξίσωση επανάληψης
είναι ακριβώς η εξίσωση επανάληψης για το είδος συγχώνευσης.
Και όλοι γνωρίζουμε ότι η συγχώνευση είναι είδος n log n χρόνου.
Ως εκ τούτου, ο αλγόριθμος μας είναι n log n και του χρόνου.
Μήπως αυτή η επανάληψη νόημα;
Ακριβώς μια σύντομη ανακεφαλαίωση του αυτό:
Τ (n) είναι ο αριθμός των σταδίων για να υπολογιστεί το μέγιστο κέρδος
κατά τη διάρκεια της ημέρας n.
Ο τρόπος που χωρίσαμε αναδρομικές κλήσεις μας
είναι καλώντας λύση μας για τις πρώτες ημέρες n / 2,
έτσι ώστε να είναι ένα τηλεφώνημα,
και στη συνέχεια καλούμε και πάλι για το δεύτερο εξάμηνο.
Έτσι, αυτό είναι δύο κλήσεις.
Και τότε θα βρείτε ένα ελάχιστο στο αριστερό μισό, το οποίο μπορούμε να κάνουμε σε γραμμικό χρόνο,
βρείτε το μέγιστο στο δεξιό μισό, το οποίο μπορούμε να κάνουμε σε γραμμικό χρόνο.
Έτσι, n / 2 + n / 2 είναι ακριβώς n.
Στη συνέχεια, έχουμε κάποια σταθερή δουλειά, που είναι σαν να κάνει αριθμητικές πράξεις.
Αυτή η εξίσωση επανάληψης είναι ακριβώς η εξίσωση επανάληψης για το είδος συγχώνευσης.
Ως εκ τούτου, ο αλγόριθμος τυχαία σειρά μας είναι επίσης n log n.
Έτσι, πόσο χώρο είμαστε χρησιμοποιείτε;
Ας πάμε πίσω στον κώδικα.
>> Μια καλύτερη ερώτηση είναι, πόσα πλαίσια στοίβα δεν μπορούμε ποτέ να έχουν ανά πάσα στιγμή;
Επειδή είμαστε χρησιμοποιώντας αναδρομή,
ο αριθμός των πλαισίων στοίβας καθορίζει χρήσης του χώρου μας.
Ας εξετάσουμε n = 8.
Καλούμε τυχαία στις 8,
η οποία θα καλέσει τυχαία στις πρώτες τέσσερις συμμετοχές,
η οποία θα καλέσει μια μετάθεση για τις δύο πρώτες καταχωρήσεις.
Έτσι στοίβα μας είναι - αυτή είναι η στοίβα μας.
Και μετά λέμε τυχαία σειρά και πάλι στο 1,
και αυτό είναι βασικό σενάριο μας είναι, έτσι ώστε να επιστρέψει αμέσως.
Έχουμε όλο και περισσότερο από αυτό πολλά πλαίσια στοίβα;
Όχι. Επειδή κάθε φορά που κάνουμε μια επίκληση,
αναδρομικό επίκληση να ανακατέψετε,
χωρίζουμε το μέγεθος μας στο μισό.
Έτσι, ο μέγιστος αριθμός των πλαισίων στοίβας που έχουν ποτέ σε οποιαδήποτε δεδομένη στιγμή
είναι της τάξεως των log n στοίβας πλαίσια.
Κάθε πλαίσιο στοίβας έχει σταθερή χώρο,
και ως εκ τούτου η συνολική ποσότητα του χώρου,
το μέγιστο ποσό του χώρου που ποτέ χρήση είναι O (log n) χώρο
όπου n είναι ο αριθμός των ημερών.
>> Τώρα, πάντα αναρωτηθείτε, "Μπορούμε να το κάνουμε καλύτερα;"
Και συγκεκριμένα, μπορούμε να μειώσουμε αυτό σε ένα πρόβλημα που έχουμε ήδη λυθεί;
Μια υπόδειξη: συζητήσαμε μόνο δύο άλλα προβλήματα πριν από αυτό, και αυτό δεν πρόκειται να είναι τυχαία.
Μπορούμε να μετατρέψουμε αυτό το πρόβλημα χρηματιστηριακή αγορά στο μέγιστο πρόβλημα subarray.
Πώς μπορούμε να το κάνουμε αυτό;
Κάποιος από εσάς; Emmy;
(Emmy, ακατάληπτο)
[Yu] Ακριβώς.
Έτσι, η μέγιστη problem subarray,
ψάχνουμε για ένα ποσό πάνω από μια συνεχή subarray.
Και πρόταση Emmy για το πρόβλημα των αποθεμάτων,
εξετάσουν τις αλλαγές, ή τα δέλτα.
Και μια εικόνα από αυτό - αυτή είναι η τιμή μιας μετοχής,
αλλά αν πήραμε τη διαφορά μεταξύ κάθε συνεχόμενη ημέρα -
έτσι βλέπουμε ότι η μέγιστη τιμή, το μέγιστο κέρδος που θα μπορούσε να κάνει
είναι αν θα αγοράσει εδώ και πωλούν εδώ.
Αλλά ας ρίξουμε μια ματιά σε συνεχή - ας δούμε το πρόβλημα subarray.
Έτσι, εδώ, μπορούμε να κάνουμε - που πηγαίνει από εδώ μέχρι εδώ,
έχουμε μια θετική αλλαγή, και στη συνέχεια πηγαίνει από εδώ εδώ έχουμε μια αρνητική αλλαγή.
Στη συνέχεια, όμως, που πηγαίνει από εδώ εδώ έχουμε μια τεράστια θετική αλλαγή.
Και αυτές είναι οι αλλαγές που θέλουμε να συνοψίσουμε για να πάρει τελικό κέρδος μας.
Στη συνέχεια, έχουμε περισσότερες αρνητικές αλλαγές εδώ.
Το κλειδί για τη μείωση problem αποθεμάτων μας σε μέγιστη problem subarray μας
είναι να εξετάσει τα δέλτα μεταξύ των ημερών.
Έτσι δημιουργούμε μια νέα σειρά που ονομάζεται δέλτα,
προετοιμάσει την πρώτη θέση να είναι 0,
και στη συνέχεια για κάθε δέλτα (ί), ας ότι είναι η διαφορά
του πίνακα εισόδου μου (i), και σειρά (i - 1).
Στη συνέχεια καλούμε διαδικασία ρουτίνας μας για μια μέγιστη subarray
περνώντας σε μια σειρά δέλτα του.
Και επειδή η μέγιστη subarray είναι γραμμικό χρόνο,
και αυτή η μείωση, η διαδικασία αυτή της δημιουργίας αυτής της δέλτα συστοιχία,
είναι επίσης γραμμικό χρόνο,
τότε το τελικό διάλυμα για τα αποθέματα είναι O (n) εργασίας συν O (n) των εργασιών, εξακολουθεί να είναι O (n) εργασίας.
Έτσι έχουμε μια γραμμική λύση στο πρόβλημά του χρόνου μας.
Μήπως όλοι κατανοούν αυτή την μεταμόρφωση;
>> Σε γενικές γραμμές, μια καλή ιδέα που θα πρέπει να έχουν πάντα
είναι να προσπαθήσουμε να μειώσει ένα νέο πρόβλημα που βλέπετε.
Αν φαίνεται οικεία σε ένα παλιό πρόβλημα,
δοκιμάστε να μειώσετε το σε ένα παλιό πρόβλημα.
Και αν μπορείτε να χρησιμοποιήσετε όλα τα εργαλεία που έχετε χρησιμοποιήσει για το παλιό πρόβλημα
να λύσει το νέο πρόβλημα.
Έτσι για να ολοκληρωθεί, τεχνική συνεντεύξεις αποτελούν πρόκληση.
Αυτά τα προβλήματα είναι πιθανόν μερικά από τα πιο δύσκολα προβλήματα
ότι μπορείτε να δείτε σε μια συνέντευξη,
οπότε αν δεν καταλαβαίνετε όλα τα προβλήματα που μόλις καλύπτονται, είναι εντάξει.
Αυτά είναι μερικά από τα πιο σημαντικά προβλήματα.
Πρακτική, πρακτική, πρακτική.
Έδωσα πολλά προβλήματα στο φυλλάδιο, έτσι σίγουρα να ελέγξετε έξω αυτά.
Και καλή τύχη σε συνεντεύξεις σας. Όλα πόροι μου δημοσιεύτηκε σε αυτό το σύνδεσμο,
και ένας από τους ανώτερους τους φίλους μου έχει προσφερθεί να κάνει εικονικές τεχνικές συνεντεύξεων,
οπότε αν σας ενδιαφέρει, e-mail Θα Yao σε αυτή τη διεύθυνση email.
Αν έχετε κάποιες ερωτήσεις, μπορείτε να με ρωτήσετε.
Μήπως εσείς έχετε συγκεκριμένες ερωτήσεις που σχετίζονται με τις τεχνικές συνεντεύξεων
ή τυχόν προβλήματα που έχουμε δει μέχρι τώρα;
Εντάξει. Λοιπόν, καλή τύχη σε συνεντεύξεις σας.
[CS50.TV]