Pull to refresh

Я хочу работать в Google! Телефонное интервью (часть 3, питоноводческая)

Reading time16 min
Views9.8K
Из комментариев к предыдущей статье кроме кучи полезной информации, обсуждения недостатков моего кода, я вынес ещё и стратегическое решение — всеми правдами и неправдами избегать программирования на 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. Но надеюсь, я не нарушаю авторское право, т.к. это распространённые программистские проблемы, и я привожу источники где ещё они обсуждались; Я выбираю только те, что мне сильно понравились; плюс задачи в книге решаются на Си, я же пытаюсь их писать на питоне.

Связанная последовательность (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, pop
class 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
            elsereturn 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.tailself.tail.next = newEl
                newEl.prev = self.tail
                if not self.headself.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(7None, 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
Tags:
Hubs:
Total votes 48: ↑38 and ↓10+28
Comments44

Articles