I want to work at Google! Telephone interview (part 2)
Today we will discuss the technical aspects and the implementation of tasks in Python and C / C ++, with which we will be thrown by an engineer from Google. Let's start with the most trivial problems with the subsequent increase in complexity. In parallel, let us pay attention to what is worth mentioning during the interview and where not to fall into the trap.
If you see a way to improve the algorithm or the code given in this article - you are welcome to unsubscribe in the comments. I want to learn something new on this publication too.
Telephone technical interview - very original in itself. In those companies where I was lucky enough to go through it, we usually talked about my previous projects, about the complexities, implementations and optimizations of the code. Then, if the examining engineer decided to test my problem-solving skills, he would give the task, which I solved simply by speaking pseudo-code, and verbally describing the algorithms and analysis of the solution. In Google, everything is much more complicated. At the very least, this is due to the fact that, in addition to the process of thinking about the problem and voicing solutions, you simultaneously have to print the code in Google Doc, which the engineer hanging from the other end of the phone line is watching at the same time.
The situation is worsened by the fact that you have to constantly monitor the indentation that does not automatically appear in Google Docs, and the lack of syntax highlighting doesn’t really help in perceiving your own code. My advice - just practice writing code in Google Docs and notifying others and perplexed pets aloud what you are doing there is so interesting.
')
If the task is very simple, which is exactly what we will consider today, the algorithm of your answer should be approximately as follows:
Probably, let's start with the problems from this source .
It seems that it can be even easier? In Python, you can flip a string in several ways.
Options - in the forehead!
The task is terribly trivial. And you can write the implementation in general in one line or using the python lambda functionality:
But sometimes the examiner asks to write another implementation version or imposes some additional conditions. For example, you wrote a function using an additional variable string to which you add a character from the given one to the beginning (a variant with out2 from the first example). And the examiner may ask to implement the function without using additional variables at all.
It is clear that the more firewood you have in your implementation, the slower the function will work.
We look as it looks in pure Si:
We need to add a few words about this implementation. Firstly, in pure ANSI C there is no boolean type (in C ++ there is a bool). Therefore, we will return to the place of this simple int. Further, why return anything at all? Often they pay attention to how the candidate foresees possible program errors and prevents them or lets the program know that such an error has occurred. In Python, language can handle exceptions by wrapping the code in a
Do not forget that in C the transfer of arguments to a function occurs by value (call by value, unlike call by reference), so that the values of the arguments passed to the function are copied to the stack. So if we want to change one or more of these arguments inside a function, it is necessary to pass a pointer to this variable, and not its own.
But the above code is not the most effective. There are two reasons for this:
Let's demonstrate a faster and more resource-saving code:
Those. this case works for even and odd lengths. And additionally, we checked the nontrivial case when the length of the string is zero.
Perhaps this will be the fastest and shortest code for this task. Since rearranging two variables in places without resorting to the help of thirds in C is not possible to implement. The last character of the string '\ 0' does not move, because when i = 0, we will change the penultimate character with the first, the length of the string does not change during the flip.
In order not to be silent, and indeed to clarify the task - it is necessary to inquire about the numbers from which the series should begin ("0 1 1", or "1 1 2", or even "1 2 3"). This is not only a clarification, but also a way to show that you are not one of those programmers who do not understand the end of the task headlong to write code. It is considered good practice to bring several algorithms or ways to solve a problem (I even started with stupid brute-force solutions, but distinctly warned that this algorithm would be extremely inefficient since it can be improved). Then he gave an analysis of the complexity of the algorithms for big-O (big-O), asked what kind of implementation the examiner would like to see, and only after that would he start coding. It often happens that an efficient algorithm requires a complex implementation. And in the conditions of a telephone conversation (30-45 minutes, rarely up to an hour), the examiner wants to look at your skills in at least several tasks. Therefore, he may decide that you know different ways to solve the problem, it will be enough to write a less efficient algorithm, but which can be written faster.
fib_N_rec is a recursive way to find the Fibonacci number. We must specify the conditions for the end of the recursion (base case), these will be the numbers at the zero and first positions, 0 and 1, respectively. The recursive case (n> 1) calls a function with the previous two numbers. But precisely because each copy of the function calls two other copies — this method of implementation is terribly wasteful. It also spends memory for storing the values of variable functions on the stack, and it also loads the processor with multiple calls to what we have just considered, giving the complexity of the algorithm of order O (2 ^ n). Therefore, if we save the values in the memo dictionary, the process will speed up many times (fib_rec), giving O (n), plus due to the preservation of the previous values, subsequent function calls will get values much faster.
For any task, recursion can be avoided altogether by replacing it with iterations. In the case of problems of passing through trees or graphs, this usually requires storing local variables on the stack. But for our simple task, we can only hold the values of the last two variable Fibonacci numbers. Again, you need to be careful with the initial conditions and check the cycle for several initial conditions. This way we prevent the occurrence of an error.
There is a way to express the values of Fibonacci numbers through the Binet formula. At the interview, such details are usually not asked, but if you know about any mathematical property of the sequence, be sure to mention it. Thus, you show your general education and the ability to analyze the problem from different angles.
For this case, the Binet formula works only up to the 70th element of the sequence, inclusive, further because of the accumulating error of floating point operations, the calculated value will be erroneous.
For C, you can write a one-liner function:
The disadvantages are the same, so if this task appears among the questions asked, we can mention such a solution, describing the shortcomings, add preservation of values to a temporary array, and recalling the Binet formula (or the Lukos sequence formulas in general) focus on an iterative solution.
There is no trick here. Instead of a separate loop in a row, a list concatenation method was used, each element of which was converted to a string and combined with tabulation and other elements.
If you decide to write a function simply as:
need to be careful in the line with the formation of numbers. If written as
In C, the exact same idea. Only printf does not put the transfer to a new line by default. Therefore, you can add a line break after the passage of the inner loop, saving on a temporary variable - a string.
Here we have written the function in a general form, as well as the variant of the one-liner through the lambda function. With lambda, the problem may be that we first create a sheet, and only then sum up all its elements. If the file is huge - we waste our memory to create this sheet. While in the usual implementation, we store only one number - the total amount. Also in the general implementation, we have set
In si we run into several problems at once. Let's look at the code:
It is necessary to read character-by-character data from a file and write it to the buffer. If the buffer ends, and the end of the line has not yet existed - it is necessary to re-allocate the memory with a volume twice as large. In this task, it was possible to specify a fixed-length buffer. But I just wanted to show how to deal with very long lines. To store the amount we use the long type. The same type is returned by the string processing function.
In C ++, some operations can be made standard functions:
The above problems are very simple and do not require deep knowledge of algorithms or data structures. Rather, they are designed to show your knowledge of the features of the language and the ability to master its standard constructions. And you need to be able to write similar functions within 10 minutes or less. In the following parts we will talk about slightly more complicated problems.
Part 1
Part 3
If you see a way to improve the algorithm or the code given in this article - you are welcome to unsubscribe in the comments. I want to learn something new on this publication too.
Telephone technical interview - very original in itself. In those companies where I was lucky enough to go through it, we usually talked about my previous projects, about the complexities, implementations and optimizations of the code. Then, if the examining engineer decided to test my problem-solving skills, he would give the task, which I solved simply by speaking pseudo-code, and verbally describing the algorithms and analysis of the solution. In Google, everything is much more complicated. At the very least, this is due to the fact that, in addition to the process of thinking about the problem and voicing solutions, you simultaneously have to print the code in Google Doc, which the engineer hanging from the other end of the phone line is watching at the same time.
The situation is worsened by the fact that you have to constantly monitor the indentation that does not automatically appear in Google Docs, and the lack of syntax highlighting doesn’t really help in perceiving your own code. My advice - just practice writing code in Google Docs and notifying others and perplexed pets aloud what you are doing there is so interesting.
')
If the task is very simple, which is exactly what we will consider today, the algorithm of your answer should be approximately as follows:
- Refine task conditions, value ranges, external conditions (approximate file size, etc.)
- Describe several solution algorithms (if you know one and if you can solve the problem in several ways), accompanied by an analysis of the complexity of the algorithm
- List possible problems with the implementation and exploitation of the code
- Talk about which language is better for implementing this function.
- text manipulation - Python
- related structures (linked lists), trees, objects of fixed length - C / C ++
- Ask if the engineer wants to clarify some more details regarding the task.
Probably, let's start with the problems from this source .
Write the line flip function
It seems that it can be even easier? In Python, you can flip a string in several ways.
Options - in the forehead!
def reverse ( st ) :
# using a slice
out1 = st [ :: - 1 ]
# putting characters at the beginning of a line
out2 = ""
for ch in st:
out2 = ch + out2
# on-growing insanity
out3 = "" . join ( [ x for x in reversed ( st ) ] )
# well, and the top - use the character index in the string
out4 = "" . join ( [ st [ len ( st ) - i - 1 ] for i in range ( len ( st ) ) ] )
return out1
The task is terribly trivial. And you can write the implementation in general in one line or using the python lambda functionality:
def reverse ( st ) : return st [ :: - 1 ]
reverse = lambda st: st [ :: - 1 ]
But sometimes the examiner asks to write another implementation version or imposes some additional conditions. For example, you wrote a function using an additional variable string to which you add a character from the given one to the beginning (a variant with out2 from the first example). And the examiner may ask to implement the function without using additional variables at all.
It is clear that the more firewood you have in your implementation, the slower the function will work.
>>> rev1 = lambda st: st [ :: - 1 ]
>>> rev2 = lambda st: '' . join ( [ x for x in reversed ( st ) ] )
>>> rev3 = lambda st: '' . join ( [ st [ len ( st ) - i - 1 ] for i in range ( len ( st ) ) ] )
>>> from timeit import Timer
>>> Timer ( "rev1 ('test')" , "from __main__ import rev1" ) . timeit ( )
0.36440300941467285
>>> Timer ( "rev2 ('test')" , "from __main__ import rev2" ) . timeit ( )
0.8630490303039551
>>> Timer ( "rev3 ('test')" , "from __main__ import rev3" ) . timeit ( )
1.6259169578552246
We look as it looks in pure Si:
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define MAX_STRING_LENGTH 128
int reverse ( char str [ ] ) { / * or char * str * /
char * buffer ;
size_t len , i ;
len = strlen ( str ) ; / * \ 0 symbol at the end of the line * /
buffer = ( char * ) malloc ( len + 1 ) ;
if ( ! buffer )
return 0 ; / * not enough buffer memory * /
for ( i = 0 ; i < len ; i ++ ) {
buffer [ i ] = str [ len - i - 1 ] ;
} ;
buffer [ len ] = '\ 0' ;
strcpy ( str , buffer ) ;
free ( buffer ) ;
return 1 ; / * performed successfully * /
} ;
void main ( ) {
char str [ MAX_STRING_LENGTH ] ;
int result ;
gets ( str ) ;
result = reverse ( str ) ;
if ( ! result )
printf ( "Execution Error: not enough memory" ) ;
else
printf ( "% s \ n" , str ) ;
} ;
We need to add a few words about this implementation. Firstly, in pure ANSI C there is no boolean type (in C ++ there is a bool). Therefore, we will return to the place of this simple int. Further, why return anything at all? Often they pay attention to how the candidate foresees possible program errors and prevents them or lets the program know that such an error has occurred. In Python, language can handle exceptions by wrapping the code in a
try: ... except ... construct try: ... except ... In C, you have to deal with error handling by means of the code itself. Thus, there are two ways to implement. Let's write their prototypes:int reverse ( char * str ) ; / * return 1 (True) if executed successfully * /
char * reverse ( char str [ ] , int * success ) ; / * we will return a new line, according to the pointer to
success we write the success of the operation * /
Do not forget that in C the transfer of arguments to a function occurs by value (call by value, unlike call by reference), so that the values of the arguments passed to the function are copied to the stack. So if we want to change one or more of these arguments inside a function, it is necessary to pass a pointer to this variable, and not its own.
But the above code is not the most effective. There are two reasons for this:
- We create a temporary string in memory (buffer) into which we will add the temporary value of the newly created string
- To flip a line, it’s enough to go only half of its length.
Let's demonstrate a faster and more resource-saving code:
int qreverse ( char str [ ] ) {
char ch ;
size_t len ;
int i = 0 ;
len = strlen ( str ) ;
for ( i = 0 ; i < len >> 1 ; i ++ ) {
ch = str [ i ] ;
str [ i ] = str [ len - 1 - i ] ;
str [ len - 1 - i ] = ch ;
} ;
return 1 ;
} ;
len>>1 in a for-loop is just a quick division by 2, by a bitwise shift to the right. When doing such a trick, I advise you to check the correctness of the execution with the simplest examples (checking the boundary / initial conditions plus mathematical induction).- If the string length is 0: 0 >> 1 = 0 - the for loop is not executed.
- line length is 1: 1 >> 1 = 0 - the for loop is not executed.
- line length is 2: 2 >> 1 = 1 - the for loop will be executed once, rearranging the first and last characters
- and so on for odd ones like 1, for even ones like 2
Those. this case works for even and odd lengths. And additionally, we checked the nontrivial case when the length of the string is zero.
Perhaps this will be the fastest and shortest code for this task. Since rearranging two variables in places without resorting to the help of thirds in C is not possible to implement. The last character of the string '\ 0' does not move, because when i = 0, we will change the penultimate character with the first, the length of the string does not change during the flip.
Calculate the N-th Fibonacci number
In order not to be silent, and indeed to clarify the task - it is necessary to inquire about the numbers from which the series should begin ("0 1 1", or "1 1 2", or even "1 2 3"). This is not only a clarification, but also a way to show that you are not one of those programmers who do not understand the end of the task headlong to write code. It is considered good practice to bring several algorithms or ways to solve a problem (I even started with stupid brute-force solutions, but distinctly warned that this algorithm would be extremely inefficient since it can be improved). Then he gave an analysis of the complexity of the algorithms for big-O (big-O), asked what kind of implementation the examiner would like to see, and only after that would he start coding. It often happens that an efficient algorithm requires a complex implementation. And in the conditions of a telephone conversation (30-45 minutes, rarely up to an hour), the examiner wants to look at your skills in at least several tasks. Therefore, he may decide that you know different ways to solve the problem, it will be enough to write a less efficient algorithm, but which can be written faster.
def fib_N_rec ( n ) :
n = int ( n ) # in case n is not an integer
if n > 1 :
return fib_N_rec ( n- 1 ) + fib_N_rec ( n- 2 )
else :
return n
memo = { 0 : 0 , 1 : 1 } # dictionary of values
def fib_rec ( n ) :
if not n in memo:
memo [ n ] = fib_rec ( n- 1 ) + fib_rec ( n- 2 )
return memo [ n ]
def fib_iter ( n ) :
fib1, fib2 = 0 , 1
if n > 0 :
for i in range ( n- 1 ) :
fib1, fib2 = fib2, fib1 + fib2
return fib2
elif n == 0 : return fib1
else : return None
# works only on the first 70 elements - further rounding error
phi = ( 1 + 5 ** 0.5 ) / 2
def fib ( n ) :
return int ( round ( ( phi ** n - ( 1 -phi ) ** n ) / 5 ** 0.5 ) )
fib_N_rec is a recursive way to find the Fibonacci number. We must specify the conditions for the end of the recursion (base case), these will be the numbers at the zero and first positions, 0 and 1, respectively. The recursive case (n> 1) calls a function with the previous two numbers. But precisely because each copy of the function calls two other copies — this method of implementation is terribly wasteful. It also spends memory for storing the values of variable functions on the stack, and it also loads the processor with multiple calls to what we have just considered, giving the complexity of the algorithm of order O (2 ^ n). Therefore, if we save the values in the memo dictionary, the process will speed up many times (fib_rec), giving O (n), plus due to the preservation of the previous values, subsequent function calls will get values much faster.
For any task, recursion can be avoided altogether by replacing it with iterations. In the case of problems of passing through trees or graphs, this usually requires storing local variables on the stack. But for our simple task, we can only hold the values of the last two variable Fibonacci numbers. Again, you need to be careful with the initial conditions and check the cycle for several initial conditions. This way we prevent the occurrence of an error.
There is a way to express the values of Fibonacci numbers through the Binet formula. At the interview, such details are usually not asked, but if you know about any mathematical property of the sequence, be sure to mention it. Thus, you show your general education and the ability to analyze the problem from different angles.
For this case, the Binet formula works only up to the 70th element of the sequence, inclusive, further because of the accumulating error of floating point operations, the calculated value will be erroneous.
For C, you can write a one-liner function:
unsigned long fib ( unsigned long n ) { return ( n < 2 ) ? n : fib ( n - 1 ) + fib ( n - 2 ) ; }
The disadvantages are the same, so if this task appears among the questions asked, we can mention such a solution, describing the shortcomings, add preservation of values to a temporary array, and recalling the Binet formula (or the Lukos sequence formulas in general) focus on an iterative solution.
Print a school multiplication table 12x12
def multTab ( ) :
for i in range ( 1 , 13 ) :
print ( '\ t' . join ( [ str ( x * i ) for x in range ( 1 , 13 ) ] ) )
There is no trick here. Instead of a separate loop in a row, a list concatenation method was used, each element of which was converted to a string and combined with tabulation and other elements.
1 2 3 4 5 6 7 8 9 10 11 12 2 4 6 8 10 12 14 16 18 20 22 24 3 6 9 12 15 18 21 24 27 30 33 36 4 8 12 16 20 24 28 32 36 40 44 48 5 10 15 20 25 30 35 40 45 50 55 60 6 12 18 24 30 36 42 48 54 60 66 72 7 14 21 28 35 42 49 56 63 70 77 84 8 16 24 32 40 48 56 64 72 80 88 96 9 18 27 36 45 54 63 72 81 90 99 108 10 20 30 40 50 60 70 80 90 100 110 120 11 22 33 44 55 66 77 88 99 110 121 132 12 24 36 48 60 72 84 96 108 120 132 144
If you decide to write a function simply as:
for i in range ( 1 , 13 ) :
st = ""
for j in range ( 1 , 13 ) :
st + = '\ t% d' % ( i * j )
print ( st )
need to be careful in the line with the formation of numbers. If written as
st += '\t%d'% i*j without brackets, then the number i will be inserted into the string and the string will be multiplied j times - in a python, such an operation simply means creating copies of the string. Therefore, brackets in this case are required.#include <stdlib.h>
#include <stdio.h>
void main ( ) {
int i , j ;
for ( i = 1 ; i < 13 ; i ++ ) {
for ( j = 1 ; j < 13 ; j ++ ) {
printf ( "\ t% d" , i * j ) ;
} ;
printf ( "\ n" ) ;
} ;
} ;
In C, the exact same idea. Only printf does not put the transfer to a new line by default. Therefore, you can add a line break after the passage of the inner loop, saving on a temporary variable - a string.
Read a text file with numbers (one number per line) and print the sum of these numbers.
def sumIntFromFile ( filename ) :
sum = 0
with open ( filename, 'r' ) as FIN:
for line in FIN. readlines ( ) :
try :
sum + = int ( line. strip ( ) )
except :
pass
return sum
sumOfFile = lambda filename: sum ( [ int ( line ) for line in open ( filename, 'r' ) . readlines ( ) ] )
Here we have written the function in a general form, as well as the variant of the one-liner through the lambda function. With lambda, the problem may be that we first create a sheet, and only then sum up all its elements. If the file is huge - we waste our memory to create this sheet. While in the usual implementation, we store only one number - the total amount. Also in the general implementation, we have set
try ... except... construction, in case you cannot convert a string to a number. An example would be an empty string. It is good to tell the examiner about possible exceptions and explain that we can write down the different behavior of the function, depending on what the final goal is.In si we run into several problems at once. Let's look at the code:
#include <stdio.h>
#include <stdlib.h>
long handle_line ( char * line ) {
return atoi ( line ) ; // return long
}
int main ( int argc , char * argv [ ] ) {
int size = 1024 , pos ;
int c ;
long summ = 0 ;
char * buffer = ( char * ) malloc ( size ) ;
FILE * f = fopen ( argv [ 1 ] , "r" ) ;
if ( f ) {
do { // start reading data from a file
pos = 0 ;
do { // read only one line
c = fgetc ( f ) ;
if ( c ! = EOF ) buffer [ pos ++ ] = ( char ) c ;
if ( pos > = size - 1 ) { // increase buffer size and one place for \ 0 character
size * = 2 ;
buffer = ( char * ) realloc ( buffer , size ) ;
}
} while ( c ! = EOF && c ! = '\ n' ) ;
buffer [ pos ] = 0 ;
// string in buffer - passed to function
summ + = handle_line ( buffer ) ;
} while ( c ! = EOF ) ;
fclose ( f ) ;
}
free ( buffer ) ;
printf ( "Summ:% ld \ n" , summ ) ;
return 0 ;
}
It is necessary to read character-by-character data from a file and write it to the buffer. If the buffer ends, and the end of the line has not yet existed - it is necessary to re-allocate the memory with a volume twice as large. In this task, it was possible to specify a fixed-length buffer. But I just wanted to show how to deal with very long lines. To store the amount we use the long type. The same type is returned by the string processing function.
In C ++, some operations can be made standard functions:
#include <string>
#include <iostream>
#include <fstream>
#include <cstdlib>
using namespace std ;
int main ( ) {
long summ = 0 ;
ifstream input ( "test.dat" ) ;
string line ;
while ( getline ( input , line ) ) {
// cout << line << 'n';
summ + = atoi ( line. c_str ( ) ) ;
}
cout << summ << '\ n' ;
return 0 ;
}
Conclusion
The above problems are very simple and do not require deep knowledge of algorithms or data structures. Rather, they are designed to show your knowledge of the features of the language and the ability to master its standard constructions. And you need to be able to write similar functions within 10 minutes or less. In the following parts we will talk about slightly more complicated problems.
Part 1
Part 3
Source: https://habr.com/ru/post/285454/
All Articles