Из комментариев к предыдущей статье кроме кучи полезной информации, обсуждения недостатков моего кода, я вынес ещё и стратегическое решение — всеми правдами и неправдами избегать программирования на C/C++ на ближайшем интервью. Сказывается отсутствие практики написания программ. Уже больше 4х лет его не трогал и питона хватало для любых статистических вычислений и визуализации данных. Но обязательно вернусь к классическим учебникам на следующей недели. Товарищи TheHorse и 0leGG застыдили меня во второй статьe, а AxisPod забил последний гвоздик в гробик моих надежд, что получится выехать на старых знаниях. Поэтому смещая акцент именно в сторону любимого Python, посмотрим на возможные задачи.
И ещё новости с фронтов: после обсуждения вопроса, поднятого danmiru, и звонка от моего рекрутера, которая узнала о данных публикациях на Хабре (тесен же всё-таки мир), я принял волевое решение не публиковать те конкретные задачи, которые были у меня на интервью. Список же тем для подготовки и стандартные задачки, взятые из общедоступных источников не вызывают больших проблем у, сильно надеюсь, моего будущего работодателя.
Ну и ещё раз, я очень благодарен хабропублике за столь активное обсуждение данных топиков. Отфильтровав комментарии «я бы автора к стенке бы поставил», и переходя сразу к предложениям, в которых обсуждается код — почерпнул для себя очень-очень много полезного. Большое Спасибо!!!
Ну давайте уже попробуем посмотреть на структуры данных и чуть более сложные алгоритмы, реализованные на питоне. Задачи, которые мы рассмотрим здесь очень сильно навеяны книгой «Types of coding questions Google asks: Programming Interviews Exposed; Secrets to Landing Your Next Job (Programmer to Programmer)» за авторством John Mongan, Noah Suojanen и Eric Giguere. Но надеюсь, я не нарушаю авторское право, т.к. это распространённые программистские проблемы, и я привожу источники где ещё они обсуждались; Я выбираю только те, что мне сильно понравились; плюс задачи в книге решаются на Си, я же пытаюсь их писать на питоне.
Замечательно данная структура данных реализуется в Си, который я так отважно решил не трогать.
Последний раз, больше не буду! В Python нету указателей per se, но можно переменной присвоить любой объект. А следовательно, мы можем сделать цепочку объектов, присваивая следующий объект из цепочки свойству предыдущего звена. Практической ценности в такой конструкции особенно нет, но ради практики… (этим можно многое оправдать).
То есть будем строить такую конструкцию:
Правильнее сделать ещё и класс для самой последовательности. Что бы добавить новый элемент в начало цепочки, найти нужное звено:
В питоне сборщик мусора отслеживает состояние объектов по числу ссылок на этот объект. Если все ссылки были удалены или переназначены — объект будет удалён. Тут, до 2.0 версии питона была потенциальная проблема, если объект ссылался сам на себя — он никогда не был бы удалён, поэтому ввели штатную проверку на зацикленность и теперь даже такая конструкция освободится после какого-то времени:
Но это такое лирическое отступление. И вообще такого рода конструкция — очень искусственная. В питоне такой тип данных с лёгкостью заменяется обычными листами (lists, tuples).
Но если же стоит задача написать такого рода конструкцию данных — можно вообще многое реализовать через лямбда функции, как это было сделано тут:
Чуть запутано названы функции, но можно разобраться, глянув на то, что они делают.
Далее посмотрим на задачу, которую могут дать для данной структуры
К тем двум классам, что мы описали раньше нужно добавить два метода
К сожалению, тут получается, как в прошлый раз — я огромное время трачу на написание 20% текста в начале, а потом понимая, что времени не так уж и много, сломя голову дописываю остальные 80. Но что поделать, это уже похоже традиция. Так что поехали, вот и начались мои скоростные 80%.
Пользуемся всё теме же связанными последовательностями. Данная задача хорошо проверяет навыки программирование на Си, т.к. приходится работать с указателями и специально отслеживать ошибки выполнения кода (нехватка памяти, неправильные входные данные). Но и для питона такая задача сойдёт.
Идея заключается в том, что вместо того, что бы хранить данные о всей последовательности и бежим по ней первых m элементов, если такое возможно (если нет — возвращаем None, хотя можно ещё и исключение поднять). А потом добегаем до конца листа одновременно со вторым указателем, который смещён от первого на m элементов. Этот способ экономит память — нам нужно только два указателя держать в памяти. И это O(n) алгоритм, в наихудшем варианте, а это лучшее, чего можно добиться для односторонней связанной последовательности.
Косноязычность на гране фантастики. Данный пример обсуждался, например, тут, используя рекурсивный метод. Можно же реализовать всё через итерации. Идея метода такова:
проходим сначала последовательности, пока не наткнёмся на пустой элемент (конец последовательности)
если видим, что у текущего элемента есть ребёнок — закидываем его в конец последовательности, связываем хвост с ребёнком и наоборот
находим новый хвост, пробегая двумя указателями (tail бежит в два раза быстрее cyclecheck), если есть цикл — указатели когда-нибудь совпадут.
Конструктор данной структуры данных очень простой, но это делалось, что бы просто создать такую структуру данных. Класс просто создаёт двойную связанную последовательность. И отдельно стоящая функция связывает два элемента, как родственники. Что бы избежать злых языков, заранее говорю, так было сделано специально. В production за такое руки нужно отрывать.
Для практики можно восстановить обратно структуру данных (deFlatten). Т.к. мы не удаляли информацию о детях, то можно бежать по последовательности и при нахождении ссылки на ребёнка — удалить связь хвоста с ребёнком, и ребёнка с хвостом; рекурсивно вызвать функцию для ребёнка.
Можно разбиения добиться и итеративно. Но бежать по последовательности лучше с конца. При нахождении ребёнка — отрезать его от предыдущего элемента (это будет новый хвост), из нового хвоста убрать ссылку на ребёнка; следовать дальше по последовательности. Всё будет нормально работать (есть замечания у спецов-алгоритмистов?), если в структуре не было циклов. Но мы проверяли на это условие, когда создавали плоскую структуру.
Одним из вопросов в списке тем (хорошо, что мне разрешили их публиковать) были типы обхода бинарных деревьев. Если Вы не помните, я говорю о preorder (КЛП), inorder (ЛКП) и postorder (ЛПК). Это всего лишь обозначает в какой последовательности мы будем смотреть на корень (К), левую (Л) ветку и правую (П) ветку. Данный вопрос встречается достаточно часто и о нём уже писали тут и на stackoverflow.
Для итерации по дереву нужно хранить информацию о ветках, которые нужно посетить. Для preorder обхода подходит стек — это же обход в глубину. Над итеративным inorder обходом пришлось посидеть подольше. Но та же идея, что и в прошлый раз. Только что бы получить самый левый элемент дерева, мы и спускаемся к нему, пока не наткнёмся на пустой лист. Вынимаем из стека предыдущие значение, это и будет сам лист, выводим его значение и смотрим вправо. Если там ничего нет, то мы достанем из стека родителя, у которого правый элемент уже может быть. И так далее. Обход идёт в порядке самый левый, корень, правый элемент.
В питоне словари (dict) и множества/наборы (set) используют хеш-таблицу для хранения и нахождения значений/ключей. Алгоритм, приведённый снизу будет как минимум O(n) (проход по всей строке), так как потратится ещё какое-то время на добавление новых символов в словарь.
Будут ли идеи как увеличить скорость ещё? Вот тут всё делалось через обычные последовательности. Проверка находится ли символ в последовательности — не делается за константное время O(1), как для словарей и множеств. Так что думается использование словарей чуть-чуть лучше.
Ну и последнее на сегодня:
Второй способ не только короче, но и быстрее:
Задач с моего интервью не будет, т.к. меня очень сильно попросили их не публиковать. Прошу прощения.
Всё, начинайте пинать!
Часть 1
Часть 2
И ещё новости с фронтов: после обсуждения вопроса, поднятого danmiru, и звонка от моего рекрутера, которая узнала о данных публикациях на Хабре (тесен же всё-таки мир), я принял волевое решение не публиковать те конкретные задачи, которые были у меня на интервью. Список же тем для подготовки и стандартные задачки, взятые из общедоступных источников не вызывают больших проблем у, сильно надеюсь, моего будущего работодателя.
Ну и ещё раз, я очень благодарен хабропублике за столь активное обсуждение данных топиков. Отфильтровав комментарии «я бы автора к стенке бы поставил», и переходя сразу к предложениям, в которых обсуждается код — почерпнул для себя очень-очень много полезного. Большое Спасибо!!!
Ну давайте уже попробуем посмотреть на структуры данных и чуть более сложные алгоритмы, реализованные на питоне. Задачи, которые мы рассмотрим здесь очень сильно навеяны книгой «Types of coding questions Google asks: Programming Interviews Exposed; Secrets to Landing Your Next Job (Programmer to Programmer)» за авторством John Mongan, Noah Suojanen и Eric Giguere. Но надеюсь, я не нарушаю авторское право, т.к. это распространённые программистские проблемы, и я привожу источники где ещё они обсуждались; Я выбираю только те, что мне сильно понравились; плюс задачи в книге решаются на Си, я же пытаюсь их писать на питоне.
Связанная последовательность (linked list)
Замечательно данная структура данных реализуется в Си, который я так отважно решил не трогать.
typedef struct IntElement {
struct IntElement *next;
int data;
} IntElement;
Последний раз, больше не буду! В Python нету указателей per se, но можно переменной присвоить любой объект. А следовательно, мы можем сделать цепочку объектов, присваивая следующий объект из цепочки свойству предыдущего звена. Практической ценности в такой конструкции особенно нет, но ради практики… (этим можно многое оправдать).
То есть будем строить такую конструкцию:
class Element:
def __init__(self, data=None):
self.next = None
self.data = data
Правильнее сделать ещё и класс для самой последовательности. Что бы добавить новый элемент в начало цепочки, найти нужное звено:
class LinkedList:
def __init__(self, data = None):
self.head = None
if data:
# инициализируя лист, мы сразу хотим запихнуть туда данные
newElement = Element(data)
self.head = newElement
def insertFront(self, data):
newElement = Element(data)
newElement.next = self.head
self.head = newElement
def insertBack(self, data):
pos = self.head
while(not pos.next): pos = pos.next
pos.next = Element(data)
def find(self, data):
next = self.head
while(not next and data != next.data): next = next.next
return next
def delete(self, delElement):
# специальный случай с началом последовательности
if delElement == self.head:
self.head = self.head.next
# gc в питоне удалит объект, если на него никто не ссылается
# (reference count)
# или же: del delElement - что скажут знатоки?
return True
pos = self.head
while(not pos.next):
# аккуратно с последним элементом. pos - будет меняться до
# предпоследнего
if delElement == pos.next:
pos.next = delElement.next
# если удаляем последний элемент, то delElement.next == None
# опять таки нужно ли здесь del delElement?
return True
pos = pos.next
return False
def deleteAll(self):
while(not self.head.next):
delElement = self.head
self.head = self.head.next
del delElement # или достаточно delElement.next = None
self.head = None
В питоне сборщик мусора отслеживает состояние объектов по числу ссылок на этот объект. Если все ссылки были удалены или переназначены — объект будет удалён. Тут, до 2.0 версии питона была потенциальная проблема, если объект ссылался сам на себя — он никогда не был бы удалён, поэтому ввели штатную проверку на зацикленность и теперь даже такая конструкция освободится после какого-то времени:
class Untouchable:
def __init__(self):
self.me = self
Но это такое лирическое отступление. И вообще такого рода конструкция — очень искусственная. В питоне такой тип данных с лёгкостью заменяется обычными листами (lists, tuples).
Но если же стоит задача написать такого рода конструкцию данных — можно вообще многое реализовать через лямбда функции, как это было сделано тут:
w = sys.stdout.write
cons = lambda el, lst: (el, lst)
mklist = lambda *args: reduce(lambda lst, el: cons(el, lst), reversed(args), None)
car = lambda lst: lst[0] if lst else lst
cdr = lambda lst: lst[1] if lst else lst
nth = lambda n, lst: nth(n-1, cdr(lst)) if n > 0 else car(lst)
length = lambda lst, count=0: length(cdr(lst), count+1) if lst else count
begin = lambda *args: args[-1]
display = lambda lst: begin(w("%s " % car(lst)), display(cdr(lst))) if lst else w("niln")
Чуть запутано названы функции, но можно разобраться, глянув на то, что они делают.
Далее посмотрим на задачу, которую могут дать для данной структуры
Написать стек, используя связанную последовательность объектов
К тем двум классам, что мы описали раньше нужно добавить два метода
push, popclass Stack(LinkedList):
def push(self, data): insertFront(data)
def pop(self):
tmp = self.head.data
delete(self.head)
return tmp
К сожалению, тут получается, как в прошлый раз — я огромное время трачу на написание 20% текста в начале, а потом понимая, что времени не так уж и много, сломя голову дописываю остальные 80. Но что поделать, это уже похоже традиция. Так что поехали, вот и начались мои скоростные 80%.
Вернуть m-тый элемент с конца последовательности (m=0 — последний элемент)
Пользуемся всё теме же связанными последовательностями. Данная задача хорошо проверяет навыки программирование на Си, т.к. приходится работать с указателями и специально отслеживать ошибки выполнения кода (нехватка памяти, неправильные входные данные). Но и для питона такая задача сойдёт.
def mFromTheEnd(self, m):
cur = self.head
if not cur: return None # проверка на пустую последовательность
for i in range(m):
if cur.next: cur = cur.next
else: return None
mcur = self.head
while(cur.next):
mcur = mcur.next
cur = cur.next
return mcur
Идея заключается в том, что вместо того, что бы хранить данные о всей последовательности и бежим по ней первых m элементов, если такое возможно (если нет — возвращаем None, хотя можно ещё и исключение поднять). А потом добегаем до конца листа одновременно со вторым указателем, который смещён от первого на m элементов. Этот способ экономит память — нам нужно только два указателя держать в памяти. И это O(n) алгоритм, в наихудшем варианте, а это лучшее, чего можно добиться для односторонней связанной последовательности.
Распластать дважды-связанные последовательности с детьми
Косноязычность на гране фантастики. Данный пример обсуждался, например, тут, используя рекурсивный метод. Можно же реализовать всё через итерации. Идея метода такова:
проходим сначала последовательности, пока не наткнёмся на пустой элемент (конец последовательности)
если видим, что у текущего элемента есть ребёнок — закидываем его в конец последовательности, связываем хвост с ребёнком и наоборот
находим новый хвост, пробегая двумя указателями (tail бежит в два раза быстрее cyclecheck), если есть цикл — указатели когда-нибудь совпадут.
Конструктор данной структуры данных очень простой, но это делалось, что бы просто создать такую структуру данных. Класс просто создаёт двойную связанную последовательность. И отдельно стоящая функция связывает два элемента, как родственники. Что бы избежать злых языков, заранее говорю, так было сделано специально. В production за такое руки нужно отрывать.
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import sys
class Element:
def __init__(self, data=None):
self.next = None
self.prev = None
self.data = data
self.child = None
class DoubleLinkedList:
def __init__(self, data=None):
self.head = None
self.tail = None
if data:
for dat in data:
newEl = Element(dat)
if self.tail: self.tail.next = newEl
newEl.prev = self.tail
if not self.head: self.head = newEl
self.tail = newEl
def addChild(parent, child):
parent.child = child
# нет проверки на зацикленности
def flat(lst):
cur = lst.head
while(cur):
if cur.child:
lst.tail.next = cur.child
cur.child.prev = lst.tail
cyclecheck = lst.tail
while(lst.tail.next and lst.tail.next.next):
cyclecheck = cyclecheck.next
lst.tail=lst.tail.next.next
# В книге ошибка в этом алгоритме, т.к. не делается первый шаг
# а начальные условия одинаковы, т.е. if всегда выполняется
if cyclecheck == lst.tail:
print("Зацикленность в структуре данных")
sys.exit()
if lst.tail.next: lst.tail= lst.tail.next
cur = cur.next
def main():
st1 = DoubleLinkedList(range(6))
st2 = DoubleLinkedList(range(4))
st3 = DoubleLinkedList(range(3))
addChild(st1.head, st2.head)
addChild(st1.tail, st3.head)
# addChild(st2.tail, st3.head) - зацикленность.
flat(st1)
cur = st1.head
while(cur):
print(cur.data)
cur = cur.next
if __name__ == '__main__':
main()
Для практики можно восстановить обратно структуру данных (deFlatten). Т.к. мы не удаляли информацию о детях, то можно бежать по последовательности и при нахождении ссылки на ребёнка — удалить связь хвоста с ребёнком, и ребёнка с хвостом; рекурсивно вызвать функцию для ребёнка.
Можно разбиения добиться и итеративно. Но бежать по последовательности лучше с конца. При нахождении ребёнка — отрезать его от предыдущего элемента (это будет новый хвост), из нового хвоста убрать ссылку на ребёнка; следовать дальше по последовательности. Всё будет нормально работать (есть замечания у спецов-алгоритмистов?), если в структуре не было циклов. Но мы проверяли на это условие, когда создавали плоскую структуру.
Итеративный обход бинарныx деревьев
Одним из вопросов в списке тем (хорошо, что мне разрешили их публиковать) были типы обхода бинарных деревьев. Если Вы не помните, я говорю о preorder (КЛП), inorder (ЛКП) и postorder (ЛПК). Это всего лишь обозначает в какой последовательности мы будем смотреть на корень (К), левую (Л) ветку и правую (П) ветку. Данный вопрос встречается достаточно часто и о нём уже писали тут и на stackoverflow.
#!/usr/bin/env python
# -*- coding: utf-8 -*-
class N:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def __unicode__(self):
return '%s' % self.data
# отличный способ выводить значение корня
def inorder(t):
if t:
for x in inorder(t.left):
yield x
yield t.data
for x in inorder(t.right):
yield x
def iterate_preorder(root):
stack = []
stack.append(root)
while stack:
cur = stack.pop()
yield cur.data
if cur.right: stack.append(cur.right)
if cur.left : stack.append(cur.left)
def iterate_inorder(root):
stack = []
cur = root
while stack or cur:
if cur:
stack.append(cur)
cur = cur.left
else:
if stack:
cur = stack.pop()
yield cur.data
cur = cur.right
def main():
bt = N(4 ,N(2, N(1), N(3)), N(6, N(5), N(7, None, N(8))))
print(list(iterate_preorder(bt)))
print(list(iterate_inorder(bt)))
return 0
if __name__ == '__main__':
main()
Для итерации по дереву нужно хранить информацию о ветках, которые нужно посетить. Для preorder обхода подходит стек — это же обход в глубину. Над итеративным inorder обходом пришлось посидеть подольше. Но та же идея, что и в прошлый раз. Только что бы получить самый левый элемент дерева, мы и спускаемся к нему, пока не наткнёмся на пустой лист. Вынимаем из стека предыдущие значение, это и будет сам лист, выводим его значение и смотрим вправо. Если там ничего нет, то мы достанем из стека родителя, у которого правый элемент уже может быть. И так далее. Обход идёт в порядке самый левый, корень, правый элемент.
Найти первый не повторяющийся символ в строке
В питоне словари (dict) и множества/наборы (set) используют хеш-таблицу для хранения и нахождения значений/ключей. Алгоритм, приведённый снизу будет как минимум O(n) (проход по всей строке), так как потратится ещё какое-то время на добавление новых символов в словарь.
#!/usr/bin/env python
# -*- coding: utf-8 -*-
def nonRepeated(st):
repeated = dict()
for l in st:
if l in repeated: repeated[l] =0
else: repeated[l] = 1
for l in st:
if repeated[l]: return l
def main():
print(nonRepeated('test'))
return 0
if __name__ == '__main__':
main()
Будут ли идеи как увеличить скорость ещё? Вот тут всё делалось через обычные последовательности. Проверка находится ли символ в последовательности — не делается за константное время O(1), как для словарей и множеств. Так что думается использование словарей чуть-чуть лучше.
Ну и последнее на сегодня:
Перевернуть порядок слов в предложении
reverseOrder = lambda str: ' '.join((x[::-1] for x in str[::-1].split()))
rev_order = lambda s: ' '.join(s.split()[::-1]) # короче вариант от уважаемого printf
Второй способ не только короче, но и быстрее:
>>> from timeit import Timer
>>> Timer("reverseOrder('1 2 3 45')", "from __main__ import reverseOrder").timeit()
3.4366888999938965
>>> Timer("rev_order('1 2 3 45')", "from __main__ import rev_order").timeit()
0.9511728286743164
Задач с моего интервью не будет, т.к. меня очень сильно попросили их не публиковать. Прошу прощения.
Всё, начинайте пинать!
Часть 1
Часть 2
