Какие вопросы задают на собеседованиях на python junior'a/middl'a
У меня есть некоторый опыт прохождения python - собеседований на позиции junior/middle python разработчика и я им поделюсь. Эти вопросы можно разделить на такие группы: основы python, более глубокие вопросы про python, обще-алгоритмические вопросы, вопросы про другие языки, вопросы по базам данных.
Попробую осветить наиболее часто встречающиеся из них. Не секрет, что часто вопросы повторяются, конечно, всегда может быть что-то оригинальное, но костяк вопросов остается примерно неизменным. К слову, надо быть готовым к написанию кода на листочке.
Основы python
Какие типы данных в python?
- Изменяемые: list, dict, set
- Неизменяемые: number, boolean, string, tuple, frozenset
Объясните следующий код:
1 b = [i for i in range(10)] 2 b = (i for i in range(10)) 3 b = {i for i in range(10)} 4 b = {x: x**2 for x in range(10)}
- Создание списка от 0 до 9
- Создание генераторного выражения
- Создание сета от 0 до 9
- Создание словаря, ключи в котором - числа от 0 до 9, а значения - квадраты ключей
Что выведет на экран следующий код?
1 def a(): 2 print('test') 3 for i in range(10): 4 yield i 5 6 7 for i in a(): 8 print(i)
Здесь создается функция - генератор, соответственно test будет напечатано один раз, далее числа от 0 до 9:
test 0 1 2 3 4 5 6 7 8 9
Что здесь происходит?
1 a = [1, 2, 3] 2 b = a 3 a.pop() 4 b.pop() 5 print(a == b == [1])
Здесь в объект b копируется не сам список, а только ссылка на него, соответственно из одного массива будет удалено два последних элемента, последняя строчка напечатает True.
Какие есть элементы функционального программирования в python?
- map
- filter
- reduce
- lambda
map позволяет применить какую-либо функцию к любому iterable - объекту:
1 alist = ['1', '2', '3'] 2 alist = map(int, alist)
В python 2 map вернет список, но в третьей версии вернется объект - итератор. Соответственно все числа преобразуются в int.
filter повзоляет отобрать только определенные элементы (например все числа больше 1). Так же, как и в случае с map, в python 2 возвращается список, но в python 3 вернется объект - итератор.
1 alist = [1, 2, 3] 2 alist = filter(lambda x: x > 1, alist) 3 print(alist) # [2, 3] 4 # Что, в принципе эквивалентно следующему (для python 2): 5 [x for x in alist if x > 1] 6 # Или, для python 3: 7 (x for x in alist if x > 1)
reduce повзоляет произвести какие-либо вычисления над элементами iterable - объекта
1 from functools import reduce 2 _sum = reduce((lambda x, y: x + y), [1, 2, 3, 4]) 3 # конечно, гораздо лучше воспользоваться sum: 4 _sum = sum([1, 2, 3, 4])
lambda функцию удобно использовать например для сортировки массива кортежей по, например, второму элементу:
1 alist = [(2, 2, 3), (1, 1)] 2 alist = sorted(alist, key=lambda x: x[1]) 3 print(alist) # [(1, 1), (2, 2, 3)]
Как работает код вида:
1 def f(x, l=[]): 2 for i in range(x): 3 l.append(i*i) 4 print(l) 5 6 7 f(2) 8 f(3, [3, 2, 1]) 9 f(3)
Тут мы имеем функцию с default аргументом - списком, этот список создается один раз, в момент определения функции, при каждом следующем вызове используется тот же список. Но на строке номер 8 мы вызываем функцию с новым списком, который и используется при этом вызове, на строке же номер 9 будет вызвана функция со списком из первого вызова, соответственно, будет напечатано:
[0, 1] [3, 2, 1, 0, 1, 4] [0, 1, 0, 1, 4]
Напишите 3 способа инвертировать список в python.
1 reversed(alist) 2 alist[::-1] 3 alist.reverse()
В первом случае вернется итератор. Первые два способа не изменяют исходный список, а создают новый, третий - изменяет.
Как из [[1, 2], [3, 4]] получить [1, 2, 3, 4]?
1 alist = [[1, 2], [3, 4]] 2 new_list = [] 3 for el in alist: 4 for x in el: 5 new_list.append(x)
Или, что аналогично, но гораздо лучше (питоничнее и быстрее):
1 new_list = [x for el in alist for x in el]
Или, например, такой вариант (подсмотрел в книге Intermediate Python):
1 import itertools 2 alist = [[1, 2], [3, 4]] 3 print(list(itertools.chain.from_iterable(alist)))
Дано число типа int, как получить количество нулей в этом числе? Самый примитивный способ:
1 my_int = 1200 2 amount = 0 3 for x in str(my_int): 4 if x == '0': 5 amount += 1 6 7 8 print(amount)
Уже получше вариант:
1 my_int = 1200 2 res = len([symbol for symbol in str(my_int) if symbol == "0"]) 3 print(res)
Совсем хорошо:
1 res = str(my_int).count("0")
Как получить сумму чисел в массиве типа [1, 2, [3, 4, [5]], 6, [7]]? С помощью рекурсии:
1 alist = [1, 2, [3, 4, [5]], 6, [7]] 2 3 def get_sum(alist): 4 sum = 0 5 for x in alist: 6 if isinstance(x, list): 7 sum += get_sum(x) 8 else: 9 sum += x 10 return sum 11 12 print(get_sum(alist))
Как написать функцию, которая меняет местами в словаре ключи и значения?
1 def rev_k_v_dict(adict): 2 new_dict = dict() 3 for k, v in adict.items(): 4 new_dict[v] = k 5 return new_dict 6 7 assert rev_k_v_dict({1:'1', 2:'2'}) == {'1': 1, '2': 2}
Как написать функцию, которая рекурсивно возводит число в степень?
1 def rec_pow(x, n): 2 if n == 0: 3 return 1 4 return x * rec_pow(x, n-1) 5 6 assert rec_pow(2, 3) == 8 7 assert rec_pow(2, 2) == 4 8 assert rec_pow(3, 3) == 27
Как написать собственную функцию, которая разворачивает список?
1 def own_reverse(alist): 2 new_list = [] 3 for i in range(len(alist)-1, -1, -1): 4 new_list.append(alist[i]) 5 return new_list 6 7 assert own_reverse([3,2,1]) == [1, 2, 3]
Как написать функцию, которая разворачивает строку, но небуквенные символы оставляет на местах, примеры:str_reverse('abc') == 'cba', str_reverse('a2bc') == 'c2ba', str_reverse('ab%cd4') == 'dc%ba4'
1 def str_reverse(astr): 2 new_str = '' 3 char_to_ind = {} 4 for i in range(len(astr) - 1, -1, -1): 5 if astr[i].isalpha(): 6 new_str += astr[i] 7 else: 8 char_to_ind[astr[i]] = i 9 10 for k,v in char_to_ind.items(): 11 new_str = new_str[:v] + k + new_str[v:] 12 return new_str 13 14 assert str_reverse('abc') == 'cba' 15 assert str_reverse('v') == 'v' 16 assert str_reverse('a2bc') == 'c2ba' 17 assert str_reverse('ab%cd4') == 'dc%ba4'
Написать функцию, которая принимает на вход список int'ов, найти в нем первое повторяющееся число:
1 def first_recurring_char(alist): 2 aset = set() 3 for i, x in enumerate(alist): 4 if i == 0 and x in alist[1:]: 5 return x 6 if x in aset: 7 return x 8 aset.add(x) 9 10 assert first_recurring_char([1,2,3,3]) == 3 11 assert first_recurring_char([1,1,2,2,3,3]) == 1 12 assert first_recurring_char([1,2,3]) == None 13 assert first_recurring_char([2,5,5,2,3]) == 2
На вход даны два сортированных списка, слить эти два списка так, чтобы список на выходе содержал числа из обоих массивов и был отсортирован.
Можно сделать так:
1 def merge_sorted_arrays_naive(alist1, alist2): 2 return sorted(alist1+alist2) 3 4 assert merge_sorted_arrays_naive([0,3,4,31], [4, 6, 30]) == [0,3,4,4,6,30,31] 5 assert merge_sorted_arrays_naive([0,3,4,31], [4]) == [0,3,4,4,31] 6 assert merge_sorted_arrays_naive([0,3,4,31], []) == [0,3,4,31] 7 assert merge_sorted_arrays_naive([], []) == []
Временная сложность такого алгоритма будет n*log(n).
Более хороший вариант:
1 def merge_sorted_arrays_better(alist1, alist2): 2 out = [] 3 i, j = 0, 0 4 while i < len(alist1) or j < len(alist2): 5 if i == len(alist1): 6 out.append(alist2[j]) 7 j += 1 8 continue 9 elif j == len(alist2): 10 out.append(alist1[i]) 11 i += 1 12 continue 13 if alist1[i] < alist2[j]: 14 out.append(alist1[i]) 15 i += 1 16 elif alist1[i] == alist2[j]: 17 out.append(alist1[i]) 18 out.append(alist1[i]) 19 i += 1 20 j += 1 21 else: 22 out.append(alist2[j]) 23 j += 1 24 return out 25 26 assert merge_sorted_arrays_better([0,3,4,31], [4, 6, 30]) == [0,3,4,4,6,30,31] 27 assert merge_sorted_arrays_better([0,3,4,31], [4]) == [0,3,4,4,31] 28 assert merge_sorted_arrays_better([0,3,4,31], []) == [0,3,4,31] 29 assert merge_sorted_arrays_better([], []) == []
Написать функцию, которая убирает из списка все дубликаты, допустим, что просто применить set() к списку нельзя:
1 def remove_dubl(alist): 2 adict = {} 3 for x in alist: 4 adict[x] = 1 5 6 new_list = [] 7 for k in adict.keys(): 8 new_list.append(k) 9 return new_list 10 11 assert remove_dubl([1,1,1]) == [1] 12 assert remove_dubl([1,1,1,2,2]) == [1,2] 13 assert remove_dubl([1,2,3]) == [1,2,3]
Как передаются аргументы в функцию: по значению или по ссылке?
Если тип аргумента изменяемый - то по ссылке, если же неизменяемый - то по значению.
Что делает with?
Позволяет, например, делать что-нибудь с файлами, файл будет автоматически закрыт:
1 with open("x.txt") as f: 2 data = f.read() 3 # do something with data
Также with используется в многопоточном программировании для захвата lock'а:
1 with lock: 2 do something
Работа with тесно связана с менеджером контекста. Менеджер контекста инкапсулирует try...except...finally паттерн.
Что будет выведено на экран?
1 [range(1,11)] == list(range(1,11))
Будет False, потому что в случае вызова list будет вызван конструктор, который сформирует развернутый список.
Можно ли в качестве ключа в словаре использовать кортеж? Да:
1 adict = {(1,2): True} 2 print(adict)
В чем различия, когда мы один метод внутри класса называем с одним нижним подчеркиванием _test1, а другой с двумя, __test2?
1 class Test(): 2 def _test1(self): 3 print('test1') 4 def __test2(self): 5 print('test2') 6 7 print(Test.__dict__)
{'__module__': '__main__', '_test1': <function Test._test1 at 0x7f33798190d0>,
'_Test__test2': <function Test.__test2 at 0x7f337977d790>,
'__dict__': <attribute '__dict__' of 'Test' objects>,
'__weakref__': <attribute '__weakref__' of 'Test' objects>, '__doc__': None}
Как можно заметить, функция _test1 не поменяла свое название, а название __test2 поменялось на _Test__test2.
Написать функцию, которая считает медиану массива:
1 def median(alist): 2 alist = sorted(alist) 3 if len(alist) % 2 == 0: 4 ind1 = len(alist) // 2 5 ind2 = ind1 - 1 6 med = (alist[ind1] + alist[ind2]) / 2 7 else: 8 med = alist[len(alist) // 2] 9 return med 10 11 assert median([3,2,1]) == 2 12 assert median([1,2,3,4,5]) == 3 13 14 assert median([1,2,3,4]) == 2.5 15 assert median([1,1,20,20,8,8]) == 8 16 17 assert median([1]) == 1 18 assert median([1, 1]) == 1 19 assert median([1, 1, 2, 4]) == 1.5 20 assert median([0, 2, 5, 6, 8, 9, 9]) == 6 21 assert median([0, 0, 0, 0, 4, 4, 6, 8]) == 2
Внутренности python
Что такое декоратор? Напишите свой декоратор, а потом декоратор с параметрами.
Декоратор - это функция, которая меняет другую функцию. Простейший декоратор:
1 def my_dec(func): 2 def wrapper(): 3 print('foo') 4 func() 5 return wrapper
Так можно применить декоратор:
1 @my_dec 2 def test(): 3 print('bar')
Или, что абсолютно аналогично:
1 def test(): 2 print('bar') 3 4 5 test = my_dec(test)
Декоратор с параметрами:
1 def my_dec(func): 2 def wrapper(*args, **kwargs): 3 for arg in args: 4 print(arg) 5 func() 6 return wrapper 7 8 9 @my_dec 10 def test(): 11 print('foo') 12 13 14 test('lol')
Более сложный пример с декоратором:
1 def outer(ttl=None): 2 def decorator(func): 3 print(func) 4 5 def wrapper(astr): 6 print('ttl', ttl) 7 func(astr) 8 return wrapper 9 return decorator 10 11 12 @outer(ttl=15*60) 13 def test(astring): 14 print(astring) 15 print('bar') 16 17 18 test('lol')
Когда я впервые увидел подобный код, я не мог понять как работает outer, мне казалось, что это какая-то особенная декораторная магия, что-то вроде декоратора вложенного в декоратор. Чтобы разобраться, мне пришлось понять, как сделать то же самое без синтаксического сахара:
1 def outer(ttl=None): 2 def decorator(func): 3 print(func) 4 5 def wrapper(astr): 6 print('ttl', ttl) 7 func(astr) 8 return wrapper 9 return decorator 10 11 12 # @outer(ttl=15*60) 13 def test(astring): 14 print(astring) 15 print('bar') 16 17 18 test = outer(ttl=15*60)(test) 19 test('lol')
То есть, по сути, это декоратор (decorator), обернутый в функцию outer, задача которой принять аргумент ttl и передать его "глубже".
Зачем нужны декораторы?
Декораторы используются для ограничения доступа к некоторым ендпоинтам, например @login_required во Flask, также во Flask'e также используются для того, чтобы "привязывать" view к url'ам.
Напишите декоратор, который замеряет время работы функции.
1 import time 2 3 4 def timer(func): 5 def wrapper(): 6 init_time = time.time() 7 func() 8 print(time.time() - init_time) 9 return wrapper 10 11 12 @timer 13 def test(): 14 print('lol') 15 16 17 test()
Что такое генератор? Напишите свой генератор.
Чтобы объяснить, что такое генератор, нужно сначала рассказать об итераторах. Итератор - это такой объект, у которого есть два метода - __iter__ и next (__next__ в python 3). Итератор можно перебрать только один раз, после этого он будет "исчерпан". Пример итератора:
1 class Counter(object): 2 def __init__(self, size): 3 self.size = size 4 self.start = 0 5 6 def __iter__(self): 7 print("called __iter__", self.size) 8 return self 9 10 def next(self): 11 if self.start < self.size: 12 self.start += 1 13 return self.start 14 raise StopIteration 15 16 17 c = Counter(3) 18 for num in c: 19 print(num) 20 21 for num in c: 22 print(num) 23 24 ... python test.py 25 ('called __iter__', 3) 26 1 27 2 28 3 29 ('called __iter__', 3)
Итератор можно использовать один раз, после чего он будет исчерпан, при этом будет выброшено исключение StopIteration:
1 >>> c = Counter(2) 2 >>> c_iter = iter(c) 3 ('called __iter__', 2) 4 >>> c_iter.next() 5 1 6 >>> c_iter.next() 7 2 8 >>> c_iter.next() 9 Traceback (most recent call last): 10 File "<stdin>", line 1, in <module> 11 File "test.py", line 219, in next 12 raise StopIteration 13 StopIteration
Использование итераторов при создании матрицы не сработает:
1 >>> c2 = Counter(2) 2 >>> c3 = Counter(3) 3 >>> for x in c2: 4 ... for y in c3: 5 ... print x, y 6 ... 7 ('called __iter__', 2) 8 ('called __iter__', 3) 9 1 1 10 1 2 11 1 3 12 ('called __iter__', 3)
Также можно убедиться в том, что наш объект Counter - это self-iteraror, потому что его метод __iter__ возвращает сам объект (instance), в отличие от iterable - объектов типа list, у которых метод iter возвращает отдельный объект - итератор:
1 >>> print c 2 <test.Counter object at 0x7fa30a4a6950> 3 >>> print iter(c) 4 ('called __iter__', 2) 5 <test.Counter object at 0x7fa30a4a6950> 6 >>> id(c) == id(iter(c)) 7 ('called __iter__', 2) 8 True 9 10 >>> items=[1,2,3] 11 >>> print items 12 [1, 2, 3] 13 >>> 14 >>> print iter(items) 15 <listiterator object at 0x7fa30a4a6a10> 16 >>> id(items) == id(iter(items)) 17 False
Пример iterable - объекта, у него задается только __iter__ метод, по нему можно итерироваться сколько угодно раз:
1 CounterIterator = Counter 2 3 4 class Counter2(object): 5 def __init__(self, size): 6 self.size = size 7 8 def __iter__(self): 9 return CounterIterator(self.size) 10 11 c = Counter2(2) 12 13 for num in c: 14 print(num) 15 16 for num in c: 17 print(num) 18 19 20 1 21 2 22 1 23 2
Генератор - это функция, которая возвращает итератор, каждый раз "запоминает" свое состояние и генерирует по одному элементу за раз. Создается генератор, используя ключевое слово yield. Пример простого генератора:
1 def simple_generator(): 2 print("generate") 3 yield 1 4 yield 2 5 6 7 >>> print(simple_generator()) 8 >>> <generator object simple_generator at 0x7f68b6937cd0> 9 >>> print(dir(simple_generator())) 10 >>> ['__class__', '__delattr__', '__doc__', '__format__', '__getattribute__', 11 '__hash__', '__init__', '__iter__', '__name__', '__new__', '__reduce__', 12 '__reduce_ex__', '__repr__', '__setattr__', '__sizeof__', '__str__', 13 '__subclasshook__', 'close', 'gi_code', 'gi_frame', 'gi_running', 14 'next', 'send', 'throw'] 15 >>> id(iter(simple_generator())) == id(simple_generator()) 16 >>> True
Как вы можете заметить, при вызове генератора он не был исполнен, потому что генераторы, в отличие от функций, не исполняются при вызове, а только при итерации по ним. Также видно, что генератор возвращает объект - генератор, который является итератором (есть next и __iter__). Кроме того, как вы можете заметить, генератор - это также self-iteraror.
1 simple_gen = simple_generator() 2 for x in simple_gen: 3 print(x) 4 5 for x in simple_gen: 6 print(x)
Как и следовало ожидать от генератора, он исчерпан после итерации:
generate 1 2
Генераторы, в отличие от функций, позволяют итерироваться по ним. Также генераторы "замораживают" свое состояние после yield. Генераторы используются при работе с большими массивами данных, чтобы не загружать их в память целиком:
1 # Python 2 2 N = 100000000000000000 3 for x in range(N): 4 print(x) 5 6 Traceback (most recent call last): 7 File "test.py", line 252, in <module> 8 for x in range(N): 9 MemoryErrors
Но если использовать генератор (функция xrange в python 2 работает как бы как генератор), то все будет ок:
1 # Python 2 2 N = 100000000000000000 3 for x in xrange(N): 4 print(x)
Кстати, является ли функция range в третьем питоне генератором - это очень интересный вопрос. Какое-то время я был правда уверен, что функции xrange во втором питоне и range в третьем являются генераторами. Но, если проверить:
1 # Python 3 2 arange = range(1, 10) 3 4 dir(arange) 5 6 ['__bool__', 7 '__class__', 8 '__contains__', 9 '__delattr__', 10 '__dir__', 11 '__doc__', 12 '__eq__', 13 '__format__', 14 '__ge__', 15 '__getattribute__', 16 '__getitem__', 17 '__gt__', 18 '__hash__', 19 '__init__', 20 '__init_subclass__', 21 '__iter__', 22 '__le__', 23 '__len__', 24 '__lt__', 25 '__ne__', 26 '__new__', 27 '__reduce__', 28 '__reduce_ex__', 29 '__repr__', 30 '__reversed__', 31 '__setattr__', 32 '__sizeof__', 33 '__str__', 34 '__subclasshook__', 35 'count', 36 'index', 37 'start', 38 'step', 39 'stop']
Как можно заметить, range не имеет метода next, но имеет метод iter, что говорит о том, что это в каком-то смысле больше похоже на iterable, чем на генератор:
1 # Python 3 2 arange = range(1, 10) 3 4 for x in arange: 5 print(x) 6 1 7 2 8 3 9 4 10 5 11 6 12 7 13 8 14 9 15 16 for x in arange: 17 print(x) 18 1 19 2 20 3 21 4 22 5 23 6 24 7 25 8 26 9
И все же, range в третьем питоне - это генератор или iterable? Для меня на данный момент это открытый вопрос, может быть кто-то сможет меня поправить в комментариях. Буду только признателен.
Чем python 2 отличается от 3?
Конечно же, во втором питоне можно принтить без скобок, самое новое (асинхронность например) есть только в 3-ем питоне, также в нем есть поддержка юникода. В python 3 был улучшен GIL. В 3 ем python функция range стала такой как xrange во втором. Также в 3 питоне была добавлена библиотека mock.
Что такое GIL?
GIL - это Global Interpreter Lock. Это механизм, который обеспечивает потокобезопасность в python, защищая память от неосмотрительных действий программиста. GIL обеспечивает то, что в каждый момент времени активен только один поток. Переключение между потоками такое быстрое, что может показаться, что ваша программа выполняет несколько потоков одновременно, хотя на деле активен только один поток.
Чем итератор отличается от iterable - объекта?
По итератору можно пройти циклом for только один раз, а по iterable - объекту сколько угодно. Iterable - объект не имеет функции next, в отличие от iterator.
Хэширование. Что такое хэш-функция? Как определить, что можно хэшировать, а что нет?
Словарь в питоне реализован на основе хэш - таблицы, поэтому ключами словаря могут быть только хэшируемые типы данных, соответственно, ключами словаря могут быть только неизменяемые типы данных.
Общие вопросы. Алгоритмы.
Как найти индекс элемента в несортированном массиве? Линейным поиском:
1 def linear_search(alist, num): 2 if num in alist: 3 return alist.index(num) 4 return -1 5 6 assert linear_search([1, 2, 3], 2) == 1 7 assert linear_search([1, 2, 3, 3, 3], 3) == 2 8 assert linear_search([1, 2, 3], 5) == -1 9 assert linear_search([], 2) == -1
Алгоритмическая временная сложность такого поиска будет O(n).
Как найти индекс элемента в сортированном массиве? Бинарным поиском:
1 # 1 2 3 4 5 2 def binary_search(alist, num): 3 lo, hi = 0, len(alist) - 1 4 while lo <= hi: 5 mid = (lo + hi) // 2 6 7 if num == alist[mid]: 8 return mid 9 elif num < alist[mid]: 10 hi = mid - 1 11 elif num > alist[mid]: 12 lo = mid + 1 13 return -1 14 15 assert binary_search([1, 2, 3, 4, 5], 2) == 1 16 assert binary_search([1, 2, 3, 3, 3], 3) == 2 17 assert binary_search([1, 2, 3], 5) == -1 18 assert binary_search([], 2) == -1
Алгоритмическая временная сложность такого поиска будет O(log(n)).
Написать функции, вычисляющие факториал и последовательность Фибоначчи рекурсивно и итеративно:
1 # O(n) 2 def fact(n): 3 res = 1 4 for i in range(1, n+1): 5 res *= i 6 return res 7 8 assert fact(0) == 1 9 assert fact(1) == 1 10 assert fact(2) == 2 11 assert fact(3) == 6 12 assert fact(4) == 24 13 assert fact(5) == 120 14 15 # тоже O(n) 16 def fact_rec(n): 17 if n in {0, 1}: 18 return 1 19 n *= fact_rec(n-1) 20 return n 21 22 assert fact_rec(0) == 1 23 assert fact_rec(1) == 1 24 assert fact_rec(2) == 2 25 assert fact_rec(3) == 6 26 assert fact_rec(4) == 24 27 assert fact_rec(5) == 120 28 29 30 # O(n) 31 def fib(n): 32 alist = [0, 1] 33 for i in range(2, n+1): 34 alist.append(alist[i-1] + alist[i-2]) 35 return alist[n] 36 37 assert fib(0) == 0 38 assert fib(1) == 1 39 assert fib(2) == 1 40 assert fib(3) == 2 41 assert fib(4) == 3 42 assert fib(5) == 5 43 assert fib(6) == 8 44 assert fib(7) == 13 45 assert fib(8) == 21 46 47 # жесть O(2^n) экспонента 48 def fib_rec(n): 49 if n in {0, 1}: 50 return n 51 return fib_rec(n-1) + fib_rec(n-2) 52 53 assert fib_rec(0) == 0 54 assert fib_rec(1) == 1 55 assert fib_rec(2) == 1 56 assert fib_rec(3) == 2 57 assert fib_rec(4) == 3 58 assert fib_rec(5) == 5 59 assert fib_rec(6) == 8 60 assert fib_rec(7) == 13 61 assert fib_rec(8) == 21 62 assert fib_rec(9) == 34
Какие алгоритмы сортировки знаете?
Сортировка пузырьком, список будет отсортирован по возрастанию:
1 import random 2 alist = [random.randrange(10) for _ in range(10)] 3 4 for i in range(len(alist)-1, 0, -1): 5 for j in range(i): 6 if alist[j] > alist[j+1]: 7 alist[j], alist[j+1] = alist[j+1], alist[j] 8 print(alist)
А, вообще, конечно, чаще всего используются mergesort, quicksort или timsort, у которых временная сложность, как правило, n*log(n).
А, вообще, хороший cheat sheet есть тут.
Назовите несколько linux команд, состоящих из трех символов:
pwd tar ssh top sed awk cat man
Чем поток отличается от процесса?
Процессы содержат в себе поток(и). Потоки могут иметь доступ к области видимости друг друга, а процессы изолированы друг от друга.
Что такое MVC?
Паттерн проектирования Model View Controller, в котором Model отвечает за связь с БД, View - за представления данных (html шаблоны), а Сontroller - за обработку данных, полученных от модели и бизнес - логику.
Какие основные принципы ООП?
- Инкапсуляция - это когда есть приватные методы, не доступные за пределами класса.
- Полиморфизм - возможность переопределить методы и переменные в дочернем классе.
- Наследование - дочерний класс получает все методы и параметры родительского.
Что такое RESTful API?
Это API, которое отвечает JSON'ом или XML'ом, принимает GET, POST, PUT, DELETE запросы, не сохраняет данные о клиенте, GET - запросы не должны приводить к изменению состояния сервера. Один запрос приводит к какому-либо одному действию.
Вопросы про базы данных
Расскажите про SQL join'ы?
Создадим две таблицы :
1 CREATE TABLE orders ( 2 order_id INT, 3 customer_id INT); 4 INSERT INTO orders (order_id, customer_id) VALUES (1, 1); 5 INSERT INTO orders (order_id, customer_id) VALUES (2, 2); 6 INSERT INTO orders (order_id, customer_id) VALUES (3, 3); 7 8 CREATE TABLE customers ( 9 customer_name char(200), 10 customer_id INT); 11 INSERT INTO customers (customer_name, customer_id) VALUES ('foo', 2); 12 INSERT INTO customers (customer_name, customer_id) VALUES ('bar', 5); 13 INSERT INTO customers (customer_name, customer_id) VALUES ('test', 6);
orders:
| order_id | customer_id |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
customers:
| customer_name | customer_id |
|---|---|
| 'foo' | 2 |
| 'bar' | 5 |
| 'test' | 6 |
Тогда данный запрос:
1 SELECT orders.order_id, customers.customer_name 2 FROM orders 3 INNER JOIN customers ON orders.customer_id=customers.customer_id;
Вернет следующую таблицу:
| order_id | csutomer_name |
|---|---|
| 2 | 'foo' |
То есть INNER JOIN возвращает только "пересечение" из двух таблиц.
Если сделать LEFT JOIN:
1 SELECT orders.order_id, customers.customer_name 2 FROM orders 3 LEFT JOIN customers ON orders.customer_id=customers.customer_id;
То вернутся все результаты из левой таблицы и "пересечение" из правой:
| order_id | csutomer_name |
|---|---|
| 2 | 'foo' |
| 1 | null |
| 3 | null |
Если сделать RIGHT JOIN:
1 SELECT orders.order_id, customers.customer_name 2 FROM orders 3 RIGHT JOIN customers ON orders.customer_id=customers.customer_id;
То вернутся все результаты из правой таблицы и "пересечение" из левой:
| order_id | csutomer_name |
|---|---|
| 2 | 'foo' |
| null | 'bar' |
| null | 'test' |
Если сделать FULL OUTER JOIN:
1 SELECT orders.order_id, customers.customer_name 2 FROM orders 3 FULL OUTER JOIN customers ON orders.customer_id=customers.customer_id;
То вернется вообще все из обоих таблиц:
| order_id | cutomer_name |
|---|---|
| 1 | null |
| 2 | 'foo' |
| 3 | null |
| null | 'bar' |
| null | 'test' |
Эти SQL JOIN'ы могут быть представлены в виде диаграмм Венна:
Вопросы про другие языки
Чем отличаются переменные с var и без var в js?
Если в глобальной области - то ничем, если же внутри функции - то без var - это глобальная перменная, а с var - локальная.
Выводы
Надеюсь, что вам поможет этот пост, конечно он не сделает вас экспертом в python. Возможно, я где-то не слишком точно отвечал на вопросы, но на собеседованиях и не требуется точных академических определений, важно, чтобы вы могли объяснить какие-то понятия своими словами. И, конечно, этого материала явно не достаточно, чтобы претендовать на позицию senior разработчика.