Станьте более уверенными и сэкономьте время на собеседованиях, изучив эти распространенные шаблоны собеседований по программированию на 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. Понимание списка (т. Е. Карта и фильтр Pythonic)

  • Общий синтаксис: 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 - список из 5 Nones
  • Для двух или более измерений не делать [[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 {
  # Write code here
} while (condition)

это в Python (не мой любимый синтаксис, но иногда его нужно делать) -

while True:
  # Write code here
  if condition:
    break

Часть 3. Функции высшего порядка.

8. Используйте понимание списка вместо `map` или` filter`.

list = list(range(10)) # [0, 1, ..., 9]# Not very Pythonic 👎
evens = filter(list, lambda x : x % 2 == 0) # [0, 2, ..., 8]
evens_doubled = map(events, lambda x : x*2) # [0, 4, ..., 16]# Using list comprehension is Pythonic 👍
evens_doubled = [x*2 for x in list if x % 2 == 0]

9. С осторожностью используйте сокращение.

С осторожностью используйте сокращение - 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

10. Использование 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_shortestshort = [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. Структуры данных

11. Методы словаря 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}

12. Использование OrderedDict

  • OrderedDict используется не очень часто, но может сделать некоторые проблемы, такие как реализация кэша LRU, почти тривиальными. OrderedDict - это фактически словарь в сочетании с двусвязным списком для упорядочивания
  • OrderedDict имеет метод .popitem(), который позволяет вам удалять элементы в порядке LIFO (последний пришел, первый ушел) (popitem(last=False) удалит элементы в порядке FIFO).
  • Также .move_to_end(item_key) вы можете переместить элемент в конец словаря (чтобы его можно было открыть следующим). .move_to_end(item_key, last=False) позволяет переместить элемент в начало.

13. Использование 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})

14. Использование heapq

  • Не используйте queue.PriorityQueue, heapq более гибкий
  • Прочтите официальную документацию по heapq - некоторые выноски ниже
  • heapify на месте, поэтому heapify(list) превратит list в кучу
  • heapq поддерживает только min-heaps, для max-heap умножьте все значения на -1 перед накоплением и умножьте на -1 после всплытия (раздражает, я знаю)
  • Если вы хотите создать кучу для объектов, вы должны добавить их как кортеж с (priority, counter, object). counter - уникальный номер для разрыва приоритетных связей (иначе вы получите сообщение об ошибке). Я начинаю counter с 0 и увеличиваю его всякий раз, когда помещаю в кучу.

15. Реализация дерева

  • В стандартной библиотеке 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

16. Реализация 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

Часть 5. Рекурсия и динамическое программирование.

17. Запоминание с помощью декоратора

Просто добавьте декоратор @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 = 62)
from functools import lru_cache
@lru_cache(64)
def fib(n):
  return fib(n - 1) + fib(n - 2) if n > 1 else n

18. Делаем рекурсивные программы итеративными.

Вот пример создания итеративной функции Фибоначчи с использованием табуляции (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 отлично объясняет, как это сделать.

Часть 6. Разное

19. Тернарный оператор if

  • condition ? a : b на других языках a if condition else b в Python

20. Манипулируйте двоичными строками

  • Избавьтесь от надоедливого префикса 0b после использования bin через нарезку - например, bin(7) = "0b111 так bin(7)[2:] = "111"
  • Чтобы добавить ведущие нули до N цифр, добавьте 2**N, а затем срежьте - например, чтобы дополнить 111 нулями до 5 цифр, выполните bin(2**5 + 7)[3:] = “00111” (обратите внимание, что 2**N > num, чтобы это работало)

21. Изменяемые и неизменяемые объекты

Изменяемый объект может быть изменен, а неизменный объект - нет. Вот список встроенных типов и их неизменяемость. Пользовательские классы обычно изменяемы.

Это просто означает, что вам нужно быть осторожным с созданием переменных из существующих переменных для изменяемых объектов. Вы можете случайно изменить существующий объект!

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]

Прокомментируйте, если у вас есть какие-либо вопросы или дополнительные предложения, и удачи тем из вас, кто участвует в собеседовании!

Больше контента на plainenglish.io