I want to work at Google! Telephone Interview (Part 2)

    Today we will discuss the technical aspects and implementation of the 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, we 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 code given in this article - you are welcome to unsubscribe in the comments. I want to learn something new from this publication too.

    A telephone technical interview is very original in itself. In those companies where I was lucky enough to go through it, we usually talked about my previous projects, about complexities, implementations, and code optimizations. Then, if the examining engineer decided to test my problem-solving skills, he would give a task that I would solve simply by saying the pseudocode and verbally describing the algorithms and analysis of the solution. In Google, everything happens an order of magnitude more complicated. At least this is due to the fact that in addition to the process of thinking over the task and voicing decisions, you also have to type the code in Google Doc, which the engineer hanging at the other end of the telephone line is looking at at the same time.

    The situation is aggravated by the fact that you have to constantly monitor the indentation that automatically does not appear in Google Docs, and the lack of syntax highlighting does not really help in perceiving your own code. My advice is just to practice writing code in Google Docs and notify aloud to those around and puzzled pets what you are doing there so interesting.

    If the task is very simple, and we will consider these today, then the algorithm for your answer should be approximately as follows:
    1. Refine task conditions, ranges of values, external conditions (approximate file size, etc.)
    2. Describe several solution algorithms (if you know those and if at all you can solve the problem in several ways), accompanied by an analysis of the complexity of the algorithm
    3. List possible problems with code implementation and maintenance.
    4. Talk about which language will be better for implementing this function
      • text manipulation - Python
      • linked structures (linked lists), trees, fixed-length objects - C / C ++
    5. Ask if the engineer wants to clarify any other details regarding the task


    Probably let's start with the puzzles from this source .

    Write a line feed function


    It seems that could be even easier? In Python, you can flip a string in several ways.

    Options - forehead!
    def reverse (st):
        # using the slice
        out1 = st [:: - 1]
     
        #
        putting the characters at the beginning of the line out2 = ''
        for ch in st:
            out2 = ch + out2
     
        # in increasing senility
        out3 = '' .join ( [x for x in reversed (st)])
     
        # well, the top is to use the index of the character 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 lambda python functionality:
    def reverse (st): return st [:: - 1]
     
    reverse = lambda st: st [:: - 1]

    But sometimes the examiner asks to write another implementation option or imposes some additional conditions. For example, you wrote a function using an additional variable string, into which you add the character from the given to the beginning (option with out2 from the first example). And the examiner may ask to implement the function without using additional variables at all.
    It’s clear that the more you make firewood 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


    Take a look at how it looks in pure C:
    #include 
    #include 
    #include 
     
     
    #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; / * there was not enough memory for the buffer * /
     
        for (i = 0; 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. Next, why bother returning anything? They often pay attention to how the examiner foresees possible program errors and prevents them or lets the program know that such an error has occurred. In Python, language tools can handle exceptions by wrapping code in a construct try: ... except .... In C, you have to deal with error handling using the code itself. Thus, there are two ways to implement it. Let's write their prototypes:
    int reverse (char * str); / * return 1 (True) if successful * /
    char * reverse (char str [], int * success); / * return a new line,
    write the success of the operation using the pointer to  success * /

    Do not forget that in C, arguments are passed to the function by value (call by value, as opposed to 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, we need to pass a pointer to this variable, and not to it.
    But the given version of the code is not the most effective. There are two reasons for this:
    1. We create a temporary line in memory (buffer), in which we will add the temporary value of the newly formed line
    2. To flip a line, it is enough to go only half its length

    Let's demonstrate a faster and 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>>1in a for loop it’s just a quick division by 2, by shifting bitwise to the right. When doing such a trick, I advise you to check the correctness of execution on the simplest examples (checking boundary / initial conditions plus mathematical induction).
    • If the string length is 0: 0 >> 1 = 0 - the for loop is not executed.
    • the length of the string is 1: 1 >> 1 = 0 - for the loop is not executed.
    • the length of the string is 2: 2 >> 1 = 1 - for the loop will execute once, rearranging the first and last characters
    • and so on for odd as 1, for even as 2

    Those. this case works for even and odd lengths. And in addition, we checked the non-trivial case when the string length is zero.

    Perhaps this will be the fastest and shortest code for this task. Because it is not possible to rearrange two variables in places without resorting to the help of thirds in C. The last character of the string '\ 0' does not start, because when i = 0, we will change the penultimate character with the first, the line length does not change during the flip.

    Calculate Nth Fibonacci Number


    In order not to be silent, and indeed to clarify the problem, it is necessary to inquire about which numbers the series should begin with (“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, without fully understanding the task, fly headlong to write code. It’s good practice to cite several algorithms or methods for solving the problem (I even started with stupid brute-force solutions, but clearly warned that this algorithm would be extremely inefficient, because you can improve it). Then he gave an analysis of the complexity of algorithms for large-O(big-O), asked what kind of implementation the examiner would like to see, and only after that he started coding. It often happens that an efficient algorithm requires a complex implementation. And in a telephone conversation (30-45 minutes, rarely up to an hour), the examiner wants to look at your skills in at least a few tasks. Therefore, he can decide that since 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
     
    # only works 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 set the conditions for the end of the recursion (the 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 implementation method is terribly wasteful. It spends memory to store the values ​​of variable functions on the stack, and it loads the processor with multiple calls of what we just counted, giving the complexity of an algorithm of order O (2 ^ n). Therefore, if we store values ​​in the memo dictionary, the process will be accelerated many times (fib_rec), giving O (n), plus due to the preservation of previous values, subsequent function calls will receive values ​​much faster.

    For any task, you can avoid recursion altogether by replacing it with iterations. In the case of passing through trees or graphs, this usually requires storing local variables on the stack. But for our simple task, we can only keep the values ​​of the last two variable Fibonacci numbers. Again, you need to be careful with the initial conditions and check the execution of the cycle for several initial conditions. In this way, we will prevent an error from occurring.

    There is a way to express the values ​​of Fibonacci numbers through the Binet formula. Such interviews are usually not asked for such details, but if you know about any mathematical property of a sequence, mention it necessarily. In this way you show your general education and ability to analyze the problem from different angles.

    For this case, the Binet formula only works up to the 70th element of the sequence inclusive, further due to the accumulating error of floating-point operations, the calculated value will be erroneous.

    For C, you can write a single-line function:
    unsigned long fib (unsigned long n) {return (n <2)? n: fib (n-1) + fib (n-2);}

    The shortcomings are still the same, so if this problem appears among the questions asked, you can mention such a solution, describing the shortcomings, add the storage of values ​​to a temporary array, and remembering the Binet formula (or the Lucos sequence formulas in general ) to stop on an iterative solution.

    Print 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, we used the method of combining a list (list concatenation), each element of which was converted to a string and connected to a tab 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 the function simply as:
    for i in range (1, 13):
        st = ""
        for j in range (1, 13):
            st + = '\ t% d'% (i * j)
        print (st)

    you need to be careful in the line with the formation of numbers. If you write as st += '\t%d'% i*jwithout brackets, then the number i is substituted into the string and the string is multiplied j times - in python such an operation simply means making copies of the string. Therefore, brackets in this case are required.
    #include 
    #include 
     
    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 same idea. Only printf does not put a line break by default. Therefore, you can add line break after passing the inner loop, saving on a temporary variable - the string.

    Read a text file with numbers (one number per line) and give 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 wrote down the function in general form, as well as a single-line version through the lambda function. The problem with lambda may be that first we create a sheet, and only then sum up all its elements. If the file is huge, we’ll waste our time creating this sheet. While in the usual implementation we store only one number - the total amount. Also, in the general implementation, we set the try ... except...construction in case we can not convert the string to a number. An example would be an empty string. It’s good to tell the examiner about possible exceptions and explain that we can record different behavior of the function, depending on what the final goal is.

    In C, we encounter several problems at once. Let's look at the code:
    #include 
    #include 
     
    long handle_line (char * line) {
      return atoi (line); // return a long one 
    }
     
    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 the file
            pos = 0;
            do {// read only one line
              c = fgetc (f);
              if (c! = EOF) buffer [pos ++] = (char) c;
              if (pos> = size - 1) {// increase the size of the buffer and one place for the \ 0 character
                size * = 2;
                buffer = (char *) realloc (buffer, size);
              }
            } while (c! = EOF && c! = '\ n');
            buffer [pos] = 0;
            // line in the buffer - pass to the function
            summ + = handle_line (buffer);
          } while (c! = EOF); 
          fclose (f);
        }
        free (buffer);
        printf ("Summ:% ld \ n", summ);
        return 0;
    }

    You have to read data from a file character by character and write them to the buffer. If the buffer ends, but there is no end of the line yet, you have to reallocate memory with a volume twice as large. In this task, a fixed-length buffer could be specified. But I just wanted to show how to deal with very long lines. To store the amount, use the long type. The same type is returned by the string processing function.
    In C ++, part of the operations can be made standard functions:
    #include 
    #include 
    #include 
    #include 
     
    using namespace std;
     
    int main () {
        long summ = 0;
        ifstream input ("test.dat");
        string line;
     
        while (getline (input, line)) {
            // cout <         summ + = atoi (line.c_str ());
        }
        cout <     return 0;
    }


    Conclusion


    The tasks discussed above are very simple and do not require in-depth 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 in 10 minutes or less. In the following sections, we will talk about slightly more complex problems.

    Part 1
    Part 3

    Also popular now: