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

Воскресная задачка.
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

Где искать стажировки?
Есть несколько надежных мест, где можно находить стажировки. Мониторить надо крупные компании. У многих уже есть отдельные лендинги под стажировки. Я решил посмотреть, что есть в ближайшее время и нашел осенний набор на стажировку в Тинькофф. Надо будет завести какую-то таблицу или страничку с подборкой стажировок, чтобы не пропускать их.
Стажировка в крупной компании - это очень хороший шанс получить привлекательную строчку в резюме и влиться в комьюнити единомышленников и двигаться семимильными шагами к единой цели. Если хорошо проявить себя на стажировке, то можно быстро вырасти в компании. Если рост не такой быстрый, как вам хочется, то через год можно будет перейти в другую крупную компанию, куда вас уже с удовольствием позовут, а ещё через пару лет вернуться в эту компанию на более серьезную позицию. Но тут каждый сам выбирает, как ему двигаться по карьерной лестнице.
К чему этот спич.
У каждой стажировки, тем более, если компания не первый раз проводит набор, есть рекомендации к подготовке. У некоторых есть тренировочные контесты с задачами. Тинькофф в этом смысле не исключение. У них 12 задач и я подумал, почему бы не создать сейчас 12 постов с задачами и в комментариях мы бы общими усилиями их разбирали, не обязательно спешить и не обязательно решить все 12 сегодня (можно растянуть на месяц и мб не получится решить всё). Затем эталонные решения я буду прикреплять к самой задаче, но ход рассуждения будет в комментариях (практически как и сейчас с задачами с литкода). Было бы отлично, если бы вы помогали друг-другу дойти до верного решения, я тоже буду помогать и разбираться сам, т.к. задачи ещё не решал.
Если у кого-то есть идеи или вопросы, можно их обозначить в комментариях.
Ссылка на стажировку https://fintech.tinkoff.ru/start/python/