Как-то раз я искал в гугле что-то насчёт Python, как вдруг всплыло приглашение принять участие в испытании по программированию от Google (так называемое foo.bar challenge). Я не фанат состязаний по написанию кода или симуляций собеседований на Leetcode по ряду причин. Однако любопытство взяло верх, и я решил попробовать. Далее я расскажу, как подготовиться и пройти первое испытание.
➡️ Читать дальше
@python_job_interview
Please open Telegram to view this post
VIEW IN TELEGRAM
Поиск будет быстрее в dict и set, потому что это хэш-таблицы, доступ к элементу которых выполняется за O(1). Для list и tuple поиск будет выполняться в среднем за O(n).
Исключение работает только для очень маленьких списков длиной до 5 элементов. В этом случае интерпретатору будет быстрей пробежаться по списку, чем считать хеш.
В Python 2 методы словаря keys, values, items возвращают список. Тоесть перед итерацией по словарю (или сету) интерпретатор сначала создает новый список, что занимает дополнительное время и память, но после создания это уже обыкновенный список. Тоесть в Python 2 итерация по словарям и сетам выполняется дольше, за счет создания нового списка и копирования в него элементов.
В Python 3 эти методы создают объект-представление. Это определенно происходит быстрее чем создание нового списка в Python2. Но итерирование по такому представлению должно происходить немного дольше, чем по списку из-за того что данные в словарях хранятся разреженно (редко, негусто). В подтверждение вышесказанного (Python 3):
>>> l = list(range(1000000))
>>> d = dict.fromkeys(l)
>>> s = set(l)
>>> def iter_list():
... for i in l:
... pass
...
>>> def iter_dict():
... for i in d:
... pass
...
>>> def iter_set():
... for i in s:
... pass
...
>>> timeit.timeit(iter_list, number=1000)
6.727667486004066
>>> timeit.timeit(iter_dict, number=1000)
9.293120226997416
>>> timeit.timeit(iter_set, number=1000)
8.627948219014797
@python_job_interview
Please open Telegram to view this post
VIEW IN TELEGRAM
Хэш-таблица это разреженный массив (массив, в котором имеются незаполненные позиции). В стандартных англоязычных учебниках ячейки хэш-таблицы называются "bucket". В хэш-таблице dict каждому элементу соотвествует ячейка, содержащая два поля: ссылку на ключ и ссылку на значение элемента. Поскольку размер всех ячеек одинаков, доступ к отдельной ячейке производится по смещению.
Python стремится оставить не менее трети ячеек пустыми; если хэш-таблица становится чрезмерно заполненной, то она копируется в новый участок памяти, где есть место для большего числа ячеек.
Для помещения элемента в хэш-таблицу нужно первым делом вычислить хэш-значение ключа элемента. Это делает встроенная функция hash().
Для выборки значения с помощью выражения my_dict[search_key] Python обращается к функции hash(search_key), чтобы получить хэш-значение search_key, и использует несколько младших битов полученного числа как смещение ячейки относительно начала хэш-таблицы (сколько именно битов зависит от текущего размера таблицы). Если найденная ячейка пуста, возбуждается исключение KeyError. В противном случае в найденной ячейке есть какой-то элемент - пара ключ:значение - и тогда Python проверяет, верно ли то, что search_key == found_key. Если да, то элемент найден и возвращается found_value. Если же search_key и found_key не совпали, то имеет место коллизия хэширования. Для разрешения коллизии алгоритм берет различные биты хэш-значения, производит над ними определенные действия и использует результат как смещение другой ячейки.
Что такое коллизия
Когда хеш-функция возвращает один и тот же ответ для разных данных.
@python_job_interview
Please open Telegram to view this post
VIEW IN TELEGRAM
Функция создается однажды при загрузке модуля. Именованные параметры и их дефолтные значения тоже создаются один раз и хранятся в одном из полей объекта-функции.
В нашем примере bar равен пустому списку. Список – изменяемая коллекция, поэтому значение bar может изменяться от вызова к вызову. Пример:
def foo(bar=[]):
bar.append(1)
return bar
foo()
>>> [1]
foo()
[1, 1]
foo()
>>> [1, 1, 1]
Хорошим тоном считается указывать параметру пустое неизменяемое значение, например 0, None, '', False. В теле функции проверять на заполненность и создавать новую коллекцию:
def foo(bar=None):
if bar is None:
bar = []
bar.append(1)
return bar
foo()
>>> [1]
foo()
>>> [1]
foo()
>>> [1]
Сказанное выше актуально в т.ч. для множеств и словарей.
@python_job_interview
Please open Telegram to view this post
VIEW IN TELEGRAM
Числовые ключи в словарях подчиняются правилам сравнения чисел. Таким образом, int(1) и float(1.0) считаются одинаковым ключом. Однако из-за того, что значения типа float сохраняются приближенно, не рекомендуется использовать их в качестве ключей.
>>> {True: 'yes', 1: 'no', 1.0: 'maybe'}
{True: 'maybe'}
@python_job_interview
Please open Telegram to view this post
VIEW IN TELEGRAM
В Python сортировка производится встроенной функцией sorted. Первым аргументом она принимает итерируемый объект. Это может быть список, кортеж, генератор, итератор и т.п. Возвращает отсортированный список.
>>> sorted([4, 2, 3, 1, 0])
[0, 1, 2, 3, 4]
>>> sorted(x * x for x in range(-5, 6))
[0, 1, 1, 4, 4, 9, 9, 16, 16, 25, 25]
Можно сортировать в обратном порядке:
>>> sorted([4, 2, 3, 1, 0], reverse=True)
[4, 3, 2, 1, 0]
Если сортируемые элементы – списки, словари или объекты, то воспользуемся параметром key. Мы передаем в key нечто вызываемое (имя функции, lambda и т.п), и при сортировки элементы сравниваются по результату вызова key на элементе. Результатом key должно быть число, строка или что-то другое сравнимое между собой.
📎 Пример. Сортировка списка строк по длине строки:
>>> sorted(["foo", "bazooka", "", "game"], key=len)
['', 'foo', 'game', 'bazooka']
📎 Пример. Сортировка списка кортежей по 0 или 1 элементу каждого.
>>> people = [("Bill", "Gates"), ("Tim", "Cook"), ("Donald", "Trump")]
>>> sorted(people, key=lambda t: t[0])
[('Bill', 'Gates'), ('Donald', 'Trump'), ('Tim', 'Cook')]
>>> sorted(people, key=lambda t: t[1])
[('Tim', 'Cook'), ('Bill', 'Gates'), ('Donald', 'Trump')]
Для этой же цели удобно использовать функцию operator.itemgetter:
>>> import operator
>>> sorted(people, key=operator.itemgetter(0))
[('Bill', 'Gates'), ('Donald', 'Trump'), ('Tim', 'Cook')]
Еще полезные функции из operator:
• attrgetter(name) – для получение значения атрибута объекта с именем name
• methodcaller(name[, args...]) – для получения результата вызова метода name у объекта. Опционально с аргументами args.
Вот пример кода с attrgetter и methodcaller.
Для списков (list) определен метод sort(), который модифицирует исходный список, выстраивая элемента по порядку.
>>> arr = [3, 4, 1, 2, 5, 6, 0]
>>> arr.sort()
>>> arr
[0, 1, 2, 3, 4, 5, 6]
Сортировка в Python – устойчива. Это значит, что порядок элементов с одинаковыми ключами будет сохранен в сортированной последовательности. Пример.
Внутри Python использует Timsort – гибридный алгоритм сортировки, сочетающий сортировку вставками и сортировку слиянием. Смысл в том, что в реальном мире часто встречаются частично отсортированные данные, на которых Timsort работает ощутимо быстрее прочих алгоритмов сортировки. Сложность по времени: O(n log n) в худшем случае и O(n) – в лучшем.
⚠️ CPython: не пытайтесь модифицировать сортируемый список во время сортировки. Эффект непредсказуем.
@python_job_interview
Please open Telegram to view this post
VIEW IN TELEGRAM
Ключом словаря может быть любой хешируемый неизменяемый объект: число, строка, datetime, функция и даже модуль. Такие объекты имеют метод
__hash__()
, который однозначно сопоставляет объект с некоторым числом. По этому числу словарь ищет значение для ключа.Списки, словари и множества изменяемы и не имеют метода хеширования. При подстановке их в словарь возникнет ошибка.
Хеш кортежа вычисляется рекурсивно по всем элементам. Так, кортеж
(1, (True, (42, ('hello', ))))
состоит только из неизменяемых элементов, поэтому может быть ключом. Однако, такой кортеж(1, (True, (42, ({'hello': 'world'}, ))))
содержит глубоко внутри словарь, поэтому хеш не может быть рассчитан.@python_job_interview
Please open Telegram to view this post
VIEW IN TELEGRAM
Выражения
*args и **kwargs
объявляют в сигнатуре функции. Они означают, что внутри функции будут доступны переменные с именами args и kwargs (без звездочек). Можно использовать другие имена, но это считается дурным тоном.args – это кортеж, который накапливает позиционные аргументы. kwargs – словарь именованных аргументов, где ключ – имя параметра, значение – значение параметра.
Важно: если в функцию не передано никаких параметров, переменные будут соответственно равны пустому кортежу и пустому словарю, а не None.
Пожалуйста, не путайте кортеж со списком.
@python_job_interview
Please open Telegram to view this post
VIEW IN TELEGRAM
Это анонимные функции. Они не резервируют имени в пространстве имен. Лямбды часто передают в функции map, reduce, filter.
Лямбды в Питоне могут состоять только из одного выражения. Используя синтаксис скобок, можно оформить тело лямбды в несколько строк.
Использовать точку с запятой для разделения операторов нельзя.
Допустимы ли следующие выражения
nope = lambda: pass
riser = lambda x: raise Exception(x)
Нет, при загрузке модуля выскочит исключение SyntaxError. В теле лямбды может быть только выражение. pass и raise являются операторами.
@python_job_interview
Please open Telegram to view this post
VIEW IN TELEGRAM
Интересности и полезности python. Часть 3
В таких языках как C++ есть переменные, хранящиеся на стеке и в динамической памяти. При вызове функции мы помещаем все аргументы на стек, после чего передаём управление функции. Она знает размеры и смещения переменных на стеке, соответственно может их правильно интерпретировать. При этом у нас есть два варианта: скопировать на стек память переменной или положить ссылку на объект в динамической памяти (или на более высоких уровнях стека). Очевидно, что при изменении значений на стеке функции, значения в динамической памяти не поменяются, а при изменении области памяти по ссылке, мы модифицируем общую память, соответственно все ссылки на эту же область памяти «увидят» новое значение.
В python отказались от подобного механизма, заменой служит механизм связывания (assignment) имени переменной с объектом, например при создании переменной: var = "john"
Интерпретатор создаёт объект «john» и «имя» var, а затем связывает объект с данным именем. При вызове функции, новых объектов не создаётся, вместо этого в её области видимости создаётся имя, которое связывается с существующим объектом. Но в python есть изменяемые и неизменяемые типы. К первым, например, относятся числа: при арифметических операциях существующие объекты не меняются, а создаётся новый объект, с которым потом связывается существующее имя. Если же со старым объектом после этого не связано ни одного имени, оно будет удалено с помощью механизма подсчёта ссылок. Если же имя связано с переменной изменяемого типа, то при операциях с ней изменяется память объекта, соответственно все имена, связанные с данной областью памяти «увидят» изменения.
@python_job_interview
Please open Telegram to view this post
VIEW IN TELEGRAM
Когда вы определяете функцию внутри другой функции и используете локальные переменные внешней функции во вложенной, вы создаете замыкание. Время жизни этих переменных "продляется" в особой области видимости enclosing даже после завершения работы внешней функции. Пример: make_adder возвращает функцию-прибавлятор. Объект из переменной a будет жить и работать даже после выхода из make_adder:
def make_adder(a):
def adder(x):
return a + x
return adder
plus_5 = make_adder(5)
print(plus_5(3)) # 8
Здесь я хочу коснуться одной популярной проблемы. Дело в том, что если мы создадим несколько функций внутри одного контекста, то они будут разделять одну область видимости enclosing. Рассмотрим пример создания трех функций в цикле:
def make_adders():
adders = []
for a in range(3):
def adder(x):
return a + x
adders.append(adder)
return adders
adders = make_adders()
for adder in adders:
print(adder(2)) # 4 4 4
Вместо функций прибавляющих разные числа от 0 до 2, мы получили 3 одинаковых функции, потому что внутри себя они поддерживают ссылку на одну и ту же переменную
a
, значение которой останется равным 2 после выполнения всего цикла целиком.Есть простой прием, помогающий "зафиксировать" значения переменной в моменте: достаточно добавить во вложенную функцию дополнительный аргумент со значением по умолчанию, равным нужной переменной
a=a
:def make_adders():
adders = []
for a in range(3):
def adder(x, a=a): # FIX!
return a + x
adders.append(adder)
return adders
adders = make_adders()
for adder in adders:
print(adder(2)) # 2 3 4
Еще лучше переименовать аргумент, чтобы избежать конфликтов имен и замечаний IDE, например, так:
def adder(x, that_a=a): # FIX!
return that_a + x
@python_job_interview
Please open Telegram to view this post
VIEW IN TELEGRAM
Итерабельный объект (в оригинальной терминологии – «iterable») – это объект, который может возвращать значения по одному за раз. Примеры: все контейнеры и последовательности (списки, строки и т.д.), файлы, а также экземпляры любых классов, в которых определён метод
__iter__()
или __getitem__()
. Итерабельные объекты могут быть использованы внутри цикла for, а также во многих других случаях, когда ожидается последовательность (функции sum(), zip(), map() и т.д.).Подробнее:
Рассмотрим итерируемый объект (Iterable). В стандартной библиотеке он объявлен как абстрактный класс collections.abc.Iterable:
class Iterable(metaclass=ABCMeta):
__slots__ = ()
@abstractmethod
def __iter__(self):
while False:
yield None
@classmethod
def __subclasshook__(cls, C):
if cls is Iterable:
return _check_methods(C, "__iter__")
return NotImplemented
У него есть абстрактный метод __iter__
который должен вернуть объект итератора. И метод __subclasshook__
который проверяет наличие у класса метод __iter__.
Таким образом, получается, что итерируемый объект это любой объект который реализует метод __iter__
class SomeIterable1(collections.abc.Iterable):
def __iter__(self):
pass
class SomeIterable2:
def __iter__(self):
pass
print(isinstance(SomeIterable1(), collections.abc.Iterable))
# True
print(isinstance(SomeIterable2(), collections.abc.Iterable))
# True
Но есть один момент, это функция iter()
. Именно эту функцией использует например цикл for для получения итератора. Функция iter() в первую очередь для получения итератора из объекта, вызывает его метод __iter__.
Если метод не реализован, то она проверяет наличие метода __getitem__
и если он реализован, то на его основе создается итератор. __getitem__
должен принимать индекс с нуля. Если не реализован ни один из этих методов, тогда будет вызвано исключение TypeError
.from string import ascii_letters
class SomeIterable3:
def __getitem__(self, key):
return ascii_letters[key]
for item in SomeIterable3():
print(item)
@python_job_interview
Please open Telegram to view this post
VIEW IN TELEGRAM
В зависимости от контекста, может означать либо функцию-генератор, либо итератор генератора (чаще всего, последнее). Методы
__iter__ и __next__
у генераторов создаются автоматически.С точки зрения реализации, генератор в Python — это языковая конструкция, которую можно реализовать двумя способами: как функция с ключевым словом yield или как генераторное выражение. В результате вызова функции или вычисления выражения, получаем объект-генератор типа types.GeneratorType. Канонический пример - генератор, порождающий последовательность чисел Фибоначчи, которая, будучи бесконечна, не смогла бы поместиться ни в одну коллекцию. Иногда термин применяется для самой генераторной функции, а не только объекта, возвращенного ей в качестве результата.
Так как в объекте-генераторе определены методы next и iter, то есть реализован протокол итератора, с этой точки зрения, в Python любой генератор является итератором.
Когда выполнение функции-генераторы завершается (при помощи ключевого слова return или достижения конца функции), возникает исключение StopIteration.
Что такое генераторная функция
Генераторная функция - функция, в теле которой встречается ключевое слово yield. Будучи вызвана, такая функция возвращает объект-генератор (generator object) (итератор генератора (generator iterator)).
Что делает yield
yield замораживает состояние функции-генератора и возвращает текущее значение. После следующего вызова __next__() функция-генератор продолжает своё выполнение с того места, где она была приостановлена.
В чем отличие [x for x in y] от (x for x in y)
Первое выражение возвращает список (списковое включение), второе – генератор.
@python_job_interview
Please open Telegram to view this post
VIEW IN TELEGRAM
Генератор хранит в памяти не все элементы, а только внутреннее состояние для вычисления очередного элемента. На каждом шаге можно вычислить только следующий элемент, но не предыдущий. Пройти генератор в цикле можно только один раз.
Как объявить генератор
использовать синтаксис (x for x in seq)
оператор yield в теле функции вместо return
встроенная функция iter, которая вызывает у объекта метод __iter__(). Этот метод должен возвращать генератор.
Как получить из генератора список
Передать его в конструктор списка: list(x for x in some_seq). Важно, что после этого по генератору уже нельзя будет итерироваться.
Что такое подгенератор
В Python 3 существуют так называемые подгенераторы (subgenerators). Если в функции-генераторе встречается пара ключевых слов
yield from
, после которых следует объект-генератор, то данный генератор делегирует доступ к подгенератору, пока он не завершится (не закончатся его значения), после чего продолжает своё исполнение.На самом деле
yield
является выражением. Оно может принимать значения, которые отправляются в генератор. Если в генератор не отправляются значения, результат данного выражения равен None.yield from
также является выражением. Его результатом является то значение, которое подгенератор возвращает в исключении StopIteration (для этого значение возвращается при помощи ключевого слова return).@python_job_interview
Please open Telegram to view this post
VIEW IN TELEGRAM
Можно ли извлечь элемент генератора по индексу
Нет, будет ошибка. Генератор не поддерживает метод getitem.
@python_job_interview
Please open Telegram to view this post
VIEW IN TELEGRAM
MRO – method resolution order, порядок разрешения методов. Алгоритм, по которому следует искать метод в случае, если у класса два и более родителей.
В классических классах поиск при наследовании по ссылкам на имена осуществляется в следующем порядке:
1. Сначала экземпляр
2. Затем его класс
3. Далее все суперклассы его класса с обходом сначала с глубину, а затем слева направо
Используется первое обнаруженное вхождение. Такой порядок называется DFLR (Обход вглубину и слева направо).
При наследовании классов нового стиля применяется правило MRO (порядок разрешения методов), т.е линеаризованный обход дерева классов, причем вложенный элемент наследования становится доступным в атрибуте mro данного класса. Такой алгорим называется C3-линеаризация. Наследование по правилу MRO осуществляется приблизительно в следующем порядке.
Перечисление всех классов, наследуемых экземпляром, по правилу поиска DFLR для классических классов, причем класс включается в результат поиска столько раз, сколько он встречается при обходе.
Просмотр в полученном списке дубликатов классов, из которых удаляются все, кроме последнего (крайнего справа) дубликата в списке.
Упорядочение по правилу MRO применяется при наследовании и вызове встроенной функции super(), которая всегда вызывает следующий по правилу MRO класс (относительно точки вызова).
Пример наследования в неромбовидных иерархаических деревьях:
class attr = 3 # D:3 E:2
class B(D) pass # | |
class E: attr = 2 # B C:1
class C(E): attr = 1 # / /
class A(B, C): pass # A
X = A() # |
print(X.attr) # X
# DFLR = [X, A, B, D, C, E]
# MRO = [X, A, B, D, C, E, object]
# И в версии 3.х и в версии 2.х (всегда) выводит строку "3"
Пример наследования в ромбовидных иерархаических деревьях:
class attr = 3 # D:3 D:3
class B(D) pass # | |
class C(D): attr = 1 # B C:1
class A(B, C): pass # / /
X = A() # A
print(X.attr) # |
# X
# DFLR = [X, A, B, D, C, D]
# MRO = [X, A, B, C, D, object] (сохраняет только последний дубликат D)
# Выводит строку "1" в версии 3.х, строку "3" в версии 2.х ("1" если D(object))
@python_job_interview
Please open Telegram to view this post
VIEW IN TELEGRAM
Основное различие между этими двумя методами состоит в том, что
__new__
обрабатывает создание объекта, а __init__
обрабатывает его инициализацию.__new__
вызывается автоматически при вызове имени класса (при создании экземпляра), тогда как __init__
вызывается каждый раз, когда экземпляр класса возвращается __new__
, передавая возвращаемый экземпляр в __init__
в качестве параметра self, поэтому даже если вы сохранили экземпляр где-нибудь глобально/статически и возвращали его каждый раз из __new__
, для него все-равно будет каждый раз вызываться __init__
.Из вышесказанного вытекает что сначала вызывается
__new__
, а потом __init__
@python_job_interview
Please open Telegram to view this post
VIEW IN TELEGRAM
В Python 3 при возбуждении исключения в блоке except, старое исключение сохраняется в атрибуте данных context и если новое исключение не обработано, то будет выведена информация о том, что новое исключение возникло при обработке старого («During handling of the above exception, another exception occurred:»). Также, можно связывать исключения в одну цепь или заменять старые новыми. Для этого используется конструкция raise новое_исключение from старое_исключение либо raise новое_исключение from None. В первом случае указанное исключение сохраняется в атрибуте
__cause__
и атрибут __suppress_context__
(который подавляет вывод исключения из __context__)
устанавливается в True. Тогда, если новое исключение не обработано, будет выведена информация о том, что старое исключение является причиной нового («The above exception was the direct cause of the following exception:»). Во втором случае __suppress_context__
устанавливается в True и __cause__
в None. Тогда при выводе исключения оно, фактически, будет заменено новым (хотя старое исключение всё ещё хранится в __context__)
.В Python 2 нет сцепления исключений. Любое исключение, выброшенное в блоке except, заменяет старое.
@python_job_interview
Please open Telegram to view this post
VIEW IN TELEGRAM
Прикрепляем два XML (1 файл, 2 файл) – это ответы на поисковые запросы, сделанные к одному из наших партнёров. В ответах лежат варианты перелётов (тег Flights) со всей необходимой информацией, чтобы отобразить билет на Aviasales.
На основе этих данных, нужно сделать вебсервис, в котором есть эндпоинты, отвечающие на следующие запросы:
- Какие варианты перелёта из DXB в BKK мы получили?
- Самый дорогой/дешёвый, быстрый/долгий и оптимальный варианты
- В чём отличия между результатами двух запросов (изменение маршрутов/условий)?
Язык реализации: python3 Формат ответа: json Используемые библиотеки и инструменты — всё на твой выбор.
Оценивать будем умение выполнять задачу имея неполные данные о ней, умение самостоятельно принимать решения и качество кода.
@python_job_interview
Please open Telegram to view this post
VIEW IN TELEGRAM
type это метакласс, который Питон внутренне использует для создания всех классов.
Когда вы пишете:
class Foo(Bar):
pass
Питон делает следующее:
- Есть ли у класса
Foo
атрибут __metaclass__
?- Если да, создаёт в памяти объект-класс с именем Foo, используя то, что указано в
__metaclass__.
- Если Питон не находит metaclass, он ищет
__metaclass__
в родительском классе Bar и попробует сделать то же самое.- Если же
__metaclass__
не находится ни в одном из родителей, Питон будет искать __metaclass__
на уровне модуля.- И если он не может найти вообще ни одного
__metaclass__
, он использует type для создания объекта-класса.@python_job_interview
Please open Telegram to view this post
VIEW IN TELEGRAM
Привет! Меня зовут Руслан. Около 12 лет я занимаюсь разработкой, из них девять — на Python. За это время я собеседовался на разные позиции десятки раз и сам провёл примерно пару сотен собеседований. Не всегда успешно :/ В этой статье поговорим о том, как снизить вероятность провалов и к чему быть готовым.
@python_job_interview
Please open Telegram to view this post
VIEW IN TELEGRAM