Привет! Сегодняшний пост может быть скучным для тех, кто уже давно нашел себе стажировку / работу, но нас чита…

Привет! Сегодняшний пост может быть скучным для тех, кто уже давно нашел себе стажировку / работу, но нас читают не только люди, которые уже нашли себе работу, но и те, кто только ее ищут. Я уже писал про то, что зачастую во многих собеседованиях, где есть алгосы для ml специалистов фигурируют в основном 3 идеи: два указателя, hash-map-ы, сортировка - примерно в таком ранжировании. Разберем 3 задачи. 1. Два указателя (easy на литкоде, но часто спрашивают): https://leetcode.com/problems/valid-palindrome-ii/ Проверить, можно ли у входящей строки удалить не более 1 символа, чтоб получился палиндром. Основная мысль тут такая - давайте просто будем смотреть слева и справа - совпадают ли наши символы. Если да, то давайте просто двигаться смещаясь к центру. Если в какой то момент мы нашли два различных символа, то не удалив их, у нас никак не получиться палиндром. Пробуем удалить 1 - смотрим получился ли у нас палиндром, пробуем удалить второй смотрим - получился ли у нас палиндром. Если хотя бы в одном случае да, то возвращаем true, иначе false. class Solution: def validPalindrome(self, s: str) -> bool: def isPalindrome(l, r): while l < r: if s[l] != s[r]: return False l += 1 r -= 1 return True left, right = 0, len(s) - 1 while left < right: if s[left] != s[right]: return isPalindrome(left + 1, right) or isPalindrome(left, right - 1) left += 1 right -= 1 return True 2. Hash Map: https://leetcode.com/problems/longest-consecutive-sequence/?envType=problem-list-v2&envId=hash-table . Найти наибольший по длине отрезок последовательных чисел (+=1). Достаточно красивая идейно задача. Каждый набор чисел из входа можно представить как объединение отрезков последовательных чисел. Давайте найдем минимальные числа отрезков и будем наращивать их длину инкрементируясь, пока не найдем конец отрезка. Утверждается, что пробежавшись только по минимальным и наращивая отрезок от них мы переберем все числа (из соображений выше). class Solution: def longestConsecutive(self, nums: List[int]) -> int: num_set = set(nums) longest_consecutive_sequence = 0 for num in nums: if num - 1 not in num_set: current_number = num current_consecutive_sequence = 1 while current_number + 1 in num_set: current_number += 1 current_consecutive_sequence += 1 longest_consecutive_sequence = max( longest_consecutive_sequence, current_consecutive_sequence ) return longest_consecutive_sequence 3. Sorting: https://leetcode.com/problems/largest-number/solutions/5785445/best-solution-simplified-easy-approach-j-ha3v/?envType=problem-list-v2&envId=sorting По массиву чисел вернуть их строкой в конкатеннированном виде, чтоб число было максимальным (склеенное) Тут основная мысль задачи в том, что чтоб составить наибольшее по значению число надо как-то правильно отсортировать строки. Давайте придумаем умный компаратор, который будет сравнивать склейку строк ab vs ba. Отсортировав так массив строк-чисел и склеив их - получим желаемый результат. Не забываем крайний случай с 0. class Solution: def largestNumber(self, nums: List[int]) -> str: from functools import cmp_to_key strs = list(map(str, nums)) def compare(a, b): if a + b > b + a: return -1 # a до b elif a + b < b + a: return 1 # b до a else: return 0 # equal strs.sort(key=cmp_to_key(compare)) if strs[0] == "0": return "0" return ''.join(strs) Надеюсь, даже в таких задачах вы увидели какие-то свежие идеи. Применяйте их в собеседованиях! Всем хорошей среды! @zadachi_ds