Предлагаю вашему вниманию небольшую историю моего провала и того как, порой, бывают безлики проверки на умение "решать задачи/проблемы" во время собеседований.
Начало
Примерно месяц назад со мной связался охотница за головами из одной крупной софтверной компании. Она объяснила что навыки и опыт указанные в моем резюме заинтересовали компанию которую она представляет и вкратце описала какой профиль она разыскивает. Я ответил что всегда мечтал работать на их компанию в принципе описанный пост выглядит заманчиво. После чего она сказала что мой профиль будет рассмотрен их командой и в случае успеха она предложит мне пройти собеседование удаленно, по видео чату. Профиль мой приглянулся и мы договорились о дате собеседования.
Собеседование
Началось все довольно неплохо, мне было заданно пара вопросов о подходах к разработке ПО, обеспечения качества ПО. Так же парочка по дизайну распределенных систем, и что-то еще на похожие темы. На все вопросы я ответил без особого труда, внятно, с чувством, с толком и расстановкой. После получаса общения мне предложили протестировать мои 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(2^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(n), 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(logN) а в разбалансированом на O(n).
Заключение
Как можно догадаться, компания ответила мне отказом, мотивируя его тем что мое умение решать проблемы не соответствует их требованиям. Я согласен что это самое умение у меня работает гораздо лучше когда я нахожусь по душем в спокойной обстановке, используя при этом конкретный IDE и конкретный язык программирования, вместо блокнота и псевдоязыка. Я ни в коем случае не пытаюсь оправдаться. Может быть работодатель действительно искал человека способного быть продуктивным в стрессовой ситуации, поскольку стресс и тайм-прессинг это их родная среда. Даже, быть может они, в целях экономии решили отказаться от всех IDE и работают только в блокноте.
Если вы работодатель и вы пытаетесь отбирать сотрудников используя подобную методологию, быть может, вы ошибаетесь? Если вы соискатель, вы теперь знаете что примерно подразумевается под этим пресловутым термином — problem solving skills.
Автор: vba
