φιζζ - μπαζζ (Google Interview test)

Άβαταρ μέλους
Χουργιατς
Δημοσιεύσεις: 6700
Εγγραφή: 02 Απρ 2018, 02:06

Re: φιζζ - μπαζζ (Google Interview test)

Μη αναγνωσμένη δημοσίευση από Χουργιατς » 22 Ιούλ 2018, 13:40

.
Χαοτικός έγραψε:
21 Ιούλ 2018, 14:47
Πληροφορικάριοι είσαστε;

Ρε συ χαο, σε πάω. Δηλαδή μην το πάρεις στραβά, μα είσαι στην καρακοσμάρα σου.
Τεσπ.

Για να κλείσω το σπαμ, νέημλεςς - δεν έβαλες λύση.
Γιατί παιδί μου χρυσό μας σνομπάρεις έτσι.
(βασικά τη γκουγκλ).

Τεσπ2. Θέλω να λάβω αυτή την ευκαιρία για να κάνω μια γενική παρατήρηση =πολιτικό σχόλιο= ανάμεσα στους αριστερούς φίλους μας και όλους τους υπόλοιπους: Οι δεδηλωμένοι αριστεροί είτε δεν ασχολούνται είτε δεν ασχολούνται πέραν παραινέσεων. Ενώ οι άνθρωποι της δουλειάς δίνουν λύση.
Προσοχή, δε λέω πως ο νέημλεςς δεν δουλεύει ή πως δεν είναι σημαντική η δουλειά του.
Λέω πως οι παρατηρήσεις του -σωστές παρατηρήσεις για να μη λέτε πως είμαι προκατειλημμένος- θα είχαν άλλη βάση αν μας έδινε και μια λύση.
Τώρα - δεν τη ζητάω τη λύση.

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

Κλείνω αυτό το ανούσιο ποστ και επανέρχομαι με λύσεις και σχόλια και νέο πρόβλημα.

Άβαταρ μέλους
Χαοτικός
Δημοσιεύσεις: 22707
Εγγραφή: 09 Απρ 2018, 16:48
Phorum.gr user: Χαοτικός

Re: φιζζ - μπαζζ (Google Interview test)

Μη αναγνωσμένη δημοσίευση από Χαοτικός » 22 Ιούλ 2018, 14:24

Χουργιατς έγραψε:
22 Ιούλ 2018, 13:40
.
Χαοτικός έγραψε:
21 Ιούλ 2018, 14:47
Πληροφορικάριοι είσαστε;

Ρε συ χαο, σε πάω. Δηλαδή μην το πάρεις στραβά, μα είσαι στην καρακοσμάρα σου.
Τεσπ.

Για να κλείσω το σπαμ, νέημλεςς - δεν έβαλες λύση.
Γιατί παιδί μου χρυσό μας σνομπάρεις έτσι.
(βασικά τη γκουγκλ).

Τεσπ2. Θέλω να λάβω αυτή την ευκαιρία για να κάνω μια γενική παρατήρηση =πολιτικό σχόλιο= ανάμεσα στους αριστερούς φίλους μας και όλους τους υπόλοιπους: Οι δεδηλωμένοι αριστεροί είτε δεν ασχολούνται είτε δεν ασχολούνται πέραν παραινέσεων. Ενώ οι άνθρωποι της δουλειάς δίνουν λύση.
Προσοχή, δε λέω πως ο νέημλεςς δεν δουλεύει ή πως δεν είναι σημαντική η δουλειά του.
Λέω πως οι παρατηρήσεις του -σωστές παρατηρήσεις για να μη λέτε πως είμαι προκατειλημμένος- θα είχαν άλλη βάση αν μας έδινε και μια λύση.
Τώρα - δεν τη ζητάω τη λύση.

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

Κλείνω αυτό το ανούσιο ποστ και επανέρχομαι με λύσεις και σχόλια και νέο πρόβλημα.
Τι να πάρω στραβά μωρέ που λες ότι με πας; Καλό μου κάνεις στην διάθεση και σ' ευχαριστώ.

Δεν το λέω είμαι στην κοσμάρα μου - νομίζω όλοι είμαστε - μια χαρά καταλαβαίνω τι λένε οι γύρω μου τι εννοούν και πως αισθάνονται. Απλά η στάση μου δεν είναι μόνο θέμα του τι αντιλαμβάνομαι. Είναι κι άλλα πράγματα.

Μαλακία η άποψη ότι οι αριστεροί δεν είναι της δουλειάς βρε.

Σαν σκουπίδια τυχαία χυμένα ο πιο όμορφος κόσμος.

Άβαταρ μέλους
Χουργιατς
Δημοσιεύσεις: 6700
Εγγραφή: 02 Απρ 2018, 02:06

Re: φιζζ - μπαζζ (Google Interview test)

Μη αναγνωσμένη δημοσίευση από Χουργιατς » 22 Ιούλ 2018, 16:22

Λοιπόν, για τις λύσεις - έκανε μια παρατήρηση ο 252 που θέλω να σταθώ ένα λεπτό.
Λύσεις της μίας γραμμής. Ναι, υπάρχουν.
Έχουν σημασία; Φυσικά.
Έχουν σημασία για το παρόν ερώτημα; Για μένα όχι. Να εξηγήσω γιατί.


Πριν από λίγα χρόνια, υπήρχε ένας διαγωνισμός ονλάην σε μία γλώσσα που δεν θέλω να αποκαλύψω (σε προηγ. ποστ) με σκοπό το να λυθούν προβλήματα με τον αποδοτικότερο κώδικα δυνατό. Όταν λέμε αποδοτικότερο, εννοούμε πως η λύση θα πρέπει να έχει το ελάχιστο parsing tree. Eξυπακούεται πως η μικρή απαίτηση σε μνήμη και ο μικρότερος χρόνος υπολογισμού λαμβάνονταν υπόψιν, κάτι που κάποιοι θα ισχυρίζονταν προκύπτει άμεσα από το προηγούμενο, μα φυσικά επιτρέπονταν και μικρές αλχημείες οι οποίες βοηθούν τη μεταγλώτισση να γίνει γρηγορότερη, ή να μη γίνει και καθόλου.
Ας το πούμε αυτό λίγο για να διασαφηνιστεί ότι δεν αναφέρω αυτό στα επόμενα.


Εδώ βλέπουμε ένα τέτοιο τρικ μεγατόννων. Δεξιά έχουμε τον κώδικα που έχει γράψει η γνωστή Μοντέλα-Προγραμματίστρια, Καρλι Κλοςς, για τον υπολογισμό του μεγίστου δύο αριθμών.
Αριστερά έχουμε έναν κάπως διάσημο κώδικα ο οποιος υπολογίζει την αντίστροφη τετραγωνική ρίζα (και προέρχεται από τη μηχανή του quake, αν κανείς εδώ ξόδεψε τα νειάτα του στα λαν πάρτυ).
Φαίνεται φυσικά πως το τρικ μοιάζει σχεδόν μαγικό για όσους δεν γνωρίζουν (μαζί και εγώ). Φαίνεται φυσικά το πως μια μοντέλα δεν χρειάζεται να μάθει προγραμματισμό, όχι για άλλο λόγο, αλλά για να μη λαμβάνει ο πιλότος ένδειξη 5 όταν οι είσοδοι στο πρόγραμμα είναι και οι δύο 7.


Εικόνα



Aυτά λοιπόν τα τρικ υπάρχουν μα δεν μας αφορούν σε αυτό που θα πω τώρα (που δεν αφορά τη λύση, το λέω ξανά, μη βγεί κανείς να το πεί).
Ο διαγωνισμός λοιπόν για τον αποδοτικότερο κώδικα με βρήκε δεύτερο και καταενθουσιάστηκα, γιατί περίμενα πως η λύση του πρώτου θα είναι τόσο σουπερντούπερ μαγευτική που θα μας έστελνε όλους σπίτια μας να ασχοληθούμε με τα πρόβατα. Όταν λοιπόν μαθεύτηκε η λύση, έπεσα από τα σύννεφα, γιατί η λογική του κώδικα ήταν ακριβώς η δική μου, μα η διατύπωση γινόταν με χρήση regexp, άρα τεχνικά το parsing tree ελαττωνόταν.
Θα μου πείτε, γιατί δεν το έκανες εσύ έτσι ρε γκρινιάρη; Γιατί πολύ απλά με ενδιέφερε ο μηχανισμός της λύσης, και όχι τα κολπάκια που μπορούμε να κάνουμε ώστε να μην γράφουμε στο πληκτρολόγιο. Το ξαναλέω πως αυτό το κολπάκι δεν είναι το τρικ που μας δείχνει η καρλι κλοςς στον αριστερό κώδικα, το οποίο αποτελεί προϊόν συμφωνίας με τον Σατανά.
Με αυτή τη λογική, οι λύσεις της μίας γραμμής είναι δεκτές - μα όχι αυτοσκοπός. Αρκεί φυσικά να είναι γραμμένες χωρίς regexp.

Με βάση λοιπόν αυτό:


- Ο κώδικας του Σρικε είναι άμεσος, χρηστικός, και διαβάζεται ακόμα και αν δεν έχουμε επαφή με την VB6 (οπως εγώ).

Η λογική του είναι να εξετάζουμε από το 1 μέχρι το τελικό αριθμό και να ελέγχουμε τρείς συνθήκες.
Με είσοδο ν, κάθε συνθήκη έχει πολυπλοκότητα Ο(ν) στη χειρότερη, και λόγω της επανάληψης, η συνολική πολυπλοκότητα είναι Ο(3ν^2).
Η λύση είναι δεκτή και εκτιμώ την απλότητά της. :bravo:



- Ο κώδικας του Σπύρου252 είναι επίσης άμεσος, και διαβάζεται ακόμα και αν δεν έχουμε επαφή με την php (όπως εγώ).

Η λογική του είναι να αποθηκεύσουμε τους αριθμούς που μας ενδιαφέρουν σε τρείς λίστες και να αναζητούμε κάθε φορά.
Κάθε αναζήτηση θα υποθέσουμε είναι βέλτιστη, με την έννοια πως η πολυπλοκότητά της θα είναι Ο(logν). Συνεπώς, μαζί με την επανάληψη, θα έχουμε συνολική πολυπλοκότητα Ο(3νlogν).

Η λύση είναι δεκτή και εκτιμώ το ότι ο Σπ είχε το σθένος, αλλά και το θράσος, να μη χρησιμοποιήσει γλώσσα προγραμματισμού. Όπως και τον τρόπο με τον οποίο παρέκαμψε το πρόβλημα με τις συμβολοσειρές. :bravo:



Ως προς την σύγκριση τώρα.

-Ο κώδικας του Σπ252 είναι γρηγορότερος, κάτι που πρέπει να λάβουμε υπόψιν λόγω την τεράστιων αριθμών.

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


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


Τώρα για τις παρατηρήσεις:

- Ο Σταθ έκανε μια σημαντική παράτηση, οι αριθμοί είναι πρώτοι. Ο λόγος γι΄αυτό είναι πως, αν δεν ήταν πρώτοι, ο κώδικας που θα ετοιμάζουμε θα εξέταζε τις περιπτώσεις ανάλογα με την ανάλυσή τους σε πρώτους παράγοντες. Άρα το να μην είναι πρώτοι δεν προσφέρει κάτι ουσιώδες στο πρόβλημα.
- Ο νεημλεςς παρατήρησε ότι δεν χρειάζεται να κάνουμε τρείς συγκρίσεις. Και αυτή η παρατήρηση έχει αξία ώστε να ελαττωθεί ο χρόνος εκτέλεσης (Παρατήρηση Νεημλεςς)


Και τώρα μια δική μου λύση επειδή το έθεσα ο ίδιος το πρόβλημα. Η λογική της λύσης ειναι η εξής. Θα χρειαστούμε ούτως η άλλως επανάληψη για να διατρέξουμε τους αριθμούς από το 1 ως το 10^7. Εκτος αν κάνουμε τον κώδικα συνάρτηση Φ και την βάλουμε να καλεί τον ευατό της αναγωγικά, ξεκινώντας από το 10^7 (εισοδος) και κατεβούμε εώς το 1. Δηλαδή,

Φ(10^7)->Φ(Φ(10^7-1))->....->Φ(Φ(...Φ(1)...))

τυπώνοντας κάθε φορά το αποτέλεσμα του ελέγχου με βάση την Παρατήρηση Νεημλεςς.

Δεν κρατήθηκα φυσικά να μη βάλω και το χρόνο εκτέλεσης (*μονο για την εκτελεση της Φ). Αυτό είναι καγκουριά και θα φανεί σε ένα λεπτό γιατί.

Εικόνα

Η λύση λοιπόν έχει μικρη πολυπλοκότητα και μηδαμινές απαιτήσεις μνήμης.
Παρ' όλα αυτά απορρίπτεται.

Ο λόγος είναι πως σε οποιοδήποτε μηχάνημα την χρησιμοποιήσετε, ο αριθμός των κλήσεων στον εαυτό της (recursion depth) υπερβαίνει το προκαθορισμένο όριο. Άρα σαν κώδικας είναι πρακτικά άχρηστος για τους μεγάλους αριθμούς που έχει ως απαιτήσεις το πρόβλημα.

Α να μην ξεχάσω, Χαο με το να ποστάρεις Νταλάρα με επιβεβαιώνεις σε αυτό που είπα.
Αυτά. Καλή κυριακή

Spiros252
Διαχειριστής
Δημοσιεύσεις: 11581
Εγγραφή: 13 Μαρ 2018, 19:22
Phorum.gr user: Spiros252
Τοποθεσία: Αθήνα

Re: φιζζ - μπαζζ (Google Interview test)

Μη αναγνωσμένη δημοσίευση από Spiros252 » 22 Ιούλ 2018, 17:35

Χουργιατς έγραψε:
22 Ιούλ 2018, 16:22
(και προέρχεται από τη μηχανή του quake, αν κανείς εδώ ξόδεψε τα νειάτα του στα λαν πάρτυ).
:vp27::vp27::vp27::vp27::vp27::vp27::vp27::lol:

Χουργιατς έγραψε:
22 Ιούλ 2018, 16:22
Όταν λοιπόν μαθεύτηκε η λύση, έπεσα από τα σύννεφα, γιατί η λογική του κώδικα ήταν ακριβώς η δική μου, μα η διατύπωση γινόταν με χρήση regexp, άρα τεχνικά το parsing tree ελαττωνόταν. Αρκεί φυσικά να είναι γραμμένες χωρίς regexp.
Στη μέση το έχω αφήσει ... δεν τα θυμόμουν όλα και κάπου κόλλησα.. δεν είχα άλλο χρόνο :011:

Χουργιατς έγραψε:
22 Ιούλ 2018, 16:22
- Ο κώδικας του Σπύρου252 είναι επίσης άμεσος, και διαβάζεται ακόμα και αν δεν έχουμε επαφή με την php (όπως εγώ).

Η λογική του είναι να αποθηκεύσουμε τους αριθμούς που μας ενδιαφέρουν σε τρείς λίστες και να αναζητούμε κάθε φορά.
Κάθε αναζήτηση θα υποθέσουμε είναι βέλτιστη, με την έννοια πως η πολυπλοκότητά της θα είναι Ο(logν). Συνεπώς, μαζί με την επανάληψη, θα έχουμε συνολική πολυπλοκότητα Ο(3νlogν).

Η λύση είναι δεκτή και εκτιμώ το ότι ο Σπ είχε το σθένος, αλλά και το θράσος, να μη χρησιμοποιήσει γλώσσα προγραμματισμού. Όπως και τον τρόπο με τον οποίο παρέκαμψε το πρόβλημα με τις συμβολοσειρές. :bravo:
Εχμμ.. βασικά δεν χρειάζεται αναζήτηση. Θα μπορούσα να δημιουργήσω εξαρχής την τελική λίστα και κατά την παραγωγή των αριθμών να αντικαταστήσω την ετικέτα (κλειδί) μόνο ως προς τα fizz - buzz - fizzbuzz. :p2:

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

Υ.Γ.1. Εχω μόνο μία λίστα, όχι 3.

Υ.Γ.2. Παρεμπιπτόντως με regexp (της πλάκας - δεν ξέρω αν θα δούλευε :lol: ) σε δοκιμές έπιασα 11 ms.
«Η παρουσία μας επιλέγει από ένα τεράστιο σύνολο μόνο σύμπαντα συμβατά με την ύπαρξή μας.
Αν και είμαστε μικροί και ασήμαντοι σε κοσμικό επίπεδο, αυτό μας κάνει κατά κάποιο τρόπο, κύριους της δημιουργίας»
.
Stephen Hawking

Άβαταρ μέλους
foscilis
Δημοσιεύσεις: 24351
Εγγραφή: 21 Ιουν 2018, 11:42

Re: φιζζ - μπαζζ (Google Interview test)

Μη αναγνωσμένη δημοσίευση από foscilis » 22 Ιούλ 2018, 23:24

shrike έγραψε:
20 Ιούλ 2018, 19:51
Χουργιατς έγραψε:
19 Ιούλ 2018, 16:26
Λοιπόν μιας και ο Σπύρος άνοιξε τον ασκό του άμαζον, ας δούμε παράλληλα και ένα προβληματάκι της γκουγκλ.
Να γραφεί κώδικας σε οποιαδήποτε γλώσσα (*) o οποίος θα τυπώνει τους ακεραίους από το 1 εώς το 10^7 σε διαδοχικές γραμμές, ώστε να εμφανίζεται φιζζ στα πολλαπλάσια του 659, μπαζζ στα πολλαπλάσια του 947, και φιζζμπαζ στα πολλαπλάσια του 624073.
Το εννοείς ή κάνεις πλάκα; Να ξέρω πώς να απαντήσω... :lol:
Ελα τωρα νομιζω στη γκουγκλ βαζουν πιο δυσκολα.

Spiros252
Διαχειριστής
Δημοσιεύσεις: 11581
Εγγραφή: 13 Μαρ 2018, 19:22
Phorum.gr user: Spiros252
Τοποθεσία: Αθήνα

Re: φιζζ - μπαζζ (Google Interview test)

Μη αναγνωσμένη δημοσίευση από Spiros252 » 23 Ιούλ 2018, 01:01

Δίνω μία σχηματική εξήγηση για τη λύση μου στο πρόβλημα της google:

Εικόνα

Αυτό που κάνω είναι το εξής, αν το μεταφέρουμε σε φυσικό μέσο (ή ένα φύλλο του Excel).

Για ευκολία έχω αριθμούς έως το 100 και ζητώ τα πολλαπλάσια των 5 και 7 καθώς και τα κοινά τους.
  • Παίρνω ένα προαριθμημένο φύλλο χαρτιού από το 1 έως το 100
  • Βρίσκω τα πολλαπλάσια του 5 πολλαπλασιάζοντάς τον με κάθε ακέραιο έως ότου δεν υπερβαίνω το 100 και αντικαθιστώ* με FIZZ στη γραμμή που αντιστοιχεί στο αποτέλεσμα. ( * αντικαθιστώ το κενό ).
  • Βρίσκω τα πολλαπλάσια του 7 πολλαπλασιάζοντάς τον με κάθε ακέραιο έως ότου δεν υπερβαίνω το 100 και αντικαθιστώ με BUZZ στη γραμμή που αντιστοιχεί στο αποτέλεσμα. ( αντικαθιστώ και το FIZZ ).
  • Βρίσκω τα πολλαπλάσια του 5*7 πολλαπλασιάζοντάς το με κάθε ακέραιο έως ότου δεν υπερβαίνω το 100 και αντικαθιστώ με FIZZ-BUZZ στη γραμμή που αντιστοιχεί στο αποτέλεσμα. ( αντικαθιστώ και το BUZZ με FIZZ-BUZZ ).
  • Βάζω έναν εκφωνητή να διαβάζει με τη σειρά τις γραμμές.
    Διαβάζει ότι βλέπει: ένα - δύο - τρία - τέσσερα - πέντε FIZZ - έξι - επτά BUZZ - οκτώ - ... - τριάντα πέντε FIZZ BUZZ - τριάντα έξι - ... - εκατό FIZZ.
Σκεφτείτε τώρα να διαιρούσα σε κάθε σειρά τον αριθμό της δια 5 και δια 7 και να ελέγχω το αποτέλεσμα αν βγαίνει ακριβώς (mod) και αν ναι, να το γράφω.
Και εδώ, στο παράδειγμα με τα 100, έχω επικάλυψη 32% ενώ στο κανονικό πρόβλημα έχω επικάλυψη μόλις 0,25%
Επικάλυψη εννοώ «γεμάτα με πληροφορία κελιά».


Υ.Γ. Δεν το τελειοποίησα τόσο πολύ αλλά έφτασα πολύ κοντά. Η βασική αρχή αυτή είναι πάντως.
«Η παρουσία μας επιλέγει από ένα τεράστιο σύνολο μόνο σύμπαντα συμβατά με την ύπαρξή μας.
Αν και είμαστε μικροί και ασήμαντοι σε κοσμικό επίπεδο, αυτό μας κάνει κατά κάποιο τρόπο, κύριους της δημιουργίας»
.
Stephen Hawking

Άβαταρ μέλους
ST48410
Δημοσιεύσεις: 24347
Εγγραφή: 31 Μαρ 2018, 20:21

Re: φιζζ - μπαζζ (Google Interview test)

Μη αναγνωσμένη δημοσίευση από ST48410 » 23 Ιούλ 2018, 01:11

Spiros252 έγραψε:
23 Ιούλ 2018, 01:01
Δίνω μία σχηματική εξήγηση για τη λύση μου στο πρόβλημα της google:

Εικόνα

Αυτό που κάνω είναι το εξής, αν το μεταφέρουμε σε φυσικό μέσο (ή ένα φύλλο του Excel).

Για ευκολία έχω αριθμούς έως το 100 και ζητώ τα πολλαπλάσια των 5 και 7 καθώς και τα κοινά τους.
  • Παίρνω ένα προαριθμημένο φύλλο χαρτιού από το 1 έως το 100
  • Βρίσκω τα πολλαπλάσια του 5 πολλαπλασιάζοντάς τον με κάθε ακέραιο έως ότου δεν υπερβαίνω το 100 και αντικαθιστώ* με FIZZ στη γραμμή που αντιστοιχεί στο αποτέλεσμα. ( * αντικαθιστώ το κενό ).
  • Βρίσκω τα πολλαπλάσια του 7 πολλαπλασιάζοντάς τον με κάθε ακέραιο έως ότου δεν υπερβαίνω το 100 και αντικαθιστώ με BUZZ στη γραμμή που αντιστοιχεί στο αποτέλεσμα. ( αντικαθιστώ και το FIZZ ).
  • Βρίσκω τα πολλαπλάσια του 5*7 πολλαπλασιάζοντάς το με κάθε ακέραιο έως ότου δεν υπερβαίνω το 100 και αντικαθιστώ με FIZZ στη γραμμή που αντιστοιχεί στο αποτέλεσμα. ( αντικαθιστώ το BUZZ με FIZZ-BUZZ ).
  • Βάζω έναν εκφωνητή να διαβάζει με τη σειρά τις γραμμές.
    Διαβάζει ότι βλέπει: ένα - δύο - τρία - τέσσερα - πέντε FIZZ - έξι - επτά BUZZ - οκτώ - ... - τριάντα πέντε FIZZ BUZZ - τριάντα έξι - ... - εκατό FIZZ.
Σκεφτείτε τώρα να διαιρούσα σε κάθε σειρά τον αριθμό της δια 5 και δια 7 και να ελέγχω το αποτέλεσμα αν βγαίνει ακριβώς (mod) και αν ναι, να το γράφω.
Και εδώ, στο παράδειγμα με τα 100, έχω επικάλυψη 32% ενώ στο κανονικό πρόβλημα έχω επικάλυψη μόλις 0,25%
Επικάλυψη εννοώ «γεμάτα με πληροφορία κελιά».


Υ.Γ. Δεν το τελειοποίησα τόσο πολύ αλλά έφτασα πολύ κοντά. Η βασική αρχή αυτή είναι πάντως.
Αφού το σχήμα 1-35 επαναλαμβάνεται ακριβώς μετά και δεδομένου ότι δεν θα έχεις μόνο 100 νούμερα αλλά περισσότερα άρα και περισσότερες επαναλήψεις μήπως μπορεί να γίνει και εκεί κάποια οικονομία;

Nameless Ghoul

Re: φιζζ - μπαζζ (Google Interview test)

Μη αναγνωσμένη δημοσίευση από Nameless Ghoul » 23 Ιούλ 2018, 01:22

Spiros252 έγραψε:
21 Ιούλ 2018, 09:38
Spiros252 έγραψε:
20 Ιούλ 2018, 23:35
Γράφω σε απλά ελληνικά τη δική μου λύση:

1. Δημιουργούμε όλα τα γινόμενα του 659 μικρότερα ή ίσα του 107 και τα αποθηκεύουμε σε πίνακα.
2. Δημιουργούμε όλα τα γινόμενα του 947 μικρότερα ή ίσα του 107 και τα αποθηκεύουμε σε πίνακα.
3. Δημιουργούμε όλα τα γινόμενα του (659*947) μικρότερα ή ίσα του 107 και τα αποθηκεύουμε σε πίνακα.
4. Ταξινομούμε και τυπώνουμε τον πίνακα από το μικρότερο στο μεγαλύτερο αποτέλεσμα, τυπώνοντας δίπλα αν προέρχεται από την 1 πράξη fizz, από τη 2 πράξη buzz, από την 3 πράξη fizz-buzz.

Δεν χρειάζεται να κάνουμε εκατομμύρια διαιρέσεις!

Αν θέλουμε και τους ενδιάμεσους αριθμούς που δεν είναι fizz, buzz τους τυπώνουμε κι αυτούς απλά με τη σειρά, μεταξύ των παραπάνω αποτελεσμάτων.

Υποψιάζομαι όμως ότι ο Χουργιατς έχει άλλη πολύ έξυπνη λύση την οποία έχω ψυλλιαστει και την ψάχνω. Υποψιάζομαι ότι θα γίνεται με 1 γραμμή κώδικα.. :vp27:
Όχι Σπύρο, την ταξινόμηση πινάκων πρέπει να την αποφύγεις, είναι λύση με πολυλοκότητα O(nlogn) στην καλύτερη, ενώ η μπορείς να έχεις O(n).

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

Nameless Ghoul

Re: φιζζ - μπαζζ (Google Interview test)

Μη αναγνωσμένη δημοσίευση από Nameless Ghoul » 23 Ιούλ 2018, 01:26

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

Άβαταρ μέλους
nick
Δημοσιεύσεις: 5052
Εγγραφή: 25 Μάιος 2018, 22:21

Re: φιζζ - μπαζζ (Google Interview test)

Μη αναγνωσμένη δημοσίευση από nick » 23 Ιούλ 2018, 01:36

Μια λυση ειναι να εχεις 2 μεταβλητές και να τις αυξάνεις κατά 659 και 947 αντιστοιχα, η σειρα που τις αυξανεις εχει σημασια ωστε τα νούμερα να εμφανίζονται ταξινομημένα. οταν συναντιούνται εχεις φιζζβαζζ. το καλο ειναι οτι δεν χρειαζεται να ελεγξεις αν διαιρειται με 659,947.

659,
947,
659*2,
947*2,
659*3,
659*4,

947*3,

Spiros252
Διαχειριστής
Δημοσιεύσεις: 11581
Εγγραφή: 13 Μαρ 2018, 19:22
Phorum.gr user: Spiros252
Τοποθεσία: Αθήνα

Re: φιζζ - μπαζζ (Google Interview test)

Μη αναγνωσμένη δημοσίευση από Spiros252 » 23 Ιούλ 2018, 02:18

ST48410 έγραψε:
23 Ιούλ 2018, 01:11
Αφού το σχήμα 1-35 επαναλαμβάνεται ακριβώς μετά και δεδομένου ότι δεν θα έχεις μόνο 100 νούμερα αλλά περισσότερα άρα και περισσότερες επαναλήψεις μήπως μπορεί να γίνει και εκεί κάποια οικονομία;
Ναι, είναι κάποια ακολουθία προφανώς και μπορείς να τη θέσεις μια φορά και να καλείται συνεχώς μέχρι να συμπληρωθούν τα νούμερα.
Αυτό έλεγα πριν με τον Χουργιατς για λύση μιας γραμμής. Βέβαια αυτός μπορεί να εννοούσε τίποτα άλλο ... :roll::D

Είχα κάνει μια παρόμοια (πολύ πιο δύσκολη) "άσκηση" στο παρελθόν, την οποία ίσως τη βάλω εδώ αργότερα.
«Η παρουσία μας επιλέγει από ένα τεράστιο σύνολο μόνο σύμπαντα συμβατά με την ύπαρξή μας.
Αν και είμαστε μικροί και ασήμαντοι σε κοσμικό επίπεδο, αυτό μας κάνει κατά κάποιο τρόπο, κύριους της δημιουργίας»
.
Stephen Hawking

Nameless Ghoul

Re: φιζζ - μπαζζ (Google Interview test)

Μη αναγνωσμένη δημοσίευση από Nameless Ghoul » 23 Ιούλ 2018, 10:14

nick έγραψε:
23 Ιούλ 2018, 01:36
Μια λυση ειναι να εχεις 2 μεταβλητές και να τις αυξάνεις κατά 659 και 947 αντιστοιχα, η σειρα που τις αυξανεις εχει σημασια ωστε τα νούμερα να εμφανίζονται ταξινομημένα. οταν συναντιούνται εχεις φιζζβαζζ. το καλο ειναι οτι δεν χρειαζεται να ελεγξεις αν διαιρειται με 659,947.

659,
947,
659*2,
947*2,
659*3,
659*4,

947*3,
Ωραίος, πλησίασες ακόμα περισσότερο.

Πράγματι, αυτή είναι ακόμα καλύτερη λύση - για την ακρίβεια, η καλύτερη δυνατή (χωρίς παράλληλες επεξεργασίες). Για πες όμως, πως επιτυγχάνεις αυτήν τη "σωστή σειρά";

(Δεν είναι ερώτηση παγίδα, υπάρχει συγκεκριμένη απάντηση, και μάλιστα είναι σχετικά απλή.)

Nameless Ghoul

Re: φιζζ - μπαζζ (Google Interview test)

Μη αναγνωσμένη δημοσίευση από Nameless Ghoul » 23 Ιούλ 2018, 10:27

Αυτή είναι η βέλτιστη δυνατή λύση με χρήση mod, δηλαδή αυτή που πλησίασε περισσότερο ο shrike:

Κώδικας: Επιλογή όλων

for(i =1; i < 10^7; i++)
{
auto isFizz = false;
auto isBuzz = false;
if (i % 659 == 0) { isFizz = true; }
if (i % 947 == 0) { isBuzz = true; }
if (isFizz) { cout << "fizz"; }
if (isBuzz) { cout << "buzz"; }
if ( !(isFizz || isBuzz)) { cout << i; }
cout << " ";
}

Nameless Ghoul

Re: φιζζ - μπαζζ (Google Interview test)

Μη αναγνωσμένη δημοσίευση από Nameless Ghoul » 23 Ιούλ 2018, 10:35

Αυτή είναι η βέλτιστη δυνατή λύση χωρίς χρήση mod, δηλαδή αυτή που πλησίασε περισσότερο ο nick:

Κώδικας: Επιλογή όλων

auto nextMult659 = 659;
auto nextMult947 = 947;
for(i =1; i < 10^7; i++)
{
auto isMult = false;
if (i == nextMult659)
 {
 cout << "fizz";
 isMult = true;
 nextMult659 += 659;
 }
if (i == nextMult947)
 {
 cout << "buzz";
 isMult = true;
 nextMult947 += 947;
 } 
if (!isMult) { cout << i; }
cout << " ";
}

Nameless Ghoul

Re: φιζζ - μπαζζ (Google Interview test)

Μη αναγνωσμένη δημοσίευση από Nameless Ghoul » 23 Ιούλ 2018, 10:37

H τελευταία είναι πιο γρήγορη, γιατί οι προσθέσεις είναι πιο γρήγορες από τις διαιρέσεις (το mod είναι πράξη διαίρεσης)

Απάντηση


  • Παραπλήσια Θέματα
    Απαντήσεις
    Προβολές
    Τελευταία δημοσίευση

Επιστροφή στο “Μαθηματικοί Γρίφοι”

Phorum.com.gr : Αποποίηση Ευθυνών