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

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

Начало

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

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

Началось все довольно неплохо, мне была задана пара вопросов о подходах к разработке ПО, обеспечения качества ПО. Так же парочка по дизайну распределенных систем, и что-то еще на похожие темы. На все вопросы я ответил без особого труда, внятно, с чувством, с толком и расстановкой. После получаса общения мне предложили протестировать мои 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, маленькая хитрость.

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


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

Для узла 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 за замечания.