Начало
Примерно месяц назад со мной связался охотница за головами из одной крупной софтверной компании. Она объяснила, что навыки и опыт, указанные в моем резюме, заинтересовали компанию, которую она представляет, и вкратце описала, какой профиль она разыскивает. Я ответил, что
Собеседование
Началось все довольно неплохо, мне была задана пара вопросов о подходах к разработке ПО, обеспечения качества ПО. Так же парочка по дизайну распределенных систем, и что-то еще на похожие темы. На все вопросы я ответил без особого труда, внятно, с чувством, с толком и расстановкой. После получаса общения мне предложили протестировать мои 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).Заключение
Как можно догадаться, компания ответила мне отказом, мотивируя его тем, что мое умение решать проблемы не соответствует их требованиям. Я согласен, что это самое умение у меня работает гораздо лучше, когда я нахожусь
Если вы работодатель и вы пытаетесь отбирать сотрудников используя подобную методологию, быть может, вы ошибаетесь? Если вы соискатель, вы теперь знаете, что примерно подразумевается под этим пресловутым термином — problem solving skills.
Правки
Мной были допущены неточности в оценке быстродействия первых двух решений, спасибо SkidanovAlex за замечания.
Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.
Комментарии (448)
shir
08.02.2016 12:09+15Скажите спасибо что было онлайн собеседование и у вас был хотя бы онлайн блокнот. А то на листочке A4 писали бы карандашом.
Regis
08.02.2016 13:46+5Лично мне «на листочке карандашом» было бы намного комфортнее. Хотя бы в силу того, что при планировании решений рукописной формой пользуюсь регулярно, а эти онлайн-блокноты каждый раз новые и у каждого свои нюансы поведения и отображения.
pravic
09.02.2016 00:21+1А кто-то ручку не держал в руках… лет 10-12. Ему заказан путь к собеседованиям?
khim
09.02.2016 02:27+3Как вы это себе представляете?
Возможно, в природе есть люди, способные сразу спроектировать и закодить систему, работающую с десятками состояний и паралльно происходящих событий без карандаша и бумаги… но я таких не встречал.
Думаю что подобному уникуму будет несложно решить задачу вообще в уме и потом только вписать её в предложенный онлайновый блокнот…
Tairesh
09.02.2016 08:57+1Я такой человек, приятно познакомиться. Использую планшет и десктоп для заметок и рисования схем. С момента расставания с институтом наверное и страницы в сумме не исписал ручкой.
khim
09.02.2016 12:27+1Я тоже много чего могу накодить не привлекая ручку и бумагу, но если задача реально сложная… Планшета и десктопа не хватает: мало влазит, сложно изменения вносить… за пять минут десять набросков не сделать…
Так что сказанное вами, почти наверняка, обозначает, что вы давненько не решали реально сложных задач.
Каковой, в частности, является любая простая задача на собеседовании. Проверить как вы с этим справитесь — будет вдвойне полезно.Tairesh
09.02.2016 12:45Скорость создания схем на бумажке или в специализированном ПО — вопрос привычки и умения. Изменения вносить уж точно проще, чем на бумаге, где можно только дописать что-то сверху.
Tairesh
09.02.2016 15:09+2Есть люди, которым и текст писать на бумаге удобнее и быстрее, чем набирать на клавиатуре компьютера.
khim
09.02.2016 18:08+1Возможно. Повторюсь: пока я таких не встречал. Встречал людей, которые плохо и медленно рисуют схемы на бумаге, таких кто хорошо и быстро делает это на компьютере — не видел.
GlukKazan
09.02.2016 09:22Ну, есть к примеру Power Designer. Шариковая ручка — довольно таки неудобный инструмент.
khim
09.02.2016 12:31+1Смотря для чего. Набросать простенькую схему, обсудить и выбросить на листке бумажки — занятие на две минуты. Я ещё никого не видел, кто бы сделал что-то подобное в Power Designer'е за сравнимое время.
А вы, напоминаю, идёте работать в команду. Тут общаться как-то придётся. Это когда вы один — можете обдумывать решения в уме (в ванной, в туалете, где хотите) и сразу «набело» врисовывать решения в Power Designer. А когда вы с кем-то общаетесь ничего лучше листка бумаги или доски не придумано (доска чуть менее удобна, но позволяет общаться больше, чем 2-3 участникам).GlukKazan
09.02.2016 14:03+1Я никуда не иду. Давно уже пришёл. Больше 20 лет уж как в команде. Ручка используется, да, но не чаще чем Power Designer, Visio и пр. В основном для себя, поскольку рисую и пишу от руки я из рук вон. У других участников команды ситуация с письмом от руки примерно аналогичная.
Aingis
08.02.2016 12:23+1Я порой могу решать задачки в уме, если достаточно вникну, или с помощью записей, если сложно представить конструкцию. Но это не в стрессовой ситуации, да. Впрочем, у автора аналогично, судя по статье.
zodchiy
08.02.2016 12:25+2Как-то раз тоже в таком же ключе был на собеседовании. Сначала просто общение, потом онлайн общение с будущей командой, а потом онлайн редактор текста, без подсветки. Тоже путался, так как привык уже к vs+r#. В итоге минут через 20, когда я с горем пополам решил проблему, но мне сказали, что решение «в лоб», можно проще и изящнее.
В итоге, потея и путаясь в переменных я завалил тест.
Hokum
08.02.2016 12:26+5Сочувствую Вам, сам бывал в подобной ситуации, когда решение вот здесь и сейчас не приходит в голову, хотя задача простая, а потом, когда успокоюсь решение приходит само (хотя вопрос — а сколько времени ушло на решение, возможно я обдумывал его все время после не удачи… я как-то не задумывался об этом).
И все же, я думаю, что навык решения задач без любимой IDE и на псевдокоде может быть полезен.Когда пишешь на одном языке, то и оперируешь конструкциями этого языка, возможности языка — ограничивают программиста, и при снятии этих ограничений человек по прежднему продолжает находится в них.
Возможно такими задачами пытаются проверить насколько кандидат в целом может решать проблемы в поставленных терминах, а потом уже с решение проблемы выбирать инструмент для реализации. Или просто насколько человек комфортно может выходить за пределы своего языка, ведь псевдокод обыно не использует какаие-то специфичные конструкции языка и может быть понят людьми использующими другой язык. Соотвествено, это уже получается не только проверка умения решать проблемы, но и навыка донести это решение до человека в терминах понятных ему.
А еще я сталкивался с ситацие когда требовалось написать рабочий код в онлайн блокноте, я примерно помнил синтаксис и в общих чертах набросал решение, на что мне сказали, что это не годится. :)santa324
08.02.2016 15:34+3Я тоже однажды столкнулся с таким. Попросили написать код на листке бумаги. Набросал примерное решение опустив проверки крайних ситуаций для краткости. На что начались придирки что мол тут вы на null не проверили, тут блок finally не написали, и т.п.
Вот это уже полный идиотизм, я все это опустил думая что проверяют в принципе понимание ситуации.
vayho
08.02.2016 15:43+15А у меня было задание отсортировать массив в Java, ну я и написал Arrays.sort(<массив>). Собеседующий посмотрел на меня как на идиота и такой — ну это, как бы сортировку напиши какую-нибудь. Я подумал подумал и написал сортировку выбором. Оказалось собеседующий такой сортировки не знаел и пришлось ему доказывать что этот код отсортирует массив, в итоге он ушел вбил код на компе у него заработало. Дальше он попросил выбрать данные из двух таблиц в SQL связав по id. Я написал не через JOIN а через SELECT..WHERE. Собеседующий снова впал в ступор. Тут я ему снова доказывал что JOIN это просто сахар для такой записи. Корчое доказать удалось, но потом я сам не пошел к ним работать.
kroshanin
08.02.2016 12:27+6У меня однажды была обратная ситуация. Собеседование состояло из двух частей: с программистом и с руководителем.
С программистом вопросы были прикладного характера, на которые я практически на все ответил, потом еще несколько «практических» (код писать) заданий, с которыми я также справился что называется «на ура».
А дальше предстояло собеседование с руководителем. Я думал, что это будут чисто организационные вопросы, мол какую зарплату хочу, какой график и т.д. А руководитель оказался бывшим программистом и начал спрашивать меня как происходят те или иные вещи на нижнем уровне. Например, как организовано хранение данных в MySQL или как на нижнем уровне передается файл на сайт и т.д. И я «поплыл», поскольку мои знания по большей части прикладного характера, т.е. я знаю, что если по полю БД должен осуществляться поиск, его нужно сделать индексированным, а как это там внутри по кластерам или по страницам разбивается — в этом я не силен.
В общем, забраковали меня тогда, Было очень обидно, поскольку я обладал требуемыми им знания, но мои знания просто не были увидены.
А по вашему примеру: как мне кажется, вы должны были предоставить хоть какое-то решение. Пусть «в лоб», пусть громоздкое и плохое, но готовое работающее решение. Вы рано сдались. Поставьте себя на место работодателя: он дал кандидату не особо сложную задачу, а кандидат ее не выполнил. Естественно, он откажет данному кандидату и возьмет на работу того, который выполнит задание.
UncleAndy
08.02.2016 12:28Такие навыки нужны только для компаний, у которых практикуется экстремальное программирование. Но в этом случае ни о каком качестве кода не может идти речь.
Delphinum
08.02.2016 15:26+2Какие «такие»? Умение решить задачу в блокноте на псевдоязыке?
UncleAndy
08.02.2016 15:49-2Содержимое задачи здесь вообще не при чем. А вот условия ее решения — быстро, под наблюдением, в не комфортных для разработчика условиях — слишком смахивают именно на экстремальное программирование. Соответственно, именно это и тестируется таким образом.
Delphinum
08.02.2016 16:08+5быстро
Обстановка и условия для решения задачи
Меня попросили решить данную задачу с использованием, своего рода, онлайн блокнота, где мой собеседник накидал задание и наблюдал за тем как я набиваю мое решение
Где тут сказано о том, что задача должна быть решена за максимально короткий срок?
под наблюдением
Тобишь, если к вашему рабочему месту подойдет коллега и постоит рядом минут 5 читая ваш код, вы не сможете работать?
в не комфортных для разработчика условиях
Это вы про «блокнот»?UncleAndy
08.02.2016 16:11-4Собеседование подразумевает ограниченность по времени. Быстрота разработки в 99% случаев приводит к говнокоду. Под психологическим давлением — еще и к говнокоду, на который тратится много времени. Ну и каким нормальным компаниям нужны навыки медленного говнокодирования?
Delphinum
08.02.2016 16:14+5Собеседование подразумевает ограниченность по времени
Да не подразумивает. Одно из моих собеседований длилось 3 часа, 2.5 из которых мы с организатором обсуждали и вместе решали данные им задачи. Никакой спешки, дружественная атмосфера, подсказки, шутки, затупы.
Под психологическим давлением — еще и к говнокоду, на который тратится много времени
Так и не увидил психологического давления. Ткните носом, прошу.
withkittens
08.02.2016 16:15-1Если в ресторане к вашему столику подойдёт некто и будет стоять смотреть, как вы едите суп, вы будете комфортно себя чувствовать?
Представьте, некоторые люди под наблюдением ощущают себя именно так.
Это вы про «блокнот»?
Это про наблюдение.
Если судить по вашим комментариям, вы вряд ли это поймёте.
Fesor
08.02.2016 21:03+1Вы путаете «стоять над душой» и «парное программирование». Последнее — практика XP, которую применяют при работе над критически важными участками кода, сложными алгоритмами, когда один мозг хорошо а два лучше проверяют друг друга. И да, в рамках парного программирования принято меняться местами.
Экстримальное программирование никакого отношения к «экстриму» не имеет.
Delphinum
08.02.2016 21:16+1Если моя работа будет заключаться в поедании супов, то вполне комфортно.
Если судить по вашим комментариям, вы вряд ли это поймёте
Повторюсь, я против того, что разработчик боиться показывать процесс своей работы. Значит разработчик не уверен, значит что то не так с разработчиком.
foxmuldercp
08.02.2016 22:11+2Процесс работы? а что такое «процесс работы»? Не буду говорить за всех, но я могу за 10 минут набросать костяк скрипта, а потом ещё неделю его обрисовывать проверками, рефакторить, тестить и читать логи.
А могу и исписать полтора бумажных блокнота алгоритмами, связями, крайними ситуациями требующими уточнений и за неделю показать пару моделей, контроллеры к ним и десяток представлений, сделанных по быстрому, для тестов.khim
08.02.2016 22:29+1Не буду говорить за всех, но я могу за 10 минут набросать костяк скрипта, а потом ещё неделю его обрисовывать проверками, рефакторить, тестить и читать логи.
И каждый день будете показывать как идут дела, правильно?
Ну вот и тут та же ситуация — только в миниатюре.
А могу и исписать полтора бумажных блокнота алгоритмами, связями, крайними ситуациями требующими уточнений и за неделю показать пару моделей, контроллеры к ним и десяток представлений, сделанных по быстрому, для тестов.
Та же самая ситация и здесь. Вы можете писать код прямо «в онлайн блокноте» или на бумажке, обсуждать его вслух или добавлять комментарии. Но к комцу собеседования код должен быть. Работающий, желательно.
Delphinum
08.02.2016 23:32+1Процесс работы? а что такое «процесс работы»?
Вот вы зарабатываете себе на хлебушек с помощью какой либо деятельности — это называется работой. А ход этой работы называется процессом. Процессов есть множество, но тот, который вы выполняете для выполнения своей работы называется рабочим процессом.
А могу и исписать...
Вы молодец, но к чему это было сказано?foxmuldercp
09.02.2016 00:02+2К тому, что у всех процессы разные. и протекать могут по разному.
khim
09.02.2016 18:12+1Правильно — но потому и собеседования разные. Впрочем оказывается что процессы (и, соответственно, собеседования) скорее зависят от того в каком мире живёт компания и меньше — от специфики самой компании. Facebook, Google и Microsoft гораздо ближе друг к другу, чем, скажем, SAP или 1С.
Было бы странно если бы собеседующие подбирали на собеседованиях людей под чей-то чужой «процесс»?
withkittens
08.02.2016 15:53+9Умение не путаться в мыслях, когда прямо над душой стоит человек и пристально наблюдает через плечо.
По-моему, это чисто социальный скилл, стрессоустойчивость, если хотите.
С умением решать задачи ничего общего не имеющее.Delphinum
08.02.2016 16:10+3Я считаю, что хороший (именно хороший) специалист, не боится того, что кто то наблюдает за его работой. Обычно новички и разного рода шарлотаны бояться того, что клиент видит процесс его работы. Это хорошо заметно в сфере ремонта помещений, когда работники резко против присутствия клиента на объекте.
UncleAndy
08.02.2016 16:13+4Если на основе только одного этого задания формируется отказ — это неадекватный наниматель. У человека в момент собеседования и так присутствует волнение. А тут неожиданно создается еще более экстремальная ситуация и на ее основе принимается решение. На мой взгляд — крайне неудачный подход.
Delphinum
08.02.2016 16:15+3Согласен. Собеседование не должно состоять из 1 вопроса и 1 ответа.
khim
08.02.2016 19:25+3Я так понимаю это был pre-screen: попытка проверить умение человека вообще программировать, в приниципе. Дальше — вопросов было бы больше.
Задачка-то элементарная. То есть начать нужно с обходом в глубину, в ширину, дать потом эту задачу (она очевидно вытекает из обхода в ширину) — и всё.
Очень тяжело оценивать всё это не зная какие именно подсказки давались.Delphinum
08.02.2016 21:20-1попытка проверить умение человека вообще программировать
Обычно это очевидно из общения, совсем не обязательно для этого решать задачи. Я предпочитаю использовать задачи для оценки мыслительного процесса собеседника.khim
08.02.2016 21:28+2В том-то и дело, что из общения это не понятно. Человек будет с умным видом рассуждать о том, как марсоходы бороздят просторы большого теарта, а потом не сможет развернуть односвязный список без потери элементов. Увы.
У нас вообще есть чёткое правило: после первого собеседования на позицию «Software Engineer» в отчёте должны быть 10-15 строк кода, написанных кандидатом. Всё остальное обсуждается, этот пункт — вообще без вариантов.Delphinum
08.02.2016 21:31+3Значит мы по разному понимаем понятие «вообще программировать». Я, обычно, просил у кандидатов их open source наработки. Такие проекты пишутся спокойно, качественно, потому они идеально подходят для оценки кода.
khim
08.02.2016 21:36+4Если кандидат вообще имеет какие-то «open source наработки», то он, во-первых, скорее всего про это скажет, а во-вторых его не испугает задача, которая буквально «убила» автора обсуждаемой статьи. Исключения — случаются (пришлось как-то нам отшить кандидата, который великолепно разбирался в таймингах разных железных протоколов, но не знаю алгоритмов от слова «совсем»...), но они крайне редки.
90% кандидатов за душой не имеют ничего, что можно было бы «пощупать».Delphinum
08.02.2016 21:47которая буквально «убила» автора обсуждаемой статьи
Ну автор утверждает, что дело не в сложности задачи, а в накале страстей.khim
08.02.2016 21:55+3Заметим, что он это утверждает в статье где первое приличное решение описано как «пример номер 3», придумано «на следующее утро», а хорошее решение не описано вообще.
Если бы то же решение было выдано в первые пять минут прямо на собеседовании, а после наводок собеседующего был бы написан код с O(1) затратами памяти (не такой и сложный, согласитесь), то никакого «накала страстей» и не было бы, а? А был бы ещё один новый сотрудник, скорее всего…Delphinum
08.02.2016 23:34+1Если бы то же решение было выдано в первые пять минут прямо на собеседовании… то никакого «накала страстей» и не было бы
Так наоборот ведь. Как утверждает автор, если бы не было никакого «накала страстей», то было бы дано идеальное решение на собеседовании.khim
08.02.2016 23:48+2Как утверждает автор, если бы не было никакого «накала страстей», то было бы дано идеальное решение на собеседовании.
Притом что оно даже не приведено в статье? Ню-ню.
khim
08.02.2016 19:23+3Почему неудачный? С точки зрения работодателя — вполне удачный. Люди, способные решать задачи «под давлением» лучше людей, которые на это неспособны.
Ну а что часть хороших кандидатов потеряется — работодателю-то какая разница? В случае если соискателей достаточно — это хороший подход. Если вы мелкая контора «Рога и копыта» и к вам никто не идёт — ситуация другая, тут, конечно, придётся действовать мягче.UncleAndy
08.02.2016 21:56Думаю, именно мелкие конторы заинтересованы в такого типа тестировании. Крупным более важно качество кода, а не скорость его написания.
khim
08.02.2016 22:02+3Опять двадцать пять! В этой задаче и планировалось обсуждать качество кода, а не время его написания. Ну там за десять-пятнадцать минут кандидат пишет какое-нибудь решение, потому вы его обсуждаем и улучшаем. Кто ж виноват что первый этам затянулся на два дня и окончился только на следующий день?
А такое «качество кода», когда 20 строк пишутся две недели даже крупные компании себе позволить не могут… пусть даже эти 20 строк будут супергениальными.
Mrrl
08.02.2016 22:36+1Разные бывают ситуации. Иногда этих 20 строк приходится ждать два года, а то и больше. Другое дело, что значит, без них можно было обойтись, и были дела поважнее.
khim
08.02.2016 22:41+1Бывает, что и исправление на две строчки делается месяц. Всё бывает. Важно, чтобы это было не правилом, а исключением.
В данном случае речь идёт о 20 строчках, которые пишутся в пять минут и про которые можно доказать, что решение — ассимптотически оптимально. И это — типичный случай. И вот самое важное (как я уже говорил) — чтобы эти типичные случаи разруливались нормально.
khim
08.02.2016 19:19+2Вы правы не на 100%, а на все 200%. С умением решать задачи этот скилл связан слабо. А с умением работать в команде — очень сильно.
Вы сколько времени планируете потратить перед тем, как послать код на ревью? День, два? Нет же, сорее речь будет идти о минутах. Ну о часах, от силы.
Да, тут всё более «сжато» — но и задача ведь игрушечная, согласитесь.withkittens
08.02.2016 20:09+2Дело ведь не в том, что код будут смотреть и критиковать, а в том, что само наблюдение выбивает из колеи и не позволяет сосредоточиться.
Также не согласен со связью с умением работать в команде. Сужу по себе: я не испытываю проблем с прохождением ревью, обсуждением кода и общением с коллегами, но вот такие онлайн-блокноты на собеседованиях очень сильно досаждают.khim
08.02.2016 20:24+3Они всех досаждуют, успокойтесь. После калибровки результат нужно умножать примерно на пять. То есть если твой коллега в спосойной обстановке в уголке решает задачу пять-шесть минут — её можно давать на собеседовании. И если кандидат её за полчаса решит — можно брать.
Если задача «в уголке» решается за полчаса давать её нельзя: даже хороший кандидат будет решать её часа два, а то и вообще психанёт и не сможет её решить.
Это-то как раз понятно.
Flammar
08.02.2016 20:03+1По-моему, это чисто социальный скилл.
Да (точнее, психологический).С умением решать задачи ничего общего не имеющее.
Ну как… Утверждение слишком сильное, из разряда «никогда», поэтому вынужден сказать «нет». В общем-то IRL нужда в подобных навыках иногда всплывает, и мера их нужности зависит от специфики места работы.withkittens
08.02.2016 20:14+1Да, верно, псхологический.
Я согласен со спецификой места работы, возможно, где-то этот скилл полезен или даже необходим.
Но я лично ставил себя на место сферического разработчика в вакууме — когда есть возможность на несколько часов уходить в «поток».khim
08.02.2016 20:17+1Интересно где это платять за работу, где можно всё делать «уходя в поток». Нет, я бы тоже так хотел. Но, увы, оказывается, что 90% времени занимает рутина, которую нужно делать «под давлением». Увы.
withkittens
08.02.2016 20:38+1Пусть рутина, это тоже неважно, главное, что за спиной никто не стоит.
khim
08.02.2016 21:12+1В том-то и дело, что стоит. Или за спиной или сбоку стоит. И просит показать. Вот прямо тут и сейчас? Что будете делать?
Mrrl
08.02.2016 12:30+3Чем-то похоже на первое решение:
static void Connect(Node x){ Connect(x,new List<Node>(),0); } static void Connect(Node x,List<Node> rightLine,int level){ if(x==null) return; if(level==rightLine.Count){ rightLine.Add(x); }else{ rightLine[level].neighbor=x; rightLine[level]=x; } Connect(x.left,rightLine,level+1); Connect(x.right,rightLine,level+1); }
Сложность O(size), память O(depth).
DenimTornado
08.02.2016 12:30+9Когда давно услышал фразу, что умение решать такие задачи говорит о том, что соискатель умеет решать такие задачи и ничего более. Никогда за 10 лет не сталкивался с тем, что вот такого рода задачи надо вот так на коленке решать.
У сотрудника был опыт решение бековой проблемы на чужом ноуте, в другой стране через впн, но при этом всё равно, кофе, IDE, сначала сесть, успокоиться, разрисовать и решать.
vba
08.02.2016 12:45+1Мне так же не приходилось за последние 10 — 12 лет сталкиваться с чем-то подобным. Хотя попадались и задачи по машинному обучению. Не было ничего сложного, была нехватка знаний, иногда. Последняя покрывалась неплохим образованием, опытом и прочтением нужной литературы.
Delphinum
08.02.2016 15:29+5Задача простая, решить ее можно хоть на коленке, хоть стоя на ушах. Не увидел причин для паники автора при решении этой задачи, видимо дело было в банальной спешке.
Fibril
08.02.2016 12:40+26Смотреть за процессом решения задачи — очень плохая практика. Это как удар ниже пояса. Понимание того, что тебя оценивают по заведомо не готовому коду, не дает сосредоточиться на поиске решения. В итоге унижение неизбежно, даже если с задачей справляешься.
vba
08.02.2016 12:48+14Вы как будто в воду смотрите. С каждой написанной строчкой я думал, как бы не сморозить, как бы не написать откровенную чепуху, это просто ужасно блокирует ход мыслей.
qwer_ty
08.02.2016 13:52+14Значит собеседование выполнило свою роль фильтра, по параметру «не брать кандидатов, которые боятся сморозить чепуху и стесняются своего кода». а так же по параметрам алгоритмического мышления, ide-независимости, способностям к быстрому анализу и синтезу решения.
Является ли такой фильтр правильным при найме разработчика — вопрос дискуссионный. Мне кажется что все эти навыки необходимы в той или иной степени, возможно их не стоило смешивать в одном тесте. Вопрос такой системы фильтрации вы наверное могли бы обсудить с HR отделом компании если бы прошли собеседование. Но раз компания существует и нанимает разработчиков — значит такая система отбора имеет право на жизнь.
Delphinum
08.02.2016 15:33Последнее время задумываюсь о таком новом направлении на моем YouTube канале, как решение задач в реальном времени и демонстрация этого процесса зрителям. Меня не беспокоит лажа или откровенно глупые решения, как это не беспокоит игровых стриммеров. Отнеситесь к написанию кода в том же русле, думаю это не только позволит вам проходить такого рода собеседования, но и не бояться совершать ошибки.
terryP
08.02.2016 18:13+2как решение задач в реальном времени и демонстрация этого процесса зрителям. Меня не беспокоит лажа или откровенно глупые решения, как это не беспокоит игровых стриммеров.
Не стоит, обычно те кого не беспокоит глупые решения и лажа в собственном коде, работают по принципу тяп ляп и в продакт. Игровой стриммер не будет демонстировать свою игру, если он играет в эту игру в первый раз в жизни, опытный танцор не выйдет на сцену с танцем, который он не умеет танцевать, так видел пару раз по телевизору. Профессионал сначала оттачивает навыки до совершенство, а уже потом идет с ними на публику, так как репутация для него — главный ресурс.poxu
08.02.2016 18:36+5Игровой стриммер не будет демонстировать свою игру, если он играет в эту игру в первый раз в жизни
Сплошь и рядом.
Delphinum
08.02.2016 21:25обычно те кого не беспокоит глупые решения и лажа в собственном коде
Разница между хорошим программистом и плохим программистом в том, что хороший программист знает, что он может допустить ошибку и применяет различные подходы для минимизации этой вероятности, а плохой программист думает что он не может допустить ошибку, так как он слишком хорош для этого.
Игровой стриммер не будет демонстировать свою игру, если он играет в эту игру в первый раз в жизни
Вы намекаете на то, что я плохой программист?))
Профессионал сначала оттачивает навыки до совершенство
Навык чего, решения задач? Новичкам интересно посмотреть, как опытный программист «в живую» решает незнакомую ему задачу, спотыкается, ищет решения, использует различные подходы для отлавливания ошибок, рассуждает, а не смотреть как лектор записывает на доске изо дня в день одно и то же, без ошибок и запинок.
foxmuldercp
08.02.2016 22:16+1Меня, кстати, почти всегда на анкетировании оставляли подумать — закончишь, дай знать.
r4nd0m
08.02.2016 13:21+5Так, собственно, процесс тут и интересен, само решение-то вполне стандартное. Как ещё можно оценить способность решать задачи, как не наблюдая и участвуя в процессе?
Каждая проверка в той или иной степени унизительна, с этим приходится считаться, это и есть профессионализм — оцениваешь ты, оценивают тебя. Это нормальная ситуация, а не повод для истерики.
jmaks13
08.02.2016 13:38Почему нельзя дать более объемную задачу на пару дней, чтобы соискатель мог спокойно ее решить?
r4nd0m
08.02.2016 13:47+2У объемной задачи другие цели. По моему скромному опыту это обычно следующий шаг собеседования. Но какой смысл давать объёмную, если соискатель не справился с простой?
Да, кстати, мне в интервью на позиции, где алгоритмизация не была сильной стороной, давали сразу объёмные задачи.jmaks13
08.02.2016 14:21+1Так может быть он не справился с простой из за стресса, а в спокойной обстановке напишет ее легко. Зачем рисковать потерей кандидата, если можно дать объемную задачу?
r4nd0m
08.02.2016 14:40+3С чего вы взяли что это «потеря»? Очевидно, что у работодателя свои критерии полезности и стопы. И работодателю и ХРу и интервьюерам выгодней, если соискатель будет нанят. Если в такой ситуации его отсеивают, то можно почти точно сказать, что в этом конкретном случае он не подходит, несмотря на всю мудрость задним умом.
jmaks13
08.02.2016 15:31Если в такой ситуации его отсеивают, то можно почти точно сказать, что в этом конкретном случае он не подходит, несмотря на всю мудрость задним умом.
Приведу пример, который сам встречал не раз. Кандидат проходит интервью в двух разных компаниях из одной отрасли.
— В компании А ему предложили задачу на 5 минут, задача была академическая, которую кандидат раньше не решал и в результате он запаниковал и провалился.
— В компании Б дали задание на пару дней, которое кандидат спокойно сделал дома и полностью удовлетворил требования работодателя.
Объемная работа исключает фактор стресса, что позволяет не терять определенный процент кандидатов. Конечно, если работа заранее предполагает постоянный стресс, то тогда нужен устойчивый человек, но я в IT сфере еще не встречал таких требований.r4nd0m
08.02.2016 16:46+4Очень хороший пример, в нём компания наняла подходящего ей соискателя, а он нашёл подходящую ему работу. Не вижу тут проблемы.
Непонятно, как объёмная работа может исключить фактор стресса. Да, тебя не проверяют в реальном времени, но потом твой объёмный код будут оценивать несколько человек, и они уж точно найдут там косяки. В таком свете, мне кажется, простая задачка с подсказками вызовет даже меньше стресса. Фактор стресса при оценке невозможно исключить в принципе.
боритесь со своим стрессом
withkittens
08.02.2016 17:17Непонятно, как объёмная работа может исключить фактор стресса.
1. Вы пишете код в комфортной для себя обстановке, у вас есть возможность показать себя и учесть всё необходимое по ТЗ.
2. Пока вы пишете код, вы не переживаете, считает ли интервьювер, что всё затянулось. И вообще, полчаса — это уже много? Ой, он начал зевать, у меня всё плохо?
При объёмной задаче косяки идут в комплекте, да, но ничего страшного. Вроде как наоборот, у компании будет более полное представление о вас. Честно и справедливо.Gray_Wolf
08.02.2016 17:30+4И вообще, полчаса — это уже много? Ой, он начал зевать, у меня всё плохо?
Ну и фаза луны в день собеседования подкачала.
А если в компанию требуются суровые кодеры, а не «комплексующие непризнанные гении»?withkittens
08.02.2016 18:07+1А если в компанию требуются суровые кодеры, а не «комплексующие непризнанные гении»?
Я-то не против, пусть набирают кого считают нужным. Я старался объяснить, как объёмная работа может если не исключить, то минимизировать фактор стресса.
r4nd0m
08.02.2016 17:39+2Вы только что лишили всех фрилансеров отговорки, почему проект не сдан во-время. Это раз.
Два — простые задачи в первом круге интервью не исключают сложных во втором.
Другой вопрос — а зачем давать человеку сложную задачу, если он с простой не справился, и вообще дрожит как осиновый лист? Нет, конечно можно, если с кандидатами совсем всё плохо, но когда не справился один из десяти, проще продолжить с остальными и не тратить ресурсы.
И снова — стресс возникает не из за того, что вас о чём то спрашивает ещё 10 минут назад незнакомый человек. Он возникает в конечном счёте от страха, что могут не взять. И это никак не исключить.vba
08.02.2016 18:33+1Я не совсем понимаю как страх и сильная дрожь связанны со ступором, с путаностью в мыслях? В моем случае я страха не испытывал, лишь ступор. Провалил я собеседование еще и от того что осознал, что не в состоянии решить задачу в данной обстановке хотя мой внутренний голос просто кричал что задача проста. Например я отчасти испытывал чувство злости на глупость ситуации и на себя.
r4nd0m
08.02.2016 19:30+2А ступор по вашему просто так, ниоткуда, взялся?
Ступор — это подсознательная реакция организма на опасность. Может вы лично и не испытывали страха, но ваше подсознание явно испытывало. А внутренний голос оказался на самом деле внешним :)
Как ещё можно объяснить ступор во вполне обычной ситуации?vba
08.02.2016 22:23+1Обычной для вас. Страх это реакция организма на внешний раздражитель. Есть два типа реакции на такой раздражитель. Такого понятия как подсознание испытывающее страх быть не может. А вот раздражитель влияющий на способность логичиски мыслить это вполне реально. Для кого-то это шум, для кого-то это чавкающий коллега. Вы спутали состояние ступора и шока, его легкое проявление. Под ступором я понимаю состояние в котором вы got stuck, со всеми вытекающими и не более.
terryP
08.02.2016 17:57+10Приведу пример, который сам встречал не раз. Кандидат проходит интервью в двух разных компаниях из одной отрасли… В компании Б дали задание на пару дней, которое кандидат спокойно сделал дома и полностью удовлетворил требования работодателя.
Другой пример, когда подходящих компаний десятка два и каждая пытается дать задание на пару дней на самом первом интервью… Особенно, когда кандидат ещё не уволился с прошлой работы и у него полно других дел, кроме поиска работы. Нет, я понимаю, если это компания мечты всех кандидатов, аля гугл. Но удивляет уверенность работодателей особо ничем не примечательной компании, что их вакансия единственная на рынке и кандидат потратить неделю на объемные задания чтобы лишь попасть на второе интервью, вместо того чтобы за это время пройти десяток собеседований в других компаниях. Во многих случаях опытные разработчики просто забивают на такие задания.
qwer_ty
08.02.2016 15:23+5лучше не взять того, чем взять не того.
jmaks13
08.02.2016 15:35+1С учетом нехватки высококвалифицированных кадров (я про IT сферу) чаще всего наоборот и испытательный срок никто не отменял.
Flammar
08.02.2016 16:32+2Вопрос поставлен правильно, но «правильный» ответ на него не столь однозначен и разнится от фирмы к фирме и от позиции к позиции.
khim
08.02.2016 19:31+3Зачем рисковать потерей кандидата, если можно дать объемную задачу?
Вы так говорите, как будто потеря кандидата — это катастрофа. Ну потеряем мы сколько-то, проблем-то. Если оставшихся хватает — всё в порядке, если нет — подходы нужно менять…
Fibril
08.02.2016 14:35+2Если человек способен решать необходимые задачи, каким образом он приходит к решению интересовать не должно, это уже личное дело разработчика. Понятно, что работодателю интересно поковыряться везде, но должны быть рамки. Разработчик в итоге справился с задачей — он способен решать такие задачи, все просто.
lair
08.02.2016 13:24+15Смотреть за процессом решения задачи — очень плохая практика.
Наоборот — очень поучительно смотреть, как человек думает, какие решения он принимает, и почему он их отбрасывает. Если он еще и комментирует свои действия вслух — вообще замечательно, можно даже до конца решения не доходить зачастую.
Понимание того, что тебя оценивают по заведомо не готовому коду, не дает сосредоточиться на поиске решения.
Почему? В нормальной ситуации обе стороны понимают, что код заведомо не готов, что в этом унизительного?Fibril
08.02.2016 14:40+1Смотреть на это может поучительно и увлекательно, но участвовать в этом в качестве кандидата — совсем нет.
TheShock
08.02.2016 14:53+6Не знаю, я лично проходил недавно несколько таких собеседований. Ничего постыдного в этом не видел. Вполне нормально принял, хотя и не все задачи были решены сходу.
пс. никогда не учавствовал в олимпиадах.
withkittens
08.02.2016 16:02-1как человек думает, какие решения он принимает, и почему он их отбрасывает.
А зачем это работодателю? Разве всё в конечном счёте не сводится к тому, чтобы работа была выполнена? Есть другие, более продуктивные (на мой взгляд, конечно) критерии оценки работы, нежели количество рассмотренных решений и причины их отбрасывания.lair
08.02.2016 16:09+3А зачем это работодателю?
Чтобы понимать, как человек думает. В частности, глядя за процессом, можно пытаться оценить, какие вещи человек будет учитывать в повседневной работе, а какие — нет.
Разве всё в конечном счёте не сводится к тому, чтобы работа была выполнена?
Нет, для таких вещей аутсорсеры есть. Выставили условия, получили (или нет) результат.
Есть другие, более продуктивные (на мой взгляд, конечно) критерии оценки работы, нежели количество рассмотренных решений и причины их отбрасывания.
«Почему сделано так» — это не критерий оценки работы, это критерий для включения результата в общий код.withkittens
08.02.2016 16:28+2В частности, глядя за процессом, можно пытаться оценить, какие вещи человек будет учитывать в повседневной работе, а какие — нет.
Разве код сам не расскажет, что было учтено, а что нет? А если есть сомнения, почему не спросить: «Что вы думаете по поводу X вот здесь?»
Нет, для таких вещей аутсорсеры есть.
Что дополнительно требуется от собственных разработчиков, сотрудников?lair
08.02.2016 16:37+4Разве код сам не расскажет, что было учтено, а что нет?
Не всегда. В частности, если человек учел какую-то побочную ситуацию, а потом отбросил ее как невозможную, то в коде об этом не будет ничего (особенно в коде на собеседовании).
А если есть сомнения, почему не спросить: «Что вы думаете по поводу X вот здесь?»
Эти вопросы как раз (а) занимают много времени и (б) их можно задавать только после завершения кода.
Что дополнительно требуется от собственных разработчиков, сотрудников?
Преемственность. Сегодня код писал один человек, завтра — уже другой.withkittens
08.02.2016 16:59+2Эти вопросы как раз (а) занимают много времени и (б) их можно задавать только после завершения кода.
(а) Найм нового сотрудника — это серьёзное вложение, и будет очень странно, если у компании не окажется времени на вопросы. (б) Верно. В том и суть: дать кандидату задачу, назначить дедлайн и позволить решить её в комфортной обстановке, результат обсудить.
Преемственность.
Очень хороший поинт. Тогда выполненная работа плюс соответствие требованиям проекта (code style, покрытие тестами и т.п.)?lair
08.02.2016 17:01Найм нового сотрудника — это серьёзное вложение, и будет очень странно, если у компании не окажется времени на вопросы.
Во-первых, у самого кандидата может не оказаться времени. Во-вторых, любое время лучше расходовать эффективно.
Тогда выполненная работа плюс соответствие требованиям проекта (code style, покрытие тестами и т.п.)?
Этого недостаточно. Ни то, ни другое не помогает для оценки design decisions.
khim
08.02.2016 19:40+3(а) Найм нового сотрудника — это серьёзное вложение, и будет очень странно, если у компании не окажется времени на вопросы.
Закон Паретто никто не отменял. Из нашей статистики: на 100 кандидатов редко когда больше 2-3 будущих сотрудников. Говорить с каждым из них по многу часов — это элементарно дорого. Особенно с учётом того, что большая их часть программировать не умеет от слова «совсем». Потому хочется сделать «первычный отсев» максимально дешевым.
(б) Верно. В том и суть: дать кандидату задачу, назначить дедлайн и позволить решить её в комфортной обстановке, результат обсудить.
Это уже потом, когда процетов 80-90 кандидатов отсеяны. Если задача большая и сложная, то и смотреть на неё приходится долго. Это дорого.
57DeD
09.02.2016 11:30Если вы нанимаете шоумена, то да.
А если программиста, то нужнее результат.lair
09.02.2016 11:31+2При работе в команде «результат» выражается не только в коде.
57DeD
09.02.2016 11:38+1Talk is cheap. Show me the code
(с)
;)lair
09.02.2016 11:39+1Ну вот показали вам код, а к коду тому — девяносто вопросов. Помогло?
57DeD
09.02.2016 11:41+2И я их задам. Обсуждение — важная часть интервью.
lair
09.02.2016 11:43+1Вы считаете, что код, вызывающий вопросы — это хороший результат?
57DeD
09.02.2016 11:53+1Ответ на Ваш вопрос зависит от того, какие кванторы Вы в нём подразумевали:
Существует такой код на интервью и существуют такие вопросы к нему, при том, что код хорош.
Существует такой код на интервью и существуют такие вопросы к нему, при том, что код плох.
Существуют вопросы, которые стоит задавать только если код плох.
Существуют ли вопросы, которые можно задать только если код хорош — это я не знаю. но подозреваю что тоже да.
Andchir
08.02.2016 14:03+2Мне как-то предложили решить тестовое задание (не маленькое), с записью процесса работы на видео (скринкаст). Я ответил, что запись меня отвлекает и нервирует, но могу сделать запись только основных моментов. На этом потенциальный работодатель испарился. Хотя даже если бы я хотел сделать запись, мне было бы очень не комфортно работать, т.к. видеозапись вместе с запущенной IDE очень нагружает ноутбук. Предпочитаю с такими работодателями не иметь дела.
r4nd0m
08.02.2016 19:33+1Почти 10 тысяч часов с регистрацией рабочего времени скриншотами. Кажется я чудом выжил и сохранил рассудок.
57DeD
09.02.2016 11:27+4Собственно в этом коренное отличие практики собеседований у нас в ABBYY от описанной (которую используют, afaik, ещё и в Google, и в MS, и в booking). У нас любят дать задачу и выйти из комнаты (причём даже сказать, что на решение есть 100500 времени).
Таким образом мы даём лишний шанс талантливым, но не слишком самоуверенным кандидатам.
Ares_ekb
08.02.2016 12:53+4Я тоже проваливал подобное собеседование с «блокнотом» и т.п. Плюс, интервью проходило на английском языке. Часть задачек решил, но на одной застопорился.
А потом погуглил чувака, который меня собеседовал и узнал, что он в прошлом ИТ-олимпиадник из СНГ. Отсюда и такой подход к собеседованию, как к олимпиаде :)
Может, и хорошо, что провалил, по крайней мере, сейчас от меня на работе требуется думать, а не решать задачки на скорость.
Zeliret
08.02.2016 12:53+24Эта глупая игра под названием «собеседование». Мне кажется, это вечный бич айтишников.
Работодатель не знает чего хочет, точнее знает, т.к. начитался умных книжек и напридумывал (нарыл в инете) каких-то задач, которые в реальной работе почти никогда не встречаются.
А соискатель попадает в стрессовую ситуацию, пытаясь решить глупые задания из книги «9000 задач, которые вам никогда не пригодятся».
По факту получается, что ищут человека, который будет выполнять работу качественно и вовремя (с некоторыми вариациями), но по собеседованиям складывается впечатление, что им нужен тот, кто умеет решать такие задачки в блокнотике.
Исключения, когда ищут реально крутого программиста, которого разбуди посреди ночи и дай листик, он тебе напишет самую оптимальную реализацию самого сложного алгоритма, который лежит в основе какой-то крутой хардварной штуки, — только подтверждают правило ;D
NYMEZIDE
08.02.2016 13:24+23У меня было похожее собеседование. По скайпу. На .net программиста.
Сказали пиши код прямо в скайп — никаких Visual Studio.
Код написал, кое как, отправляя в скайп куски кода. Визуально все проверил — вроде правильно. Получаю ответ — у тебя прога мало того что не скомпилится, да и еще не вернет правильный ответ. Типо не справился, следующий вопрос.
Меня разозлило это. Скопировал код в студию, запускаю — все ОК, собралось. Выводит правильный ответ.
Кто меня собеседовал даже не стал слушать меня, мол он лучше знает и вообще, тут оценивают мои знания — а не его. Начальник умный, ты дурак.
Потом тоже самое было с SQL кодом, мол напиши запрос. Написал, тоже я дурак. Проверяю на БД, накидал несколько таблиц, данных тестовых. Все верно вывелось! Не хочет даже смотреть.
А потом как начал меня унижать, по каждой фигне. И за все собеседование я его на 3 буквы не послал, думал может проверяет стрессоустойчивость. А нет, оказалось просто он мудак, который самоутверждается за счет таких провенциальных соискателей, сам он типо «москвич» уже.Zeliret
08.02.2016 13:28+28В таких случаях стоит прерывать собеседования со словами «ваша шарага мне не подходит». Потому что работать в компании с такими вот «умниками» вам нервных клеток не прибавит.
egor_nullptr
08.02.2016 13:26+5Рекурсивное решение с использованием стека.
struct leaf { public: int value; leaf* right; leaf* left; leaf* neighbor; leaf(int v, leaf* r, leaf* l) : value(v), right(r), left(l), neighbor(nullptr) {}; }; void find_neighbors(leaf* node, std::stack<leaf*> & stack) { if (node == nullptr) { return; }; if (!stack.empty()) { node->neighbor = stack.top(); stack.pop(); }; find_neighbors(node->right, stack); find_neighbors(node->left, stack); stack.push(node); return; }
Сложность O(N), память O(logN).abudnik
08.02.2016 16:52+1Не будет работать даже для тривиального случая дерева с двумя дочерними узлами.
Даже если пофиксите, то память будет не O(logN)egor_nullptr
08.02.2016 20:15Вы неправы, вот доказательство ideone.com/OjNWMU.
Расход памяти вычисляется как максимальный размер стека, и равен он, как несложно догадаться, глубине дерева, которая для сбалансированного бинарного дерева равна log2N.
Tairesh
08.02.2016 13:26+2Аналогичная была ситуация, когда пытался на собеседовании с помощью ручки и листа бумаги написать структуру для хранения очереди на абстрактном языке без ссылок, указателей и динамических массивов. Промучился пол часа и сдался. Вышел из офиса и, пока переходил улицу, придумал решение, но возвращаться было уже как-то неловко.
Собеседование было, к слову, на вакансию PHP-программиста. До сих пор не понимаю — нахрена?
kyb27
08.02.2016 13:33Мне кажется, что второй вариант может быть использован для обработки уже готового дерева с каким-то произвольным размещением в памяти.
В массиве достаточно разместить только один слой узлов (листьев), по памяти будет заведомо лучше чем O(N).
dikkini
08.02.2016 13:37-3Прямо вот бесят такие и подобные задачи, особенно когда надо решить за время без кофе и перекуров на «подумать». Даже если их можно решить за 20 строчек кода. Даже тот же «FizzBuzz» — элементарная задача, но, что она дает на собеседовании?
f0rk
08.02.2016 13:42+8Показывает, что соискатель хотя бы циклы и ветвления понимает. Я собеседовал много людей и как ни странно, многие не могут fizzbuzz написать, хотя рассказывают байки о большом опыте работы. Нафиг таких нанимать?
f0rk
08.02.2016 13:39+2На мой взгляд, вполне адекватная задачка. Думаю, автор ошибся только в том, что не стал сразу писать самый тупой вариант с рекурсией. Кстати, где там О(2^n) в решении «в лоб»? Разве что n — высота дерева…
Cheater
08.02.2016 13:41-4То, что вы прошли, я бы назвал стресс-тестированием, и к тестированию реальных способностей сотрудника оно не имеет никакого отношения (ну разве что к способностям выживать в похожих условиях, типа «дедлайн + стоящий над душой ПМ/лид»).
TheShock
08.02.2016 14:58+5Я вас умоляю, какое это стресс-тестирование? Обычное милое собеседование.
И вообще в повседневной работе парное программирование, когда другой разработчик смотрит, как ты пишешь код — обычная практика. Профессионал не имеет права относится к этому как к стрессу.vba
08.02.2016 16:10Ну да. Вы видимо никогда не бывали ни в той ни в другой ситуациях. Я вот например почти каждый день работаю в паре, благо скрум у нас. Поверьте мне на слово, ничего общего с парным программированием данное задание не имеет. Работа в паре подразумевает смену ролей каждые Х минут. Там даже сама суть отличается, дескать когда ты печатаешь, то процесс созидания не так глубок как когда просто сидишь, смотришь и размышляешь. А тут своего рода подавление всякого созидательного процесса из за нависшей над душой личности, которая кстати, не произносит ни слова пока ты сам пытаешься размышлять вслух, а ты в это время стараешься уловить как она реагирует на каждую строчку, ибо как раз привык работать в паре. Не сравнивайте бараньи рога и северное сияние.
TheShock
09.02.2016 13:42+3Вы видимо никогда не бывали ни в той ни в другой ситуациях
Почему же вдруг? Я сменил пару месяцев назад работу и прошел десятки собеседований, бывало до трех собеседований за день (у меня было время и я хотел выбрать). Были и собеседования онлайн, где я в онлайн-блокнотике пишу код и тет-а-тет и очень странные где прям в комнате, где проходило собеседование собирали шкаф и громко стучали молотком.
А уж парное программирование — обычная практика. Так чего сложного в том, когда ты сидишь дома, в любимом кресле, за любимым компьютером с вкусным чаем и программируешь?
а ты в это время стараешься уловить как она реагирует на каждую строчку
А ты не пытайся. Не думай об этом. Будь собой. Думай над кодом, как думаешь обычно. Если надо подумать, порисовать, то скажи, что надо подумать, порисовать, порисуй на листочке. И помни, что тебе не надо решить как-то особо, чтобы понравилось собеседнику. Тебе надо решить так, как решил бы ты. Потому что именно тебе работать в этой фирме, а не тому образу, который ты создал.
Cheater
08.02.2016 16:17+1Нет, это далеко не обычная практика. Обычная практика — это дать разработчику спокойно сесть за комп и разобраться с задачей один на один в своём ритме. Man «состояние потока», man «интроверт».
Delphinum
08.02.2016 16:19+4Не припомню еще ни одного моего собеседования на должность IT разработчика, которое не включало бы письменного или устного решения поставленной задачи перед интервьюером. Скажите, доктор, моя практика слишком расходится с нормальным положением вещей в области устройства на работу?
Cheater
08.02.2016 16:35Конечно не расходится, практически на всех собеседованиях дают решать задачу на месте. Я к тому, что у такого подхода много ложно-отрицательных срабатываний (заволновался — забыл простейшие вещи — провалил). Взять хотя бы ТСа — тест никаким образом не показал, что он, в принципе, разбирается в предметном вопросе (знает про оценки сложности, преимущества/недостатки рекурсивного подхода ит.д.).
Delphinum
08.02.2016 17:38Ну это да, современное тестирование при приеме на работу не идеально. Предлагаемое вами решение так же не идеально.
lair
08.02.2016 16:39+2Man «состояние потока», man «интроверт».
Бывают компании, где разработчики-интроверты, которые могут работать только в состоянии потока, не ценятся. Так что подобный тест как раз может проверять, совместим ли разработчик со внутренней культурой компании.Flammar
09.02.2016 11:02+3Да, есть кое-где тенденция ценить в первую очередь не максимальный результат, а повторяемый.
terryP
08.02.2016 18:26И вообще в повседневной работе парное программирование, когда другой разработчик смотрит, как ты пишешь код — обычная практика. Профессионал не имеет права относится к этому как к стрессу.
А почему профессионал не имеет права отказаться от работы где будет постоянно использоваться парное программирование? Я бы, например, скорее всего бы от такой работы отказался.khim
08.02.2016 19:54+1Может, конечно. Но это просто значит что кандидату, который не хочет раротать в таком режиме в этой компании делать нечего. И чем раньше это выяснится — тем лучше. И для компании и для кандидата.
dcc0
08.02.2016 13:44+5Всегда умиляли такие работодатели.
Есть реальный случай на моей памяти, когда один мой знакомый подробсил сразу нескольким очень грамотным математикам комбинаторную задачу, кстати, школьного уровня. Один из решающих просидел над задачей 4 часа (за плечами мат. вуз).
Это не насмешка. Просто немногие умеют расчитывать собстенное состояние, когда берутся за что-то. Ну и в ступор впасть может даже очень грамотный специалист.
Я уж не буду вдаваться в историю и рассуждать о том, как много понадобилось человечеству времени, чтобы додуматься до вещей, которые мы сейчас считаем тривиальными.
Видно, что автор творческий человек. А компания, похоже, искала человека, натасканного на типовые задачи.khim
08.02.2016 20:06+3Видно, что автор творческий человек.
Откуда видно? Из собеседования — нифига не видно. До тривального, простейшего, практически очевидного решения он дополз на следующий день. Это — творчество? Я вас умоляю.
Да, автор может быть весьма творческим человеком и многое мочь, а на собеседовании провал случился из-за волнения — бывает. Но из собеседования этого не видно.
А компания, похоже, искала человека, натасканного на типовые задачи.
Нет. Она искала человека, который не будет делать косяков в простых задачах. Это не одно и то же.
Я прямо и откровенно говорю кандидатам на собеседовании: да, у нас интересная работа. Да, мы занимаемся и наукой тоже. Но статьи и прочее — это достаточно небольшая часть вашей работы. Если вы упрётесь в задачу, с которой вы не совладаете — у нас десятки докторов наук, математиков, статиcтиков и т.д. и т.п. Найдём, поможем, сделаем как надо. Не бойтесь.
Но гораздо важнее — чтобы вы не засунули нам куда-то решение в O(N3), там где элементарно делается O(N log N) или не потратили памяти на два порятка больше, чем нужно, в простых задачах. Просто потому что доктора наук их вам помогать решать не будут. Тут уж, извините, вы всё должны делать сами.
Не бывает такого, чтобы все задачи были творческими. Рутины — всегда больше. И потому «творческий человек» — это хорошо. Это просто замечательно. Но при условии, что он рутинные задачи умеет решать тоже.
Allfar
08.02.2016 21:44-2А зачем вашим кандидатам работать у вас, если они могут спокойно себе писать O(N3) код и получать большИе деньги. И даже, кто бы мог подумать, приносить этим вот кодом прибыль своим работадателям.
Ну, странно как-то.
Я понимаю, наука, вот это все. Но трудно найти компанию, которая платит больше всех. А таких, которые платят меньше и мучают тупыми вопросами на собеседованиях — пруд пруди.
Это риторический вопрос, в общем. Реалии рынка, так сказать.khim
08.02.2016 21:51А зачем вашим кандидатам работать у вас, если они могут спокойно себе писать O(N3) код и получать большИе деньги.
Вот и я думаю: а с чего это кандидаты ломятся в Apple, Google, Microsoft, Yandex и тому подобные компании, где «изуверские собеседования», а не зашибают «больши?е деньги» своим O(N3) кодом в каких-нибудь конторах «Рога и Копыта»?
Я был бы счастлив, если бы подобных кандидатов вообще не приходилось видеть — и им бы было лучше, не пришлось бы писать статей на Хабр… Но как-то так не получается, да…
А таких, которые платят меньше и мучают тупыми вопросами на собеседованиях — пруд пруди.
Ну если они как-то существуют и как-то работников всё-таки находят, значит не так и мало они платят, да?
baldr
08.02.2016 21:54+1Ну не так уж и ломятся и не так уж «все». Оттуда тоже много уходит.
khim
08.02.2016 21:59-1Про «всех» я не говорил. Но при отсеве 98-99% и притом, что «много уходит» там ещё работают десятки тысяч сотрудников, а это значит что на собеседования туда приходят, в буквальном смысле, миллионы — если это не называется «ломятся», то как вы это назовёте?
baldr
08.02.2016 22:14Я называю это просто рекламой. Молодым разработчикам говорят что работать в Яндексе — модно, престижно и каждый день клевое селфи в офигенно модном офисе. Поэтому там большой поток кандидатов и поэтому они могут себе позволить выбирать какими угодно способами. Те, кто прошел их отбор — не обязательно самые лучшие. Просто они смогли пройти отбор.
Ко мне на собеседование приходили люди из Яндекса, которые поработали там и три месяца и два года. Они просто разочаровались. Бывает.
Есть люди, которые серьезно считают что вопрос «сколько теннисных шариков поместится в эту комнату» как-то связан с абстрактным мышлением. Никто не запрещает им проводить собеседования, чтож делать…
rboots
08.02.2016 13:45-1Не знаю на кого вы собеседовались, но за 12 лет работы фронтэндером, хоть в транснациональных корпорациях, хоть в маленьких стартапах, ни разу не приходилось применять на практике не только деревья, но даже алгоритмы сортировки. Современное программирование больше про паттерны и борьбу со сложностью и связанностью. Жаль, что многие собеседующие слишком сосредоточеты на том, что их учили в ВУЗе преподаватели, работающие по учебному плану, написанному в 80-х, и получающие в пять раз меньше их. Хотя, возможно, в серверной разработке это более актуально.
f0rk
08.02.2016 13:53+10Да ладно, а вложенные меню чем не деревья?
f0rk
08.02.2016 13:59+18А ну и конечно, DOM я забыл, с DOM вам тоже не приходилось работать за 12 лет работы фронтэндером?
PerlPower
08.02.2016 18:48-2Потому что со вложенными массивами(списками) работать проще.
lair
09.02.2016 12:24+4… а вложенные массивы/списки — это не деревья, по вашему?
PerlPower
09.02.2016 12:49-2Они самые. Но подход к обработке массивов мне кажется проще, чем к обработке деревьев. Вложенные циклы против рекурсивного прохода. Любой подмассив можно тут же отсортировать/отфильтровать. При определенной сноровке можно тоже самое делать и над деревьями, только сноровка должна откуда-то взяться. А откуда ей взяться, если в подавляющем большинстве можно написать алгоритм и без них?
В общем я согласен с rboots — сейчас в вебе можно замечательно обходиться без работы с деревьями и вообще структурами данных сложнее массива и алгоритмами.lair
09.02.2016 12:54+4Но подход к обработке массивов мне кажется проще, чем к обработке деревьев.
Не просто «массивов», а «вложенных массивов». Поэтому вам кажется.
Мне начинает становиться интересно — а что вообще вы называете деревом?
сейчас в вебе можно замечательно обходиться без работы с деревьями и вообще структурами данных сложнее массива
… и как бишь, вы обрабатываете JSON или XML сложной (а еще веселее — неформализованной) структуры?PerlPower
09.02.2016 15:20-3Не просто «массивов», а «вложенных массивов». Поэтому вам кажется.
Мне начинает становиться интересно — а что вообще вы называете деревом?
Мил человек, если вам удобнее обрабатывать массивы алгоритмами для деревьев, я ничего против не имею, от меня вам чем чего надо?
… и как бишь, вы обрабатываете JSON или XML сложной (а еще веселее — неформализованной) структуры?
Мне не приходится обрабатывать сложные древовидные структуры, только списки, где for и foreach максимум второго уровня вложенности хватает за глаза.lair
09.02.2016 16:07+5Мил человек, если вам удобнее обрабатывать массивы алгоритмами для деревьев, я ничего против не имею, от меня вам чем чего надо?
Мне от вас ничего не надо. Но если вы беретесь утверждать, что вложенные массивы/списки обрабатывать проще, чем деревья — то мне-таки интересно, что вы называете деревьями.
Мне не приходится обрабатывать сложные древовидные структуры, только списки, где for и foreach максимум второго уровня вложенности хватает за глаза.
Заводно. Расстрою вас, но это не «сейчас в вебе» (потому что «сейчас в вебе» дофига нетривиальной интеграции), это лично ваш опыт.
faiwer
08.02.2016 18:03+2Ну ? это смотря чем заниматься. Я за 3 года frontend-разработки уже и конечных автоматов, и разного рода механизмов парсинга, и имутабельных деревьев, и чего только не накушался. Но не жалею, ибо сложные задачи интересны, не наскучивают. Если бы я всё это время, как предыдущие года два, клепал однотипные корпоративные веб-сайты, мне бы пожалуй уже это всё опостылело.
Ну вот например одна из задач: разработать контрол, который предоставит удобный выбор элементов из иерархического словаря произвольной вложенности, с возможностью фильтрации. Этакое древо с галочками и input-text-ом для фильтрации всей этой груды значений. При этом словарь может быть объёмным, и контрол при этом не должен тормозить.
Ну или разработать контрол для вывода чего-либо огромного, и не однотипного. К примеру у вас есть миллион элементов произвольной высоты. Все сразу их в DOM пускать нельзя, вкладка помрёт. Нужно обеспечить показ только видимой части. А теперь представим что элементы могут иметь произвольную вложенность. Становится интереснее, да?
Все эти вещи, вроде одно и двунаправленного стека, конечные автоматы, деревья, всякие хеш-таблицы и пр., то и дело встречаются, когда отходишь от архитектурной задачи вглубь, к реализации чего-то конкретного.
Вот вы говорите, что frontend-разработчик. Неужели не приходилось заниматься парсингом какого-нибудь левого HTML-а на nodeJS? А свой собственный шаблонизатор писать пробовали?
BalinTomsk
08.02.2016 20:48+2Вам просто не повезло с компанией или позицией.
Краткий список интересныx задач заданныйх мне, где CS таки пришлось применить:
имплементировать crc64
сделать 2D-tile engine с компактым хранением
компрессор данных для float с регулируеммыми потерями
А вообше сильно помог сайт http://www.careercup.com.
Перед тем как лечь спать берешь один из самых трудных вопросов, ишешь в wiki как решать, смотришь ответы других, ручками пишешь имплементацию. Перед тем как уснуть прокручиваешь в голове решение. Число алгоритрмов в CS конечно и рано или поздно будешь знать их все и способы их имплементации.
Стремится нужно к тому что за 5 минут будешь готов предложить оптимальное алгоритмическое решение.
Компании из top-100 как правило не дают непосильных задач.
Чаше все я рассказывал им про алгоритм, который интервюеры не знали, потому что он не был в книжках по CS.
Да, желательно сидеть на форумах по алгоритмам и отслеживать что там новое в CS.
Да, большинство в жизни не будет использовано, но сильно меняет мышление.
santa324
08.02.2016 13:58+1Задача простая, но немного нестандартная. Видимо предполагается что собеседуемый вряд-ли сталкивался именно с ней, но если хорошо разбирается в алгоритмах — быстро придумает решение. Мне, например, рекурсивное решение пришло в голову в течении минуты. Но если никогда не писал обработку деревьев — быстро придумать может не получиться.
Возможная цель такой проверки — была ли у человека практика в написании алгоритмов, или только теорию читал.
И разве это стрессовая ситуация? Вот когда после 4 часов собеседования из 4х частей с разными собеседующими просят написать на бумажке решение чего — то подобного, и еще 3 человек сидят над душой…
Scf
08.02.2016 14:57+4Да, умение написать на бумажке работающий рекурсивный алгоритм — очень важное качество для программиста. Это самый простой способ определить, может ли программист в принципе писать алгоритмы или его будут вгонять в ступор вещи типа «написать toString для нашего рекурсивного доменного объекта».
khim
08.02.2016 20:10Тут не нужен рекурсивный алгоритм. Тут очередь нужна. Это если не думать. А если подумать — то вообще ничего не нужно.
«Провяжите» Nю строку — у вот у вас исходные данные для (N+1)й. Два цикла. Два if'а. Никакой рекурсии.
VitGo
08.02.2016 14:59-1я тоже не поддерживаю такого рода «интервью»…
1) Не понимаю: какая польза от кода написанного человеком за 5 минут?
О какой эффективности может идти речь ?! Если вы хотите проверить именно эффективность — то дайте задачу и скажите, что встретимся завтра. и вот тогда смотрите как задача решена — с использованием стека, или рекурсией или еще как! На собеседовании, человек творческий вряд ли сразу выдаст решение… и я не могу назвать это не профессиональным или следствием отсутствия знаний… Скорее наоборот — человек не зашоренный стандартными решениями совершенно точно не сможет решить задачу сразу… — он над ней должен подумать
2) Абсолютно не понимаю когда обсуждая знания и опыт человека в одном языке программирования просят решить задачу на другом… — это примерно тоже самое как нанимая учителя по русскому языку его на собеседовании попросят правильно расставить языки препинания в предложении написанном на китайском… — вроде как понятно что знания есть, значит должен разобраться… — но что таким образом проверяют ?!
3) Ну и конечно самое главное: мне всегда интересно спросить и задающих такие вопросы — а каким образом эта задача связана с реальной работой? Неужели работники часто пишут код в блокноте, в режиме цайт-нот'а на неизвестном языке ?! гм… боюсь тогда для этой работы не программисты нужны, а затыкатели дыр… (В идеале отключатели части функционала до поры пока в нем не разбирутся и не исправят программисты)
В банковской среде такие стрессовые интервью одно время часто любили проводить (лет 5 назад), например, для менеджера по работе с клиентами типичным было поставить задание «продать» депозит директору какой то торговой точки находящейся рядом с банком прямо сейчас (то есть кандидат должен выйти и осуществить продажу!) — но это хотя бы по существу работы (хотя с точки зрения организации самих продаж очень спорно), и опять таки менеджера никто в кассу не сажал…
в данном же случае, я замечу, что работодатель скорее всего сам не знает кого ищет. от того и такие требования и задания и организация интервью. Так что автор статьи много не потерял…lair
08.02.2016 15:18+2Скорее наоборот — человек не зашоренный стандартными решениями совершенно точно не сможет решить задачу сразу… — он над ней должен подумать
Вот то, как он будет думать, и представляет интерес для проводящего собеседование.
Абсолютно не понимаю когда обсуждая знания и опыт человека в одном языке программирования просят решить задачу на другом…
Обычно просят решить либо на языке, на котором будут писать на позиции, либо на псевдоязыке.VitGo
08.02.2016 15:47-1Вот то, как он будет думать, и представляет интерес для проводящего собеседование.
После этого хочется спросить: а вы деньги будете платить за то как он будет думать или за решение которое он в итоге сгенерит?
(конечно это не лично к вам вопрос, а к работодателю которому интересны пути которыми я приду к решению той или иной задачи)
Боюсь нарваться на минусы тем что вторгаюсь в профессиональные споры, сам к сожалению не программист (я любитель), зарабатываю абсолютно другим…
я долгое время ставил продажи в банках, всех своих менеджеров я обязательно обучал продажам, обязательно период обучения, потом тренинги, потом наставничество, потом периодический контроль продаж… в общем все по науке…
опыт постановок продаж у меня был, и я с удовольствием его оттачивал на новых командах, соответственно я знал (считал что знал) как лучше продавать (потому что сам в наставничестве и контроле постоянно участвовал в продажах)…
Ну так вот: в каждом банке где я внедрял систему продаж (а таких в чистом виде таких было 3) — я не спешил сбрасывать со счетов нестандартных менеджеров. Более того могу сказать, что по меньшей мере у меня было 2 менеджера при наставничестве которых хотелось выйти с переговоров и перейти с этим менеджером на уровень обучения — настолько все было «не так» и «через ж.п.»… — но эти менеджеры продавали… и продавали очень даже хорошо...- и они продавали не «не правильно» — они продавали по своему!
Так что не всегда нужно устанавливать стандарты на то как человек думает, в конце концов работодатель должен понять что он платит за результат… — думаю те работодатели которые это поняли — и устраивают рабочее место как тут было описано про гугл (если я правильно помню — вплоть «до перерывов на ничего не делание по своей задаче для того чтобы помочь в чужой»)
другим работодателям тоже об этом не мешало бы задуматься, к сожалению часто работодатель ставит свои (одному ему понятные) нормы деятельности в том или ином направлении, причем зачастую они очень далеки от эффективных (на это у меня тоже есть пример из своей деятельности, но опять таки он из другой сферы...)
кстати, еще одна мысль: все эти стандарты на решение задач, тестовые задачи для тестовых результатов нужны для того чтобы выбрать НЕ ХУДШЕГО СОТРУДНИКА требованиям которые поставлены… — еще раз прочитайте что я написал! НЕ ХУДШЕГО!!! то есть готового середнячка, который стандартно решит и сделает…
Всякий раз когда вы будете применять этот метод для поиска людей одаренных — будьте готовы на получение отрицательного результата!!!
просто потому что человек одаренный возможно обратит свое внимание на другой аспект решаемой задачи, или на другой способ (который возможно вы уже посчитали как неэффективный)… и скорее всего то что он будет делать сперва будет жутко не эффективным и не правильным! (потому что человек ищет СВОЙ ПУТЬ)… возможно он придет к избитому решению, но он в отличие от многих других будет искать еще!!!
мне повезло в жизни, и я встречал людей которые делали вещи которые просто не возможно объяснить нормальной логикой… у таких людей просто чутье находить решение там где никто уже и не ищет.., думаю что в программировании этот процесс должен быть более востребован, но как часто бывает в больших организациях зачастую рядовой-HR просто не понимает целей найма, как не понимают сотрудники проводящие тестирование.
Либо, не стоит сбрасывать со счетов, искали все таки НЕ ХУДШЕГО СОТРУДНИКА удовлетворяющего заданным критериям для решения плюс/минус стандартных задач (то есть не для создания чего то действительно нового (продукта), а для сопровождения, контроля, описания, обучения и так далее)lair
08.02.2016 15:53+5После этого хочется спросить: а вы деньги будете платить за то как он будет думать или за решение которое он в итоге сгенерит?
То, как он думает, как раз и показывает, какое решение он в итоге сгенерит. Более того, это показывает, какие решения он будет генерить для других задач.
(Если мне нужно только готовое финальное решение — мне не нужен сотрудник, мне нужен аутсорсер, у которого на входе задача, а на выходе — решение.)
Так что не всегда нужно устанавливать стандарты на то как человек думает
А с чего вы взяли, что кто-то устанавливает стандарты?
работодатель должен понять что он платит за результат
Вот только «результат» в программировании — это не просто готовый код.
просто потому что человек одаренный возможно обратит свое внимание на другой аспект решаемой задачи, или на другой способ (который возможно вы уже посчитали как неэффективный)… и скорее всего то что он будет делать сперва будет жутко не эффективным и не правильным! (потому что человек ищет СВОЙ ПУТЬ)… возможно он придет к избитому решению, но он в отличие от многих других будет искать еще!!!
Вот именно поэтому и интересно наблюдать, как человек решает задачу — сразу берет готовое решение с полочки или рассуждает, и если рассуждает, то как именно.VitGo
08.02.2016 16:02и много пытались проанализировать у автора статьи?
я так понял что его пытались натолкнуть на решение которое было известно (подсказывая), а не выясняя что же он хочет написать…
опять таки- для решения вопроса о профессиональных качествах — есть испытательный срок
все остальное чем обычно занимается HR — это обоснование собственной зарплаты, и к найму сотрудников подходящих для той или иной работы зачастую это отношение имеет весьма отдаленное…
P.s. у меня достаточный опыт и в найме и увольнении сотрудников (с подбором, собеседованиями и прочими «прелестями»)… и могу сказать что очень редко при приеме было ясно на что же способен тот или иной кандидат…lair
08.02.2016 16:12+3и много пытались проанализировать у автора статьи?
Автор про это ничего не пишет.
я так понял что его пытались натолкнуть на решение которое было известно (подсказывая)
Это только ваше предположение. С равным успехом его могли пытаться просто вытолкнуть из ступора, в который он, по его же словам, впал.
опять таки- для решения вопроса о профессиональных качествах — есть испытательный срок
Если каждого потенциального кандидата брать на испытательный срок, слишком много ресурсов будет потрачено.
все остальное чем обычно занимается HR
А при чем тут вообще HR?
vintage
08.02.2016 21:20+1Собеседующие зачастую переоценивают свои аналитические способности, особенно в области мышления.
lair
08.02.2016 22:32+1Многие люди ошибаются в оценке своих способностей, но суть не в этом. Все равно оценку на этом собеседовании будет проводить тот же человек, так что нет разницы, ошибется он в оценке во время выполнения задания или во время его обсуждения после. Более того, часто с этим же человеком и предстоит работать впоследствии, поэтому какова бы ни была его ошибка во время собеседования, она же будет сказываться и на работе. Так что все честно.
HaruAtari
08.02.2016 17:57+32) Абсолютно не понимаю когда обсуждая знания и опыт человека в одном языке программирования просят решить задачу на другом… — это примерно тоже самое как нанимая учителя по русскому языку его на собеседовании попросят правильно расставить языки препинания в предложении написанном на китайском… — вроде как понятно что знания есть, значит должен разобраться… — но что таким образом проверяют ?!
Вот тут не соглашусь с вами. Есть два вида специалистов, которых нанимают:
1. Программист с глубокими знаниями в узкой области. Тут важны те знания, которые уже есть у него т.к. большую часть своего времени он будет решать типовые задачи.
2. Программист широкого профиля (я говорю не о full stack разработчиках). Здесь важнее не то, что человек знает сейчас, а как быстро он может научиться новому. Чтобы он умел быстро разбираться в новых областях и решить новые для себя задачи.
Я в свое время собеседовал новых программистов в свою команду. Мы искали джунов, для дальнейшего обучения. Понятно, что не ожидалось от них глубоких знаний. Но если он умел учиться, то скорее всего мы его брали. Умение учиться проверялось простеньким тестовым заданием на языке, которого собеседуемый не знал. В конце нашей беседы давалось небольшое задание (требовало потратить примерно полдня), которое нужно было сделать дома на незнакомом языке (о языке договаривались). Задание сводилось не к алгоритмам, а к базовым знаниям этого языка. Без жестких временных ограничений.
Так и проверяли способность учиться. Если программист способен в спокойной обстановке за пару дней разобраться с основами незнакомого языка, то он умеет искать нужную информацию и учиться новому. И такого человека не страшно брать в команду.
Конечно, такой подход будет уместен не всегда.VitGo
08.02.2016 18:26поставил вам +1
Абсолютно согласен.
если человека вывели из зоны знаний (по крайней мере в которых он более уверен) — то это должно быть компенсировано временем и возможности делать задание в комфортной обстановке…
+абсолютно с вами согласен — вы искали людей способных учиться!!! — и выбрали абсолютно правильный способ (как минимум: восприятие новой информации о языке, принятие задачи, ее решение на основе полученных знаний)
но что произошло у автора статьи?
почему чему другой язык в блокноте в цайт-нот'е? проверить что ?! обучаемость к новому языку (наполовину придуманному самому (!!! то есть нужно еще и логически верные инструкции выработать со всеми ньюансами) ?!
не понимаю :-(HaruAtari
09.02.2016 01:27В конкретно этой ситуации, думаю, просто не придали этому значения. Это для собеседуемого это важно, а интервьюер мог просто не задуматься об этом.
boblenin
08.02.2016 15:38+2Либо вам отказали по совокупности различных моментов, обсуждаемых на собеседовании (напр. им нужен C#, а вы специалист по JavaScript) — и это наиболее вероятный вариант.
Либо если действительно отказали по одной задачке, но тогда идти к ним работать не стоит, т.к. у них лид — самодур или подбор персонала идет практически рандомно. В любом случае работать в такой обстановке — карьерное самоубийство для разработчика.vba
08.02.2016 15:59Нет с C# у меня проблем нет, просто небольшое предпочтение отдаю JS, да и онлайн редакторов типа напиши, запусти и поделись для JS гораздо больше чем для C#.
Мне кажется все же последнее, так мне, во всяком случае, сказала охотница за головами.VitGo
08.02.2016 16:05+1Знаете, в моем опыте было несколько случаев когда я отказывался от работы пройдя все собеседования… просто на основе анализа того как проводились собеседования, какие задачи мне ставились, какие решения принимались…
так что возможно вам нужно на собеседовании тоже более внимательно смотреть что от вас требуют, тогда и отказы будут для вас более понятными. И найденная работа действительно не только желанная, но и интересная и радующая…
tranquil
08.02.2016 16:35+6У меня подозрение что для прохождения этого задания не требуется полное правильное решение.
Тут проверяется как человек думает о проблемах и как разговаривает о проблемах. Ожидаются рассуждения в духе «так, здесь есть произвольное дерево, значит нужна рекурсия», «возможно можно сделать как-то без рекурсии более оптимально, но это чуть сложнее а поэтому сделаем хотя бы так», «дерево бинарное, значит у него есть такие-то и такие-то свойства, которые можно использовать», «так, пишем рекурсию: сначала пишем условия выхода, затем ...», «я сейчас попробую нарисовать схемку на листочке чтобы понять проблему». То что собеседователь задаёт наводящие вопросы и даёт обратную связь это только помогает.
В больших проектах и командах нельзя просто запереться в углу, войти в поток и выдать результат. Потому что проект длится месяцы и в нем участвуют десятки человек. Нужно постоянно разговаривать с заказчиками и разработчиками других модулей, причём разговаривать продуктивно.
Почему это называется problem solving? Возможно чтобы избежать слишком частых проблем вида «а я думал...», «мне никто не сказал», «ты же говорил», «я не знал» и т.п.
Mrrl
08.02.2016 17:02+11Без рекурсии и за О(1) дополнительной памяти:
void Connect(Node x){ while(x!=null){ Node newStart=null,y=null; while(x!=null){ if(x.left!=null) y=addNode(x.left,y,ref newStart); if(x.right!=null) y=addNode(x.right,y,ref newStart); x=x.neighbour; } x=newStart; } } Node addNode(Node x,Node y,ref Node start){ return start==null ? start=x : y.neighbour=x; }santa324
08.02.2016 17:27Красота! даже стыдно что не догадался а подумал о рекурсии :)
f0rk
08.02.2016 17:36Классно, не спорю, но я минут 20 разглядывал эти 14 строчек прежде чем понял, как они работают. Если потребление ресурсов не критично, я бы предпочел увидеть рекурсивное решение. Все же, этот кусок кода сложен для восприятия.
santa324
08.02.2016 18:25+4Восприятие субъективно, а асимптотика по памяти объективна.
В общем, подробный комментарий к методу — и решение будет идеально.
Mrrl
08.02.2016 17:42+1Мне тоже стыдно, что не заметил сразу. Хотя на рисунке чётко видно, что из очередной строчки можно получить следующую.
PsyHaSTe
18.02.2016 20:46+1Долго смотрел на это, никак не мог понять. Только потом заметил, что в addNode не просто вычисления делаются, а еще и присваивание… Не понимаю эту любовь все писать в 1 строчку, как будто бумаги жалко или места на экране.
zim32
08.02.2016 17:23-2Мне в топтал попалась задача написать функцию, которая находит минимальное кво шагов необходимое чтобы конь на доске добрался от точки 1 до точки 2. Завалил. Только потом узнал что это олимпиадная задачка. Полегчало
santa324
08.02.2016 17:32В каком смысле функцию? поиск в ширину нельзя?
Hokum
08.02.2016 18:09Например, функция принимает начальные и желаемые координаты, а возвращает список необходимых перемещений.
zim32
08.02.2016 18:47function (sourceX, sourceY, targetX, targetY): minSteps
santa324
08.02.2016 18:49Тогда поиск в ширину должен подойти
f0rk
08.02.2016 18:58-1Не все так просто, там циклы есть, так что метки на поле придется все таки ставить.
zim32
08.02.2016 19:20А еще условие что все это за O(1)
Mrrl
08.02.2016 19:26А доска ограничена или бесконечна?
zim32
08.02.2016 19:26Нет. Хотя уже не помню точно извините.
Mrrl
08.02.2016 20:00+1Тогда при чём здесь вообще программирование? Рисуем на бумажке карту и кодируем:
int dx=abs(targetX-sourceX); int dy=abs(targetY-sourceY); int p=max((dx+1)/2,max((dy+1)/2,(dx+dy+2)/3); if((p+dx+dy)%2!=0) p++; if(dx+dy==1 || (dx==2 && dy==2)) p+=2; return p;
PapaBubaDiop
08.02.2016 20:06+1-А доска ограничена или бесконечна?
-Нет.
2 часа пытаюсь понять ответ.
michael_vostrikov
08.02.2016 18:34У меня то же самое — сложно сделать задачу, которую раньше не решал или с которой не сталкиваешься постоянно, если разговариваешь с кем-то или просто кто-то смотрит и ждет. Я не сталкиваюсь, например, с алгоритмическими задачами, но при этом многие из них могу решить, если подумать над ними некоторое время в спокойной обстановке и представить все в деталях.
Я думал над этим, почему так происходит. Возможно, это из-за того, что работают разные отделы мозга. У кого-то общение забирает фокус внимания (как на этой картинке), и серьезно думать не получается, у кого-то получается совмещать и переключаться, кто-то такие задачи часто решает, и ему не надо задумываться, кто-то может вообще мыслит по-другому и у него это взаимосвязано.
То есть, это не боязнь завалить собеседование, или боязнь собеседника, а нестандартная для мозга ситуация, которая требует внимания и ресурсов, которые забирает на себя общение с собеседником. Примерно как в квантовой физике — наблюдение влияет на результат наблюдения.
IL_Agent
08.02.2016 18:38А что-то мешало написать решение в IDE и скопипастить в онлайн? Сам недавно проходил онлайн-собеседование с подобными задачками и делал именно так :)
И да, задачки такого плана на собеседовании — это нормально. Просто надо стараться меньше волноваться. :)
tyomitch
08.02.2016 18:38+1Уважаемый vba, вот вы озвучили аргументы, почему «решение олимпиадных задачек без IDE» — плохой, негодный способ проверять problem solving skills в условиях собеседования.
Какой способ, по-вашему, был бы хорошим и годным?baldr
08.02.2016 20:47+5Разрешите я отвечу своим мнением…
Что проверяется в этом случае? Что есть «problem solving skills»? Способность решать проблемы в случае факапа? Тогда дайте реальную задачу, более приближенную к жизни.
В чем будет срочность в реальной жизни? Service outage, логичнее всего.
Вы хотите чтобы после деплоя новой версии и при лежащем сервере разработчик решал олимпиадные задачи на сортировку и поиск пути в дереве? Точно? В нормальных компаниях это решается откатом назад и спокойным анализом ситуации в курилке, а потом спокойной починкой в течение нескольких дней, тестированием и деплоем.
Вы хотите чтобы человек умел решать олимпиадные задачи и нестандартно решал вопросы? Насчет «нестандартно» можно поговорить отдельно, если вы и правда этого хотите.
А про сложные алгоритмы — будут ли в вашей компании при реальной работе сидеть за спиной и смотреть на экран разработчика? Будут?? Ну нафиг такую компанию.
Не будут — тогда дайте задачу на дом и пусть он спокойно роется на stackoverflow и в гугле. То же самое он будет делать и на работе. Решит — молодец и неважно как. Не решит — ну тем более не подходит.
Если ваша компания предполагает постоянню работу в условиях стресса — тогда имеет смысл проводить такие собеседования. Пусть будет готов что его на работе будут бить внезапно током или спрашивать «сколько будет 18 в степени 42, решить за 5 минут при памяти в 36 килобайт и 17 рублях в кармане??».
Автор вполне убедительно обяснил, что решения приходят в голову при расслабленном состоянии — в душе или при мытье посуды…
У меня точно так же — после работы в метро внезапно сам собой всплывает в голове код и я понимаю что сделал ошибку в конкретно вот этом месте.
На собеседованиях я никогда не давал задания написать код на бумажке длиннее трех строк. Это не было нужным. Умного человека видно сразу. Задайте вопросы по архитектуре или по абстрактному решению задач. Ну спросите, если хочется, какие алгоритмы поиска в дереве человек знает. Код написать по алгоритму сможет любой.khim
08.02.2016 21:10-1Что проверяется в этом случае? Что есть «problem solving skills»? Способность решать проблемы в случае факапа?
Способность решать простые задачи без закладывания «бомб».
А про сложные алгоритмы — будут ли в вашей компании при реальной работе сидеть за спиной и смотреть на экран разработчика?
Где вы тут увидели «сложный алгоритм»? Ту на выбор полдюжины алгоритмов — и все элементарны просто как не знаю что.
Не будут — тогда дайте задачу на дом и пусть он спокойно роется на stackoverflow и в гугле. То же самое он будет делать и на работе.
Вот этого и боятся. Задачи подобного уровня не должны искаться «на stackoverflow и в гугле». Наоборот — человек должен выдавать приличный ответ сходу (хотя бы такой, как в решении номер 3) и дальше его можно уже обсуждать. Например спросить: «да, потребление памяти у вас тут приемлемо, но можно ли сделать лучше?».
На собеседованиях я никогда не давал задания написать код на бумажке длиннее трех строк. Это не было нужным.
Извините, но… не верю.
Умного человека видно сразу.
Фиг. Есть куча кандидатов готовых рассуждать о толкостях блокировки в Java или ещё о чём-нибудь подобном, но неспособных написать цикл так, чтобы чего-нибудь не потерять.
Код написать по алгоритму сможет любой.
Поделитесь травой, а? Которой вы откуриваете 90% кандидатов, которые на это не способны? Всем легче станет, чесслово.vba
08.02.2016 21:32человек должен выдавать приличный ответ сходу (хотя бы такой, как в решении номер 3) и дальше его можно уже обсуждать.
Приличный ответ? Вы серьезно? Для олипиадника может быть. Вы посмотрите на эти задачки, они кишат императивностью и «moving parts». Вы попробуйте подобный алгоритм поставить на поток, да и к чему? Зачем это нужно сегодня, помимо олимпиад? Кто сегодня пишет свои собственные реализации красно-черных деревьев?Delphinum
08.02.2016 21:33+2Кто сегодня пишет свои собственные реализации красно-черных деревьев?
*опасливо поднимаю руку*
khim
08.02.2016 21:45Кто сегодня пишет свои собственные реализации красно-черных деревьев?
Эк вы меня уели. Нет, красно-чёрных деревьев я давненько не реализовывал, признаюсь. А вот изменение алгоритмов от списков к массивам с аренами-аллокаторами — это пожалуйста. И задачки подобные обсуждаемой тут (и их адаптация под не слишком «удобные» структуры данных, которые, зато более «Cache-Friendly» — это наше всё.
Вы попробуйте подобный алгоритм поставить на поток, да и к чему?
К тому, что если у вас есть несколько миллиардов пользователей, то вы вполне можете выделить десяток программистов для того, чтобы снизить затраты на обслуживание одного из них на один цент в год — и это будет выгодно.Delphinum
08.02.2016 21:49есть несколько миллиардов пользователей
Чет вы перегнули с цифрой. Не уверен что у гугла если несколько миллиардов пользователей, а вы о какой то астрактной фирме рассуждаете )khim
08.02.2016 22:09+1Google. Только Android'ов сейчас уже больше миллиарда. А поиском не только с Андроида пользуются.
Microsoft. Пользователей Оффиса — 1.2 миллиарда и это притом, что не всякия винда с Офисом приходит.
Yandex, конечно, до миллирда не дотягивает, но даже его десятки миллионов — это очень неплохо с учётом того, что он фактически «окучивает» одну страну.
baldr
08.02.2016 21:59Что будет если на собеседовании у вас человек при реализации алгоритма допустит ошибку? Допустим, логическую — типа неправильного условия выхода из цикла.
Вы его сразу прогоните?khim
08.02.2016 22:14+1С этого момента собеседование только начинается :-) Заметит ли он её сам или придётся подсказывать? Какие мере предложит, чтобы разрулить ситуацию? Что сделает, чтобы такое больше не повторялось? Это как раз самая интрересная часть собеседования — но, как я понял, автор статьи до неё не добрался.
Что касается после приёма на работу… Тут ничего не надо придумывать, всё придумано тысячи лет назад: Errare humanum est, perseverare autem diabolicum, et tertia non datur.
Все допускают ошибки. Важно не допускать одних и тех же ошибок повторно — тогда можно надеяться что со временем ситуация будет улучшаться и вы не будете ходить по кругу.baldr
08.02.2016 22:22В общем-то, на этом самом месте уже определяется самое главное — ведет ли кандидат себя так, как вы хотите чтобы он вел себя в команде под вашим руководством.
Вы (и я) имеете свои представления о том, каких людей вы хотите видеть в команде и исходя из этого проводите отбор.
Вам важно, чтобы у него от зубов отскакивали простейшие вещи в плане кода и алгоритмов — вы таких и будете брать, возможно отсеивая вполне хороших кандидатов, которые запутались и не смогли ответить нервничая (как автор статьи).
Мне важно чтобы человек умел думать и находить решения, пусть даже в интернете и через какое-то время. Я сам не всегда чист с точки зрения кода и могу простить людям ошибки, которые могу допустить сам.
Но мне тоже важно, чтобы в моей команде и подо мной он плясал под мою дудку. То есть если он пишет сразу код и красиво говорит, но мне не нравится — я его не возьму. Думаю что и вы тоже.
vba
08.02.2016 22:13Послушайте но ведь, что-бы подойти к определенной, часто узкой, проблеме серьезно вы никогда не начнете с алгоритма. Вы сначала подберете и изучите определенную математическую модель под ваши нужды и лишь потом приступите к написанию кода. Вы никогда не начинаете писать кода и лишь потом напильником встраивать математическую модель.
khim
08.02.2016 22:18Вы никогда не начинаете писать кода и лишь потом напильником встраивать математическую модель.
Почему нет? Для большей части кода математическая модель столь проста, что вы берёте всем известные числа, делаете простую прикидку — и понимаете есть тут пресловутый цент или нету.
В сложных случаях, да, нужно проектировать и тестировать. Но нерально это делать для десятков и сотен миллионов строк кода!
baldr
08.02.2016 21:52+1Да пожалуйста, спрашивайте на собеседованиях о чем угодно. Я совершенно не собираюсь что-то доказывать. Я, в общем-то, согласен с вами в том, что хочется видеть как человек думает при написании кода и убедиться что это он писал, а не его помощник-друг из вашей же компании.
Моя мысль, которую я хочу пояснить: если человек написал алгоритм сразу и правильно — он, конечно, молодец, но если он не написал или ошибся — это ничего не значит. А значит ценность проверки невелика.
Психологически все люди разные, а программисты, как мне кажется, многие — социопаты и вообще люди, которых довольно легко вывести из равновесия.
Мне совершенно неинтересно на собеседовании видеть перед собой нервничающего человека и смотреть как он потеет и заикается.
Вы хотите обсудить оптимизацию памяти в алгоритме или проверить как он знает код? Проще распечатать несколько вариантов готового кода и дать ему с просьбой прокомментировать подход или найти ошибки. Вы сможете спокойно побеседовать, человек не будет нервничать и переживать за то, что не поставил точку с запятой в конце и ничего не запускается.
Я пишу на Django последние пять лет и постоянно допускаю глупейшие ошибки. Не могу запомнить как правильно пишется метод — «create_or_update» или «update_or_create» или еще как-то… Недавно было собеседование, там тоже попросили меня в Google Docs решить простейшую задачу в реальном времени. Даже не сортировку и ни разу не олимпиадную. За мной поправляли синтаксические ошибки, добавляли переносы и пробелы для читаемости, чтобы я не отвлекался от логики. Но я тоже запутался и что-то корявое написал. Хотя дома вечером спокойно потом для себя решил.
Если же вам нравится видеть как человек в вашем присутствии чувствует себя неловко — тогда да, есть смысл в таких задачах. Иначе — нет.
ИМХО.khim
08.02.2016 22:25+1Если он не написал или ошибся — это ничего не значит.
Если ошибся — не проблема. Не ошибается тот, кто ничего не делает. Но если он за час не решил задачу, которую, в общем-то, нужно решать за пару минут… то это о чём-то да, говорит, да? Иногда это говорит о том, что связь была отвратительная и кандидат просто не слышал ваших подсказок. Но не всегда же!
А значит ценность проверки невелика.
Совершенно верно. Мы же решаем не вопрос где ставить запятую в известном выражении «казнить нельзя помиловать», а и всего лишь вопрос: «стоит ли вот этого кандидата вот прямо сейчас брать на работу». Если это была случайная оплошность — ну придёт кандидат через год-два. Или не придёт. В любом случае это — не конец света!
Проще распечатать несколько вариантов готового кода и дать ему с просьбой прокомментировать подход или найти ошибки.
Большинство кандидатов будут потеть столь же усердно, но о кандидате вы узнаете меньше.faiwer
09.02.2016 08:31+1Но если он за час не решил задачу, которую, в общем-то, нужно решать за пару минут…
Откуда в вас столько снобизма? Аж противно читать. При том, что, кажется, уже каждый 4-ый комментарий в этом топике ваш. Вы так самоутверждаетесь что-ли? Да, это не самая сложная задача, но и не самая простая. Да, человек, который с подобным почти не сталкивается в реальной работе, вполне может затупить. А вы уже счёт на минуты повели.khim
09.02.2016 12:52+2Это не снобизм. Это — взгляд с другой стороны баррикад. Задача, которая не решается в спокойной, расслабленной обстановке «без нажима» за две-три минуты вообще не имеет права появляться на собеседовании. Ну пять минут — от силы (и то, если есть уверенность в том, что кандидат достаточно сильный).
Просто потому, что во время интервью на эту же самую задачу будет пострачено раз в пять больше времени и если задача за несколько минут в спокойной обстановке не решается, то ваш кандидат (даже хороший) в ней потонет — и вы ничего о кандидате не узнаете.
Что касается комментариев: тут вообще не так много людей с приличным опытом собеседований (проинтервьюировавших в своей жизни хотя бы сотню кандидатов из которых хотя бы десяток были приняты на работу), так чтобы была возможность сравнить ощущения от кандидатов во время интервью и а в работе. Приходится объяснять подробно, раз уж я в эту дискуссию встрял: я такую возможность имею и потому вижу мир в совсем ином свете. Вы видите «непризнанного гения», которого «отсеяли злые рекрутеры», я, как уже объяснял, вижу процесс где интервьюер увидел потенциальные болевые места после прочтения 5 строчек резюме, аккуратно и честно проверил их и кандидата «отсеял».
Ну вот где вы видите в описанном процессе проблему? Подсказки, как утверждается, были, попытки помочь — были, то, что кандидат их «не взял» скорее говорит о кандидате, чем об интервьюере, то, что дойдя до написания статьи он так и не дошёл до ассимптотически оптимальноего решения, а смог предложить только лишь хорошее — ну вы тут действительно видите повод для обсуждения?faiwer
09.02.2016 13:51+5В описанном процессе собеседования я не вижу проблемы. Если работа как-то связана с навыками в алгоритмах, и от соискателя требуется понимание алгоритмов, структур данных и соображайка в этом деле, то почему нет.
Главное чтобы соискателей хватало. Кадровый кризис, он ведь суров. Когда я столкнулся с задачей набора стажёров, я эту задачу с треском провалил. Соискателей было много, но людей, которые, хотя бы, имели опыт с СУВ, не писали транслитом, и имели зачаточные навыки в ООП, ? практически не было. Про «О большое» я вообще молчу. Про такие вещи я даже не заикался.
Меня смутил только лишь снобизм. Следуя вашим словам, получается, что автор вообще никуда не годен, раз не может решить за 2 дня задачу, на которую вам потребовалось бы всего 2 минуты. Гнать её в шею, да? Да и меня, наверное, мне тоже 2 минут не хватит. Быть может 10 или 20… Зачем меня только на работе держат.tyomitch
09.02.2016 13:59Меня смутил только лишь снобизм. Следуя вашим словам, получается, что автор вообще никуда не годен, раз не может решить за 2 дня задачу, на которую вам потребовалось бы всего 2 минуты.
Не никуда не годен, а в их команду не годен.
Цель собеседования — выявить не самого талантливого программиста, а самого полезного на данном конкретном месте.
vba
09.02.2016 16:34-3Следуя вашим словам, получается, что автор вообще никуда не годен, раз не может решить за 2 дня задачу
Вы знаете, у меня такое же впечатление сложилось. Вот и пиши после этого очерки о собственном опыте, тебя самого же еще и в грязь мокнут…
khim
09.02.2016 18:28Если работа как-то связана с навыками в алгоритмах, и от соискателя требуется понимание алгоритмов, структур данных и соображайка в этом деле, то почему нет.
Любая работа в большой компании всегда связана с алгоритмами и структурами данных. Про одну сторону я уже говорил. Но есть и другая. Если вы засунули O(N2) «не по делу» в сайтик с маленьким интеренет-магазином, то вы можете превратить тысячу в миллион, а десять тысяч — в сто миллионов. При быстродействии современных компьютеров в миллиарды операций в секунду «это» будет тормозить, но работать.
А вот если вы сделаете это с миллиардом пользователей — то вы миллиард превратите в квинтиллион и всё. Конец. Это — уже не полетит. Одна подобного рода ошибка, случайно допущенная и незамеченная, стоит столько, что правило: «людей, которые могут подобное сотворить и не заметить на работу мы не берём» абсолютно железное.
Байку про русский код читали? Вот именно для того, чтобы чтобы такого никогда не видеть подобные собеседования и проводятся.
billyevans
08.02.2016 22:26Мне кажется, что более адекватный вариант — это брать чувака сначала по контракту на какую-нить среднюю задачу или на пару недель и смотреть как он работает и как с ним ладит команда и тд. Тк кроме чисто технических скилов, есть еще социальные, которые тоже могут быть важны и которые сложно уловить на собеседование. А потом уже, если все хорошо переводить в штат.
Но, естественно, нужно брать не всех подряд, а по-любому как то пофильтровать, по резюме, возможно подобными простейшими задачами, какими-нить разговорами, мне кажется давать реализовать какую-нить дейкстру или еще какой-нить алгоритм, до которого люди доходили десятилетиями сходу на 40 минут это перебор для кандидатов.khim
08.02.2016 22:37мне кажется давать реализовать какую-нить дейкстру или еще какой-нить алгоритм, до которого люди доходили десятилетиями сходу на 40 минут это перебор для кандидатов.
Вы это серьёзно? Вот прямо так? А ничего, что на изобретение дробей ушли тысячелетия? А ничего, что о матане всего лишь лет 400 назад никто и не догадывался? Прикажите теперь кандидатов, не умеющих складывать дроби и рассуждать в терминах O большого на работу брать?
Времена меняются, требования к кандидатам — тоже.billyevans
09.02.2016 00:34+2Я имел ввиду не это. Знание настолько базовых вещей, естественно необходимо. Я про, то, что кандидат скорее всего не напишет сходу реализацию регулярных выражений, например, за 1 час без ошибок и требовать это несколько странно. Но как они устроены и какая сложность у них, знать хорошо бы. Я скорее про то, что умение решать задачи на интервью не совсем адекватный измеритель. По тому как я видел кучу народа, который, легко решает алгоритмические задачи и пишет код без багов(видимо тренировались долго решать такие задачки), но код сильно крив и эти кандидаты, имели слабое представление о процессе разработки, тестирования и деплоя вообще.
khim
09.02.2016 02:53+5Вы так говорите, как будто сами интервью никогда не проводили. Когда вы берёте резюме в руки и бегло его просматриваете, то вам сразу становится ясно — куда копать и на что смотреть.
То есть грубо:
A) Ага. Олимпиадник. Программировать умеет, но возможны однобуквенные переменные, замороченный код и вообще что-то такое, что пускать в нашу кодобазу опасно.
Что делать: дать заковыристую задачу, посмотреть как решит (заодно убедимся, что он настощий олимпиадник), поговорить о тестировании и оформлении. Бонус: если он что-то ещё и реальное программировал где-то.
Б) Так. Java. Тесты знает, любит, но может переусложнить всё нафиг и потратить памяти дофига и больше на ровном месте.
Что делать. Нужно посмотреть — может ли он обходиться без генерации 300 объектов для печати одного числа на экран. Бонус: если он что-то знает про всякие низкоуровневые вещи и понимает как ему в этом Java мешает — так вообще хорошо.
В) JavaScript (PHP, 1C, VBA — да, такие случаи тоже были). Тяжёлый случай. Предварительные ожидания: ни черта не знает ни про память, ни про сложность.
Что делать. 90% no hire сразу, но нужно посмотреть — может его просто судьба обидела и какие-то базовые знания о сложности и затратах памяти ещё сохранились (вариант что их просто нет не рассматриваем: мы не благотворительная компания и не ВУЗ, на нет и суда нет)? Нужна задачка, имеющая, в том числе, смысл и на JavaScript'е, но при этом чтобы там можно было поговорить и о сложности и о памяти. Вариант описан в статье. Задача выбрана, как на мой взгляд, неплохо.
Заметьте: вы можете вообще давать одну и ту же задачу, но в зависимости от ваших ожиданий (которые собеседование, отчасти, призвано проверить) смотреть на разные аспекты.billyevans
09.02.2016 03:28Я проводил, собеседования, но видимо Б и В до меня не доходили, тк вакансия была С++ разработчик. Кстати из тех, что смахивали на В был какой то особый вид C++ QT разработчики, которые кроме своего QT вообще ничего не знали, они даже на простые вопросы про сам С++ толком сказать мало, что могли, что было для меня сюрпризом, таких прям человек 5 было(может не показатель, но тем не менее странно).
Я в итоге как раз посмотрел человек 50 наверное и на очном и на скайпе.
В итоге взяли только 2х, да и то оба были по рекомендациям от коллег. Но я видел кучу народа, которого в брали, но я бы с ними не смог бы работать вообще и я это понимал еще на собеседовании. И потом было довольно сложно их уволить из тех команд куда они поподали, тк это выявлялось довольно небыстро. Я видимо, чисто по случайности и очень субъективной оценки их для себя отсеивал.
Это не такой простой и формализованный процесс и я не уверен, что заковыристая задача все может сказать про кандидата.khim
09.02.2016 13:00+1QTшники — это отдельный вид. Дело в том, что сама библиотека изначально появилась в Linux'е во времена, когда STL там был весьма и весьма покоцанный, потому в ней практически всё было реализовано с нуля.
Лучше всего их рассматривать как людей, которые программируют на «C++ из паралллельной вселенной». То есть есть среди них такие, которые ближе к варианту В), а есть и те, кто ближе к А) — но всё равно С++ (в смысле обычный, нормальный, C++) они не знают!
Ничего страшного. Просто проверяем их знание основ и прикидываем — сколько времени им потребуется переучиваться.
На самом деле «заковыристая задача» вообще ничего о кандидате сказать не может. Нужна задача простая (такая, как тут описана, к примеру) и нужно смотреть на то, как кандидат на неё реагирует.
Слабые-сильные стороны вы знаете (в большой степени) из резюме, ваша задача — прощупать насколько кандидат слаб там, где он должен быть (исходя из резюме) слаб и понять — сможет ли он подтянуться (сильные стороны — это бонус, нас волнует, чтобы провалов не было).
tyomitch
09.02.2016 01:31+1Скажите, зачем вообще собеседования нужны? Можно же брать всех, кто прислал резюме — а потом по ходу работы смотреть, справляются или нет. Как в макдональдсе каком-нибудь.
Или нет? Мне вот кажется, что в команде разработчиков будет сильно нездоровая атмосфера, если в неё всё время вливать «программистов на неделю».billyevans
09.02.2016 01:56Я предлогал не отмену собеседований, а скорее некоторое видоизменение процесса набора. Конечно, чтоб дойти до процесса контракта на неделю нужно тоже пройти некоторый немалый отсев.
Нет же набора в команду постоянно кучи народа, обычно нужно 1-2 человека. Так же это даст возможность составить впечатление о новичке, не только 5-10 людям, что его собеседовали, но и остальной команде, с которой он будет работать. Может, в процессе этой недели выяснится, что с ним не уживается полкоманды, а на собеседование это былоб невозможно уловить.
Возможно, это не лучший способ, это был мой ответ на вопрос «Какой способ, по-вашему, был бы хорошим и годным? ». Но и текущий вид собеседований тоже так себе вариант.khim
09.02.2016 02:08+1Нет же набора в команду постоянно кучи народа, обычно нужно 1-2 человека.
Вы плохо себе представляете процедуру набора. Набор идёт постоянно — просто потому, что для того, чтобы взять 1-2 человек нужно просмотреть от 50 до 200 кандидатов. Просмотреть такое количество кандидатов 5-6 людьми (типичный размер команды) нереально, потому отбор ведут далеко не только члены той команды где вы будете работать.
Может, в процессе этой недели выяснится, что с ним не уживается полкоманды, а на собеседование это былоб невозможно уловить.
А чего тут за неделю изменится? Если даже вновь нанятый за эту неделю не только успеет освоить процесс сборки, но и, о боги, чего-то сочинит (невероятное везение, кстати: если на прохождение всех стадий и доведение первого кода до влития в репозиторий уходит месяц, то это у нас считается черезывачайно быстро)… по этим двум строчкам кода о чём-то судить вряд ли получится.
За неделю в лучшем случае получится то же самое собеседование, только с кучей бумаг и усилий всей команды. Зачем такое?billyevans
09.02.2016 02:24То, что собеседование проводят люди из совершенно различный команд, это итак всем понятно и про количество кандидатов на 1 место тоже понятно, я не предлагаю их всех брать на поработать на одну-две недели. Это уже так сказать самая финальная стадия, до которой должны дойти единицы. Возможно чуть больше чем реально нужно.
Ну за неделю-две человек будет активно со всеми общаться, что то изучать, входить в курс дел. Можно понять его способность к обучению, как он с командой взаимодействует, может его смешной британский акцент никто не осилит понимать или еще что…
leventov
08.02.2016 19:46+1О, давно не было плача о собеседованиях на Хабре.
Я не считаю решение алгоритмических задач в блокнотах или досках на собеседовании несправедливым. В такой ситуации лажают ВСЕ программисты. Не стоит думать, что в компанию проходят программисты, которые почему-то научены хорошо решать задачи именно в таких условиях. Таких людей не существует. Ситуация одинаково дискомфортна для всех.
Если кто-то налажал меньше других — говорит ли это о том, что он будет лучше работать над реальными задачами? Я не знаю. Думаю, определенная корреляция есть. Может, есть тест, который дает лучшую корреляцию.
Однако то, что такая практика принята почти во всех крупнейших софтверных компаниях (Микрософт, Гугл, Яндекс точно), указывает на то, что что-то в этом есть. Все-таки не дураки там рулят HR-отделами.baldr
09.02.2016 00:58+3Однако то, что такая практика принята почти во всех крупнейших софтверных компаниях (Микрософт, Гугл, Яндекс точно), указывает на то, что что-то в этом есть. Все-таки не дураки там рулят HR-отделами.
Простите, но в этой фразе логики не больше чем синусов в электроне.
Оставим за скобками вопрос о том кто там рулит HR-отделами… Но…
В HR много методик, которые технически здравым людям кажутся немного… эмм… странными.
Вы никогда не сталкивались с методиками подсчета эффективности сотрудников в компании? Единая методика чтобы уравнять программистов, бухгалтеров и водителей… И соответственно начисления им всем премий-окладов… Написание бессмысленных отчетов и логирование времени с точностью до 5 минут…
Из крупных компаний идут такие методики и все кидаютсяя их копировать.
То же и с популярными вопросами типа «почему люки круглые» и монеток в стакане.
А за фразу «если уж Гугл/Яндекс так делает, значит это хорошо» — я бы предлагал сразу ставить вопрос о соответствии человека должности (особенно руководящей). Слишком часто на моей памяти это убивало хорошие решения. Сорри, но сам пострадал из-за таких людей — больной вопрос.khim
09.02.2016 02:17-1Сорри, но сам пострадал из-за таких людей — больной вопрос.
Оно и чувствуется.
Слишком часто на моей памяти это убивало хорошие решения.
Простите, но… откуда вы знаете, что предлагаемые вами решения были хорошими?
А за фразу «если уж Гугл/Яндекс так делает, значит это хорошо» — я бы предлагал сразу ставить вопрос о соответствии человека должности (особенно руководящей).
Почему вдруг? Если что-то делает [Известная компания], то это — однозначно не самое плохое решение. Оно может быть и не самым лучшим тоже (когда-то то, что делали IBM и Digital было эталоном, а то, что делают Гугл/Яндекс было «чем-то странным»), но оно точно не самое плохое. Уж по крайней мере какую-никакую, но обкатку оно прошло, можно говорить об эффективности.
А вот новые «правильные» решения — с ними сложнее. В большинстве случаев они являются бредом (бо?льшая часть молодых компаний банкротится в первый год), но, разумеется, какая-то часть новшеств оказываются более эффективна, чем «проверенные временем» решения… осталость только понять почему предлагаемые вами меры относятся к разделу «прорыв», а не «бред». Довод: «но ведь люди страдают!», понятно, никого не волнует сам по себе. В варианте «но ведь люди страдают — и больше к нам не придут!» его можно рассмотреть, конечно, но нужна статистика…baldr
09.02.2016 03:06+2Я считаю что у меня есть некоторое понимание как проектировать сервисы и я могу определить будет ли некоторая технология к месту в моем проекте или нет. Не все мои решения были хорошими, но как принимались плохие решения просто с оглядкой на какие-то странные аргументы — это я видел.
Я был свидетелем как об фразу «все используют mongodb, значит и нам тоже нужно» разбивались все мои аргументы. Точно такие же примеры были с кивком на Google — если они используют, то и у нас должно быть.
Решения должны приниматься исходя из целесообразности, а не моды. У Google и других больших компаний было достаточно много не взлетевших или неудачных технологий.
Если что-то делает [Известная компания], то это — однозначно не самое плохое решение
Не самое плохое, но может быть достаточно плохим даже для самой компании. Я работал, например, в Motorola 10 лет назад в золотые годы ее телефонов. Я видел изнутри достаточно плохих решений на уровне компании. Если уж мы говорим про управление персоналом и метрики — это вообще [censored] [censored].khim
09.02.2016 03:21У Google и других больших компаний было достаточно много не взлетевших или неудачных технологий.
Совершенно верно. И именно это позволяет вам сказать, что один тот факт, что Google использует (или не использует) какую-то технологию не говорит о том, что она является лучшим выбором. Я сам лично наблюдал как и Microsoft и Google делали очевидные глупости с выбором технологий.
Но мы-то говорим о наборе сотрудников здесь! Google использует один подход, Microsoft — слегка другой… и они работают! Мы это видим. Так что сказать «не стоит так делать, потому что и Google и Microsoft иногда принимают на работу идиотов (как вариант: никак не могут закрыть кучу вакансий)» — нельзя. Единичные проколы случаются, да, но в целом — уровень сотрудников в обоих компаниях вполне приличный, то есть эти технологии работают как и должны…
Я работал, например, в Motorola 10 лет назад в золотые годы ее телефонов. Я видел изнутри достаточно плохих решений на уровне компании.
Которые привели-таки компанию к краху, да. Причём случилось это не 10 лет назад, «сыпаться» Motorola начала раньше — но и здесь нужно скорее говорить о том, что метрики оценки работы внутри компании стали плохо работать (это объективный факт, иначе краха бы не случилось), а не о том, что стали принимать худших рабоников (скорее уходить начали лучшие).
Куда более красноречивый пример — это Nokia после прихода Элопа. Тут можно просто многотомники писать на тему «как не нужно управлять компанией». Но всё это — уже обсуждения компаний, которые «провалились». Пока компания успешна — говорить о том, что её методы управления «никуда не годятся», согласитесь, странно.
Конечно тут нужно смотреть не на первую производную, а на вторую, а то и третью (недаром акционеры Apple бодрость потеряли), но приницип — именно таков. Что с технологиями, что с методами управления…
andreishe
08.02.2016 19:59+2Собеседовался в фейсбук, микрософт и гугл. По телефону во все три, на онсайтах был в первых двух. Везде HR-заранее предупреждают о формате собеседования. В фейсбуке по телефону используют онлайн-IDE с совместным редактированием (ссылку не дам, забыл) — самое технологичное что я видел из этих трех, в микрософте в моем случае «собеседование» было чисто формальным, проверили, что я могу хоть какой-то код написать (написал 5 строк кода в скайп), в гугле использовали гугл докс. На онсайтах используют маркерные доски в всех трех, в гугле предлагают на выбор доску или хромбук. И, да, задачки весьма в духе того, что в топике везде. Особенно по телефону. На онсайтах могут о всяком разном разговаривать (разработать архитектуру чего-нибудь в общих чертах), но такие задачи тоже будут.
Так что то, что автор был не готов — это вина и HR-а и его самого. HR должен был сообщить о формате заранее, а соискатель мог бы и поинтересоваться, если HR не сообщил.
ababo
08.02.2016 20:56Чтобы решить эту задачу без напряга достаточно понимать, как реализуется обход дерева в ширину (я про использование очереди).
khim
08.02.2016 21:16-2Это не самое лучшее решение, но да — неплохой первый шаг. Рекурсия — тоже приемлемо. То, чего хочется получить — это примерно вот это, но если кандидату для этого потребуется пара подсказок — это не страшно. А вот то, что в статье написано — страшно. Ну то есть я понимаю: заскок, со всеми бывает, но при чём тут собеседование? Ну переклинило, ну не смог элементарную задачу решить от слова «никак»… это повод статью на Хабр писать?
SkidanovAlex
08.02.2016 22:46+7Такие задачи на интервью, на самом деле, показывают много. Например, по вашей статье я могу сразу ответить для себя на следующие вопросы о вас:
1. Вы не знаете что такое обход в ширину, потому что не поняли сразу, что это задача на обход в ширину. Только к третьему решению вы начали использовать очередь.
2. Вы не умеете оценивать время работы алгоритмов:
2.1. потому что ваше первое решение работает за О(n) а не за O(2^n), как вы его оценили (navigate вызовется один раз для каждой вершины, и имеет константный оверхед).
2.2. потому что ваше второе решение работает за О(2^h) где h — это высота дерева. filter не бесплатный, да? Есть деревья у которых n = h, то есть ваше второе решение в худшем случае, как раз-таки, работает за O(2^n), а не первое.
3. То, как вы оцениваете потребление памяти, тоже вызывает нарекания. Во втором решении вы меняете представление дерева, но не учитываете стоимость нового представления в вашей оценке потребляемой памяти.
А самое главное, даже в удобной обстановке с вашей любимой IDE вы так и не нашли правильного решения за O(n) времени и O(1) памяти (оно существует, без изменения представления).
Как же это плохая задача, если с помощью нее за такое короткое время можно показать огромные пробелы в вашем знании базовых алгоритмов и оценке их сложности?
Отвечая на ваш другой вопрос: нет, не для любой работы эти знания нужны. Это не отменяет того факта, что для работы в той конторе, куда вы отбирались, они-таки требуются. Вероятно, есть другие компании, где эти навыки не требуются. Они, соответственно, не будут задавать вам такие задачи. И я искренне желаю вам удачи на интервью в них.baldr
08.02.2016 23:02-2А что если кандидат написал неоптимальное решение только потому, что боялся за отведенное время еще больше облажаться с правильным?
Он может это сказать, конечно (я решил вот так, но это неоптимально, лучше было сделать через вон тот способ), но какой в этом для вас смысл если вам нужен именно код, а не разговоры?
Что если он не помнит (ну вот не помнит, перепутал на нервах) какая из двух библиотечных функций оптимальнее в данном случае, а посмотреть в гугле не может?
Что если у него нет, как в нормальных привычных условиях, возможности написать и запустить тесты для проверки?
Хотя, получив аналогичную задачу на работе он вполне может сделать все правильно и хорошо. Получается что на собеседовании вы не раскрыли человека?
Вариант «попросить подсказку» я все-таки предпочту не рассматривать, поскольку для большинства кандидатов, мне кажется, это равносильно признанию «не знаю» и они стремятся этого избежать всеми способами.khim
08.02.2016 23:16+4А что если кандидат написал неоптимальное решение только потому, что боялся за отведенное время еще больше облажаться с правильным?
А он об этом сказал? А что он ответил после этого? А после разъяснений?
Это-таки именно собеседование, очень важно что и как делается. Но если в конце-концов решения нет никакого — то это провал однозначно.
Он может это сказать, конечно (я решил вот так, но это неоптимально, лучше было сделать через вон тот способ), но какой в этом для вас смысл если вам нужен именно код, а не разговоры?
Тут уже много говорилось: если у вас подход «есть задача, нужно решение», то вам сотрудник не нужен совсем, отдаёте задачу «на сторону» и всё.
В реальной жизни техлиду постоянно приходится решать: то ли идеальное решение через месяц, то ли корявое — но прямо завтра. А может что-то не такое корявое, но не через месяц, а через неделю?
Вот и собеседование вопроизводит эту ситуацию в миниатюре.
Что если он не помнит (ну вот не помнит, перепутал на нервах) какая из двух библиотечных функций оптимальнее в данном случае, а посмотреть в гугле не может?
Вот именно поэтому мы тут обсуждаем задачку, которая гугления не требует, не так ли?
Что если у него нет, как в нормальных привычных условиях, возможности написать и запустить тесты для проверки?
Много вы видели тестов способных отличить O(N2) реализацию от O(N)?
Вариант «попросить подсказку» я все-таки предпочту не рассматривать, поскольку для большинства кандидатов, мне кажется, это равносильно признанию «не знаю» и они стремятся этого избежать всеми способами.
Наоборот: это тот вариант, с которого нужно начать!
Если кандидат упорно ломится «не в ту степь» несмотря ни на какие подсказки, или, ещё хуже, не задаёт вопросов не имея своих идей, то велик шанс, что он так же и на работе будет поступать.
Сотрудник, который вам через неделю после получения задачи скажет «ну не шмогла я, не шмогла» — столь же плох, как и тот, который у вас потребует 20 минут разъяснений на 15 минутную задачу (проще и быстрее самому уж сделалть).
И ровно это и оценивает собеседование. Неплохо оценивает, если по статье судить.vba
08.02.2016 23:33-1Неплохо оценивает, если по статье судить.
Ну это сугубо ваше мнение, опрос показывает что оно идет в разрез с большинством. Я все же считаю по другому.khim
08.02.2016 23:50+3Ну это сугубо ваше мнение, опрос показывает что оно идет в разрез с большинством.
Большинством собеседующих? Или большинством тех, кто хочет устроиться на работу?
Тут, понимаешь, балшая разница.vba
09.02.2016 11:18-5Ну вы еще сюда приплетите сколь из проголосовавших было неграми, китайцами и женщинами а какие были неграми работодателями. Потому что там тоже понимаешь, разница просто огромная.
SkidanovAlex
08.02.2016 23:58+2На самом деле все ваши комментарии упираются в то, что «ну я мог бы сказать / спросить» — так мы на собеседовании же и вашу коммуникабельность тестируем. Похоже, что в вашей гипотетической ситуации кандидат был не раскрыт из-за пробелов в навыках обяснить свои идеи и проблемы.
vba
08.02.2016 23:28+11. Вы не знаете что такое обход в ширину, потому что не поняли сразу, что это задача на обход в ширину. Только к третьему решению вы начали использовать очередь.
Вынужден с вам не согласиться, я знал и знаю что такое проход в ширину, меня смутил факт отсутствия смежных узлов. Я изначально начал мое решение в блокноте с прохода в ширину.
Вы не умеете оценивать время работы алгоритмов
Тут каюсь, есть пробел, стараюсь его преодолеть. Я не был уверен до конца в точности моих цифр, тем более что для рекурсии изначально поставил O(n).
2.2. потому что ваше второе решение работает за О(2^h) где h — это высота дерева.
Тут право я не совсем понял почему.
Во втором решении вы меняете представление дерева, но не учитываете стоимость нового представления в вашей оценке потребляемой памяти.
Тут я согласен, я об этом и говорил, что такое представление малоэффективно. Как тогда более конкретно спроецировать стоимость нового представления на оценку потребляемой памяти? Умножить на некий C?
Как же это плохая задача, если с помощью нее за такое короткое время можно показать огромные пробелы в вашем знании базовых алгоритмов и оценке их сложности?
В том то и дело, что упражнение называется, не упражнением на знание теории алгоритмов и оценке их сложности а упражнением на умение решать проблемы.SkidanovAlex
08.02.2016 23:50> Тут право я не совсем понял почему.
Представьте себе дерево, у которого n вершин, у каждой только левый ребенок. В вашем представлении размер массива будет (2^n)-1, и его надо будет целиком профильтровать чтобы убрать nulls.
khim
09.02.2016 00:00-2В том то и дело, что упражнение называется, не упражнением на знание теории алгоритмов и оценке их сложности а упражнением на умение решать проблемы.
Вы не поверите, но это упражнение является упражнением на умение решать проблемы. Про том условии, конечно, что вы информатику computer science, а не умение работать в Ворде!) знаете в приличном объёме.
Ну примерно как сочинение при поступлении в ВУЗ: да, оно оно призвано выяснить как хорошо вы умеете выражать свою мысль, но если у вас будет достаточно много ошибок в грамматике и/или пунктуации — то никто на ваши фабулу и экспозицию внимания обращать уже не будет. Поставят «неуд» и всё.vba
09.02.2016 11:21-2А для вас люди делятся на две категории, те кто умеет решать алгоритмические олимпиадные задачки и те кто, всего лишь умеет работать в ворде?
khim
09.02.2016 14:50Причём тут «олимпиадные задачки»? Люди, в с точки зрения приёма на работу, делятся на две категории: знающие инфрматику (теория алгоритмов, теория информации и прочее) и её не знающие.
К сожалению так исторически сложилось, что на «уроках информатики» зачастую людей учат работать в Word'е и Excel'е и пятёрки там получают вовсе не люди, которые знают почему самая быстрая сортировка не бывает, в теории, быстрее, чем O(N log N), и знают когда на практике — бывает и быстрее, а люди, которые лучше всех знают систему меню в какой-либо программе. Вот такое, с позволения сказать, «знание информатики» никому не интересно. Отсюда — моё уточнение.vba
09.02.2016 16:15-2знающие инфрматику (теория алгоритмов, теория информации и прочее) и её не знающие.
Т.е. насколько я понял для вас люди знающие информатику это люди способные решать типовые задачки оторванные от всяких реалий. Ну а все остальные это вордо-отличники, знания которых никому не интересны.tyomitch
09.02.2016 16:32+3Как по-вашему: «люди, знающие математику» — это те, кто способны сдачу в магазине пересчитать, не сбившись? Или те, кто способны решать типовые квадратные уравнения, оторванные ото всяких реалий?
khim
09.02.2016 18:05+1Т.е. насколько я понял для вас люди знающие информатику это люди способные решать типовые задачки оторванные от всяких реалий.
Да, конечно. Но вы забываете что это — только первый этап.
То есть алгоритм таков:
1. Если человек умеет решать «типовые задачки оторванные от всяких реалий», то
2. Надо посмотреть сможет ли он в реалиях находить подобные задачи и
3a. Знаете ли он про то, как писать юниттесты, а также
3b. Понимает ли он что-то в CSS, и, может быть
3c. Разбирается ли он в TCP/IP, и, возможно
3d. У него есть неплохой опыт работы с базами данных,
3e, 3f, 3g…
Дальше по совокупности уже смотреть. Пунктов 3 много, так как технологий тоже много, они часто меняются и с ними всякое происходит. Плюс сегодня может не быть плюсом завтра.
А вот «быстрая сортировка» — она полвека назад «быстрая сортировка» и сегодня «быстрая сортировка» и в следующем веке она такой же будет. Её знать нужно обязательно. Так же как и обходы в ширину, глубину, рекурсию и прочее. Сильно специализированные вещи (типа фибоначчевой кучи) — это «по желанию». Ну о чём можно говорить если человек не может даже алгоритм Дейкстры изобразить? Он может его даже не уметь называть по имени (это как раз необязательное умение), но программу-то на его основе он сделать должен (если вдруг вы тоже не знаете что такое алгоритм Дейкстры, то не поленитесь — пройдитесь по ссылке, прочитайте, подумайте и поймите что если вы что-то мало мальски сложное программировали, то наверняка уже реализовывали его много раз в разных формах).
Ну а все остальные это вордо-отличники, знания которых никому не интересны.
Почему же сразу «никому»? Кому-то другому, в другой компании, на другой позиции — да, они могут быть и интересны. В Google или Microsoft — нет.vba
09.02.2016 18:28-4Да, конечно. Но вы забываете что это — только первый этап.
Ну по вашему может и первый. Он все так же не связан с реалиями
Надо посмотреть сможет ли он в реалиях находить подобные задачи и
Речь шла о задачах оторванных от реальности
В Google или Microsoft — нет.
Microsoft, хм, подождите ка минутку, эта не та ли компания что продолжает нас радовать выпусками шарпоинта, отсутствием нормальной файловый системы и прочими плюшками? Вы еще забыли амазон упомянуть, они тут неплохо звездили в NWT в сентябре прошлого года. Про Google тут тоже упомянули.
khim
09.02.2016 19:19Microsoft, хм, подождите ка минутку, эта не та ли компания что продолжает нас радовать выпусками шарпоинта, отсутствием нормальной файловый системы и прочими плюшками?
Эта та компания которая в борьбе с BeOS, GEOS и прочими всякими IRIX взяла и просто-таки уничтожила всех конкуретнов. Осталась парочка на десктопе и горсточка на сервере. Причём и там и там присутствует (кроме творения Microsoft) ещё только лишь одна система — которую при этом пилят «всем миром» (всякие Kolibri и ReactOS уж позвольте не учитывать — это хобби, а не коммерческие системы, совсем другая категория).
То, что у Microsoft файловая система не идеально — известно, но она оказалась достаточно хороша для того, чтобы этого результата достичь. И вот чтобы так суметь — и проводятся подобные собеседования.
Сумеете сделать лучше — сможете рассказывать про «отсуствие файловой системы и прочие плюшки»…tyomitch
09.02.2016 19:48Осталась парочка на десктопе и горсточка на сервере. Причём и там и там присутствует (кроме творения Microsoft) ещё только лишь одна система — которую при этом пилят «всем миром» (всякие Kolibri и ReactOS уж позвольте не учитывать — это хобби, а не коммерческие системы, совсем другая категория).
MacOS и {Free|Open}BSD вы в хобби-проекты записали, или в линуксы?khim
09.02.2016 20:00MacOS — это как раз одна из двух «альтернативных» систем, оставшихся на декстопе. Но её нет на сервере.
{Free|Open}BSD — есть на сервере, но нет на десктопе (вернее есть, но там это чистый хобби-проект: никто из серьёзных производителей уже давно ничего под {Free|Open}BSD десктопоного не выпускает, что, как бы, основной показатель).
Единственная система (кроме Windows), которая как-то присутствует на сервере и на десктопе — это GNU/Linux. Всякие Android и ChromeOS пытаются прорваться, но во-первых пока не шибко успешно, а во-вторых в своей основе это всё равно Linux…
vics001
09.02.2016 04:03Что конечно же не отменяет главного факта, что для многих людей интервью это стресс. А программирование это совершенно не стрессовое занятие, даже наоборот это drive, а не стресс. И то, что люди не могут показать лучших результатов тоже об этом говорит, они же не тренируются проходить интервью каждый день.
Для обычной работы обучаемость человека может перекрыть все перечисленные недостатки с лихвой, если человек сядет за книжку и выучит все за неделю, это говорит о его стимуле, который может быть гораздо полезнее в работе, по сравнению с человеком, который подготовился к интервью, хладнокровен, но абсолютно не хочет выполнять будущую работу.
В общем, интервью это быстрый способ принять очень сложное решение в неопределенных условиях и я думаю интервью, ну никак не способны решить эту задачу, тем более создавая стресс для интервьюируемого. Поэтому я за, то чтобы публиковать примеры задач перед тем как идти на интервью вообще, а может быть даже давать задачи до интервью.tyomitch
09.02.2016 04:28+1Что конечно же не отменяет главного факта, что для многих людей интервью это стресс. А программирование это совершенно не стрессовое занятие, даже наоборот это drive, а не стресс.
У вас никогда не было ситуации «build system накрылась за день до релиза»? Когда надо всё починить вот прямо сейчас, и «сходить погулять, расслабиться, подумать» — не вариант?vics001
09.02.2016 11:37Постоянно бывает, что совсем не одно и тоже, что стресс при собеседовании. Такие обстоятельства можно сравнить с обычным стрессом, когда опаздываешь на работу и т.п. И конечно же в таких ситуациях не пишется программа в блокноте, в неизвестных условиях и т.п.
И все равно, далеко не все должны уметь работать в стрессовой ситуации.
utf
08.02.2016 22:53+7Я сам задаю такие задачки на собеседованиях. Считаю что это нормально и дает многое узнать о кандидате, например:
- На сколько упёрт кандидат. Некоторые сразу демонстрируют что им это не нравится и они не хотят писать задачки на листочке (или в онлайн редакторе). Это большой минус.
- На сколько легко он понимает мои подсказки (ведь мне с ним работать). Кстати, если кандидат берет подсказку, это еще не значит что все плохо. Просто иногда не получается вспомнить какую-то мелочь человеку. Бывает.
- Как кандидат мыслит при выполнении задачи
- Какие ошибки делает. Многие, например, не знают как проверить что значение это массив.
- Знает ли он базовые концепции программирования, такие как рекурсия, область видимости, и т.д.
- Знает ли он алгоритмы
- И что самое худшее, не сдастся ли он преждевременно. Если кандидат говорит «не смогу», даже если собеседник всячески старается подсказать решение, то это 100% провал.
oYASo
08.02.2016 23:47+1Прям вот согласен, особенно пункт 1 (про упертость). Помимо приведенных проблем, если человек как баран пытается решить задачу в лоб, и никакие подсказки его никуда не могут увести, то этот кандидат, скорее всего, в дальнейшем плохо покажет себя в команде.
oYASo
08.02.2016 23:38Как тут уже многие написали, такие собеседования — типичная практика в крупных софтерных компаниях. Причем, это нулевой этап, т.е. если вы его проходите, то вас уже приглашают на личное собеседование, где задачи практически точно будут намного сложнее.
Думаю, основная проблема автора в том, что он сразу побежал писать код. Обычно на таких собеседованиях хотят посмотреть, как человек анализирует задачу, перебирает варианты и предлагает решения. Возможно — насколько правильно человек задает вопросы. Знания синтаксиса языка или каких-то хитрых конструкции, как правило, никого не интересуют, но хоть и громоздкое, но решение хотят увидеть. Да, вам может попасться педант, который завернет на отсутствующей точки с запятой, но это редко и маловероятно.
Теперь, собственно, зачем вообще такие задачи. Тут многие пишут, что вот проработали программистом n лет, а всякие там деревья или сортировки им так и не понадобились. Это действительно так для целого ряда направлений разработки ПО (интернет-магазин, мобильные приложения банков и прочее, и прочее). Но если речь идет о задачах (как правило очень интересных), в которых нужно обрабатывать большие массивы данных, все эти деревья становятся просто базовый скиллом для разработчика (СУБД, 3d-движки, поисковые движки, геоинформационные системы и т.д). Если взять разработчика без соответствующих навыков, то он так и будет все складывать в последовательный массив, а потом удивляться отсутствию памяти и долгой работе. Поэтому человека, который начинает явно думать не так, как того требует окружающая среда компании, проще отсеять, чем переучивать.
Что касается предложений написать длинные задачи (посиди пару дней и напиши). Такое тоже встречается довольно часто и имеет полное право на жизнь. Тут уже зависит от специфики компании (есть много времени на исследования, есть долгоиграющие задачи, есть большая команда разработчиков и наставников и т.д.).
Если говорить о моей личной статистике интервьювера, то у меня сложилось мнение, что люди, которые могут быстро предложить хоть какие-то решения, которые много задают вопросов по границам и применимости задачи, пытаются ее анализировать и хотя бы проговаривать оптимальные решения, в большинстве случаев в дальнейшем оказываются намного эффективнее людей, которые молча садятся писать идеальный код. Люди с долгой раскачкой довольно часто кучу времени тратят не на результат, а на сторонние вещи, которые потом все равно приходится выбрасывать (идеальная математическая модель, идеальная архитектура, идеальные комментарии в коде и т.д.).
splatt
09.02.2016 04:05+2Вы путаете умение использовать подобные структуры данных, и знание наизусть алгоритмов для работы с ними.
Если в вашей компании необходимо обрабатывать большие массивы данных, то я готов спорить, что для решения таких задач как в статье вы используете готовые библиотеки для работы с бинарными деревьями, ну или на крайний случай готовые алгоритмы.
Если в вашей компании думают, что «сейчас я буду решать задачу эффективного обхода бинарного дерева, не подглядывая в гугл», то скорее всего, в вашей компании что-то не так.
Людям потребовались годы, что бы изобрести подобные алгоритмы, и ни один соискатель не сможет придумать их за 5 или за 10 минут. Взгляните правде в глаза — если человек на собеседовании решил подобную задачу и сказал, что он за 10 минут придумал алгоритм горизонтального обхода двоичного дерева, до этого про него не знав, то он либо гений, либо просто врет (что скорее всего).tyomitch
09.02.2016 04:30На ваш аргумент уже был дан ответ выше.
splatt
09.02.2016 05:16+2Не увидел там ответа на мой аргумент. Ответ в стиле «а вот на изобретение дробей ушли тысячелетия» — это какой-то бессвязный бред, вступать в обсуждение и спорить о том откуда начинать летоисчесление у меня желания нет. Я говорю не о том, сколько у человечества ушло времени на изобретение алгоритмов, а о том, что не зная алгоритмов обхода бинарного дерева их практически невозможно придумать самому за 10 минут. Собственно, как и формулы мат. анализа и даже вещи гораздо проще. Если вы их не знаете, не изучали в школе или просто забыли, изобрести их самому невозможно.
В качестве аргумента я готов предложить вам сесть и не пользуясь сторонними источниками, используя лишь ручку и листок бумаги вывести формулу дискриминанта/корней уравнения для многочлена N-ной степени (4й, кубического, ну или хотя бы для обычного квадратного уравнения, 8й класс). Сможете решить, если не помните как оно выводится? Будьте честны хотя бы сами с собой.
Еще раз — я говорю о том, что есть разница между тем что бы знать материал и уметь изобрести подобные вещи самому. Все, (ну или почти все) знают формулу квадратного уравнения, но вывести ее самому могут немногие (за исключением тех, кто помнит, как ее выводить). Вывести в условиях собеседования за 10 минут, не помня как она выводится, смогут лишь гении.Mrrl
09.02.2016 09:02+1Формула корней уравнения 4-й степени? Вот что получилось за 5 минут:
x^4 + a*x^2 + b*x + c = 0.
Попробуем разложить на квадратичные множители:
x^4 + a*x^2 + b*x + c = (x^2 + p*x +q)*(x^2 — p*x +r)
a = — p^2 + (q+r)
b = p * (r-q)
c = q*r
Возведём второе уравнение в квадрат и подставим p^2 из первого уравнения, а r*q — из третьего:
b^2 = p^2 * (r-q)^2 = ((q+r) — a) * ((r+q)^2 — 4*q*r) = ((q+r) — a) * ((r+q)^2 — 4*c).
Получили кубическое уравнение относительно q+r. Решаем его по формуле Кардано, а потом, зная q+r и q*r, находим q и r. p найдём из второго уравнения (это позволит не беспокоиться о лишних корнях).
Последние 30 лет я точно не вспоминал, как это решается, а когда решал в первый раз, то вспоминать было еще нечего.
Про дискриминант — вопрос вообще с подвохом. Насколько я помню, для высоких степеней он определяется, как результант многочлена и его производной, после чего считается по формуле. Тут либо знаешь, либо нет.
Про то, что существует специальный «алгоритм горизонтального обхода двоичного дерева», я в первый раз услышал из этого обсуждения. Если мне нужно будет так обойти дерево — напишу с нуля, хотя, скорее всего, вместо очереди воспользуюсь двумя списками. Потому что очередь мне изначально кажется неэффективной структурой. И в любом случае, буду стараться этого обхода избежать — дорого по памяти. Лучше поискать решение с рекурсией. Приведённая здесь задача — исключение, здесь списки строятся, как часть ответа.
И да, я буду писать обход дерева/графа/топологическую сортировку/поиск изоморфизма графов/метод главных компонент/интегрирование по непрямоугольной области/радикс-сортировку массива/etc, не подглядывая в Гугл. Потому что мне решение будет нужно не для общего случая, а для конкретной задачи, и дополнительные данные могут дать лучший вариант алгоритма. К тому же, возможно, что удастся склеить этот этап алгоритма с предыдущим или следующим и избавиться от затрат лишней памяти или от ненужных вычислений.
Боюсь, правда, что с таким подходом меня в Гугл не возьмут :)
tyomitch
09.02.2016 12:13не зная алгоритмов обхода бинарного дерева их практически невозможно придумать самому за 10 минут. Собственно, как и формулы мат. анализа и даже вещи гораздо проще. Если вы их не знаете, не изучали в школе или просто забыли, изобрести их самому невозможно.
Ну и на что годится кандидат, который элементарных вещей не знает, не изучал в школе, или просто забыл?
Шаблоны на вордпресс натягивать?splatt
09.02.2016 19:24+2Мне не очень понятен ваш сарказм про «шаблоны на вордпресс натягивать». Грамотно натягивать шаблоны на вордпресс — это тоже нужно уметь, это тоже работа, за которую, между прочим, платят неплохие деньги.
Не знаю, что вы называете «элементарными» вещами, но я из школьного/университетского курса математики помню только то, что мне в программировании приходилось использовать. А именно — логарифмы, производные, векторы, матрицы, триг. Все что выше этого (интегралы, дифференциальные уравнения) — как ветром сдуло. Что не отменяет того факта, что если мне будет нужно, я зайду в гугл и за пол часа — час вспомню, что там к чему.tyomitch
09.02.2016 19:44Мне не очень понятен ваш сарказм про «шаблоны на вордпресс натягивать». Грамотно натягивать шаблоны на вордпресс — это тоже нужно уметь, это тоже работа, за которую, между прочим, платят неплохие деньги.
В этом я не сомневаюсь.
Но топикстартера, очевидно, собеседовали не на такую работу.
Что не отменяет того факта, что если мне будет нужно, я зайду в гугл и за пол часа — час вспомню, что там к чему.
Топикстартер продемонстрировал, что гугл и два дня времени не помогут, если не знаешь, что искать.
tyomitch
09.02.2016 14:13Напомню ещё, что Ньютон — не самый глупый человек, наверное — написал: «Если я видел дальше других, то потому, что стоял на плечах гигантов.»
Черта умного человека — быть в курсе существующих достижений и уметь ими пользоваться, а не искать с нуля своё собственное решение.
vayho
09.02.2016 10:20> Если взять разработчика без соответствующих навыков, то он так и будет все складывать в последовательный массив, а потом удивляться отсутствию памяти и долгой работе. Поэтому человека, который начинает явно думать не так, как того требует окружающая среда компании, проще отсеять, чем переучивать.
Да нифига, как показывает практика программист посмотрит вокруг что и как и сделает как надо, почитает две три умных книжки, набьет пару шишек и все.
На самом деле эта задача вообще нифига не скажет вам о программисте кроме того что в данной конкретной ситуации он решить ее не смог(если не решил). Это очень очень очень плохое заблуждение когда мнение мгновенно составляют на основе этого конкретного случая на собеседовании. Причин по которым человек не решил задачу может быть миллион. Он плохо спал, для него это стресс, для него это непривычная задача и нужно перестраиваться и так далее и тому подобное.
И еще. А вы думали когда-нибудь что человек завалив подобную задачу на первом собеседовании спокойно решает ее на 15? На самом деле за 15 собеседований человек так натаскивается на такого рода задачи, что к 15 уже просто заходит в кабинет садится напротив собеседующего с видом: «Ну давай задавай мне эти свои вопросы про шарики в корзинах, горящие веревки и разворот односвязного списка». Короче я клоню к тому что часто вам решение задачи вообще ничего не скажет о человеке, и даже когда что-то скажет не факт что человек обладает глубокими знаниями а не набрался их за последние 5 собеседований. Ну а если он набрался глубоких знаний за последние 5 собеседований(например прочитал книгу) то вы большой идиот что упустили на первом собеседовании такого человека и нихрена эта ваша система набора не работает.khim
09.02.2016 17:52-2Да нифига, как показывает практика программист посмотрит вокруг что и как и сделает как надо, почитает две три умных книжки, набьет пару шишек и все.
Не всё. Всё — это если у вас острая нехватка кандидатов. А если их хватает, то зачем брать человека, который ещё не читал умных книжек и только лишь, возможно, прочитает их в будущем?
На самом деле эта задача вообще нифига не скажет вам о программисте кроме того что в данной конкретной ситуации он решить ее не смог(если не решил).
Это если давать её в таком виде, в каком тут многие предлагают: типа «иди куда хочешь, решай как хочешь». В противном случае можно смотреть как человек реагирует на подсказки и тому подобное.
Ну не нужны в больших компаниях loose canon'ы, которые могут сделать что-то гениальное, а могут — просидеть полгода и не родить ничего. Или, если и нужны, то ограниченных количества в отделе исследователей.
От рядовых разработчиков требуется не гениальность, а некоторые навыки плюс работа в комманде.
Ну а если он набрался глубоких знаний за последние 5 собеседований(например прочитал книгу) то вы большой идиот что упустили на первом собеседовании такого человека и нихрена эта ваша система набора не работает.
Ваши слова имели бы какой-то вес, если бы на одного кандидата «набравшегося глубоких знаний за последние 5 собеседований» не приходилось несколько десятков таких, которые и после сотни собеседований пышут негодованием и кричат «да, конечно, я могу… если только книжку почитаю… и если ещё на несколько собеседований схожу», а сами по прежнему не могут развернуть список и провязать дерево.
И вот как вы предлагаете отличать людей, которые реально прочитают книжку и научатся решать задачи от тех, которые так и будут завлять о том, что они «смогут, обязательно смогут… когда-нибудь… в параллельной вселенной… может быть… если повезёт — и по прежнему не будут даже понимать где налажали»?
То, что хорошего кандидата (да даже и дюжину хороших кандидатов) можно при таком подходе упустить — не проблема, главное, что плохих после такого отбора становится гораздо меньше.
Siper
08.02.2016 23:53+1Как и люди, компании бывают успешны в разной степени. Как уже выше упомянули, в некоторые компании подаются толпы желающих среди которых даже сильных кандидатов на порядок больше чем вакансий. Умение решать задачки помимо прочего это по сути приобретенный навык, сигнализирующий о том что кандидат реально фанат программирования, готовый убивать кучу личного времени чтобы во всем разобраться (список алгоритмов и методик известен).
Т.е. неумение их решать это впринципе ничем не хуже здорового нежелания работать по 60 часов в неделю, целыми днями ковыряться в легаси, и т.п. Не все готовы делать чтото нестандартное за полуторную зарплату, верхняя часть которой кромсается по самой мощной налоговой ставке.
yar3333
09.02.2016 06:29Ох уж эти собеседования! Лет эдак 10 назад давали мне решить тестовое задание: типично олимпиадная задача про распределение поездов в соответствии с расписаниями (или как-то так), но при этом мне намекнули, что важно, чтобы решение было красивым с точки зрения ООП. В итоге задачу решил не так, как хотели потенциальные работодатели, ибо здравый смысл во мне победил :) (Хотя, решение было, действительно, не идеальным.)
Singerofthefall
09.02.2016 09:17И что в итоге? Взяли/не взяли?
yar3333
09.02.2016 15:14Не взяли: нашли пару небольших, на мой взгляд, ошибок и отсутствие красивого ООП (который был в этой задаче не к месту), что по их мнению было фатальным. Одна из ошибок — неверные комментарии (!!!), которые отловились Решарпером.
skjame
09.02.2016 09:18+2У меня были 2 ситуации с подглядывающими нанимателями. Первый случай был с решением простой задачи на Си и меня прервали после того как я написал хедер 2й ( из где-то 6 ) функций ( первую функцию всё же написал ). И сказали, что всё ясно, знаешь — могёшь. Предложили написать теперь тоже самое только на ассемблере, я без лишних слов начал писать на нём, но меня опять остановили и сообщили мне о том, что это была просто шутка. Дальше было ещё пару задач, которые заканчивались или просто набросками псевдо кода, или блок схемой.
Второй же случай протекал абсолютно иначе… Задача была написать поиск в отсортированном массиве ( скукота вообщем ). Алгоритм настолько быстро поиска в таком массиве избит уже до безобразия, однако после пары строк( 8-10 ), меня прервали. Сказали, что я пишу неправильно и нужно переписать. Я выпал в полный осадок, ведь точно знал что пишу лучшее решение. Как оказалось от меня ждали пару if'ов начале поиска, для проверки крайних значений, мол будет намного быстрее.
Резюмирую: на первой фирме искали человека, который понимает как писать, а нюансы реализации оставили на рабочий процесс, ведь в IDE и с документацией однозначно удобнее, на второй же не дали даже прописать нормально функцию, которая по сути была правильная, из-за отсутствия пары строк, которые были самыми незначительными в поставленной задаче.
Наниматели, берите пример с тех с кого нужно, и выбирайте тщательно экзаменаторов.
redlinelm
09.02.2016 09:44+1А вот что у меня получилось на Python…
import itertools class Node: def __init__(self, d, l=None, r=None): self.data = d self.left = l self.right = r self.next = None def __str__(self): return 'Node: {} Next: {}'.format(self.data, self.next) def link_tree(tree_root): def link_layer(roots): items_layer = filter(None, itertools.chain(*[(root.left, root.right) for root in roots])) items_layer.append(None) for (cur, n) in zip(items_layer[:-1], items_layer[1:]): cur.next = n return items_layer[:-1] cur_roots = [Node(None, tree_root)] while cur_roots: cur_roots = link_layer(cur_roots) def prin_tree(root): if root: print root prin_tree(root.left) prin_tree(root.right) tree = Node(1, Node(2, Node(4)), Node(3, Node(6), Node(7))) link_tree(tree) prin_tree(tree)khim
09.02.2016 18:32Годится. Вот тут — уже можно обсуждать стиль, подходы (
link_layerвнутриlink_treeмногим не нравится, к примеру), но само понимание задачи — налицо. И даром, что язык не самый подходящий для обсуждения вопросов сложности и потребления памяти, их понимание у соискателя — явно имеется. Есть повод для дальнейших разговоров.
alexeiz
09.02.2016 10:42+3Вот такая интересная вещь: если ты на работе для решения какой либо задачи начал изобретать супер-пупер алгоритм, вместо того чтобы просто взять стандартный из книжки или простую вариацию на тему стандартного опять-же из книжки, то с тобой что-то явно не так. Практически на 100% твой супер-пупер алгоритм будет переусложнён, с кучей багов и алгоритмическая сложность у него будет плохая.
У меня на практике был пример, когда человек написал свой супер-алгоритм сортировки, а потом мы долго искали, где баг. А знал бы он, что можно сделать schwartzian transform, а потом тупо отсортировать стандартной функцией, пусть даже это будет не максимально оптимально, то никаких багов бы не было, и с алгоритмической сложностью всё нормально.
С моей точки зрения, на интервью надо давать задачи приближенные к реальности с прицелом на алгоритмы. И если человек начал на интервью изобретать алгоритм, чтобы решить задачу, то бац — red flag. А если он говорит, что тут мы применим такой и такой стандартный алгоритм, то это наш человек — знает и умеет решать задачи на практике.
За многолетний опыт профессионального программирования реально приходилось думать над нестандартными алгоритмами штучное количество раз. И то потом получалось, что легче и надёжнее применить комбинацию стандартных алгоритмов.
shuron
09.02.2016 11:15-4Да в том то и дело что нафиг вам в такой компании работать…
Я также лет 10 назад проходил собоседование, ко мне докопались с английским, так как в школе у меня был немецкий…
Реально за 6 лет рыботы в этом концерне мне мой английский потом (который в полне на уровне) нафиг не пригодился…
И когда он мне пару рз понадобился в разговоре с килентом, то проблема была не во мен ав клиенте, который хреного говорил по английски…
И так всю дорогу… Компабния часто решала несуществующие проблемы, а существующие игнорировала.
IL_Agent
09.02.2016 11:50Рефлекторно попробовал решить :)
void ConnectNeighbors(Node[] neighbors) { while(neighbors.Any()) { for(int i=0; i< neighbors.Length-1; ++i) neighbors[i].Neighbor = neighbors[i+1]; neighbors = neighbors .SelectMany(n=>new []{n.Left, n.Right}) .Where(n=>n!=null) .ToArray(); } }
vba
09.02.2016 13:09Так и было, в блокнотик скопировали ASCII-арт сначала без указателей а потом с ними.
RobotVzryvatelMin
09.02.2016 14:09-2Не читал все комментарии — времени нет. Но из случайно прочитанных 20 уяснил, что никто не представляет, что реальный problem solving skill, ожидаемый руководителем, это фраза: я буду решать задачу в любимом IDE на любимом языке, а потом, если это реально вам нужно, спортирую на псевдоязык. Все это время стойте у меня за спиной, раз вам это нужно, но молчите — вы мне мешаете, а никакой своей задачи при этом не выполняете (наблюдение, очевидно, выполняет важную задачу).
khim
09.02.2016 18:38Интересно — где это подобные руководители встречатся? Подобного рода замашки прощаются, да — но только если ваш стартап имеет «за душой» хотя бы пару миллионов пользователей. Если же вы устраиваетесь как наёмный работник — то нет, такой вариант принят не будет.
Flammar
09.02.2016 14:12Ну раз был разговор про «псевдоязыки» и «решение на пальцах», то (не претендуя на оригинальность)…
А) «На пальцах»:
1) сопоставить каждому узлу его «путь» типа «LRLLLRR» или «0100011»
2) написать компаратор для «путей», который бы сравнивал сначала длину «пути», потом «праволевость» его ветвей
3) рекурсивно залить дерево с путями в массив/«вектор»
4) отсортировать массив по «путям» с использованием компаратора из (2)
5) проставить связь между узлами согласно содержанию массива/«вектора»
Б) Рекурсивно на псевдоязыке (ну раз уж можно совсем «псевдо»...):
Node.{ leftmost = left || right isLeft = parent.left == this neighbor lazy = parent ?. (( this.isLeft ? rigth : Nil) || neighbor ?. leftmost ) || Nil } nextItem(Node) = _ . ( leftmost || neighbor || parent) for(var item = root; item; item = nextItem(item));
Itachi261092
09.02.2016 17:48Я тут один, кто практически ничего не понял ни в условии ни в решении? =/
Drazd
09.02.2016 18:51-1Данная ситуация в общем нормальная. Как писали выше — на обычных собеседованиях дается ручка, бумажка — и решай. Никаких IDE, никаких синтаксических проверок, интеллисенса, итд. Да и главное не столько совсем правильность кода, сколько уменее решить задачу, понять алгоритм. Данная автору задача, например, решается обычной рекурсией с использованием дописываемого метода к классу.
Ключевая ошибка автора заключается в сказанной им же фразе:
Оригинал кода задания был сделан на псевдо C#, но я предпочитаю javascript.
Честно признаюсь — лично я не особый специалист в javascript, но зато в C# все решается на раз. Хотя, думаю, можно было написать примерно и те, кто проводил интервью — приняли бы задание. А решение простое. Примерно так:
class Node { int data; Node left; Node right; Node neighbour; public Node (int data) { this.data = data; left = null; right = null; neighbour = null;} public Node CreateLeft (int data) { var newNode = new Node(data); this.left = newNode; return newNode;} public Node CreateRight (int data) { var newNode = new Node(data); this.right = newNode; return newNode;} public int ConnectAllNeighbours() { int links = 0; if (left != null && right != null) { left.neighbour = right; links++; } if (left != null) links += left.ConnectAllNeighbours(); if (right != null) links += right.ConnectAllNeighbours(); return links; } }
*Для чистоты эксперимента код был написан на чистую полностью в окне комментария хабра, не компилировал, но в общем должно работать. Думал над решением — минуту, писал около двух. При аналогичном собеседовании написал такое же решение.Mrrl
09.02.2016 19:02+1К сожалению, этот код не свяжет left.right с right.left. А по условию, должен.
Drazd
09.02.2016 19:13+1Давайте разберемся со схемой и сопоставим ее с написанным выше. Возьмем начало дерева:
1-> Nil
/ \
2-> 3-> Nil
Здесь у нас корень — элемент №1. У него есть два ответвления — левое и правое. Они завязаны к корню, но не между собой (изначально).
У каждого элемента есть один сосед, который указывается на схеме как «находится справа». По логике моего кода будет такой процесс:
1) Создается элемент 1
2) Для элемента 1 создается и привязывается как левый элемент 2
3) Для элемента 1 создается и привязывается как правый элемент 3
4) Элемент 1 знает, что для левого элемента 2 элемент 3 является соседом и он проставляет эту связку.
Но, в любом случае, это собеседование, а не конкурс «реши за одну попытку». Тут так и принято — ты даешь свое видение решения, как ты понял постановку, далее интервьювер смотрит, оценивает и, если надо, вносит корректировки в задачу \ поясняет те моменты задания, которые ты понял не так. Мне встречались такие варианты, когда задача решалась сразу верно, но работодатель дополнял задание. Делается это специально — посмотреть сможет ли кандидат поменять программу так, чтобы она работала по новому (иногда вносятся такие корректировки, которые вынуждают менять чуть ли не на корню алгоритмы). Это нормально.
Это и есть та самая способность решать проблемы. Они встречаются в продуктиве много где. Есть множество систем, которые разрабатывались 10 лет назад и не подходят для настоящих реалий — их надо переделывать по новому так, чтобы не терялся изначальный функционал… А если кандидат не в состоянии поменять свою же программу, которую написал полчаса назад — это никуда не годится.khim
09.02.2016 19:34Вот тут как раз очень хорошо видно почему важно писать код (как я уже говорил).
Слова вы все правильные произносите. Всё просто супер, закачаисся.
Но.
В условии, в качестве примера, было приведено конкретное дерево:
1
/ \
2 3
/ / \
4 6 7
Которое должно быть конкретно преобразовано в конкретно другое дерево:
1
/ \
2>3
/ / \
4>6>7
Так вот я не понимаю: где и когда в вашем решении возникает связь между узлами 4 и 6. О каком «понимании» и «уточнении формулировок» может идти речь если ваше решение сразу на том примере, которым иллюстрировалась исходное задание не работает?
Кандидат, который такое напишет, посмотрит, поводит пальчиком и начнёт «копать глубжее» — это вполне себе ничего кандидат, но кандидат, который прямо такой сразу отдаст… я даже не знаю что сказать…
0serg
09.02.2016 19:08Это решение не соединит вершины 4 и 6 в исходном примере, плюс даже в исправленном виде оно потребует O(n) памяти в худшем случае (причем на стеке), а как указали вверху, есть лучшее решение требующее лишь O(1) по памяти :).
khim
09.02.2016 19:36То, что решение займёт O(n) памяти может быть страшно или не страшно. В любом случае — это не критично (хотя, конечно, повод для обсуждения). А вот то, что вершины 4 и 6 не соединены — это уже очень плохо. Таких ляпов хороший кандидат оставлять не должен (сам посадил, сам исправил — это нормально, главное, чтобы это не осталось на долю интервьюера).
GlukKazan
Оба голосования неполны (и потому предвзяты). Отсутствует пункт «определяется спецификой выполняемой работы». IMHO, разумеется.
Обида конечно понятна, но возможно действительно искали человека, способного решать такие задачи без любимой IDE.
jmaks13
А мне вот интересно, какая работа предполагает такое требование, плюс стрессовые ситуации?
GlukKazan
Детали рассказывать не буду, но на одном проекте пришлось на JS писать скрипты для настройки оборудования Cisco.
Из инструментов, по большому счёту, был блокнот.
GlukKazan
Кстати, процесс «собеседования» на этот проект был тоже… своеобразный
jmaks13
Было бы интересно прочитать об этом
GlukKazan
Не могу, к сожалению
jmaks13
Но при этом за Вами же не следили, как вы пишете код? В добавок написание настроек это больше рутинная задача.
GlukKazan
Ох, поверьте, рутины там было мало. Вся работа — одно сплошное приключение, растянувшееся на год.
На собеседовании, не то чтобы следили. Общались очень плотно.
Flammar
GlukKazan
Из соображений глубокой костыльности. Не было там стандартных решений (именно по этому направлению).
Нельзя было, например, отладить код в какой либо IDE. Задача не позволяла.
Flammar
Интересно, почему всё же нельзя было поставить IDE, поддерживающую JS, или, в крайнем случае, Notepad++? Запрещалось ставить сторонний софт? Платформа была не Windows/i386 и вообще не i386? Не было физической возможности закачать на диск инсталлятор (или уже развёрнутую программу, если она не требовала инсталляции)? Почему нельзя было перенести скрипт на более удобную машину, там отредактировать, а потом перенести обратно?
GlukKazan
Ставить можно было что угодно. В работе это не помогало. Notepad++ отдельные товарищи пользовали, я не любитель.
Просто задачка не очень традиционная. Не Web. Сложно объяснить не вдаваясь в детали. Всё было завязано на сторонний фреймворк.
Наверное можно было написать обвязку для отладки этого всего под IDE, но времени на эксперименты не было.
khim
Давайте я про свой случай расскажу, что ли. Исходники лежат в папке [условно]
/src, куда смонтрирована кластерная файловая система, сколько тех исходников знает только Господь Бог и сисадмин (известно только что терабайтов там много, но петабайт, вроде как, пока нету). Как несложно догадаться никакого Windows/i386 нет и не планируется, собирается всё командой, условно,build(тоже где-то в облаке), общаться с программой можно через встроенный в неё web-сервер (сама программа при этом работает, опять-таки, в облаке — там где её поднимет условная командаrun). Не так давно думали что делать с тем, что в кое-каких системах упёрлись в старое древнее ограничение в 2GiB кода в одной библиотеке под Linux'ом.Ваши действия? С какой стороны прикручивать IDE? И как она вам поможет отлаживать код?
P.S. Кстати какое-то количество разработчиков у нас использует IDE. Eclipse, IDEA, CLion. Не могу сказать, что кода от них поступает заметно больше, чем от других.
pavelsh
«Настройки оборудования Cisco» звучит страшно. На самом деле вещь очень простая — текст.
Я думаю что 90 процентов цисковиков настройки циско в блокноте пишут и не жужжат.
Используя perl или python для разворачивания шаблонов.
В итоге — не убедили. Не нужны эти скилзы.
GlukKazan
Я как бы и не стремился Вас убеждать. Меня попросили пример — я дал (настолько подробно насколько мог). Верить или нет — ваше дело. Разумеется, сложность была не в Cisco (я вообще не цискарь). Просто конкретно в этой работе IDE не помогало никак. И да, все пользовались блокнотом и не жужжали.
Gray_Wolf
Стрессовые ли?
Сидя дома за своим компьютером, а не добираясь до офиса компании в людном метро или пробираясь через пробки на машине…
mirrr
Мне вот не совсем понятно, почему данная ситуация считается стрессовой? То, что для автора она была таковой, вовсе не значит, что собеседник этого и добивался. Мне даже кажется, что он давал подсказки, чтобы разрядить ситуацию и помочь. И возможно ждал бы решения еще полчаса, если бы автор попросту не сдался.
А само решение задач не должно зависеть от IDE или блокнота. Если в голове есть представление алгоритма, то описать его псевдокодом или js не должно составлять труда. Разве-что без IDE и autocomplete программист не помнит языковых конструкций, ну это не делает ему чести.
jmaks13
1. Отсутствие привычной среды разработки. Автора вывели из зоны комфорта, заставив писать не в любимой IDE.
2. Работа под присмотром. В комментариях ниже очень красочно описали, каково это
habrahabr.ru/post/276673/#comment_8764473
habrahabr.ru/post/276673/#comment_8764489
3. Академическая задача. Когда на собеседовании предлагают решать задачу не из списка часто практикуемых, то это тоже может выбить из колеи.
Gray_Wolf
1. На большинстве собеседований у кандидата на должность есть только листок и ручка и это стандартная практика, а не вывод из зоны комфорта.
2. Опять-же более чем стандартная практика для любого собеседования.
3. Во время работы задача не из списка часто практикуемых как мне кажется норма, если уж человек не является очень уж узким специалистом.
А вообще как мне кажется если бы человек вместо того чтобы сразу начать писать код в дискомфортной для него ситуации предложил бы начать с наброска блок-схемы решения ему врядли бы отказали и это сильно бы упростило процесс.
jmaks13
Я согласен с Вами, что это обычная практика, я просто отвечал на вопрос: почему данная ситуация считается стрессовой?
YChebotaev
Ох уж эти «стандартные практики». Не счесть сколько неимоверных глупостей я слышал перед этой формулой. В итоге, собеседования проходят не те, кто лучше остальных соискателей, а те, кто либо больше других прошел собеседований, либо еще совсем не опытный и не понимает всей серьезности ситуации: первое свое (очень суровое) собеседование я прошел без запинки, а вот на последующих уже заметно волновался, хотя и профессиональные навыки были, разумеется, уже выше.
Gray_Wolf
Я даже на первом собеседовании довольно сильно волновался.
То что проф. навыки были выше помогло бы избежать волнения только в случае если бы вы собеседовались на туже должность что и раньше, а не выше.
Я говорю о том что какую бы глупость вы не увидели на собеседовании это не повод спадать в ступор из-за волнения, тем более если эта глупость считается нормой для 90% собеседований. Вот если бы он рассказывал о чём-то совершенно неожиданном (заставили бы его писать на А4 листе перьевой ручкой) это было бы вполне понятный повод для волнения.
YChebotaev
Есть навыки, полезные при программировании и есть навыки, полезные при прохождении собеседований. Если человек часто программирует, то он развивает одни навыки, а если часто проходит собеседования, то совсем другие.
Тут я имел в виду эффект «второго прыжка»: прыгать с парашютом по-настоящему страшно во второй раз, а не в первый.
Про стандартные практики — это не столько по поводу собеседований, сколько вообще в целом, я неоднократно видел ужасные вещи, которые оправдываются тем что «ну а че, все так делают».
Есть весьма веские аргументы в пользу того, что «стандартные практики» при приеме на работу, о которых идет речь, попросту неэффективны.
pavelsh
Обычная практика — ведь не означает — хорошая практика, так ведь?
khim
По умолчанию — означает. То есть обычная практика может быть и плохой (тогда она заменяется на другую «обычную практику»), но «по умолчанию» — она считается хорошей.
vba
Согласен с вам насчет проверки синтаксиса в IDE. Например в моем случае я его использую как, своего рода, REPL, в режиме отладки. Я не считаю что это обязательно, но согласитесь, как же это удобно.
khim
Кроме того в C# (как и в Java, как и в C++) очередь — есть. В JavaScript — нет. Это — тоже грабли, которые соикатель себе подложил сам.
А как ешё должно выглядеть собеседование? Дать элементарную задачу, посмотреть что получится… как иначе-то?
Aracon
Вообще говоря, и очередь написать не должно составлять проблемы, так что есть она в фреймворке или нет — неважно. Как минимум можно сделать просто массив, пояснив интервьюеру недостатки такого подхода и какие есть более эффективные варианты.
khim
Дык можно и интерпертатор x86 на CSS при желании изобразить! Дело-то не в этом.
Дело просто в том, что «писатели фронтэндов» вообще не думают в терминах очередей, стеков, деревьев. Вот пример. Они даже не осознают, что DOM-дерево — оно таки тоже дерево и при работе с ним могут возникать типичные задачи, связанные с деревьями!
Ну и куда девать такого человека в компании, где на 100 строк кода на «фронтэнде» приходится 10'000 строк на «бэкенде»? Знание JavaScript'а при этом не помешает («бэкенд» тоже может JavaScript использовать… особенно если это, скажем, код для поддержи offine-работы в браузере), но куда ж тут без понимания очередей?
funnybanana
Работа без любимой IDE — уже стрессовая ситуация =)
khim
А кто вам сказал, что у вас будет возможность использовать вашу любимую IDE в будущем? Нет, специально никто палки в колёса вставлять не будет, но если, скажем, проект собирается только под MacOS, то вашу «любимую IDE» может оказаться затруднительно использовать. Бонус — за проект, который собирается тремя системами сборки, две из которых работает под MacOS и две — под Linux (это я не из пальца высысываю, это реальный пример, с которым мы работали пару лет назад).
Если вы без «любимой IDE» 20 строк написать не можете, то может вам и не стоит в подобную компанию собеседоваться?
Fesor
Как же легко вас можно в стресс вогнать. Берегите нервы.
vba
Все кто про стресс говорит, вы статью читали? У меня не нервы сдали и не стресс был, а была ситуация где я выпал из колеи привычного мыслительного процесса из-за того что слишком много внешних факторов изменились. Термины впасть ступор, got stuck, freeze the brain имеют мало общего со стрессом. Почему было такое окружение, по моим догадкам испытание на стрессо-устойчивость, хотя может мне показалось. Статья кстати не обо мне и о том какой я бедный и несчастный. На мой взгляд я поднял несколько важных вопросов такой статьей, хотя я могу ошибаться.