Проходьте технічні співбесіди як профі: ключові алгоритми, що гарантують успіх!

def two_sum(nums: list[int], target: int) -> list[int]:
    seen: dict[int, int] = {}  # value -> index

    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i

    return []

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>(); // value -> index

    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (seen.containsKey(complement)) {
            return new int[] { seen.get(complement), i };
        }
        seen.put(nums[i], i);
    }

    return new int[0];
}

function twoSum(array $nums, int $target): array
{
    $seen = []; // value => index

    foreach ($nums as $i => $num) {
        $complement = $target - $num;
        if (isset($seen[$complement])) {
            return [$seen[$complement], $i];
        }
        $seen[$num] = $i;
    }

    return [];
}

func twoSum(nums []int, target int) []int {
    seen := make(map[int]int) // value -> index

    for i, num := range nums {
        complement := target - num
        if j, ok := seen[complement]; ok {
            return []int{j, i}
        }
        seen[num] = i
    }

    return []int{}
}

def max_profit(prices: list[int]) -> int:
    min_price = float("inf")
    max_profit = 0

    for price in prices:
        if price < min_price:
            min_price = price
        elif price - min_price > max_profit:
            max_profit = price - min_price

    return max_profit

public int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE;
    int maxProfit = 0;

    for (int price : prices) {
        if (price < minPrice) {
            minPrice = price;
        } else if (price - minPrice > maxProfit) {
            maxProfit = price - minPrice;
        }
    }

    return maxProfit;
}

function maxProfit(array $prices): int
{
    $minPrice = PHP_INT_MAX;
    $maxProfit = 0;

    foreach ($prices as $price) {
        if ($price < $minPrice) {
            $minPrice = $price;
        } elseif ($price - $minPrice > $maxProfit) {
            $maxProfit = $price - $minPrice;
        }
    }

    return $maxProfit;
}

func maxProfit(prices []int) int {
    minPrice := math.MaxInt
    maxProfit := 0

    for _, price := range prices {
        if price < minPrice {
            minPrice = price
        } else if price-minPrice > maxProfit {
            maxProfit = price - minPrice
        }
    }

    return maxProfit
}

def max_sub_array(nums: list[int]) -> int:
    current_sum = max_sum = nums[0]

    for num in nums[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)

    return max_sum

public int maxSubArray(int[] nums) {
    int currentSum = nums[0];
    int maxSum = nums[0];

    for (int i = 1; i < nums.length; i++) {
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        maxSum = Math.max(maxSum, currentSum);
    }

    return maxSum;
}

function maxSubArray(array $nums): int
{
    $currentSum = $nums[0];
    $maxSum = $nums[0];

    for ($i = 1; $i < count($nums); $i++) {
        $currentSum = max($nums[$i], $currentSum + $nums[$i]);
        $maxSum = max($maxSum, $currentSum);
    }

    return $maxSum;
}

func maxSubArray(nums []int) int {
    currentSum, maxSum := nums[0], nums[0]

    for i := 1; i < len(nums); i++ {
        currentSum = max(nums[i], currentSum+nums[i])
        maxSum = max(maxSum, currentSum)
    }

    return maxSum
}
// Go 1.21+ has built-in max(); earlier versions need a tiny helper.

def reverse_string(s: list[str]) -> None:
    left, right = 0, len(s) - 1
    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1

public void reverseString(char[] s) {
    int left = 0;
    int right = s.length - 1;

    while (left < right) {
        char tmp = s[left];
        s[left] = s[right];
        s[right] = tmp;
        left++;
        right--;
    }
}

function reverseString(array &$s): void
{
    $left = 0;
    $right = count($s) - 1;

    while ($left < $right) {
        [$s[$left], $s[$right]] = [$s[$right], $s[$left]];
        $left++;
        $right--;
    }
}

func reverseString(s []byte) {
    left, right := 0, len(s)-1

    for left < right {
        s[left], s[right] = s[right], s[left]
        left++
        right--
    }
}

from collections import Counter

def is_anagram(s: str, t: str) -> bool:
    return Counter(s) == Counter(t)

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;

    int[] counts = new int[26];
    for (int i = 0; i < s.length(); i++) {
        counts[s.charAt(i) - 'a']++;
        counts[t.charAt(i) - 'a']--;
    }

    for (int c : counts) if (c != 0) return false;
    return true;
}

function isAnagram(string $s, string $t): bool
{
    if (strlen($s) !== strlen($t)) return false;

    return count_chars($s, 1) === count_chars($t, 1);
}

func isAnagram(s, t string) bool {
    if len(s) != len(t) {
        return false
    }

    var counts [26]int
    for i := 0; i < len(s); i++ {
        counts[s[i]-'a']++
        counts[t[i]-'a']--
    }

    for _, c := range counts {
        if c != 0 {
            return false
        }
    }
    return true
}

def longest_palindrome(s: str) -> str:
    if len(s) < 2:
        return s

    start, max_len = 0, 1

    def expand(left: int, right: int) -> None:
        nonlocal start, max_len
        while left >= 0 and right < len(s) and s[left] == s[right]:
            if right - left + 1 > max_len:
                start = left
                max_len = right - left + 1
            left -= 1
            right += 1

    for i in range(len(s)):
        expand(i, i)      # odd
        expand(i, i + 1)  # even

    return s[start:start + max_len]

public String longestPalindrome(String s) {
    if (s.length() < 2) return s;

    int[] best = {0, 1}; // {start, maxLen}
    for (int i = 0; i < s.length(); i++) {
        expand(s, i, i, best);
        expand(s, i, i + 1, best);
    }
    return s.substring(best[0], best[0] + best[1]);
}

private void expand(String s, int left, int right, int[] best) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        if (right - left + 1 > best[1]) {
            best[0] = left;
            best[1] = right - left + 1;
        }
        left--;
        right++;
    }
}

function longestPalindrome(string $s): string
{
    if (strlen($s) < 2) return $s;

    $start = 0;
    $maxLen = 1;

    $expand = function (int $left, int $right) use ($s, &$start, &$maxLen): void {
        while ($left >= 0 && $right < strlen($s) && $s[$left] === $s[$right]) {
            if ($right - $left + 1 > $maxLen) {
                $start = $left;
                $maxLen = $right - $left + 1;
            }
            $left--;
            $right++;
        }
    };

    for ($i = 0; $i < strlen($s); $i++) {
        $expand($i, $i);
        $expand($i, $i + 1);
    }

    return substr($s, $start, $maxLen);
}

func longestPalindrome(s string) string {
    if len(s) < 2 {
        return s
    }

    start, maxLen := 0, 1
    expand := func(left, right int) {
        for left >= 0 && right < len(s) && s[left] == s[right] {
            if right-left+1 > maxLen {
                start = left
                maxLen = right - left + 1
            }
            left--
            right++
        }
    }

    for i := 0; i < len(s); i++ {
        expand(i, i)
        expand(i, i+1)
    }

    return s[start : start+maxLen]
}

def contains_duplicate(nums: list[int]) -> bool:
    return len(set(nums)) != len(nums)

public boolean containsDuplicate(int[] nums) {
    Set<Integer> seen = new HashSet<>();
    for (int num : nums) {
        if (!seen.add(num)) return true; // add() returns false if already present
    }
    return false;
}

function containsDuplicate(array $nums): bool
{
    return count(array_unique($nums)) !== count($nums);
}

func containsDuplicate(nums []int) bool {
    seen := make(map[int]struct{})
    for _, num := range nums {
        if _, ok := seen[num]; ok {
            return true
        }
        seen[num] = struct{}{}
    }
    return false
}

from collections import defaultdict

def group_anagrams(strs: list[str]) -> list[list[str]]:
    groups: dict[str, list[str]] = defaultdict(list)
    for s in strs:
        key = "".join(sorted(s))
        groups[key].append(s)
    return list(groups.values())

public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> groups = new HashMap<>();

    for (String str : strs) {
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars);
        groups.computeIfAbsent(key, k -> new ArrayList<>()).add(str);
    }

    return new ArrayList<>(groups.values());
}

function groupAnagrams(array $strs): array
{
    $groups = [];

    foreach ($strs as $str) {
        $chars = str_split($str);
        sort($chars);
        $key = implode("", $chars);
        $groups[$key][] = $str;
    }

    return array_values($groups);
}

func groupAnagrams(strs []string) [][]string {
    groups := make(map[string][]string)

    for _, str := range strs {
        chars := []byte(str)
        sort.Slice(chars, func(i, j int) bool { return chars[i] < chars[j] })
        key := string(chars)
        groups[key] = append(groups[key], str)
    }

    result := make([][]string, 0, len(groups))
    for _, g := range groups {
        result = append(result, g)
    }
    return result
}

def find_max_average(nums: list[int], k: int) -> float:
    window_sum = sum(nums[:k])
    max_sum = window_sum

    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]
        max_sum = max(max_sum, window_sum)

    return max_sum / k

public double findMaxAverage(int[] nums, int k) {
    int windowSum = 0;
    for (int i = 0; i < k; i++) windowSum += nums[i];

    int maxSum = windowSum;
    for (int i = k; i < nums.length; i++) {
        windowSum += nums[i] - nums[i - k];
        maxSum = Math.max(maxSum, windowSum);
    }

    return (double) maxSum / k;
}

function findMaxAverage(array $nums, int $k): float
{
    $windowSum = array_sum(array_slice($nums, 0, $k));
    $maxSum = $windowSum;

    for ($i = $k; $i < count($nums); $i++) {
        $windowSum += $nums[$i] - $nums[$i - $k];
        $maxSum = max($maxSum, $windowSum);
    }

    return $maxSum / $k;
}

func findMaxAverage(nums []int, k int) float64 {
    windowSum := 0
    for i := 0; i < k; i++ {
        windowSum += nums[i]
    }

    maxSum := windowSum
    for i := k; i < len(nums); i++ {
        windowSum += nums[i] - nums[i-k]
        if windowSum > maxSum {
            maxSum = windowSum
        }
    }

    return float64(maxSum) / float64(k)
}

def length_of_longest_substring(s: str) -> int:
    seen: set[str] = set()
    left = 0
    max_len = 0

    for right, ch in enumerate(s):
        while ch in seen:
            seen.remove(s[left])
            left += 1
        seen.add(ch)
        max_len = max(max_len, right - left + 1)

    return max_len

public int lengthOfLongestSubstring(String s) {
    Set<Character> seen = new HashSet<>();
    int left = 0;
    int maxLen = 0;

    for (int right = 0; right < s.length(); right++) {
        while (seen.contains(s.charAt(right))) {
            seen.remove(s.charAt(left));
            left++;
        }
        seen.add(s.charAt(right));
        maxLen = Math.max(maxLen, right - left + 1);
    }

    return maxLen;
}

function lengthOfLongestSubstring(string $s): int
{
    $seen = [];
    $left = 0;
    $maxLen = 0;

    for ($right = 0; $right < strlen($s); $right++) {
        while (isset($seen[$s[$right]])) {
            unset($seen[$s[$left]]);
            $left++;
        }
        $seen[$s[$right]] = true;
        $maxLen = max($maxLen, $right - $left + 1);
    }

    return $maxLen;
}

func lengthOfLongestSubstring(s string) int {
    seen := make(map[byte]bool)
    left, maxLen := 0, 0

    for right := 0; right < len(s); right++ {
        for seen[s[right]] {
            delete(seen, s[left])
            left++
        }
        seen[s[right]] = true
        if right-left+1 > maxLen {
            maxLen = right - left + 1
        }
    }

    return maxLen
}

def climb_stairs(n: int) -> int:
    if n <= 2:
        return n

    prev2, prev1 = 1, 2
    for _ in range(3, n + 1):
        prev2, prev1 = prev1, prev1 + prev2

    return prev1

public int climbStairs(int n) {
    if (n <= 2) return n;

    int prev2 = 1;
    int prev1 = 2;

    for (int i = 3; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }

    return prev1;
}

function climbStairs(int $n): int
{
    if ($n <= 2) return $n;

    $prev2 = 1;
    $prev1 = 2;

    for ($i = 3; $i <= $n; $i++) {
        $curr = $prev1 + $prev2;
        $prev2 = $prev1;
        $prev1 = $curr;
    }

    return $prev1;
}

func climbStairs(n int) int {
    if n <= 2 {
        return n
    }

    prev2, prev1 := 1, 2
    for i := 3; i <= n; i++ {
        prev2, prev1 = prev1, prev1+prev2
    }

    return prev1
}

def rob(nums: list[int]) -> int:
    prev2 = prev1 = 0
    for num in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + num)
    return prev1

public int rob(int[] nums) {
    int prev2 = 0;
    int prev1 = 0;

    for (int num : nums) {
        int curr = Math.max(prev1, prev2 + num);
        prev2 = prev1;
        prev1 = curr;
    }

    return prev1;
}

function rob(array $nums): int
{
    $prev2 = 0;
    $prev1 = 0;

    foreach ($nums as $num) {
        $curr = max($prev1, $prev2 + $num);
        $prev2 = $prev1;
        $prev1 = $curr;
    }

    return $prev1;
}

func rob(nums []int) int {
    prev2, prev1 := 0, 0

    for _, num := range nums {
        curr := max(prev1, prev2+num)
        prev2 = prev1
        prev1 = curr
    }

    return prev1
}

def longest_common_subsequence(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]

public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length();
    int n = text2.length();
    int[][] dp = new int[m + 1][n + 1];

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[m][n];
}

function longestCommonSubsequence(string $text1, string $text2): int
{
    $m = strlen($text1);
    $n = strlen($text2);
    $dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));

    for ($i = 1; $i <= $m; $i++) {
        for ($j = 1; $j <= $n; $j++) {
            if ($text1[$i - 1] === $text2[$j - 1]) {
                $dp[$i][$j] = $dp[$i - 1][$j - 1] + 1;
            } else {
                $dp[$i][$j] = max($dp[$i - 1][$j], $dp[$i][$j - 1]);
            }
        }
    }

    return $dp[$m][$n];
}

func longestCommonSubsequence(text1, text2 string) int {
    m, n := len(text1), len(text2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if text1[i-1] == text2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            }
        }
    }

    return dp[m][n]
}

from collections import deque

def num_islands(grid: list[list[str]]) -> int:
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    count = 0

    def bfs(r: int, c: int) -> None:
        queue = deque([(r, c)])
        grid[r][c] = "0"
        while queue:
            row, col = queue.popleft()
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = row + dr, col + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "1":
                    grid[nr][nc] = "0"
                    queue.append((nr, nc))

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                count += 1
                bfs(r, c)

    return count

public int numIslands(char[][] grid) {
    if (grid.length == 0) return 0;
    int rows = grid.length;
    int cols = grid[0].length;
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int count = 0;

    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] != '1') continue;
            count++;
            Deque<int[]> queue = new ArrayDeque<>();
            queue.offer(new int[]{r, c});
            grid[r][c] = '0';
            while (!queue.isEmpty()) {
                int[] cell = queue.poll();
                for (int[] d : dirs) {
                    int nr = cell[0] + d[0];
                    int nc = cell[1] + d[1];
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == '1') {
                        grid[nr][nc] = '0';
                        queue.offer(new int[]{nr, nc});
                    }
                }
            }
        }
    }

    return count;
}

function numIslands(array $grid): int
{
    if (empty($grid)) return 0;
    $rows = count($grid);
    $cols = count($grid[0]);
    $dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    $count = 0;

    for ($r = 0; $r < $rows; $r++) {
        for ($c = 0; $c < $cols; $c++) {
            if ($grid[$r][$c] !== '1') continue;
            $count++;
            $queue = [[$r, $c]];
            $head = 0;
            $grid[$r][$c] = '0';
            while ($head < count($queue)) {
                [$row, $col] = $queue[$head++];
                foreach ($dirs as [$dr, $dc]) {
                    $nr = $row + $dr;
                    $nc = $col + $dc;
                    if ($nr >= 0 && $nr < $rows && $nc >= 0 && $nc < $cols && $grid[$nr][$nc] === '1') {
                        $grid[$nr][$nc] = '0';
                        $queue[] = [$nr, $nc];
                    }
                }
            }
        }
    }

    return $count;
}

func numIslands(grid [][]byte) int {
    if len(grid) == 0 {
        return 0
    }
    rows, cols := len(grid), len(grid[0])
    dirs := [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
    count := 0

    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            if grid[r][c] != '1' {
                continue
            }
            count++
            queue := [][2]int{{r, c}}
            grid[r][c] = '0'
            for len(queue) > 0 {
                cell := queue[0]
                queue = queue[1:]
                for _, d := range dirs {
                    nr, nc := cell[0]+d[0], cell[1]+d[1]
                    if nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == '1' {
                        grid[nr][nc] = '0'
                        queue = append(queue, [2]int{nr, nc})
                    }
                }
            }
        }
    }

    return count
}

from collections import defaultdict, deque

def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
    graph = defaultdict(list)
    in_degree = [0] * num_courses

    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1

    queue = deque(i for i in range(num_courses) if in_degree[i] == 0)
    processed = 0

    while queue:
        course = queue.popleft()
        processed += 1
        for nxt in graph[course]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)

    return processed == num_courses

public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> graph = new ArrayList<>();
    int[] inDegree = new int[numCourses];
    for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());

    for (int[] p : prerequisites) {
        graph.get(p[1]).add(p[0]);
        inDegree[p[0]]++;
    }

    Deque<Integer> queue = new ArrayDeque<>();
    for (int i = 0; i < numCourses; i++) {
        if (inDegree[i] == 0) queue.offer(i);
    }

    int processed = 0;
    while (!queue.isEmpty()) {
        int course = queue.poll();
        processed++;
        for (int next : graph.get(course)) {
            if (--inDegree[next] == 0) queue.offer(next);
        }
    }

    return processed == numCourses;
}

function canFinish(int $numCourses, array $prerequisites): bool
{
    $graph = array_fill(0, $numCourses, []);
    $inDegree = array_fill(0, $numCourses, 0);

    foreach ($prerequisites as [$course, $prereq]) {
        $graph[$prereq][] = $course;
        $inDegree[$course]++;
    }

    $queue = [];
    for ($i = 0; $i < $numCourses; $i++) {
        if ($inDegree[$i] === 0) $queue[] = $i;
    }

    $processed = 0;
    $head = 0;
    while ($head < count($queue)) {
        $course = $queue[$head++];
        $processed++;
        foreach ($graph[$course] as $next) {
            if (--$inDegree[$next] === 0) $queue[] = $next;
        }
    }

    return $processed === $numCourses;
}

func canFinish(numCourses int, prerequisites [][]int) bool {
    graph := make([][]int, numCourses)
    inDegree := make([]int, numCourses)

    for _, p := range prerequisites {
        graph[p[1]] = append(graph[p[1]], p[0])
        inDegree[p[0]]++
    }

    queue := []int{}
    for i := 0; i < numCourses; i++ {
        if inDegree[i] == 0 {
            queue = append(queue, i)
        }
    }

    processed := 0
    for len(queue) > 0 {
        course := queue[0]
        queue = queue[1:]
        processed++
        for _, next := range graph[course] {
            inDegree[next]--
            if inDegree[next] == 0 {
                queue = append(queue, next)
            }
        }
    }

    return processed == numCourses
}