I want to work at Google! Telephone interview (part 3, nutritional)

From the comments to the previous article, in addition to a heap of useful information, a discussion of the flaws in my code, I also made a strategic decision to avoid C / C ++ programming in the next interview by hook or by crook. Affects the lack of practice of writing programs. For more than 4 years, he did not touch him and there was enough python for any statistical calculations and data visualization. But be sure to return to the classic textbooks next week. Comrades TheHorse and 0leGG shamed me in the second article, and AxisPod scored the last carnation in the coffin of my hopes that it will turn out to go on the old knowledge. Therefore, shifting the emphasis in the direction of your favorite Python, look at the possible tasks.

And more news from the fronts: after discussing the issue raised by danmiru , and a call from my recruiter, who learned about these publications on Habré (the world is too small), I made a strong decision not to publish the specific tasks that I had on interview. The list of topics for preparation and standard tasks taken from publicly available sources do not cause major problems for my future employer, I strongly hope.
Well, once again, I am very grateful to the habropublik for such an active discussion of these topics. After filtering out the comments “I would put the author on the wall,” and going straight to the proposals in which the code is discussed, I learned a lot of useful things for myself. Thank you very much!!!

Well, let's try to look at the data structures and a little more complex algorithms implemented on python. The tasks that we consider here are very strongly 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 programmer problems, and I cite sources where else they were discussed; I choose only those that I liked a lot; plus the problems in the book are solved in C, but I try to write them on 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, no more! In Python, there are no pointers per se , but you can assign any object to a variable. Consequently, we can make a chain of objects by assigning the next object from the chain to the property of the previous link. Practical value in this design is not particularly, but for the sake of practice ... (this can be a lot to justify).
That is, we will build the following structure:

class Element:
def __init__ ( self , data = None ) :
self . next = None
self . data = data

It is also more correct to make a class for the sequence itself. To add a new element to the beginning of the chain, find the necessary link:

class LinkedList:
def __init__ ( self , data = None ) :
self . head = None
if data:
# initializing the sheet, we immediately want to stuff data there
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 start of sequence
if delElement == self . head :
self . head = self . head . next
# gc in python will delete an object if no one references it.
# (reference count)
# or: del delElement - what will the experts say?
return true
pos = self . head
while ( not pos. next ) :
# neatly with the last element. pos - will change to
# the last
if delElement == pos. next :
pos. next = delElement. next
# if we delete the last element, then delElement.next == None
# again do you need del delElement 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 references to this object. If all links were deleted or reassigned - the object will be deleted. Here, before the 2.0 version of the python, there was a potential problem if the object referred to itself - it would never be deleted, so they introduced a regular check for obsession and now even such a construction will be released 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 lists (lists, tuples).
But if the task is to write such a data structure, you can generally implement a lot through the lambda functions, as it 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" )

Functions are a little confused, but you can figure out by looking at what they are doing.
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 of 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 much time, I finish the remaining 80 at breakneck speed. But what to do is a tradition. So let's go, that’s where my speed 80% began.

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

We use all the same topic related sequences. This task well tests C programming skills, since you have to work with pointers and specifically track code execution errors (lack of memory, incorrect input data). But for the python such a task will come down.

def mFromTheEnd ( self , m ) :
cur = self . head
if not cur: return None # check for 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, we run the first m elements along it, 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 need only two pointers to keep 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-sided connected sequence.

Spread double-related sequences with children

Tongues on the verge of fiction. This example was discussed, for example, here using the recursive method. You can also implement everything through iteration. The idea of ​​the method is as follows:

go through the sequences first, until we hit the empty element (end of the sequence)
if we see that the current element has a child - we throw it at the end of the sequence, we associate the tail with the child and vice versa
we find a new tail, running two pointers (tail runs twice as fast as cyclecheck), if there is a cycle, the pointers will sometime 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 bound sequence. And the stand-alone function links the two elements as relatives. To avoid evil tongues, I say in advance, this was done on purpose. In the production of such a hand to tear 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 looping checking

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
# The book has an error in this algorithm, since the first step is not taken
# and the initial conditions are the same, i.e. if always executed
if cyclecheck == lst. tail :
print ( "Circumference in 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) - obsession.

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 back (deFlatten). Since we did not delete information about children, then we can run through the sequence and when finding a link to the child - remove the connection of the tail with the child, and the child with the tail; call the child function recursively.
It is possible to achieve partitioning and iteratively. But it is better to run through the sequence from the end. When a child is found, cut it off from the previous element (this will be a new tail), remove the reference to the child from the new tail; follow the sequence. Everything will work fine (are there any comments from the algorithmic specialists?), 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 questions on the list of topics (well, that I was allowed to publish them) was the types of bypassing binary trees. If you don’t remember, I’m talking about the preorder (LPC), inorder (LPC) and postorder (LPC). This only means in what sequence we will look at the root (K), the left (L) branch and the right (R) branch. This question is quite common, and it has already been written about it 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
# great way to display root value

def inorder ( t ) :
if t:
for x in inderder ( t. left ) :
yield x
yield t. data
for x in inderder ( 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 ( )

For the iteration of the tree you need to store information about the branches that you want to visit. For a preorder traversal, a stack is suitable — this is a traversal in depth. Over iterative inorder bypass it was necessary to sit longer. But the same idea as last time. Just to get the leftmost element of the tree, we go down to it until we stumble on an empty sheet. We remove the previous value from the stack, this will be the sheet itself, print its value and look to the right. If there is nothing there, then we will get from the stack of the parent, who can already have the right element. And so on. The traversal goes in the order of the leftmost, root, right element.

Find the first non-duplicate character in the string.

In python, dictionaries (dict) and sets / sets (set) use a hash table for storing and finding values ​​/ keys. The algorithm given below will be at least O (n) (pass through the whole 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 any ideas how to increase the speed yet? Here everything was done through the usual sequence. Checking whether a character is in a sequence is not done in O (1) constant time, as for dictionaries and sets. So I think the use of dictionaries is slightly better.

Well, the last for today:

Reverse 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 respected 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

Tasks from my interview will not be, because I was very much asked not to publish them. I apologize.
Everything, start to kick!

Part 1
Part 2