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

[ST48410]

Δεύτερη απόπειρα. Δεν ξέρω αν προγραμματιστικά είναι ανοησία.

1. Διαιρώ με 659. Αν 0 γράφω φιζζ. Αν όχι 0 γράφω κενό και πάω στο 2
2. Διαιρώ το ίδιο νούμερο με 647. Αν 0 γράφω μπαζ δίπλα σε αυτό που έγραψα στο 1. Αν όχι 0 πάω στο επόμενο νούμερο

[Nameless Ghoul]

Δεύτερη απόπειρα. Δεν ξέρω αν προγραμματιστικά είναι ανοησία.

1. Διαιρώ με 659. Αν 0 γράφω φιζζ. Αν όχι 0 γράφω κενό και πάω στο 2
2. Διαιρώ το ίδιο νούμερο με 647. Αν 0 γράφω μπαζ δίπλα σε αυτό που έγραψα στο 1. Αν όχι 0 πάω στο επόμενο νούμερο

Πλησιασες πολύ. Μόνο μια λεπτομέρεια σου ξέφυγε.

[Spiros252]

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

<?php

$lim = pow(10,7); 

for ($n = 1; $r1 <= $lim; $n++) {
    
  $r1 = $n * 659; 
  $r2 = $n * 947; 
  $r3 = $n * (659 * 947); 
  
  if ($r1 <= $lim) { $array['1'."$n"] = $r1; }
  if ($r2 <= $lim) { $array['2'."$n"] = $r2; }
  if ($r3 <= $lim) { $array['3'."$n"] = $r3; }

}

asort($array);
  
foreach ($array as $r => $v) { 
	
	if (substr($r,0,1) == 1) { print "| $v | fizz <br />"; }
	if (substr($r,0,1) == 2) { print "| $v | buzz <br />"; }
  	if (substr($r,0,1) == 3) { print "| $v | fizz-buzz <br />"; }

}

?>

Επιδέχεται σίγουρα απλοποίησης, αλλά είμαι σε σωστό δρόμο; Πφφ..

[ST48410]

Δεύτερη απόπειρα. Δεν ξέρω αν προγραμματιστικά είναι ανοησία.

1. Διαιρώ με 659. Αν 0 γράφω φιζζ. Αν όχι 0 γράφω κενό και πάω στο 2
2. Διαιρώ το ίδιο νούμερο με 647. Αν 0 γράφω μπαζ δίπλα σε αυτό που έγραψα στο 1. Αν όχι 0 πάω στο επόμενο νούμερο

Πλησιασες πολύ. Μόνο μια λεπτομέρεια σου ξέφυγε.

να τυπώσω τις λέξεις από τα βήματα 1 και 2;

[Χουργιατς]

Γράφω σε απλά ελληνικά τη δική μου λύση:

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

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

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

Υποψιάζομαι όμως ότι ο Χουργιατς έχει άλλη πολύ έξυπνη λύση την οποία έχω ψυλλιαστει και την ψάχνω. Υποψιάζομαι ότι θα γίνεται με 1 γραμμή κώδικα..

[ST48410]

Υποψιάζομαι όμως ότι ο Χουργιατς έχει άλλη πολύ έξυπνη λύση την οποία έχω ψυλλιαστει και την ψάχνω. Υποψιάζομαι ότι θα γίνεται με 1 γραμμή κώδικα..

και ο Nameless Ghoul αν κατάλαβα καλά μίλησε για 2 πράξεις όχι για 3.
Ο πολλαπλασιασμός απαιτεί λιγότερη υπολογιστική ισχύ από την διαίρεση επειδή δεν έχεις να υπολογίσεις υπόλοιπο;
Η τελική ταξινόμηση των αριθμών από τους 3 πίνακες είναι εύκολη;

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

[shrike]

Γράφω σε απλά ελληνικά τη δική μου λύση:

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

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

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

Υποψιάζομαι όμως ότι ο Χουργιατς έχει άλλη πολύ έξυπνη λύση την οποία έχω ψυλλιαστει και την ψάχνω. Υποψιάζομαι ότι θα γίνεται με 1 γραμμή κώδικα..

Σπύρο, μου φαίνεται λίγο δύσκολο να είναι πιο γρήγορο αυτό που προτείνεις (μια που το θέμα είναι η ταχύτητα σύμφωνα με τον Nameless Ghoul). Κυρίως λόγω του sorting που θες να κάνεις συνδυάζοντας 4 πίνακες, ο ένας εκ των οποίων έχει 10.000.000 στοιχεία.

Μπορώ να κάνω μια δοκιμή γι' αυτό που λες, στις άλλες τις δικές μου λύσεις που δοκίμασα πάντως, όντως η δεύτερη ήταν πιο γρήγορη (περίπου κατά 100ms) όπως είπε κι ο Ghoul.
Στο μεταξύ, χθες βράδυ σκεφτόμουν τη λύση στο... εχμμμ... ξες... αγαπημένο μέρος του Nameless Ghoul (παραδόξως εκεί μου 'ρχονται όλες οι εμπνεύσεις και έχω βρει πολλές φορές λύσεις σε πράματα που είχα μπλοκάρει) και σκέφτηκα κάτι άλλο, επειδή ακριβώς πιάστηκα από το hint του να κάνω αποθήκευση δεδομένων. Σκέφτηκα λοιπόν να τρέξω το βρόχο μια φορά μόνο μέχρι το 624073 και να κρατήσω τα αποτελέσματα (πότε είναι φιζζ, πότε μπαζζ κλπ) συν τη μία φορά που θα είναι φιζζμπαζ. Αυτό λογικά θα επαναλαμβάνεται για κάθε ομάδα των 624073 αριθμών (δηλ. από 624074 έως 2 * 624073 κλπ). Θέλει απλά να το οργανώσω λίγο στο μυαλό μου πώς θα το μετατρέψω σε κώδικα...

[ST48410]

Σκέφτηκα λοιπόν να τρέξω το βρόχο μια φορά μόνο μέχρι το 624073 και να κρατήσω τα αποτελέσματα (πότε είναι φιζζ, πότε μπαζζ κλπ) συν τη μία φορά που θα είναι φιζζμπαζ. Αυτό λογικά θα επαναλαμβάνεται για κάθε ομάδα των 624073 αριθμών (δηλ. από 624074 έως 2 * 624073 κλπ). Θέλει απλά να το οργανώσω λίγο στο μυαλό μου πώς θα το μετατρέψω σε κώδικα...

Πολύ καλή ιδέα. Αν διαιρέσεις το 10 στην 7 με το 624073 βρίσκεις πόσες φορές και με πια νούμερα πρέπει να πολλαπλασιάσεις την αρχική ομάδα

ΥΓ Το αρχικό ερώτημα μιλά για ακεραίους. Μήπως πρέπει κάπου στο τέλος να συμπεριλάβουμε και όλες τις αρνητικές λύσεις;

[shrike]

Σκέφτηκα λοιπόν να τρέξω το βρόχο μια φορά μόνο μέχρι το 624073 και να κρατήσω τα αποτελέσματα (πότε είναι φιζζ, πότε μπαζζ κλπ) συν τη μία φορά που θα είναι φιζζμπαζ. Αυτό λογικά θα επαναλαμβάνεται για κάθε ομάδα των 624073 αριθμών (δηλ. από 624074 έως 2 * 624073 κλπ). Θέλει απλά να το οργανώσω λίγο στο μυαλό μου πώς θα το μετατρέψω σε κώδικα...

Πολύ καλή ιδέα. Αν διαιρέσεις το 10 στην 7 με το 624073 βρίσκεις πόσες φορές και με πια νούμερα πρέπει να πολλαπλασιάσεις την αρχική ομάδα

ΥΓ Το αρχικό ερώτημα μιλά για ακεραίους. Μήπως πρέπει κάπου στο τέλος να συμπεριλάβουμε και όλες τις αρνητικές λύσεις;

Λέει από 1 έως 10^7, οπότε φαντάζομαι αφορά μόνο τους θετικούς.

[ST48410]

Σκέφτηκα λοιπόν να τρέξω το βρόχο μια φορά μόνο μέχρι το 624073 και να κρατήσω τα αποτελέσματα (πότε είναι φιζζ, πότε μπαζζ κλπ) συν τη μία φορά που θα είναι φιζζμπαζ. Αυτό λογικά θα επαναλαμβάνεται για κάθε ομάδα των 624073 αριθμών (δηλ. από 624074 έως 2 * 624073 κλπ). Θέλει απλά να το οργανώσω λίγο στο μυαλό μου πώς θα το μετατρέψω σε κώδικα...

Πολύ καλή ιδέα. Αν διαιρέσεις το 10 στην 7 με το 624073 βρίσκεις πόσες φορές και με πια νούμερα πρέπει να πολλαπλασιάσεις την αρχική ομάδα

ΥΓ Το αρχικό ερώτημα μιλά για ακεραίους. Μήπως πρέπει κάπου στο τέλος να συμπεριλάβουμε και όλες τις αρνητικές λύσεις;

Λέει από 1 έως 10^7, οπότε φαντάζομαι αφορά μόνο τους θετικούς.

Δίκιο έχεις. Δεν πρόσεξα καλά την αρχική διατύπωση.

[ST48410]

Το 624073 χωράει 16 φορές στον 10.000.000 αλλά έχει και υπόλοιπο 14832 συνεπώς πρέπει να εξεταστούν και τα φιζζ ή μπαζ που υπάρχουν εκεί.

για ν από 1 έως 624073
1. Διαιρώ με 659. Αν 0 γράφω φιζζ. Αν όχι 0 γράφω κενό και πάω στο 2
2. Διαιρώ το ίδιο νούμερο με 647. Αν 0 γράφω μπαζ δίπλα σε αυτό που έγραψα στο 1. Αν όχι 0 πάω στο επόμενο νούμερο
3. Πολλαπλασιάζω και τυπώνω διαδοχικά τα μέχρι τώρα αποτελέσματα x1 x2 χ3 κλπ έως χ17
4. Πετάω τα τελευταία νούμερα > 10.000.000

[shrike]

Το 624073 χωράει 16 φορές στον 10.000.000 αλλά έχει και υπόλοιπο 14832 συνεπώς πρέπει να εξεταστούν και τα φιζζ ή μπαζ που υπάρχουν εκεί.

Το αστείο είναι ότι το 'κανα, το έτρεξα, είναι όντως τραγικά πιο γρήγορο στον υπολογισμό των τιμών, αλλά τρώω κάποια σκαλώματα με την απόδοσή τους σε μεταβλητή (πόσο μάλλον με την εκτύπωση). Λογικά είναι κάποιο πρόβλημα της γλώσσας που χρησιμοποιίησα (VB6), πρέπει να μπουκώνει πολύ στη μετατροπή σε string (όπου δηλαδή πρέπει να προστεθούν τα "φιζζ" κλπ και δεν το βλέπει σαν αριθμό), δεν ξέρω...

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

Dim t(624073)
For r = 1 To 624072
    If r Mod 947 = 0 Then
        t(r) = " μπαζζ"
    ElseIf r Mod 659 = 0 Then
        t(r) = " φιζζ"
    End If
Next
t(624073) = " φιζζμπαζ": i = 0
For r = 1 To 10 ^ 7
    i = i + 1: If i > 624073 Then i = 1
    Print r & t(i)
Next

Κάτι τέτοιο, τέλος πάντων...

[Spiros252]

και ο Nameless Ghoul αν κατάλαβα καλά μίλησε για 2 πράξεις όχι για 3.
Ο πολλαπλασιασμός απαιτεί λιγότερη υπολογιστική ισχύ από την διαίρεση επειδή δεν έχεις να υπολογίσεις υπόλοιπο;
Η τελική ταξινόμηση των αριθμών από τους 3 πίνακες είναι εύκολη;

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

Μόνο 25.749 αριθμοί από τους 10.000.000 ανήκουν στα ζητούμενα αποτελέσματα.
Δεν έχω κέρδος όταν τους βρίσκω / παράγω κατευθείαν; αντί να διαιρώ 10.000.000 αριθμούς με δυο ή τρεις ;

[shrike]

και ο Nameless Ghoul αν κατάλαβα καλά μίλησε για 2 πράξεις όχι για 3.
Ο πολλαπλασιασμός απαιτεί λιγότερη υπολογιστική ισχύ από την διαίρεση επειδή δεν έχεις να υπολογίσεις υπόλοιπο;
Η τελική ταξινόμηση των αριθμών από τους 3 πίνακες είναι εύκολη;

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

Μόνο 25.749 αριθμοί από τους 10.000.000 ανήκουν στα ζητούμενα αποτελέσματα.
Δεν έχω κέρδος όταν τους βρίσκω / παράγω κατευθείαν; αντί να διαιρώ 10.000.000 αριθμούς με δυο ή τρεις ;

Ναι ρε συ, οκ, κατανοητό. Δεν θα διαιρείς με 10.000.000, αλλά θα έχεις κάνει μια σειρά πολλαπλασιασμούς για να βρεις τους 25.749, να τους αποθηκεύσεις όπως λες σε ένα array (φαντάζομαι) και στη συνέχεια, θα πρέπει να κάνεις νέες συγκρίσεις αυτών με τους 10.000.000 για να δεις πότε ισχύει τι. Πώς γίνεται αυτό πιο γρήγορα;

Παρεμπιπτόντως, το τελευταίο που έγραψα είναι περίπου 6 φορές πιο γρήγορο από το προηγούμενο... "γρήγορό" μου.
Αν δεν σκάλωνα και στο θέμα των strings που λέω, νομίζω θα ήταν η λύση. Ίσως σε μια πιο "σοβαρή" γλώσσα, να είναι όντως αυτή η λύση.

[Spiros252]

Σπύρο, μου φαίνεται λίγο δύσκολο να είναι πιο γρήγορο αυτό που προτείνεις (μια που το θέμα είναι η ταχύτητα σύμφωνα με τον Nameless Ghoul). Κυρίως λόγω του sorting που θες να κάνεις συνδυάζοντας 4 πίνακες, ο ένας εκ των οποίων έχει 10.000.000 στοιχεία.

Γιατί βρε; Ποιος πίνακας έχει 10 μύρια; Οι 3 πίνακές μου έχουν 25.749 στοιχεία συνολικά.