Как видно знание хэш таблиц жизненно необходимо, чтобы продержаться на собеседовании первые 5 минут).
Поэтому про них будет отдельный пост и тут мы уже затронули сложность алгоритмов, про них тоже в ближайшее время сделаю отдельный пост. Тема сложности алгоритмов на самом деле простая, если мы её будем разбирать с точки зрения собеседований и литкод задач.

Воскресная задачка.
3. Valid Anagram (легкая)
leetcode.com/problems/valid-anagram
Имеется 2 строки s и t, вернуть True, если t является анаграммой s и False в противном случае.

Анаграмма - это слово или фраза образованная путем перестановки букв другого слова или фразы обычно с использованием всех исходных букв ровно 1 раз.

Пример 1:
Input: s = "anagram", t = "nagaram"
Output: true

Пример 2:
Input: s = "rat", t = "car"
Output: false

def isAnagram(s, t):
«Ваше решение»

Ваша задача решить эту задачу на литкоде и успешно засабмитить

*разбор будет в комментариях в нескольких сообщениях, чтобы вы могли подумать над решением

Список всех задач
#ps_leetcode

Мы уже начали заходить в тупик, т.к. измерение сложности алгоритмов сопровождает программиста повсюду (при работе). Поэтому пришло время разобрать, что это такое, чтобы комфортно двигаться дальше.
Сложность алгоритмов (О большое)

Воскресная задачка.
4. Top K Frequent Elements (средняя)
leetcode.com/problems/top-k-frequent-elements
Имеется список чисел nums, необходимо вернуть k наиболее часто встречающихся элементов. Порядок не важен.

Пример 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Пример 2:
Input: nums = [1], k = 1
Output: [1]

def topKFrequent(nums, k):
«Ваше решение»

Ваша задача решить эту задачу на литкоде и успешно засабмитить

*разбор будет в комментариях в нескольких сообщениях, чтобы вы могли подумать над решением
*задачи среднего уровня, если показалась сложной, это вполне нормально

Список всех задач
#ps_leetcode

Методы для работы со списками.
Подумайте, какая может быть сложность у каждого метода и напишите, у каких методов сложность О(1) или может быть О(1) при определенных условиях.

Оглавление
#ps_base

Сложность методов для работы со списками.

Оглавление
#ps_base

Чтобы подготовиться к завтрашней задаче, надо разобраться, что такое стек.

Стек
Подумайте, как можно реализовать стек из того, что мы уже знаем? Можно конечно написать свой класс и реализовать все эти методы, а информацию как-то хранить внутри. Но классы ещё не проходили, как без них реализовать?
Ещё учтите, что все операции со стеком должны производиться за О(1).

Воскресная задачка.
5. Valid Parentheses (легкая)
leetcode.com/problems/valid-parentheses
Получаем строку s, содержащую только символы '(', ')', '{', '}', '[' и ']', определите, валидна ли эта строка.
Эта строка валидна, если:
- Открытые скобки должны быть закрыты однотипными строками
- Открытые скобки должны быть закрыты в правильном порядке
- Каждой закрывающей скобке соответствует открытая скобка того же типа

Пример 1:
Input: s = "()"
Output: true

Пример 2:
Input: s = "()[]{}"
Output: true

Пример 3:
Input: s = "(]"
Output: false

def isValid(s):
«Ваше решение»

Ваша задача решить эту задачу на литкоде и успешно засабмитить

*разбор будет в комментариях в нескольких сообщениях, чтобы вы могли подумать над решением

Список всех задач
#ps_leetcode

Чтобы закрепить, как реализовать стек в python, самым простым способом, приведу табличку с эквивалентными методами. Также добавлю её в основной пост про стек.
Стек

Добиваем работу со списками. Альтернативные способы работы со списками

Оглавление
#ps_base

Давайте разберемся в тонкостях выделения памяти под список и как она себя ведет при увеличении, размера, какая сложность этих операций, и почему иногда лучше сразу создать список на столько элементов, сколько вам пригодится в будущем.
https://telegra.ph/Kogda-slozhnost-append-mozhet-byt-On-06-23

Всем, привет!
Мы уже решали задачи на списки, на хэш таблицы и на стек.
Завтра будет задача на литкод паттерн - two pointers. Когда мы итерируемся по списку, то как правило мы перебираем элементы подряд, и текущий элемент у нас 1. Суть паттерна two pointers заключается в том, что мы вводим 2 указателя и по сути у нас 2 текущих элемента. Самый простой пример, это определение, что слово - полиндром (эта задача будет на следующей неделе и её усложненная версия тоже). Можно развернуть строку/список и сравнить с первоначальной. Но если строка слишком большая, то не очень хорошо выделять ещё столько же памяти. Тогда можно ввести 2 указателя, один будет идти с конца строки, а второй с начала и идти с двух концов до середины строки, сравнивая элементы.
Также интересно, какие темы больше интересуют на канале.

Все выдохнули? В понедельник можно будет решить ещё одну задачку, раз выходной 🌚

Воскресная задачка. Кстати у меня она была давным давно в Яндекс)
6. Move Zeroes (легкая)
leetcode.com/problems/move-zeroes
Получаем целочисленный массив nums, необходимо перенести все 0 в его конец, сохраняя порядок ненулевых элементов.

Пример 1:
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Пример 2:
Input: nums = [0]
Output: [0]

def moveZeroes(nums):
«Ваше решение»

Ваша задача решить эту задачу на литкоде и успешно засабмитить

*разбор будет в комментариях в нескольких сообщениях, чтобы вы могли подумать над решением

Список всех задач
#ps_leetcode

Тот самый день, когда хотел пойти на работу как жест доброй воли, но на работе сказали, что день рабочий
7. Valid Palindrome (легкая)
leetcode.com/problems/valid-palindrome
Фраза является палиндромом, если после преобразования всех прописных букв в строчные и удаления всех не буквенно-цифровых символов она читается одинаково вперед и назад. На вход подается строка s верните True, если полиндром и False, если нет.

Пример 1:
Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" полиндром.

Пример 2:
Input: s = "race a car"
Output: false
Explanation: "raceacar" не полиндром.

Пример 3:
Input: s = " "
Output: true

def isPalindrome(s):
«Ваше решение»

Ваша задача решить эту задачу на литкоде и успешно засабмитить

*разбор будет в комментариях в нескольких сообщениях, чтобы вы могли подумать над решением

Список всех задач
#ps_leetcode

Всем привет, у канала есть чат, там можно задавать вопросы, не относящиеся к постам и что-то обсуждать. Ссылки на него нет, но если кто-то не знает, как его найти, прикрепляю видео)

Воскресная задачка:
8. Valid Palindrome II (легкая)
leetcode.com/problems/valid-palindrome-ii
Есть входная строка s, верните True если она может стать подиндромом при удалении не более 1-го символа и False, если нельзя.

Пример 1:
Input: s = "aba"
Output: true

Пример 2:
Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.

Пример 3:
Input: s = "abc"
Output: false

def validPalindrome(s):
«Ваше решение»

Ваша задача решить эту задачу на литкоде и успешно засабмитить

*разбор будет в комментариях в нескольких сообщениях, чтобы вы могли подумать над решением

Список всех задач
#ps_leetcode

Пришло время подробнее разобрать, что такое хэш-таблица, которая уже не раз упоминалась. Следующий вопрос с собеседования будет как раз про хэш-таблицы.

Воскресная задачка, закрепляем two pointers:
9. Remove Duplicates from Sorted Array (легкая)
leetcode.com/problems/remove-duplicates-from-sorted-array
На вход подается целочисленный массив nums, отсортированный в неубывающем порядке, удалите дубликаты, чтобы каждый уникальный элемент появлялся только один раз. Порядок элементов должен быть сохранен. Затем верните количество уникальных элементов в nums.
Важно, надо изменить сам списов и вернуть кол-во уникальных элементов.

Пример 1:
Input: nums = [1,1,2]
Возвращаем: 2
При этом nums = [1,2,_] или nums = [1,2], главное, чтобы первые k элементов были уникальными

Пример 2:
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Возвращаем: 5
При этом nums = [0,1,2,3,4,_,_,_,_,_] или nums = [0,1,2,3,4]

def removeDuplicates(nums):
«Ваше решение»

Ваша задача решить эту задачу на литкоде и успешно засабмитить

*разбор будет в комментариях в нескольких сообщениях, чтобы вы могли подумать над решением

Список всех задач
#ps_leetcode