Я хочу работать в Google! Телефонное интервью (часть 2)

Сегодня мы будет обсуждать технические аспекты и реализацию задач на Python и C/C++, которыми нас будет закидывать инженер из Google. Начнём с самых тривиальных проблем с последующим нарастанием сложности. Параллельно обратим внимание о чём стоит упомянуть во время интервью и где не попасть в ловушку.
Если Вы видите способ улучшить алгоритм или код приведённый в данной статье — милости прошу отписаться в комментариях. Я хочу научиться чему-то новому на этой публикации тоже.

Телефонное техническое интервью — весьма оригинально само по себе. В тех компаниях, где мне посчастливилось его проходить, обычно мы говорили о моих предыдущих проектах, о сложностях, реализациях и оптимизациях кода. Потом, если экзаменующий инженер решал проверить мои навыки решения проблем — он давал задачу, которую я решал просто проговаривая псевдокод, и устно описывая алгоритмы и анализ решения. В Google всё происходит на порядок сложнее. Как минимум это из-за того, что кроме процесса обдумывания задачи и озвучивания решений, Вам параллельно приходится ещё и печатать код в Google Doc, на который в это же время смотрит инженер, висящий на другом конце телефонной линии.

Ситуация ухудшается ещё и тем, что приходится постоянно следить за выставлением отступов, которые автоматически в Google Docs не появляются, да и отсутствие подсветки синтаксиса — не особо помогает в восприятии собственного кода. Мой совет — просто тренируйтесь писать код в Google Docs и вслух оповещать окружающих и озадаченных домашних питомцев что же вы там такое интересное делаете.

Если задача очень простая, а именно такие мы сегодня и рассмотрим, то алгоритм Вашего ответа должен быть приблизительно следующим:

1. Уточнить условия задачи, диапазоны значений, внешние условия (приблизительный размер файла, т.д.)
2. Описать несколько алгоритмов решения (если знаете таковые и если вообще можно несколькими способами решить задачу), сопровождая анализом сложности алгоритма
3. Перечислить возможные проблемы с реализацией и эксплуатированием кода
4. Поговорить о том, какой язык будет лучше для реализации данной функции
   • манипуляции с текстом — Python
   • связанные структуры (linked lists), деревья, объекты фиксированной длины — C/C++
5. Поинтересоваться хочет ли инженер уточнить какие-то ещё детали касательно задачи

Наверное, давайте начнём с задачек из этого источника.

Напишите функцию переворота строки

Кажется что может быть ещё проще? В Python можно перевернуть строку несколькими способами.

Варианты — в лоб!

def reverse(st):
    # используя срез
    out1 = st[::-1]
 
    # поставляя символы в начало строки
    out2 = ''
    for ch in st:
        out2 = ch + out2
 
    # по-наростающей маразма
    out3 = ''.join([x for x in reversed(st)])
 
    # ну и вершина - использовать индекс символа в строке
    out4 = ''.join([st[len(st) - i - 1] for i in range(len(st))])
 
    return out1

Задача жутко тривиальная. И можно написать реализацию вообще в одну строчку или используя lambda функциональность питона:

def reverse(st): return st[::-1]
 
reverse = lambda st: st[::-1]

Но иногда экзаменатор просит написать другой вариант реализации или накладывает какие-нибудь дополнительные условия. Например, вы написали функцию используя дополнительную переменную строку, в которую добавляете символ из данной в начало (вариант с out2 из первого примера). А экзаменатор может попросить реализовать функцию без использования дополнительных переменных вообще.
Понятное дело, чем больше вы наворотили дров в своей реализации — тем медленнее будет функция работать.

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

Глянем как это выглядит в чистом Си:

#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 в конце строки */
    buffer = (char*) malloc(len);
    if(!buffer)
        return 0; /* не хватило памяти для буфера */
 
    for(i=0;i<len;i++){
        buffer[i] = str[len-i-1];
    };
    buffer[len] = '\0';
    strcpy(str, buffer);
    free(buffer);
    return 1; /* выполнили удачно */
};
 
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);
};
 

Нужно добавить пару слов об этой реализации. Во-первых в чистом ANSI C нету boolean типа (в Си++ есть bool). Поэтому будем возвращать в место этого простой int. Далее, зачем вообще что-то возвращать? Часто обращают внимание как экзаменуемый предвидит возможные ошибки программы и предотвращает их или даёт программе знать, о том, что такая ошибка произошла. В Python средствами языка можно обрабатывать исключения, оборачивая код в конструкцию try: ... except .... В Си же приходится заниматься обработкой ошибок средствами самого кода. Таким образом существует два способа реализации. Давайте напишем их прототипы:

int reverse(char *str); /* возвращаем 1(True) , если выполнились удачно */
char* reverse(char str[], int* success); /* вернём новую строку, по указателю на 
success запишем успешность операции */

Не забывайте, что в Си передача аргументов в функцию происходит по значению (call by value, в отличии от call by reference), так что при этом в стек копируются значения аргументов, передаваемых в функцию. Так что если мы хотим поменять один или несколько этих аргументов внутри функции — необходимо передать указатель на эту переменную, а не саму её.
Но приведенный вариант кода не является самым эффективным. На то есть две причины:

1. Мы создаём временную строку в памяти (buffer), в которую будем складывать временное значение новообразованной строки
2. Для переворота строки достаточно пройти только половину её длины

Давайте продемонстрируем более быстрый и ресурсосберегающий код:

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 в for-цикле это просто быстрое деление на 2, путём побитного смещения вправо. Когда делаете такой трюк, советую проверять правильность выполнения на простейших примерах (проверка граничных/начальных условий плюс математическая индукция).

• Если длина строки равна 0: 0>>1 = 0 — for цикл не выполняется.
• длина строки равна 1: 1>>1 = 0 — for цикл не выполняется.
• длина строки равна 2: 2>>1 = 1 — for цикл выполнится один раз, переставив первый и последний символы
• и так далее для нечётных как 1, для чётных как 2

Т.е. такой случай работает и для чётных, и для нечётных длин. И дополнительно мы проверили нетривиальный случай, когда длина строки равна нулю.

Пожалуй это будет самый быстрый и самый короткий код для этой задачи. Т.к. переставить две переменные местами, не прибегая к помощи третей в Си реализовать не возможно. Последний символ строки '\0' не трогается, т.к. при i=0 мы будем менять предпоследний символ с первым, длина строки при перевороте не меняется.

Вычислить N-ое число Фибоначчи

Что бы не молчать, да и действительно уточнить задачу — необходимо поинтересоваться о том, с каких чисел должен начинаться ряд ( «0 1 1», или «1 1 2», или даже «1 2 3»). Это не только уточнение, а ещё способ показать, что вы не из тех программистов, что не поняв до конца задачу сломя голову летят писать код. Хорошей практикой считается привести несколько алгоритмов или способов решения задачи (я даже начинал с тупых brute-force решений, но внятно предупреждал, что этот алгоритм будет крайне не эффективным, т.к. можно его усовершенствовать). Потом приводил анализ сложности алгоритмов по большой-О (big-O), спрашивал какую бы реализацию хотел бы видеть экзаменатор и только после этого начинал кодить. Часто случается так, что эффективный алгоритм требует сложной реализации. А в условиях телефонного разговора (30-45 минут, редко до часа) экзаменатор хочет посмотреть на ваши умения как минимум в нескольких задачах. Поэтому он может принять решение, что т.к. вы знаете разные способы решения задачи, будет достаточно написать менее эффективный алгоритм, но который можно написать быстрее.

def fib_N_rec(n):
    n = int(n) # на случай если n не целое число
    if n>1:
        return fib_N_rec(n-1) + fib_N_rec(n-2)
    else:
        return n
 
memo = {0:0, 1:1} # словарь значений
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
 
# работает только на первые 70 элементов - дальше ошибка округления
phi = (1 + 5**0.5) / 2
def fib(n):
    return int(round((phi**n - (1-phi)**n) / 5**0.5))

fib_N_rec — рекурсивный способ найти число фибоначчи. Мы должны задать условия окончания рекурсии (базовый случай), это будут числа на нулевой и первой позициях, 0 и 1 соответственно. Рекурсивный случай (n>1) вызывает функцию с предыдущими двумя числами. Но именно из-за того, что каждая копия функции вызывает две другие копии — данный способ реализации жутко расточительный. Он тратит и память для хранения значений переменных функций на стеке, да ещё и загружает процессор многократными вызовами того, что мы только что посчитали, давая сложность алгоритма порядка O(2^n). Поэтому, если мы будем сохранять значения в словаре memo — процесс многократно ускорится (fib_rec), давая O(n), плюс из-за сохранение предыдущих значений последующие вызовы функции получат значения намного быстрее.

Для любой задачи можно избежать рекурсию вообще, заменив её итерациями. В случае задач прохода по деревьям или графам, это обычно требует сохранения локальных переменных на стеке. Но для нашей простой задачи мы можем держать значения только двух последних переменных чисел Фибоначчи. Опять нужно быть аккуратным с начальными условиями и проверять выполнения цикла для нескольких начальных условий. Таким образом мы предотвратим возникновение ошибки.

Есть способ выражения значений чисел Фибоначчи через формулу Бине. На интервью обычно таких подробностей не спрашивают, но если Вы знаете о каком-нибудь математическом свойстве последовательности — упомяните её обязательно. Таким образом Вы покажите Вашу общую образованность и способность анализировать проблему с разных сторон.

Для данного случая формула Бине работает только до 70ого элемента последовательности включительно, дальше из-за накапливающейся ошибки операций с плавающей точкой, вычисленное значение будет ошибочным.

Для Си можно записать функцию-однострочник:

unsigned long fib(unsigned long n){ return (n<2) ? n : fib(n-1)+fib(n-2);}

Недостатки всё те же, поэтому если эта задача появится среди заданных вопросов, можно упомянуть такое решение, описав недостатки, добавить сохранение значений во временный массив, и вспомнив формулу Бине (или в целом формулы последовательностей Лукоса) остановиться на итеративном решении.

Напечатать школьную таблицу умножения 12х12

def multTab():
    for i in range(1, 13):
        print('\t'.join([str(x*i) for x in range(1, 13)]))

Тут нету никакой хитрости. Вместо отдельного цикла по ряду, использовался способ объединения списка (list concatenation), каждый элемент которого был преобразован в строку и соединён с табуляцией и другими элементами

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

Если же вы решите записать функцию просто как:

for i in range(1, 13):
    st=""
    for j in range(1, 13):
        st += '\t%d'%(i*j)
    print(st)

нужно быть аккуратным в строке с формированием чисел. Если записать как st += '\t%d'% i*j без скобок, тогда в строку подставится число i и строка умножится j раз — в питоне такая операция означает просто создание копий строки. Поэтому скобки в данном случае — обязательны.

#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");
    };
};

В Си таже идея. Только printf не ставит перенос на новую строку по умолчанию. Поэтому можно добавить перенос строки после прохода внутреннего цикла, экономя на временной переменной — строке.

Прочитать текстовый файл с числами (одно число в строке) и выдать сумму этих чисел

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()])

Тут мы записали функцию в общем виде, а так же вариант однострочника через лямбда-функцию. С лямбдой проблема может быть в том, что сначала мы создадим лист, и только потом просуммируем все его элементы. Если файл огромный — мы зря потратим память на создание этого листа. В то время как в обычной реализации мы храним только одно число — общую сумму. Так же в общей реализации мы поставили try ... except... конструкцию, на случай если не удастся преобразовать строку в число. Примером может быть пустая строка. Хорошо сказать экзаменатору о возможных исключениях и объяснить, что мы можем записать разное поведение функции, в зависимости от того, какой является конечная цель.

В си мы наталкиваемся сразу на несколько проблем. Давайте посмотрим на код:

#include <stdio.h>
#include <stdlib.h>
 
long handle_line(char *line) {
  return atoi(line); //возвращаем длинное 
}
 
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 { // начинаем читать данные из файла
        pos = 0;
        do{ // читаем только одну строку
          c = fgetc(f);
          if(c != EOF) buffer[pos++] = (char)c;
          if(pos >= size - 1) { // увеличиваем размер буфера и одно место для \0 символа
            size *=2;
            buffer = (char*)realloc(buffer, size);
          }
        }while(c != EOF && c != '\n');
        buffer[pos] = 0;
        // строка в буфере - передаём в функцию
        summ += handle_line(buffer);
      } while(c != EOF); 
      fclose(f);
    }
    free(buffer);
    printf("Summ: %ld \n", summ);
    return 0;
}

Приходится читать посимвольно данные из файла и записывать их в буфер. Если буфер заканчивается, а конца строки ещё не было — приходится перевыделять память с объёмом в два раза больше. В данной задаче можно было задать буфер фиксированной длины. Но просто хотелось показать, как быть с очень длинными строками. Для хранения суммы используем тип long. Этот же тип возвращаем функцией обработки строки.
В Си++ часть операций можно сделать стандартными функциями:

#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;
}

Заключение

Рассмотренные выше задачи являются очень простыми и не требуют глубоких знаний алгоритмов или структур данных. Скорее они рассчитаны показать ваше знание особенностей языка и умение владеть его стандартными конструкциями. И нужно уметь написать похожие функции в течение 10 или меньше минут. В следующих же частях мы поговорим о чуть более сложных проблемах.