Muster Two Pointers HashMap Stack für Interviews

Drei unverzichtbare Muster für Algo-Interviews

Das Zwei-Zeiger-Muster nutzt zwei Zeiger, um Daten in einem Durchgang zu scannen. Es reduziert die Komplexität von O(n²) auf O(n) bei Palindromen, Elementpaaren und Filteraufgaben.

Zwei Hauptvarianten:

• Links-Rechts (konvergierend): links startet bei Index 0, rechts bei s.length - 1. Bewege sie zum Zentrum für Symmetrieprüfungen.
• Langsam-Schnell: langsam aktualisiert das Ergebnis, schnell scannt voraus für Duplikatentfernung oder Elementverschiebung.

Beispiel: Prüfung eines Palindroms unter Ignorieren nicht-alphabetischer Zeichen.

const isPalindrome = (s) => {
  let left = 0;
  let right = s.length - 1;

  while (left < right) {
    if (s[left] !== s[right]) {
      return false;
    }
    left++;
    right--;
  }

  return true;
};

console.log(isPalindrome("madam")); // true
console.log(isPalindrome("abc")); // false

HashMap: Schnelle Abfragen und Gruppierung

HashMap (Objekt oder Map) speichert Schlüssel-Wert-Paare für O(1)-Zugriff. Ideal für Häufigkeitszählungen, Einzigartigkeitprüfungen, Anagramme und Caching.

Algorithmus: Ein Durchgang zum Aufbau, zweiter zur Abfrage. Vermeidet verschachtelte Schleifen komplett.

Beispiel: Erstes einzigartiges Zeichen in einem String.

const firstUniqueChar = (s) => {
  const map = {};

  for (const char of s) {
    map[char] = (map[char] || 0) + 1;
  }

  for (const char of s) {
    if (map[char] === 1) {
      return char;
    }
  }

  return null;
};

console.log(firstUniqueChar("banana")); // 'b'
console.log(firstUniqueChar("aabbc")); // 'c'

Stack: Umgang mit LIFO-Strukturen

Stack folgt Last In - First Out. Ein Array mit push/pop glänzt bei Klammerprüfungen, rekursionsfreien Stacks und Backtracking.

Beispiel: Validierung von Klammersequenzen.

const isValidBrackets = (s) => {
  const stack = [];
  const map = {
    ')': '(',
    ']': '[',
    '}': '{' 
  };

  for (const char of s) {
    if ('([{'.includes(char)) {
      stack.push(char);
    } else {
      const last = stack.pop();
      if (last !== map[char]) {
        return false;
      }
    }
  }

  return stack.length === 0;
};

console.log(isValidBrackets("{[()()]}")); // true
console.log(isValidBrackets("{[(])}")); // false

Wann welches Muster einsetzen

Bevor du codest, erkenne diese Hinweise:

Zwei Zeiger:

• Array/String mit Symmetrie (Palindrom).
• Suche nach Elementpaaren.
• Sortiertes Array.
• Vergleich von beiden Enden.

HashMap:

• Zählen von Häufigkeiten oder Einzigartigkeit.
• Anagramme, Gruppierung.
• Prüfung auf Elementexistenz.
• Unsortierte Daten mit schnellen Abfragen.

Stack:

• Klammern oder verschachtelte Strukturen.
• LIFO-Logik (zuletzt geöffnetes wird zuerst geschlossen).
• Backtracking oder Zustandsverlauf.

Wichtige Erkenntnisse

• Zwei Zeiger spart Durchgänge, perfekt für lineare Strukturen.
• HashMap liefert O(1)-Zugriff, tauscht verschachtelte Schleifen gegen zwei Durchgänge.
• Stack gewährleistet korrekte Verschachtelungsreihenfolge ohne Rekursion.
• Übung: Löse 10 Probleme pro Muster, dann mische sie.

Diese Muster meistern die meisten LeetCode/Codewars Easy/Medium-Aufgaben. Regelmäßige Anwendung schafft Interview-Intuition auf Senior-Niveau.

— Editorial Team