I want to work at Google! Telephone Interview (Part 3, Nutritional)

    From the comments on the previous article, in addition to a bunch of useful information, discussion of the shortcomings of my code, I also made a strategic decision - by hook or by crook to avoid C / C ++ programming in the next interview. Affects the lack of practice writing programs. For more than 4 years he has not been touched and the python was enough for any statistical calculations and data visualization. But I will definitely return to the classic textbooks next week. Comrades TheHorse and 0leGG ashamed, I have a second state, and AxisPod scored the last nail in the coffin of my hopes, that will go to the old knowledge. Therefore, shifting the emphasis towards the beloved Python, let's look at possible tasks.

    And more news from the fronts: after discussionthe question raised by danmiru , and the call from my recruiter who found out about these publications on Habré (the world is still small), I made a strong-willed decision not to publish the specific tasks that I had in the interview. The list of topics for training and standard tasks taken from public sources do not cause big problems for, I hope, my future employer.
    Well and again, I am very grateful to the habro-audience for such an active discussion of these topics. Having filtered out the comments “I would have put the author to the wall”, and proceeding immediately to the proposals in which the code is discussed, I learned a lot of useful things for myself. Many thanks!!!

    Well, let's try to look at data structures and slightly more complex algorithms implemented in python. The tasks that we will consider here are very much inspired by the book Types of coding questions Google asks: Programming Interviews Exposed; Secrets to Landing Your Next Job (Programmer to Programmer) ” by John Mongan, Noah Suojanen and Eric Giguere. But I hope I do not violate copyright, because these are common programming problems, and I give sources where else they were discussed; I choose only those that I liked a lot; plus the tasks in the book are solved in C, I'm trying to write them in python.

    Linked list


    Remarkably, this data structure is implemented in C, which I so bravely decided not to touch.
    typedef struct IntElement {
        struct IntElement * next;
        int data;
    } IntElement;

    Last time, I won’t! There are no per se pointers in Python , but any object can be assigned to a variable. And therefore, we can make a chain of objects by assigning the next object from the chain to the property of the previous link. There is no particular practical value in such a design, but for the sake of practice ... (much can be justified by this).
    That is, we will build such a construction:
    class Element:
        def __init __ (self, data = None):
            self.next = None
            self.data = data

    It’s more correct to make a class for the sequence itself. To add a new element to the beginning of the chain, find the link you need:
    class LinkedList:
        def __init __ (self, data = None):
            self.head = None
            if data:
                # initializing the sheet, we immediately want to
                stuff the 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):
            # special case with the beginning of the sequence
            if delElement == self.head:
                self.head = self.head.next
                # gc in python will delete an object if no one refers to it
                # (reference count )
                # or: del delElement - what will the experts say?
                return True
            pos = self.head
            while (not pos.next):
                # tidy with the last element. pos - will change to
                # the penultimate 
                if delElement == pos.next:
                    pos.next = delElement.next
                    # if we delete the last element, then delElement.next == None
                    # again, is del delElement necessary here?
                    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 # or enough delElement.next = None
            self .head = None

    In python, the garbage collector tracks the state of objects by the number of links to this object. If all links have been deleted or reassigned, the object will be deleted. Here, prior to the 2.0 version of python, there was a potential problem if the object referred to itself - it would never have been deleted, so they introduced a regular check for looping and now even such a design will be freed after some time:
    class Untouchable:
        def __init __ (self):
            self.me = self

    But this is such a lyrical digression. In general, this kind of design is very artificial. In python, this type of data is easily replaced by regular sheets (lists, tuples).
    But if the task is to write this kind of data construction, you can generally implement a lot through the lambda functions, as was done here :
    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")

    The functions are a little confused, but you can figure it out by looking at what they do.
    Next, we look at the task that can be given for this structure

    Write a stack using a linked sequence of objects


    To those two classes that we described earlier, you need to add two methods push, pop
    class Stack (LinkedList):
        def push (self, data): insertFront (data)
     
        def pop (self):
            tmp = self.head.data
            delete (self.head)
            return tmp

    Unfortunately, it turns out like last time - I spend a lot of time writing 20% ​​of the text at the beginning, and then realizing that there is not that much time, I’ll add the rest 80 headlong. But what to do, this already looks like a tradition. So let's go, so my high-speed 80% started.

    Return the mth element from the end of the sequence (m = 0 - the last element)


    We use the whole subject with related sequences. This task tests the C programming skills well, as you have to work with pointers and specifically monitor code execution errors (lack of memory, incorrect input data). But for python, such a task will do.
        def mFromTheEnd (self, m):
            cur = self.head
            if not cur: return None # check for an empty sequence
            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

    The idea is that instead of storing data about the entire sequence and running along the first m elements, if this is possible (if not, return None, although you can also raise an exception). And then we reach the end of the sheet simultaneously with the second pointer, which is offset from the first by m elements. This method saves memory - we only need to keep two pointers in memory. And this is the O (n) algorithm, in the worst case, and this is the best that can be achieved for a one-way connected sequence.

    Spread double-linked sequences with children


    Inert tongue on the brink of fiction. This example was discussed, for example, here , using a recursive method. You can implement it all through iterations. The idea of ​​the method is as follows:

    we go through the sequence first, until we come across an empty element (end of the sequence)
    if we see that the current element has a child - throw it at the end of the sequence, tie the tail with the child and vice versa
    find a new tail, running with two pointers (tail runs twice as fast as cyclecheck), if there is a cycle - pointers will ever coincide.

    The constructor of this data structure is very simple, but it was done to simply create such a data structure. The class simply creates a double linked sequence. And a stand-alone function connects two elements, like relatives. To avoid evil languages, I say in advance, this was done on purpose. In production, hands need to be torn off.
    #! / 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
        # no loopback test
     
    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
                    # There is an error in the book this algorithm since the first step is not done
                    # and the initial conditions are the same, i.e. if is always executed
                    if cyclecheck == lst.tail:
                        print ("Looping in the data structure")
                        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) - loop .
     
        flat (st1)
     
        cur = st1.head
        while (cur):
            print (cur.data)
            cur = cur.next
     
    if __name__ == '__main__':
        main ()

    For practice, you can restore the data structure (deFlatten) back. Because Since we did not delete information about children, we can run in sequence and when we find a link to a child - remove the connection between the tail and the child, and the child with the tail; recursively call a function for a child.
    It is possible to achieve partitioning iteratively. But running in sequence is better from the end. When a child is found, cut it off from the previous element (this will be a new tail), remove the link to the child from the new tail; follow further in sequence. Everything will work fine (specialists-algorithmists have comments?), If there were no cycles in the structure. But we checked for this condition when we created a flat structure.

    Iterative binary tree traversal


    One of the issues on the list of topics (it’s good that I was allowed to publish them) was the types of binary tree traversal. If you do not remember, I’m talking about preorder (KLP), inorder (LKP) and postorder (KLP). This just indicates in what sequence we will look at the root (K), the left (L) branch and the right (P) branch. This question is quite common and has already been written about here and on 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
            # a great way to print the root value
     
    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 ()

    To iterate through the tree, you need to store information about the branches that you need to visit. A stack is suitable for a preorder traversal - this is a traversal in depth. I had to sit longer on the iterative inorder bypass. But the same idea as last time. Just to get the leftmost element of the tree, we go down to it until we come across an empty sheet. We take out the previous value from the stack, this will be the sheet itself, display its value and look to the right. If there is nothing there, then we will get from the stack the parent who already has the right element. Etc. The crawl is in the order of the leftmost, root, rightmost element.

    Find the first non-duplicate character in a string


    In python, dictionaries and sets use a hash table to store and find values ​​/ keys. The algorithm shown below will be at least O (n) (pass along the entire line), since it will take some more time to add new characters to the dictionary.
    #! / 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 ()

    Will there be ideas how to increase speed yet? Here then everything was done through the normal sequence. Checking whether a character is in a sequence is not done in constant time O (1), as for dictionaries and sets. So I think the use of dictionaries is slightly better.

    Well, the last for today:

    Flip the word order in a sentence


    reverseOrder = lambda str: '' .join ((x [:: - 1] for x in str [:: - 1] .split ()))
    rev_order = lambda s: '' .join (s.split () [ :: - 1]) # shorter version from reputable  printf

    The second method is not only shorter, but also faster:
    >>> 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

    There will be no problems from my interview, because I was very much asked not to publish them. I apologize.
    Everything, start kicking!

    Part 1
    Part 2

    Also popular now: