Praxis — Klausur-Aufgaben

1. 1) Komplexität bestimmen. Was ist die O-Notation von:

   for (let i = 0; i < n; i++)
     for (let j = i; j < n; j++)
       sum += arr[i] * arr[j];

   Lösung: O(n²) — innere Schleife läuft im Schnitt n/2 mal, also n·n/2 = O(n²).
2. 2) Binäre Suche implementieren. Iterativ, nicht rekursiv. Sortiertes Array.
   Lösung:Siehe Code in Kapitel 4. lo, hi, mid mit lo <= hi.
3. 3) Sortierung wählen. Du hast 100 Mio Datensätze, die nicht alle in den RAM passen. Welcher Sortieralgorithmus?
   Lösung: External Merge Sort — Stücke in den RAM sortieren, dann mit Merge zusammenführen. Kein In-Memory-Algorithmus reicht.
4. 4) Doppelte finden. Gib das erste duplizierte Element in einer Liste zurück.

   function findFirstDup(arr) {
     const seen = new Set();
     for (const x of arr) {
       if (seen.has(x)) return x;
       seen.add(x);
     }
     return null;
   }

   O(n) Zeit, O(n) Speicher.
5. 5) BFS-Schritte. Graph: A→B, A→C, B→D, C→D, D→E. BFS von A.
   Lösung: Reihenfolge: A, B, C, D, E. Kürzester Weg A→E hat 3 Kanten.
6. 6) Fibonacci ohne Rekursion. O(n) Zeit, O(1) Speicher.

   function fib(n) {
     let a = 0, b = 1;
     for (let i = 0; i < n; i++) [a, b] = [b, a + b];
     return a;
   }

7. 7) Anagramm-Check. Sind "listen" und "silent" Anagramme?
   Lösung:

   function isAnagram(a, b) {
     const sort = s => s.split("").sort().join("");
     return sort(a) === sort(b);
   }

   Alternative: Buchstaben zählen mit Map (O(n) statt O(n log n)).