Analyse des FizzBuzz-Problems

Problembeschreibung

FizzBuzz ist eine klassische Programmieraufgabe, die häufig in technischen Interviews und zur Überprüfung grundlegender Programmierkenntnisse eingesetzt wird. Die Aufgabe besteht darin, eine Sequenz von Zahlen von 1 bis n zu generieren und dabei spezifische Regeln für die Teilbarkeit anzuwenden:

• Ist eine Zahl durch 3 teilbar, wird "Fizz" ausgegeben.
• Ist eine Zahl durch 5 teilbar, wird "Buzz" ausgegeben.
• Ist eine Zahl sowohl durch 3 als auch durch 5 teilbar, wird "FizzBuzz" ausgegeben.
• Trifft keine dieser Bedingungen zu, wird die Zahl selbst ausgegeben.

Obwohl die Aufgabe einfach erscheint, prüft sie grundlegende Konzepte wie Schleifen, Bedingungslogik, den Modulo-Operator (%), die korrekte Reihenfolge von Prüfungen sowie Aspekte der Testbarkeit (z.B. die Trennung von Logik und Ausgabe).

Formale Definition

Implementieren Sie eine Funktion fizzBuzz(n).

• Eingabe: Eine ganze Zahl n, typischerweise n >= 1.
• Ausgabe: Eine Sequenz (z.B. ein Array) der Länge n, deren Elemente entweder Zahlen oder Zeichenketten gemäß den oben genannten Regeln sind.

Behandlung von Randfällen

Eine wichtige Überlegung bei der Implementierung ist der Umgang mit ungültigen Eingaben. Es empfiehlt sich, diese explizit zu definieren.

• Pragmatischer Ansatz: Für ungültige Eingaben (z.B. n < 1 oder nicht-ganzzahlige Werte) wird eine leere Sequenz [] zurückgegeben. Dieser Ansatz vereinfacht Tests und die Wiederverwendung der Funktion.
• Strikter Ansatz: Bei ungültiger Eingabe wird ein Fehler ausgelöst (z.B. throw new TypeError(...)), um eine fehlerhafte Verwendung sofort zu signalisieren.

Die folgenden Beispiele verwenden den pragmatischen Ansatz.

Beispiel

Ein Aufruf von fizzBuzz(15) sollte die folgende Sequenz erzeugen: [1, 2, "Fizz", 4, "Buzz", "Fizz", 7, 8, "Fizz", "Buzz", 11, "Fizz", 13, 14, "FizzBuzz"]

Relevanz des Problems

FizzBuzz ist relevant, da es in kurzer Zeit mehrere fundamentale Programmierkenntnisse testet:

• Schleifenkonstrukte: Iteration über einen definierten Zahlenbereich.
• Bedingte Anweisungen: Verwendung von if / else if / else.
• Modulo-Operator: Prüfung der Teilbarkeit über den Rest 0.
• Logische Operatoren: Insbesondere der UND-Operator (&&) für kombinierte Bedingungen.
• Prüfreihenfolge: Sicherstellung, dass kombinierte Bedingungen (Teilbarkeit durch 3 und 5) korrekt vor den Einzelbedingungen geprüft werden, um logische Fehler zu vermeiden.

Implementierungsstrategien

Empfehlung: Trennung von Logik und Ausgabe

Für eine hohe Code-Qualität, insbesondere im Hinblick auf die Testbarkeit, ist es sinnvoll, die Generierung der Daten von deren Ausgabe (z.B. via console.log) zu trennen. Die Kernfunktion sollte ein Array zurückgeben. Eine separate Wrapper-Funktion kann dann die Ausgabe übernehmen.

Logik-Funktion (Testbar)

function fizzBuzz(num) {
  if (!Number.isInteger(num) || num < 1) {
    return [];
  }

  const result = [];
  for (let i = 1; i <= num; i++) {
    let output = "";
    if (i % 3 === 0) {
      output += "Fizz";
    }
    if (i % 5 === 0) {
      output += "Buzz";
    }
    result.push(output || i);
  }
  return result;
}

Wrapper für die Ausgabe

function printFizzBuzz(num) {
  const results = fizzBuzz(num);
  for (const value of results) {
    console.log(value);
  }
}

Alternative Lösungsansätze

Klassische Lösung mit if/else

Bei diesem Ansatz ist die korrekte Prüfreihenfolge entscheidend. Die spezifischste Bedingung (i % 15 === 0) muss zuerst geprüft werden.

function fizzBuzzClassic(num) {
  if (!Number.isInteger(num) || num < 1) {
    return [];
  }

  const result = [];
  for (let i = 1; i <= num; i++) {
    if (i % 15 === 0) {
      result.push("FizzBuzz");
    } else if (i % 3 === 0) {
      result.push("Fizz");
    } else if (i % 5 === 0) {
      result.push("Buzz");
    } else {
      result.push(i);
    }
  }
  return result;
}

Hinweis: i % 15 === 0 ist eine optimierte Form von i % 3 === 0 && i % 5 === 0.

Lösung über Mustererkennung (Zyklus-Ansatz)

Die FizzBuzz-Sequenz wiederholt sich alle 15 Zahlen (das kleinste gemeinsame Vielfache von 3 und 5). Dieses Muster kann vorab berechnet und zur Generierung der Ausgabe genutzt werden.

function fizzBuzzPattern(num) {
  if (!Number.isInteger(num) || num < 1) {
    return [];
  }

  const pattern = [
    null, null, "Fizz", null, "Buzz", "Fizz",
    null, null, "Fizz", "Buzz", null, "Fizz",
    null, null, "FizzBuzz",
  ];

  return Array.from({ length: num }, (_, index) => {
    const i = index + 1;
    return pattern[index % 15] ?? i;
  });
}

Dieser Ansatz demonstriert ein Verständnis für zyklische Muster in Algorithmen.

Implementierung ohne Modulo-Operator

Falls der Modulo-Operator nicht verwendet werden darf, kann die Logik über Zähler abgebildet werden.

function fizzBuzzWithCounters(num) {
  if (!Number.isInteger(num) || num < 1) {
    return [];
  }

  let counter3 = 0;
  let counter5 = 0;
  const result = [];

  for (let i = 1; i <= num; i++) {
    counter3++;
    counter5++;
    let output = "";

    if (counter3 === 3) {
      output += "Fizz";
      counter3 = 0;
    }
    if (counter5 === 5) {
      output += "Buzz";
      counter5 = 0;
    }

    result.push(output || i);
  }
  return result;
}

Erweiterbare, generische Lösung

Eine fortgeschrittene Implementierung abstrahiert die Regeln in eine Konfigurationsstruktur (z.B. eine Map oder ein Objekt), um die Funktion leicht erweiterbar zu machen.

function fizzBuzzGeneric(num, rules = { 3: "Fizz", 5: "Buzz" }) {
  if (!Number.isInteger(num) || num < 1) {
    return [];
  }

  return Array.from({ length: num }, (_, index) => {
    const i = index + 1;
    let output = "";

    for (const [divisor, word] of Object.entries(rules)) {
      if (i % Number(divisor) === 0) {
        output += word;
      }
    }

    return output || i;
  });
}

// Beispiel mit erweiterter Regel:
// fizzBuzzGeneric(21, { 3: 'Fizz', 5: 'Buzz', 7: 'Bang' });

Komplexitätsanalyse

• Standard-Implementierung:
  • Zeitkomplexität: O(n), da jede Zahl einmal durchlaufen wird.
  • Speicherkomplexität: O(n) bei Rückgabe eines Arrays.
• Variante mit reiner Ausgabe:
  • Speicherkomplexität: O(1), da die Werte direkt ausgegeben und nicht gespeichert werden.
• Generische Implementierung mit m Regeln:
  • Zeitkomplexität: O(n * m), da für jede Zahl alle Regeln geprüft werden.

Testfälle

Ein minimales Set an Testfällen sollte Folgendes abdecken:

Häufige Fehlerquellen

1. Falsche Prüfreihenfolge: Wird i % 3 oder i % 5 vor i % 15 geprüft, wird der "FizzBuzz"-Fall nie erreicht.
   code[ copy ]

   // FALSCH: Der Fall i % 15 === 0 wird nie erreicht.
   if (i % 3 === 0) { /* ... */ }
   else if (i % 5 === 0) { /* ... */ }
   else if (i % 15 === 0) { /* ... */ }
   

2. Globale Variablen: Vergessene let- oder const-Deklarationen in Schleifen können zu unbeabsichtigtem globalen Scope führen.
3. Off-by-One-Fehler: Falsche Schleifengrenzen, z.B. Start bei 0 statt 1 oder Ende bei < num statt <= num.

Empfehlungen für Interviews

1. Randfälle ansprechen: Klären Sie kurz den Umgang mit ungültigen Eingaben und begründen Sie Ihre Entscheidung.
2. Simpel starten: Beginnen Sie mit einer einfachen, korrekten Lösung und diskutieren Sie anschließend mögliche Verbesserungen (z.B. Lesbarkeit, Testbarkeit, Generalisierung).
3. Prüfreihenfolge begründen: Erklären Sie, warum die Prüfung auf Teilbarkeit durch 15 (oder 3 und 5) Priorität haben muss.
4. Testbarkeit betonen: Bevorzugen Sie eine Funktion, die Daten zurückgibt, anstatt sie direkt auszugeben, und erläutern Sie die Vorteile.

Weiterführende Ressourcen

• Why FizzBuzz is Used in Interviews: https://wiki.c2.com/?FizzBuzzTest
• 100+ Ways to Solve FizzBuzz: https://ditam.github.io/posts/fizzbuzz/
• FizzBuzz Enterprise Edition (Satire): https://github.com/EnterpriseQualityCoding/FizzBuzzEnterpriseEdition