Станьте более уверенными и сэкономьте время на собеседованиях, изучив эти распространенные шаблоны собеседований по программированию на Python
При кодировании в реальной жизни я иногда забываю синтаксис и вынужден прибегать к помощи Google. К сожалению, во время собеседований по программированию такая роскошь недоступна. Чтобы решить эту проблему, я рассмотрел распространенные шаблоны синтаксиса в Python для собеседований по кодированию. Синтаксис не так важен, как понимание основных алгоритмов и концепций структуры данных, но для меня анализ синтаксиса вселяет уверенность в мой код и экономит бесценное время. Я надеюсь, что то же самое и с вами.
Часть 1: Списки
1. Сортировка
sorted(numbers)
вернет отсортированные числа в порядке возрастания и оставит исходные числа без изменений. Вы также можете использоватьnumbers.sort()
, который сортирует числа на месте и изменяетnumbers
на местеsorted
имеет два необязательных аргумента:key
иreverse
.key
позволяет изменять значения для сравнения. Таким образом,sorted(..., key=str.lower)
будет сортировать без учета регистра.reverse
позволяет сортировать по убыванию, поэтомуsorted(..., reverse=True)
по убыванию.sorted
использует Timsort, который имеетO(nlogn)
среднюю и наихудшую временную сложность, используетO(n)
пространство (аналогично сортировке слиянием) и имеетO(n)
временную сложность наилучшего случая (аналогично сортировке вставкой).
2. Синтаксис нарезки списка
- Общий синтаксис
iterable[start:stop:step]
list[i:j]
возвращается из индексаi
, вплоть до , но не включаяj
list[i:]
возвращается из индексаi
до концаlist[:j]
возвращается с начала до индексаj
list[::2]
возвращает каждый второй элемент из списка (индексы0, 2, ..
)list[::-1]
переворачивает список - хотя list.reversed () быстрее
3. Понимание списка (т. Е. Питоническая карта и фильтр)
- Общий синтаксис:
expression for member in iterable [if conditon]
- Например, _ 27_ вернет новый список, в котором каждый четный элемент будет удвоен из исходного списка.
- Используйте это вместо
map
иfilter
для лучшей читаемости.
4. Использование диапазона
- Общий синтаксис
range(start, stop, step)
range(n)
для итерации от0
доn — 1
range(i, j)
для итерации отi
доj
, но не включаяrange(i, j, n)
для того же, что и выше, но для каждого n-го элемента. Обратите внимание, что вам нужно указатьstart
иstop
, если вы хотите использоватьstep
—range(10, step=2)
приводит к ошибке, поэтому сделайтеrange(0, 10, 2)
вместо этого - прочтите this, чтобы узнать, почемуrange
не поддерживает аргументы ключевых слов.
5. Создание списков размера N
- Вы можете использовать диапазон и преобразовать его в список (например,
list(range(N))
или[*range(N)]
, если вам нравится) - Для одного и того же элемента используйте
[element] * N
- Например,
[0] * 10
- это список из 10 нулей,[None] * 5
- список из 5Nones
- Для двух или более измерений не
[[0] * 5] * 10
. 10 строк будут просто ссылками на одну строку с 5 значениями, поэтому редактирование одной строки изменит другие 9. Вместо этого сделайте[[0 for i in range(5)] for j in range(10)]
.
Часть 2. Итерация
6. Используйте enumerate
# Use enumerate to get index and element # from an iterable for index, element in enumerate(list): print(element + ' is at index ' + str(index))
7. Как написать `do while`
Заявление do while
, подобное этому на других языках -
do { # Write code here } while (condition)
это в Python (не мой любимый синтаксис, но иногда его нужно делать) -
while True: # Write code here if condition: break
8. Как пользоваться генераторами
Я считаю, что генераторы наиболее полезны при поиске соседей для проблемы DFS или BFS с любой структурой типа графа. Возьмем, к примеру, Leetcode 200 - Количество островов. Мы можем создать вспомогательную функцию getNeighbors
, которая возвращает генератор. Это похоже
def numIslands(grid) -> int: def getNeighbors(i, j): for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]: ni, nj = i + di, j + dj if 0 <= ni < len(grid) and 0 <= nj < len(grid[i]): yield ni, nj def dfs(i, j): grid[i][j] = "-1" for new_i, new_j in getNeighbors(i, j): if grid[new_i][new_j] == "1": dfs(new_i, new_j) islands = 0 for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] == "1": islands += 1 dfs(i, j) return islands
Часть 3. Функции высшего порядка.
9. Используйте понимание списка вместо `map` или` filter`.
list = list(range(10)) # [0, 1, ..., 9] # Not very Pythonic 👎 evens = filter(lambda x : x % 2 == 0, list) # [0, 2, ..., 8] evens_doubled = map(lambda x : x*2, events) # [0, 4, ..., 16] # Using list comprehension is Pythonic 👍 evens_doubled = [x*2 for x in list if x % 2 == 0]
10. С осторожностью используйте сокращение.
Используйте сокращение с осторожностью - sum
, math.prod
, all
и any
более читабельны, и для чего-то более сложного стоит написать более читаемый цикл for
. Даже сам Гвидо (создатель Python) так думал, поэтому reduce был понижен в должности со встроенной библиотеки до библиотеки functools
.
Тем не менее, это полезно знать. Синтаксис: functools.reduce(function, iterable[, initializer])
. Некоторые примеры ниже
from functools import reduce nums = [1, 2, 3, 4, 5] bools = [True, False, True, False, True] # sum reduce(lambda a, b: a + b, nums, 0) # 15 # math.prod reduce(lambda a, b: a * b, nums, 1) # 120 # min reduce(lambda a, b: a if a < b else b, nums) # 1 # max reduce(lambda a, b: a if a > b else b, nums) # 5 # any reduce(lambda a, b: a or b, bools) # true # all reduce(lambda a, b: a and b, bools) # false
11. Использование zip, zip_longest и zip_shortest
zip
позволяет перебирать списки одновременно
list_a = [1, 2, 3, 4] list_b = [10, 20, 30, 40] list_sum = [a + b for a, b in zip(list_a, list_b)] # OR list_sum = [] for a, b in zip(list_a, list_b): list_sum.append(a + b) print(list_sum) # [11, 22, 33, 44]
Для списков неравной длины zip
обрезает вывод до самого короткого списка. zip_longest
в библиотеке itertools
позволяет дополнить меньший список fill_value
, чтобы вы могли zip
, как если бы они были одинаковой длины.
from itertools import zip_longest, zip_shortest short = [1, 2] long = [10, 20, 30, 40] zip_short = [a + b for a, b in zip(short, long)] print(zip_short) # [11, 22] zip_long = [a + b for a, b in zip_longest(short, long, fillvalue=0)] print(zip_long) # [11, 22, 30, 40]
Часть 4. Структуры данных
12. Методы словаря Python
- Чтобы проверить, есть ли ключ в словаре, используйте
key in my_dict
my_dict[key]
обращается к элементу в словаре и возвращаетKeyError
, если ключа нет в словаре. Чтобы избежать ошибки, используйтеmy_dict.get(key, default_value=None)
, который возвращаетdefault_value
вместо ошибки, если ключа нет в словаре.- Чтобы удалить ключ из словаря, используйте
del my_dict[key]
, если вы знаете, чтоkey
находится вmy_dict
. В противном случае используйтеmy_dict.pop(key, None)
, который вернетNone
, еслиkey
не находится вmy_dict
my_dict.setdefault(key, default_value)
возвращает текущее значение дляkey
, если он находится вmy_dict
, если нет, он устанавливает его вdefault_value
и возвращает этоsetdefault
особенно полезен для подсчета элементов, где вы можете сделать что-то вродеcounts[element] = counts.setdefault(element, 0) + 1
my_dict.keys()
,my_dict.values()
иmy_dict.items()
вернут список ключей, значений и кортежей(key, value)
из словаря соответственно (это полезно для итераций)- Вы можете использовать понимание словаря, как и понимание списка, для создания новых словарей.
my_basket = {'apple': 2, 'banana': 3, 'starfruit': 1} double_my_basket = {k:v*2 for (k, v) in my_basket.items()} print(double_my_basket) # {'apple': 4, 'banana': 6, 'starfruit': 2}
- Для наборов и словарей вы можете использовать операторы слияния и обновления
|
и|=
соответственно для добавления ключей и значений (доступно только для словарей начиная с Python 3.9)
a = {1, 2, 3} # New set a += {4} # ❌ Returns a `TypeError` a |= {4} # ✅ {1, 2, 3, 4}
13. Использование OrderedDict
OrderedDict
используется не очень часто, но может сделать некоторые проблемы, такие как реализация кэша LRU, почти тривиальными.OrderedDict
- это фактически словарь в сочетании с двусвязным списком для упорядочиванияOrderedDict
имеет метод.popitem()
, который позволяет вам удалять элементы в порядке LIFO (последний пришел, первый ушел) (popitem(last=False)
удалит элементы в порядке FIFO).- Также
.move_to_end(item_key)
позвольте вам переместить элемент в конец словаря (чтобы его можно было открыть следующим)..move_to_end(item_key, last=False)
позволяет переместить элемент в начало.
14. Использование collections.Counter
- Часто вопросы собеседования включают добавление счетчиков в хеш-карту. Для этого вы можете просто использовать
collections.Counter
, как показано ниже.Counter
является подклассомdict
, и вы можете взаимодействовать с ним как с одним.
things = ['a', 'a', 'b', 'c', 'b', 'b'] counts = collections.Counter(things) print(counts) # Counter({'b': 3, 'a': 2, 'c': 1})
15. Использование heapq
- Не используйте
queue.PriorityQueue
,heapq
более гибкий - Прочтите официальную документацию по heapq - некоторые выноски ниже.
heapify
на месте, поэтомуheapify(list)
превратитlist
в кучуheapq
поддерживает только минимальную кучу, для максимальной кучи умножьте все значения на-1
до кучи и умножьте на-1
после всплытия (раздражает, я знаю)- Если вы хотите создать кучу объектов, вы должны добавить их как кортеж с
(priority, counter, object)
.counter
- уникальный номер для разрыва приоритетов (иначе вы получите сообщение об ошибке). Я начинаюcounter
с 0 и увеличиваю его всякий раз, когда помещаю в кучу.
16. Реализация дерева
- В стандартной библиотеке Python нет никаких структур данных Tree, которые были бы полезны для собеседований, поэтому вам нужно будет реализовать свои собственные
- Для двоичного дерева вы можете создать класс узла с левым и правым атрибутами узла. Обязательно отслеживайте «головной» узел в своем коде.
- Для недвоичного дерева вы можете использовать массив или словарь для детей. Если вы не ожидаете детей с повторяющимися значениями и хотите
O(1)
поиск, может быть лучше словарь.
# Binary Tree Node class Node: def __init__(value): self.value = value self.left = None self.right = None # Non-Binary Tree Node class Node: def __init__(value): self.value = value self.children = [] # or self.children = {} for dict
17. Реализация Trie
- В стандартных библиотеках Python нет Trie, но вы можете легко реализовать его. Здесь есть только
insert
иsearch
функциональные возможности, и вы можете создать дополнительные функциональные возможности поверх этого.
class TrieNode: def __init__(self): self.is_complete_word = False self.children = {} class Trie: def __init__(self): # Blank Trie self.root = TrieNode() def insert(self, word: str) -> None: """ Insert a word: — Iterate through all characters in the word - If we we encounter a char we don't have a node for, create a new node - Mark the last node as a complete word """ curr = self.root for char in word: curr = curr.children.setdefault(char, TrieNode()) curr.is_complete_word = True def search(self, word: str) -> bool: """ Search for a word: — Iterate through all characters in the word - If we we encounter a char we don't have a node for, return False - At the last node, return whether the word is a complete word in our Trie """ curr = self.root for char in word: if char not in curr.children: return False curr = curr.children[char] return curr.is_complete_word
Часть 4: Рекурсия и динамическое программирование
18. Запоминание с помощью декоратора.
Просто добавьте декоратор @cache
# No memoization O(2**N) time complexity def fib(n): return fib(n - 1) + fib(n - 2) if n > 1 else n # Memoized, now O(N) time complexity from functools import cache @cache def fib(n): return fib(n - 1) + fib(n - 2) if n > 1 else n # Similar to doing this memo = {} def fib(n): return memo.setdefault(n, fib(n - 1) + fib(n - 2) if n > 1 else n) # You can limit the memo size to N # using lru_cache (here N = 64) from functools import lru_cache @lru_cache(64) def fib(n): return fib(n - 1) + fib(n - 2) if n > 1 else n
19. Делаем рекурсивные программы итеративными
Вот пример создания итеративной функции Фибоначчи с использованием табуляции (O(n)
пространственная сложность).
def fib(n): fibs = [None] * n fibs[0], fibs[1] = 0, 1 for i in range(2, n): fib[i] = fib[i - 1] + fib[i - 2] return fib[i]
А вот и версия O(1)
космической сложности.
def fib(n): if n <= 1: return n first, second = 0, 1 for i in range(2, n + 1): first, second = second, first + second return second
Другой способ сделать программу итеративной - создать свой собственный стек. Этот ответ от StackOverflow отлично объясняет, как это сделать.
Часть 4. Разное
20. Тернарный оператор if
condition ? a : b
на других языкахa if condition else b
на Python
21. Управление двоичными строками
- Избавьтесь от надоедливого префикса
0b
после использованияbin
с помощью нарезки - например,bin(7) = "0b111
такbin(7)[2:] = "111"
- Чтобы добавить ведущие нули до N цифр, добавьте
2**N
, а затем разделите - например, чтобы добавить111
нулями до 5 цифр, выполнитеbin(2**5 + 7)[3:] = “00111”
(обратите внимание, что2**N > num
, чтобы это работало)
22. Изменяемые и неизменяемые объекты
Изменяемый объект может быть изменен, а неизменный объект - нет. Вот список встроенных типов и их неизменяемость. Пользовательские классы обычно изменяемы.
Это просто означает, что вам нужно быть осторожным с созданием переменных из существующих переменных для изменяемых объектов. Вы можете случайно изменить существующий объект!
ones = [1] * 3 twos = ones for i, _ in enumerate(twos): twos[i] = 2 print(twos) # [2, 2, 2] print(ones) # Also [2, 2, 2]!
Чтобы этого избежать, вам нужно создать копию из переменной.
ones = [1] * 3 twos = list(ones) # Creates a copy instead for i, _ in enumerate(twos): twos[i] = 2 print(twos) # [2, 2, 2] print(ones) # [1, 1, 1] # or using list comprehension twos = [2 for i in ones] print(twos) # [2, 2, 2] print(ones) # [1, 1, 1]
Прокомментируйте, если у вас есть какие-либо вопросы или дополнительные предложения, и удачи тем из вас, кто участвует в собеседовании!