8 February 2016

Месье, ваши problem solving skills не на высоте, или как я провалил одно собеседование

Website developmentJavaScriptAlgorithms
Предлагаю вашему вниманию небольшую историю моего провала и того как, порой, бывают безлики проверки на умение "решать задачи/проблемы" во время собеседований.

image

Начало


Примерно месяц назад со мной связался охотница за головами из одной крупной софтверной компании. Она объяснила, что навыки и опыт, указанные в моем резюме, заинтересовали компанию, которую она представляет, и вкратце описала, какой профиль она разыскивает. Я ответил, что всегда мечтал работать на их компанию в принципе описанный пост выглядит заманчиво. После чего она сказала, что мой профиль будет рассмотрен их командой и в случае успеха она предложит мне пройти собеседование удаленно, по видео чату. Профиль мой приглянулся и мы договорились о дате собеседования.

Собеседование


Началось все довольно неплохо, мне была задана пара вопросов о подходах к разработке ПО, обеспечения качества ПО. Так же парочка по дизайну распределенных систем, и что-то еще на похожие темы. На все вопросы я ответил без особого труда, внятно, с чувством, с толком и расстановкой. После получаса общения мне предложили протестировать мои problems solving skills, я не возражал, поскольку мне казалось, что если мой профиль им понравился, то и спросят у меня тоже, что-нибудь профильное, да не тут то было.

Задача


Для простоты я буду использовать в этой статье javascript для описания кода. Итак, у нас имеется бинарное дерево

          1
         / \
        2   3
      /     / \
     4     6   7

Нужно связать все узлы по горизонтали, слева направо, чтобы получилось:

          1-> Nil
         / \
        2-> 3-> Nil
       /   / \
     4 -> 6-> 7-> Nil

Каждый узел может быть описан в виде:

function Node(data) {
    this.data = data;
    this.left = this.right = null;
    this.neighbour = null;
}

Обстановка и условия для решения задачи


Меня попросили решить данную задачу с использованием, своего рода, онлайн блокнота, где мой собеседник накидал задание и наблюдал за тем, как я набиваю мое решение. Скажу честно, блокнот, даже онлайновый, вышиб меня из колеи. Оригинал кода задания был сделан на псевдо C#, но я предпочитаю javascript.

Провал и его последствия


Скажу честно, я сглупил и решил зазвездить решение без рекурсии, на базе вертикального прохода дерева, слой за слоем. Я начал писать код но через 5 минут понял что этого не достаточно. Еще через 5 минут я понял что окончательно заблудился и начал паниковать. Мой собеседник давал мне подсказки, которые, из-за моего состояния вгоняли меня еще в больший ступор. В конце концов, после ~30 минут дырканья и мырканья, я сдался и сказал, что не могу решить задачу сходу. Это был полный провал.

Продолжение


В конце концов я попрощался с собеседником и после 5 минут обдумывания всего процесса, отходников и успокоения я открыл мой профессиональный ноут и запустил мой любимый, ламповый IDE, и тут понеслось.

Решение 1, в лоб


После 20 минут написания кода, его правки, и снова исправления, я получил решение, как говориться, в лоб. Полный код решения доступен здесь. Вкратце, для равномерного прохода по уровням, я использовал рекурсию. Так же, на каждом этапе погружения я указывал номер уровня, что очень упростило мне задачу. Для решения в лоб, вполне неплохо, на мой взгляд. Вот кусочек кода, который выполняет проход и маркировку:

BinaryTree.prototype.findLinkedNeighbours = function (entry) {
    var links = [];
    var node = entry || this.root;
    var i, j, size;
    this.navigate(node, 0, links);
    size = links.length;
    for (i = 1; i < size; i++) {
        var link = links[i];
        var linkLength = link.length;
        if (linkLength < 2) {
            continue;
        }
        for (j = 1; j < linkLength; j++) {
            link[j-1].neighbour = link[j];
        }
    }
};

BinaryTree.prototype.navigate = function (node, level, links) {
    if (node === null) {
        return;
    }
    if(!links[level]) {
        links[level] = [];
    }
    links[level].push(node);
    this.navigate(node.left, level + 1, links);
    this.navigate(node.right, level + 1, links);
};

Данное решение не блещет ни оригинальностью ни быстродействием. Вердикт:
Time complexity: O(n), Space complexity: O(n)

Решение 2, маленькая хитрость.


Вечером того же дня, когда я мыл посуду, меня озарило. Я вспомнил что бинарные деревья как и графы имеют две различные формы представления. Первая форма реализуется, как мы видели выше, через ссылки между объектами, а вот вторая строится на базе массива. Форма эта используется довольно редко, так как в некоторых случаях, попусту не оптимальна с точки зрения использования памяти. Вот как это выглядит на примере из википедии:
image

Для навигации по такому дереву используется следующий подход:

Для узла i, индекс его левого потомка вычисляется по формуле: 2i+1,
а индекс его правого потомка вычисляется по формуле: 2i+2.
Индекс родителя узла находится по формуле: (i-1)/2

С помощью данного подхода поставленная проблема решается очень просто. Код всего решения доступен здесь. Организация данного кода оставляет желать лучшего, но он решает поставленную задачу, и это пока главное. Вот два основных метода этого подхода:

BinaryTree.prototype.linkNeighbours = function(array) {
    var pace = 0;
    var level = 0;
    var limit = 0;
    var size = array.length;
    var previous = null;
    while (pace < size) {
        limit = (Math.pow(2, level) + pace);
        for (;pace < limit; pace++) {
            if (array[pace]) {
                if (previous !== null) {
                    previous.neighbour = array[pace];
                }
                previous = array[pace];
            }
        }
        previous = null;
        level++;
    }
};

BinaryTree.prototype.printNeighbours = function(array) {
    var length = array.length,
        level = 0,
        left = 0,
        right = 0;
    while(right < length) {
        left = right;
        right = Math.pow(2, level) + right;
        console.log(array.slice(left, right)
            .filter(function(x) { return x != null;})
            .map(function(x) {return x.data;})
        );
        level ++;
    }
};

По поводу быстродействия можно сказать следующее:
Time complexity: O(2^h), Space complexity: O(1)
Просьба не обольщаться O(1) в плане памяти, так как, само по себе представление в виде массива, за частую, бывает не очень эффективно.

Решение 3, то, к чему я стремился изначально.


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

LinkedTree.prototype.traverseAndCountingLevel = function() {
    var queue = new Queue();
    var node = this.root;
    var result = [];
    var level = 0, pace = 1, capacity = 1, leafsFactor = 0;

    queue.add(node);

    while(queue.size() > 0) {
        node = queue.poll();
        if(pace === capacity) {
            result.push([]);
            level++;
            leafsFactor *= 2;
            capacity = (Math.pow(2, level) - leafsFactor);
            pace = 0;
        }
        result[result.length-1].push(node.data);

        if (node.left !== null) {
            queue.add(node.left);
        } else {
            leafsFactor += 1;
        }
        if (node.right !== null) {
            queue.add(node.right);
        } else {
            leafsFactor += 1;
        }
        pace += 2;
    }
    return result;
};

Сводка по быстродействию:
Time complexity: O(n), Space complexity: O(n)
В расчеты я не взял массив result, так как для решения задачи он в принципе не нужен. По поводу памяти могу сказать что в сбалансированном дереве это будет больше походить на O(log n) а в разбалансированном на O(n).

Заключение


Как можно догадаться, компания ответила мне отказом, мотивируя его тем, что мое умение решать проблемы не соответствует их требованиям. Я согласен, что это самое умение у меня работает гораздо лучше, когда я нахожусь под душем в спокойной обстановке, используя при этом конкретный IDE и конкретный язык программирования, вместо блокнота и псевдоязыка. Я ни в коем случае не пытаюсь оправдаться. Может быть, работодатель действительно искал человека способного быть продуктивным в стрессовой ситуации, поскольку стресс и тайм-прессинг это их родная среда. Даже, быть может они, в целях экономии решили отказаться от всех IDE и работают только в блокноте.

Если вы работодатель и вы пытаетесь отбирать сотрудников используя подобную методологию, быть может, вы ошибаетесь? Если вы соискатель, вы теперь знаете, что примерно подразумевается под этим пресловутым термином — problem solving skills.

Правки

Мной были допущены неточности в оценке быстродействия первых двух решений, спасибо SkidanovAlex за замечания.
Only registered users can participate in poll. Log in, please.
Должен ли, по-вашему, современный разработчик уметь решать подобные задачи за короткое время, довольствуясь блокнотом и псевдокодом?
13.25% Просто обязан 480
52.66% Можно, но это совсем не обязательно 1908
38.89% Нет, это совершенно не обязательно 1409
3623 users voted. 960 users abstained.
Only registered users can participate in poll. Log in, please.
Можно ли вообще назвать такие проверки проверками на умение решать задачи/проблемы?
17.24% Да, и никак иначе 591
49.15% Наверное, но только для около-олимпиадных задач 1685
41.69% Нет, это не имеет ничего общего с умением решать задачи/проблемы 1429
3428 users voted. 999 users abstained.
Tags:алгоритмыструктуры данныхсобеседование вопросы
Hubs: Website development JavaScript Algorithms
+46
98.6k 165
Comments 474
Popular right now
Top of the last 24 hours