Теперь можно разобрать первую задачу:
1. Two Sum (легкая)
leetcode.com/problems/two-sum

Вы получаете список целых чисел nums и число target.
Надо вернуть список из 2-х индексов чисел из списка, которые в сумме дают target.
Такая комбинация встречается 1 раз.
Вернуть числа можно в любом порядке

Пример 1:Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

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

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

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

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

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

3-ий вопрос:
Что может быть ключом в словаре?
Ответить можно, что ключом может быть неизменяемый тип.

Почему?
Дело в том, что если у нас будет 2 ключа - списки, тогда теоретически мы сможем их изменить до одинакового состояния и у нас в словаре получится 2 одинаковых ключа, таким образом когда мы попытаемся по ключу достать значение, словарь не будет знать, что нам вернуть.

Может ли кортеж или другой контейнерный тип быть ключом в словаре?
Ответ тут будет и да и нет.

Если у нас будет кортеж, в котором будут только неизменяемые переменные, например:
(1, "my_str", (1, 2)) - то, все ок, он может быть ключом.
Но если у нас будет кортеж, в котором будет хоть один изменяемый тип, то он уже не сможет быть ключом в словаре, например:
(1, "my_str", [1, 2]) - содержит список, и не может быть ключом.

Чтобы очевидно проверить, может ли какая-то переменная быть ключом в словаре, надо попробовать взять у неё hash, если можно будет, то ок, если нельзя, то значит нельзя.
Поэтому можно ответить, что ключом в словаре может быть все, у чего можно взять хэш.

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

Сегодня разберем вторую задачу из порядка 300, которые необходимо решить)
2. Сontains duplicate (легкая)
leetcode.com/problems/contains-duplicate

Дан список чисел nums, если все числа в списке уникальны, то надо вернуть False, а если хоть одно число повторяется, то надо вернуть True.

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

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

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

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

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

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

4-ий вопрос:
В чем разница между списком и словарем?
Список в python это массив данных, словарь, это ключ-значение. Можно провести аналогию, что в словаре это ключ-значение, а список - это индекс-значение. Разница в сложности вставки элемента в список/словарь, удаления и поиска.

Сложность поиска элемента в списке - O(n), в словаре O(1). Но тут надо уточнить, что если мы хотим получить элемент из списка по индексу, то сложность будет O(1), т.к. в памяти компьютера элементы списка находятся подряд и python знает на сколько надо сделать сдвиг, чтобы попасть на нужный элемент.
Чтобы найти элемент в списке в худшем случае мы пройдемся по всему списку, размером n, значит сложность будет О(n).
Но чтобы найти ключ в словаре и получить по нему значение, надо ключ пропустить через хэш функцию, которая вернет что-то похожее на индекс таблички, где хранятся значения и уже по этому индексу мы получим значение, которое привязано к ключу. Сложность всего этого О(1).

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

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

Как правило так подробно рассказывать не нужно, но знать надо, обычно достаточно сказать, что у списка сложность О(n), а словаря О(1)

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

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