[Перевод] Программирование на собеседованиях: Какие задачки следует давать разработчикам

Примечание переводчика: В наших блогах на Хабре и Мегамозге мы много пишем о построении облачного сервиса 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 считаем, что инженеры должны с самого начала иметь возможность понять, задачи какого уровня им предстоит решать в работе. В том числе поэтому мы подробно рассказываем о построении инфраструктуры нашего проекта в блоге на Хабре (список таких топиков представлен в конце этого материала).

В случае же разработчиков, идея Реджинальда Брэтуэйта о том, что нужно давать не абстрактную задачу, а привязывать ее к некоему реальному рабочему сценарию выглядит хорошим инструментом, который позволяет избежать недопонимания между работодателем и инженером.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.