Vzory Two Pointers HashMap Stack pro pohovory

Tři klíčové vzory pro algoritmické úlohy na pohovorech

Vzor Dva ukazatele používá dva ukazatele pro jednorázový průchod daty. To snižuje složitost z O(n²) na O(n) v úlohách na palindromy, páry prvků a filtraci.

Dva hlavní varianty:

• Left-Right (naproti): left na indexu 0, right na s.length - 1. Pohybují se k centru pro symetrické kontroly.
• Slow-Fast: slow aktualizuje výsledek, fast skenuje dopředu pro odstranění duplicit nebo přesunutí prvků.

Příklad: kontrola palindromu bez zohlednění nealfanumerických znaků.

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: rychlé vyhledávání a seskupování

HashMap (objekt nebo Map) ukládá dvojice klíč-hodnota pro přístup s O(1). Používá se pro počítání frekvencí, kontrolu unikátnosti, anagramy a ukládání do mezipaměti.

Algoritmus: jeden průchod pro naplnění, druhý pro vyhledávání. Vyhýbá se vnořeným cyklům.

Příklad: první unikátní znak v řetězci.

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: zpracování LIFO-struktur

Stack pracuje na principu Last In - First Out. Pole s push/pop je ideální pro kontrolu závorek, rekurzi bez zásobníku volání a návraty.

Příklad: validace závorkové posloupnosti.

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

Kdy použít každý vzor

Před kódováním zkontrolujte znaky:

Dva ukazatele:

• Pole/řetězec se symetrií (palindrom).
• Hledání párů prvků.
• Seřazené pole.
• Porovnávání od konců.

HashMap:

• Počítání frekvencí nebo unikátnosti.
• Anagramy, seskupování.
• Kontrola přítomnosti prvku.
• Neseřazená data s rychlým vyhledáváním.

Stack:

• Závorky nebo vnořené struktury.
• LIFO-logika (poslední uzavřený první).
• Návrat zpět nebo historie stavů.

Co je důležité

• Dva ukazatele šetří průchody daty, ideální pro lineární struktury.
• HashMap poskytuje přístup O(1), nahrazuje vnořené cykly dvěma průchody.
• Stack zaručuje správný pořadí zpracování vnoření bez rekurze.
• Praxe: řešte 10 úloh na vzor, pak kombinujte.

Tyto vzory pokrývají většinu úloh na LeetCode/Codewars úrovně Easy/Medium. Pravidelné používání vytváří intuici pro seniorní pohovory.

— Editorial Team