Предлагаю вашему вниманию небольшую историю моего провала и того как, порой, бывают безлики проверки на умение "решать задачи/проблемы" во время собеседований.
Начало
Примерно месяц назад со мной связался охотница за головами из одной крупной софтверной компании. Она объяснила что навыки и опыт указанные в моем резюме заинтересовали компанию которую она представляет и вкратце описала какой профиль она разыскивает. Я ответил что всегда мечтал работать на их компанию в принципе описанный пост выглядит заманчиво. После чего она сказала что мой профиль будет рассмотрен их командой и в случае успеха она предложит мне пройти собеседование удаленно, по видео чату. Профиль мой приглянулся и мы договорились о дате собеседования.
Собеседование
Началось все довольно неплохо, мне было заданно пара вопросов о подходах к разработке ПО, обеспечения качества ПО. Так же парочка по дизайну распределенных систем, и что-то еще на похожие темы. На все вопросы я ответил без особого труда, внятно, с чувством, с толком и расстановкой. После получаса общения мне предложили протестировать мои 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.
Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.
ссылка на оригинал статьи https://habrahabr.ru/post/276673/
Добавить комментарий