Wzorce Two Pointers HashMap Stack na rozmowy kwalifikacyjne

Trzy kluczowe wzorce dla zadań algorytmicznych na rozmowach kwalifikacyjnych

Wzorzec Dwa Wskaźniki wykorzystuje dwa wskaźniki do jednokrotnego przejścia przez dane. Zmniejsza to złożoność z O(n²) do O(n) w zadaniach dotyczących palindromów, par elementów i filtracji.

Dwa główne warianty:

• Left-Right (naprzeciw siebie): left na indeksie 0, right na s.length - 1. Przesuwają się ku centrum w celu symetrycznych sprawdzeń.
• Slow-Fast: slow aktualizuje wynik, fast skanuje do przodu w celu usunięcia duplikatów lub przesunięcia elementów.

Przykład: sprawdzanie palindromu bez uwzględniania znaków niealfabetycznych.

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: szybkie wyszukiwanie i grupowanie

HashMap (obiekt lub Map) przechowuje pary klucz-wartość dla dostępu O(1). Stosowany do liczenia częstotliwości, sprawdzania unikalności, anagramów i buforowania.

Algorytm: jedno przejście do wypełnienia, drugie do wyszukiwania. Unika zagnieżdżonych pętli.

Przykład: pierwszy unikalny znak w ciągu.

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: przetwarzanie struktur LIFO

Stack działa na zasadzie Last In - First Out. Tablica z push/pop idealna do sprawdzania nawiasów, rekursji bez stosu wywołań i cofania.

Przykład: walidacja sekwencji nawiasów.

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

Kiedy zastosować każdy wzorzec

Przed kodowaniem sprawdź oznaki:

Dwa Wskaźniki:

• Tablica/ciąg z symetrią (palindrom).
• Wyszukiwanie pary elementów.
• Posortowana tablica.
• Porównanie z końców.

HashMap:

• Liczenie częstotliwości lub unikalności.
• Anagramy, grupowanie.
• Sprawdzanie obecności elementu.
• Nieposortowane dane z szybkim wyszukiwaniem.

Stack:

• Nawiasy lub zagnieżdżone struktury.
• Logika LIFO (ostatni zamknięty jako pierwszy).
• Cofanie wstecz lub historia stanów.

Co jest ważne

• Dwa Wskaźniki oszczędzają przejścia przez dane, idealne dla struktur liniowych.
• HashMap zapewnia dostęp O(1), zastępuje zagnieżdżone pętle na dwa przejścia.
• Stack gwarantuje prawidłowy porządek przetwarzania zagnieżdżenia bez rekursji.
• Praktyka: rozwiązuj 10 zadań na wzorzec, następnie kombinuj.

Te wzorce obejmują większość zadań na LeetCode/Codewars poziomu Easy/Medium. Regularne stosowanie kształtuje intuicję dla rozmów kwalifikacyjnych senior-level.

— Editorial Team