Давайте разберемся в тонкостях выделения памяти под список и как она себя ведет при увеличении, размера, какая сложность этих операций, и почему иногда лучше сразу создать список на столько элементов, сколько вам пригодится в будущем.
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/

Мы ознакомились с тем, что такое хэш-таблицы, и после вопросов про словарь, обычно спрашивают про них.
5-ый вопрос:
Что такое Хэш-таблица?
Хэш-таблица - структура данных, напоминающая ассоциативный массив, позволяющая хранить пары ключ-значение. Ключ при этом должен быть уникальным.

Какая сложность операций с хэш-таблицами?
Добавление/удаление/поиск/получение значения по ключу происходит за О(1).

Какие данные могут быть ключом в хэш таблице?
Как и в словаре, https://t.me/python_simple/89

Что будет если 2 разных ключа получат один и тот же хэш?
Это называется коллизией, при этом в бакете (ячейка таблицы) создается связный список из объектов, в которых хранится ключ и значение. И потом когда нам надо получить конкретный объект, то мы ищем, какому ключу соответствует текущий ключ, когда находим, возвращаем значение.

Что будет, если в этих бакетах будет много значений?
Есть коэффициент load factor, он получается, если разделить кол-во элементов на размер хэш таблицы, когда этот коэффициент становится больше 0.7, то хэш таблица расширяется и все данные перераспределяются уже в новой таблице.

все вопросы
#ps_question

Тинькофф задачи с контекста стажировки 2023 Осень:
1. Задача 1
2. Задача 2
3. Задача 3
4. Задача 4
5. Задача 5
6. Задача 6
7. Задача 7
8. Задача 8
9. Задача 9
10. Задача 10
11. Задача 11
12. Задача 12