Примечание переводчика: В наших блогах на Хабре и Мегамозге мы много пишем о построении облачного сервиса 1cloud, опыте по работе с инфраструктурой различных компаний и перспективных подходах к управлению ИТ-проектами.
Сегодня мы представляем вашему вниманию адаптированный перевод заметки Реджинальда Брэтуэйта (Reginald Braithwaite) из компании Pager Duty. Он написал в своем блоге материал о том, как несложные задачки на собеседованиях могут помогать находить хороших программистов, и как разработчикам следует к ним относиться.
Fizzbuzz-задачки
Часто на собеседованиях на должность разработчика кандидатам дают решить несложные задачки, позволяющие оценить навыки программирования. Их часто называют fizz buzz-задачками и вся их суть сводится к отфильтровыванию тех, кто вообще не умеет программировать.
Вот пример такой задачки, который может быть использован в ходе телефонного интервью или беседы с эйчаром на первом уровне.
Напишите функцию merge, которая обрабатывает два сортированных списка и выдает сортированный список объединений элементов двух списков.
К примеру:
merge ([1, 7, 11, 17], [3, 5, 13]) //=> [1, 3, 5, 7, 11, 13, 17] merge([2, 3, 5, 7, 11], [2, 4, 6, 8, 10, 12, 14]) //=> [2, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 14] Если использовать язык с удобной семантикой для работы со списками и особенно не задумываться об использовании памяти и общей производительности, то код решения будет простым:
function merge (originalA, originalB) { const merged = [], tempA = originalA.slice(0), tempB = originalB.slice(0); while (tempA.length > 0 && tempB.length > 0) { merged.push( tempA[0] < tempB[0] ? tempA.shift() : tempB.shift() ); } return merged.concat(tempA).concat(tempB); } Популярными проблемами в подобной ситуации являются ситуации, когда, к примеру, оба списка пусты или содержат лишь один элемент. Такой код хорош тем, что в ходе дальнейшей беседы на интервью можно обсудить минусы предложенной реализации и возможные пути ее оптимизации.
Больше сложности
Иногда после первой легкой задачки интервьюер решает несколько усложнить ситуацию. В то время как первый этап должен был отсеять тех людей, которые вообще не должны были попасть на интервью, второй уже фокусируется на проверке навыков решения проблем.
В ходе таких «фоллоу-ап» обсуждений уже возникают дополнительные элементы, с которыми нужно разобраться. Они не должны быть легкими или очень сложным, просто проблемы, решение которых можно придумать, поразмышляв некоторое время. К примеру:
Напишите функцию, которая обрабатывает произвольное число упорядоченных потоков элементов и выдает упорядоченный поток, содержащий объединение элементов каждого потока.
Напишем код
В ECMAScript 2015 можно представить потоки, которые необходимо объединить, в качестве итераблов (Iterables). Мы напишем генератор, то есть функцию, которая создает значения. Генератор будет брать итерируемые элементы в качестве аргументов, и генерировать значения в корректном порядке.
Скелет кода может выглядеть так:
function * merge (...iterables) { // обработка while (our_iterables_are_not_done) { // найти итератор с наименьшим значением yield lowestIterator.next().value; } } Первая проблема заключается в обработке более чем двух итераблов. Вторая — для итерации итераблов, их нужно превратить в итератор. Тут все довольно просто — у каждого итерабла есть метод Symbol.iterator, который возвращает новый итератор для этого итерабла.
function * merge (...iterables) { const iterators = iterables.map( i => i[Symbol.iterator]() ); while (our_iterables_are_not_done) { // найти итератор с наименьшим значением yield lowestIterator.next().value; } } Третья проблема посложнее: для того, чтобы выяснить, сколько значений может вернуть итератор (одно или больше) мы вызываем .next(). Но его использование удаляет значение и меняет состояние итератора.
Если мы напишем:
while (iterators.some(i => !i.next().done)) То первый элемент каждого итератора будет выделен и отвергнут. И это проблема. Нам нужен «магический итератор». Который позволит взбираться на следующий элемент, оставляя возможность использовать его позднее.
Так что придется написать класс адаптора итератора:
const _iterator = Symbol('iterator'); const _peeked = Symbol('peeked'); class PeekableIterator { constructor (iterator) { this[_iterator] = iterator; this[_peeked] = iterator.next(); } peek () { return this[_peeked]; } next () { const returnValue = this[_peeked]; this[_peeked] = this[_iterator].next(); return returnValue; } } Класс PeekableIterator «оборачивается» вокруг существующего итератора, и в дополнение к методу next, создает метод peek, который не изменяет итератор.
Теперь можно использовать PeekableIterator вместо чистых итераторов:
function * merge (...iterables) { const iterators = iterables.map( i => new PeekableIterator(i[Symbol.iterator]()) ); while (iterators.some(i => !i.peek().done)) { // найти итератор с наименьшим значением yield lowestIterator.next().value; } } Метод peek можно использовать и для поиска итератора с наименьшим значением. В таком случае мы возмьем итераторы, отфильтруем уже отработанные, отсортируем их по значению peek — первый итератор в списке будет иметь наименьшее значение:
function * merge (...iterables) { const iterators = iterables.map( i => new PeekableIterator(i[Symbol.iterator]()) ); while (iterators.some(i => !i.peek().done)) { const lowestIterator = iterators .filter( i => !i.peek().done ).sort( (a, b) => a.peek().value - b.peek().value )[0]; yield lowestIterator.next().value; } }
Полное решение
const _iterator = Symbol('iterator'); const _peeked = Symbol('peeked'); class PeekableIterator { constructor (iterator) { this[_iterator] = iterator; this[_peeked] = iterator.next(); } peek () { return this[_peeked]; } next () { const returnValue = this[_peeked]; this[_peeked] = this[_iterator].next(); return returnValue; } } function * merge (...iterables) { const iterators = iterables.map( i => new PeekableIterator(i[Symbol.iterator]()) ); while (iterators.some(i => !i.peek().done)) { const lowestIterator = iterators .filter( i => !i.peek().done ).sort( (a, b) => a.peek().value - b.peek().value )[0]; yield lowestIterator.next().value; } } Для программистов, умеющих работать с итераторами и генераторами, здесь нет ничего сложного. Поскольку наша функция merge — это генератор, то мы можем легко итерировать ее содержимое для распределения элементов в массив. В принципе, реализация может заменять даже решение для массивом, нужно просто не забыть распределить результаты:
const primes = [2, 3, 5, 7, 11]; const evens = function * () { for (let n of [1, 2, 3, 4, 5, 6, 7]) { yield n * 2; } } for (let value of merge(primes, evens())) { console.log(value); } //=> 2 2 3 4 5 6 7 8 10 11 12 14 [...merge(primes, evens())] //=> [2, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 14] Из плюсов здесь также наличие возможностей для дальнейшего обсуждения. Например, можно поговорить о следующих вещах:
- Как наличие большого количества итераблов (сотни или тысячи) может повлиять на производительность?
- Что произойдет, если у вас есть итерабл, который производит тысячи значений, а остальные производят не больше нескольких сотен? Проще говоря, что если существет обратная степенная зависимость между количеством итераблов и числом производимых ими значений?
В качестве упражнения можно подумать, какие еще вопросы можно было бы задать кандидату, который написал представленный выше код за отведенные ему 40 минут.
А что, если я ненавижу такие паззлы?
Да, опытный кандидат, увидев подобную задачку может закатить глаза — это же «непрактичное программирование». Но является ли этот факт достаточным основанием для отказа от fizz-buzz задач на собеседованиях?
Тут можно пойти другим путем, и просто обернуть задачу в некую историю. Например:
Вы работаете в компании, которая занимается обработкой оповещений и реагированием на инциденты. У вас есть большой, распределенный кластер серверов, каждый из которых генерирует огромное количество событий, привязанных к id клиента, типу, времени и другим параметрам. Вы ищите определенные паттерны событий. Напишите функцию, которая создает алерт, когда видит, что определенный тип событий возникает в рамках заданного временного промежутка.
Здесь нужно будет поместить все алерты для определенного клиентского идентификатора в поток, упорядочив его по времени. Затем мы создаем поток событий, который объединяет потоки с разных серверов. Затем уже можно написать код для поиска паттернов событий, который будет обрабатывать общий поток.
Может в JavaScript это и не получится, а ECMAScript будет не единственным инструментом, с помощью которого можно решить проблему. Но все равно у нас будет некий код, который объединяет потоки и демонстрирует, что его автор понимает работу подобных алгоритмов — а это уже относится к навыкам, которые нужны в практической работе.
Заключение
Программирование на собеседованиях останется распространенной практикой еще долгое время. И покуда дела обстоят таким образом, инженеры, находящиеся в поиске работы, должны уметь писать код в режиме реального времени, а работодатели должны давать им решать задачи, которые определенным образом связаны с будущими рабочими обязанностями.
Поэтому, когда на интервью встречается проблема «из ряда вон», разработчик имеет полное право спросить: «Хорошо, если я решу задачу, а затем вы меня наймете, то когда я смогу начать работать над алгоритмами вроде этого?»
И есть вероятность, что ответ разработчика приятно удивит.
P.S. Мы в 1cloud считаем, что инженеры должны с самого начала иметь возможность понять, задачи какого уровня им предстоит решать в работе. В том числе поэтому мы подробно рассказываем о построении инфраструктуры нашего проекта в блоге на Хабре (список таких топиков представлен в конце этого материала).
В случае же разработчиков, идея Реджинальда Брэтуэйта о том, что нужно давать не абстрактную задачу, а привязывать ее к некоему реальному рабочему сценарию выглядит хорошим инструментом, который позволяет избежать недопонимания между работодателем и инженером.
ссылка на оригинал статьи http://habrahabr.ru/post/271351/
Добавить комментарий