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

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

Комментарии (100)


  1. Suvitruf
    20.11.2015 19:16

    а работодатели должны давать им решать задачи, которые определенным образом связаны с будущими рабочими обязанностями

    Но в тоже время:
    Если использовать язык с удобной семантикой для работы со списками и особенно не задумываться об использовании памяти и общей производительности, то код решения будет простым

    То есть, придя на собеседование по Java вакансии, я могу реализовать тестовые задания, скажем, на питоне? Только не надо говорить, что «не важно на каком языке вы будете выполнять тестовое задание, ведь оцениваются общие способности программиста без привязка к конкретному языку».


    1. SkidanovAlex
      20.11.2015 20:58

      Но ведь «не важно на каком языке вы будете выполнять тестовое задание, ведь оцениваются общие способности программиста без привязка к конкретному языку»


      1. Suvitruf
        20.11.2015 21:18

        Если я ищу Java-разработчика, то буду слегка в недоумении, если кандидат будет решать тестовое задание на чём-то другом.


        1. SkidanovAlex
          20.11.2015 21:30

          Наше основное разногласие здесь в том, разумно ли искать <язык программирования>-разработчика вообще.
          Мое мнение, что это хорошая краткосрочная инвестиция, потому что человек быстрее начнет быть полезным, но это также сильно сужает круг потенциальных кандидатов, что должно ожидаемо уменьшить качество в долгосрочной перспективе.
          Но это все субъективно и без статистики, я могу представить как противоположная моей точка зрения может быть разумной.


          1. Suvitruf
            20.11.2015 21:35

            Просто в моём текущем проекте у нас нет возможности брать разработчиков на вырост, посему ищутся люди, которые смогут сразу же работать с тем, что у нас есть, так как сроки не резиновые.

            Поэтому при ответе я отталкивался от этого опыта.


    1. billyevans
      21.11.2015 00:44

      По-моему это вполне нормальная практика. Я сам прошел собеседование год назад на питон-разработчика, задачи решая на С++.


  1. musuk
    20.11.2015 20:02

    Не вижу проблемы в таких задачках. Главное, чтобы защиталось такое решение:

    var listA = new List<int>() {1,2,3};
    var listB = new List<int>() {3,2,1};
    var listC = listA.Concat(listB).OrderBy(x => x).ToList();          
    


    1. Lol4t0
      20.11.2015 20:14

      Главное, чтобы защиталось такое решение:

      from heapq import merge
      


  1. Mrrl
    20.11.2015 20:18

    Эээ… И что, решение, в котором минимум ищется, как нулевой элемент результата сортировки будет хоть как-то засчитано? Я понимаю, что можно не сразу вспомнить о приоритетной очереди для выбора очередного минимума. Но чтобы так?


    1. Fury
      20.11.2015 22:27

      Тоже удивлён, что про хип, который просто просится сюда, ни слова, как впрочем и про оценку сложности алгоритма.


  1. BalinTomsk
    20.11.2015 21:16

    ---Программирование на собеседованиях останется распространенной практикой еще долгое время

    В последнюю компанию где я сейчас работаю (большая международная корпорация) я не написал ни одной строчки кода, просто побеседовал часик с менеджером.

    Чем больше компания тем меньше у них требования к написанию кода.

    Чем меньше компания и дурнее менеджеры тем мозгопарюшие у них задачи.


  1. NightmareZ
    20.11.2015 21:54

    Проработав программистом десяток лет в разных компаниях, стал склоняться к мнению, что задачки на собеседованиях вообще не нужны и являются неуважением ко мне к нанимаемому человеку.

    Чего прицепились? Изучите мою гитхаб репу.


    1. noder
      20.11.2015 23:17

      А что если у разработчика нет активности в открытых проектах? Отсутствие проектов на гитхабе ни как не говорит о несостоятельности разработчика.


      1. NightmareZ
        21.11.2015 00:28

        А если у человека нет телефона, то как ему позвонить? А если нет языка или он глухой, то как с ним разоваривать? И ведь эти досадные недоразумения не говорят о несостоятельности его как разработчика.

        Ну в самом деле. Я вам говорю, как стоит делать в общем случае, а вы мне в качестве контраргумента приводите частный.


        1. Rasifiel
          21.11.2015 01:40

          Т.е. вы считаете, что случай когда у человека есть активность в публичном репозитории это единственно нормальный вариант? У меня, вот, нет ни строчки кода в публичном репозитории и меня почему-то взяли на нормальную работу. А так же у большинства нанимаемых разработчиков.


          1. NightmareZ
            21.11.2015 02:33

            Я считаю, что в настоящее время это очень популярный вариант. А вот когда публичного репозитория нет — это, скорее, исключение из правил.


            1. Rasifiel
              21.11.2015 02:53

              Мне кажется, что ваше представление о норме ошибочно. Но все равно статистики нет и ее надо собирать для того, чтобы что-то утверждать.


            1. leremin
              21.11.2015 13:34

              Например, у меня. Учитывая место, где я работаю — мои проекты никогда не будут в публичном доступе. Правда, большая часть кода, разумеется, ничего интересного не содержит и не выдаст область применения. Но такой порядок.


              1. NightmareZ
                21.11.2015 13:54

                У вас нет pet-проектов? Как так?


                1. Rasifiel
                  21.11.2015 14:08

                  Зачем мне заводить pet проекты если я на работе занимаюсь тем, что мне интересно?


    1. Rasifiel
      20.11.2015 23:22

      В репе нет динамики того как ты решаешь задачу и думаешь


      1. Lol4t0
        20.11.2015 23:28

        Как это нет — а история коммитов?


        1. Rasifiel
          20.11.2015 23:30

          Коммит это уже решение какой-то задачи. Особенно учитывая любовь к rebase и чистке истории ничего о том как решалась задача не остается.


          1. Lol4t0
            20.11.2015 23:41

            Не встречал, если честно, большой любви к rebase. Если коммиты небольшие, то по ним как легко проследить ход решения на макроуровне, так и оценить скорость решения задач по частоте коммитов. (А делать большие коммиты непраивльно, и кандидат просто получает минус в карму) На микроуровне проследить действительно не получится, но оно нужно? (С учетом того, что решение и временные затраты понятны)?


      1. NightmareZ
        21.11.2015 00:23

        Да хоть выбираю решение путём голосования тараканов в моей голове! Кому какое дело, если задача решена и решена корректно? А это видно как раз в репе.


        1. Rasifiel
          21.11.2015 01:35

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


          1. NightmareZ
            21.11.2015 02:39

            И то, как я контактирую с людьми, и «множество других нюансов» можно посмотреть только на испытательном сроке, но никак не на собеседовании.

            А при решении задачи я ни с кем не контактирую, я занят решением задачи.


            1. Rasifiel
              21.11.2015 03:00

              Это вы считаете, что нельзя ничего посмотреть. Работодатель вполне себе наблюдает.
              Вот вам дают условия задачи и вы сразу садитесь и начинаете делать что-то? Не уточняете условия, не проясняете что от вас хотят и не планируете?


              1. Suvitruf
                21.11.2015 05:07

                Если задача чётко поставлена, зачем что-то уточнять?


                1. Rasifiel
                  21.11.2015 05:14

                  Для проверки взаимопонимания, для проверки того, что говорят используя одно и то же понимание термина, для того, чтобы банально не ослышаться. Для того, чтобы после не выяснилось, что решалась совсем другая задач.
                  Да и кто сказал, что дадут идеально сформулированые условия? Это же тоже проверяемые навыки — как человек воспринимает постановку задачи, видит ли он слабости или неопределенные умолчания.


                  1. Suvitruf
                    21.11.2015 05:17

                    Вы всё ссылаетесь на социальный аспект. Я когда выполняю/ставлю задачи, стараюсь почти не общаться с людьми. Есть система тикетов/вики, человек всегда может там спросить. А вербальное общение многим приносит дискомфорт.


                    1. Rasifiel
                      21.11.2015 05:31

                      Это не социальный аспект. В том же самом тикете могут написать такую же не идеально сформулированную задачу. И точно так же надо уточнить, задать дополнительные вопросы и т.д.


                1. Mrrl
                  21.11.2015 05:22

                  Например, хотят ли они, чтобы код был
                  — быстро написан
                  — красив
                  — понятен
                  — устойчив к некорректным входным данным
                  — эффективно работал
                  — экономно расходовал память.
                  Разные ответы или приоритеты этих параметров могут потребовать очень разного кода.
                  И ещё полезно узнать диапазон входных данных — а вдруг они хотят, чтобы программа считала числа Фибоначчи до номера 10^9?


                  1. Suvitruf
                    21.11.2015 05:24

                    Такие вещи мы обычном в тикете описываем, чтоб по 100 раз к ним не возвращаться.


    1. KvanTTT
      21.11.2015 02:39

      Ну честно говоря конкретно ваша репа мало о чем скажет работодателю — мало проектов, они все без описания и без демок. Кроме того, мало коммитов, старов, issue и прочих социальных вещей, которые потенциально говорили бы работодателю об умении контактировать с другими разработчиками. Да и кода мало.


    1. Karroplan
      21.11.2015 13:38

      вы считаете себя реально такой звездой? вы в курсе, что на любую вакансию с нормальными деньгами тут же приходит больше сотни отзывов и после первичного фильтра остается 50? и что, мне таки по всем 50 ходить и читать репы? ищите дальше )


      1. NightmareZ
        21.11.2015 13:42

        Я вот слышал, что нынче дефицит хороших разработчиков. А вы вот говорите, что по сто человек на место…


        1. Rasifiel
          22.11.2015 03:32

          Зависит от уровня компании. Гугл получает в сотни раз больше резюме чем нанимает.


      1. KvanTTT
        21.11.2015 17:05

        Да уж, с сотней вы мягко говоря преувеличили.


      1. Fibril
        21.11.2015 20:24

        Типа я ищу разработчиков, но не вы мне нужны, а я вам. У меня деньги — построились и пляшем. К таким работодателям опытные разработчики обычно даже не приходят, а работу получают те, кто лучше пляшет. Выбрать из 50 кандидатов с портфолио одного или несколько подходящих — совсем несложно.


    1. Fibril
      21.11.2015 20:23

      Все верно, кандидатов надо отбирать по портфолио. Очень часто, устраивая всякого рода экзамены, работодатель ищет не знания, а пробелы в знаниях для сбивания цены. Типа ищем опытного сантехника и устраиваем ему экзамен по сопромату и атлетике. Чем больше кандидат рвет пупок и тратит времени, тем легче после этого будет сбить цену.


  1. VitaZheltyakov
    20.11.2015 22:17

    Чтобы давать задачки на собеседованиях, надо уметь их адекватно оценивать. Зачастую работодатель хочет получить ответ, именно, то который он знает, а не тот который может предложить кандидат


  1. aml
    20.11.2015 23:19

    Не могу не поделиться рекомендациями Google про то, как надо интервьюировать кандидатов: rework.withgoogle.com/guides/hiring-use-structured-interviewing/steps/define-hiring-attributes


  1. AlexanderG
    20.11.2015 23:55

    какие еще вопросы можно было бы задать кандидату, который написал представленный выше код за отведенные ему 40 минут.

    Любопытно, а сам Реджинальд уложился в 40 минут при написании кода из статьи?


  1. free__man
    21.11.2015 06:17

    Задачи на собеседовании это хорошо. Но задача должна решаться без привязки к методам (функциям) конкретного языка. Вы знание человеком плюшек JS (ES) проверяете или его умение составить алгоритм? По приведённым решениям задач скорее первое.


    1. leremin
      21.11.2015 13:44

      Тут же палка о двух концах. Если нужен просто толковый программист, то Вы правы. Но иногда нужен спец по конкретному языку/фреймворку.


  1. free__man
    21.11.2015 14:03

    Совершенно согласен! Просто исходя из названия статьи (туда не вынесен ЯП) ожидал увидеть описание универсальных вопросов, без привязки к конкретному ЯП.


  1. relgames
    21.11.2015 15:02

    Если бы кандидат писал слияние сортированных списков вручную, я бы ему минус поставил — не знает про библиотечные функции. Например в Java стандартный sort — это TimSort, который отлично работает именно на таких задачах.


    1. Suvitruf
      21.11.2015 17:15

      Что важнее, знать библиотечные функции или понимать/уметь написать тоже самое самому? Извечный холивар.


      1. Borz
        21.11.2015 17:27

        а как же умение применять то, что написали другие и понимание того, как это работает?


      1. relgames
        23.11.2015 11:45

        Важнее всего через 3 года посмотреть на свой код и сразу же понять, что он делает.
        А еще лучше, другой программист сразу должен его понять.
        Библиотечные функции протестированы на кучу проектов и хорошо документированы.
        Свой велосипед может содержать баги (только не надо говорить, что нужно писать без багов — вероятность допустить ошибку есть всегда).


    1. leremin
      21.11.2015 17:16

      Тут опять палка о двух концах. Если мне на Яве дать задание, то я тоже сходу не вспомню, где там стандартная сортировка. Просто потому, что на ней ничего не писал уже много лет. То есть да, можно сказать, что я не знаю про библиотечные функции, но в то же время я в кратчайшее время все вспомню. Не будем задаваться вопросом, почему я не подготовился к собеседованию, зная, что там будет Java. Я просто хочу сказать, что проводить собеседование по жестко заданным правилам нельзя — надо смотреть по обстоятельствам. Но проводить собеседование программиста должен тоже программист. Только он поймет, на что способен кандидат.


      1. relgames
        23.11.2015 11:54

        Я неправильно выразился. Не «поставил бы минус», а «поставил бы плюс за знание библиотечной функции» — так лучше? :)


        1. leremin
          23.11.2015 20:24

          Ну в принципе согласен. Знание их — плюс, незнание — не обязательно минус.


    1. vedenin1980
      21.11.2015 20:43

      Если бы кандидат писал слияние сортированных списков вручную, я бы ему минус поставил — не знает про библиотечные функции. Например в Java стандартный sort — это TimSort, который отлично работает именно на таких задачах
      .
      Вот поэтому я и не люблю такие задачи на собеседованиях, так они скорее предназначены для поднятия ЭГО того кто их проводит.

      Ничего что TimSort дает в среднем O(N log N) + O(N) объединение списков до сортировки, а слияние вручную простым движением по спискам и сравнением стабильно O(N), причем скорее всего значительно более быстрый O(N) чем Timsort? А то что затраты памяти будут вдвое больше? А если каждый список по нескольким миллионам элементов и требуется написать как можно более производительный код?


      1. Mrrl
        21.11.2015 20:55

        Что даст TimSort, если массив сразу состоит из двух отсортированных частей? O(N log N), или что-нибудь ближе к O(N)? И откуда «вдвое больше памяти»? Если исходные списки имели суммарный размер K, то при ручном слиянии вам потребуется дополнительно K для хранения результата, итого 2*К. Если идти через сортировку, то массив (который и будет результатом) имеет размер К, плюс дополнительный массив на слияния будет длиной К/2 (конечно, зависит от реализации, но если она написана хорошо, то больше не нужно). Итого 5/2*К, всего на 25% больше ручного слияния. А никак не вдвое.
        По производительности. Стандартная сортировка, скорее всего, будет написана на низкоуровневом языке (например, на С), если тип данных базовый и операция сравнения стандартная. Обойти такую сортировку, работая со структурами высокого уровня (такими, как список), будет непросто.
        Но, конечно, всё решает эксперимент. Результаты могут различаться в несколько раз в любую сторону.


        1. vedenin1980
          21.11.2015 21:20

          А что гадать откройте исходники Java и посмотрите:
          1. Никакой нативной реализации там, конечно, нет, так как это нарушило универсальность,
          2. Там сначала списки объединяются addAll (O(n)) список превращается в Array (O(N)), потом производится сортировка (от O(N) до O( N log N), потом массив записывается обратно в список (O(N)), сколько раз вы переплатили за Trimsort?
          3. Да, я ошибся памяти будет занято даже больше чем в два раза, так как будет копирование в массив и у TimSort занятость памяти указывается как N, то есть от 2 до 3 раз расход памяти увеличится.
          4. А ручная реализация соединения очень простая, сравниваем текущие элементы, если больше первый добавляем его в результирующий список и итерируемся по первому списку, иначе добавляем второй и итерируемся по второму списку.


          1. Mrrl
            21.11.2015 21:57

            0. Для этого надо во-первых, знать, где лежат исходники Java, во вторых, ориентироваться в них. Честное слово, пока необходимости в этом у меня нет. Лучше я в исходниках C# поковыряюсь.
            1. Если её нет — то это недостаток библиотеки. В C#, например, сортировка базовых типов переключается на низкий уровень, и никакой универсальности это не нарушает:

                            if (comparer == Comparer.Default || comparer == null) {
                                bool r = TrySZSort(keys, items, index, index + length - 1); 
                                if (r)
                                    return; 
                            } 
            

            TrySZSort — native метод.
            2. «Там» это где? Разве нельзя копировать списки сразу в нужные места массива? Кроме того, пересылка занимает гораздо меньше времени, чем поэлементное сравнение того же количества элементов, да ещё и со сложной логикой. И откуда у вас всё время возникает O(N log N)? Вы про TimSort говорите или про сортировку вообще?
            3. Да, про обратное создание списка я забыл. Действительно потребуется 3*N (дополнительный массив TimSort и итоговый список одновременно в памяти не живут, поэтому память на них общая). Итого, 3/2 раза от ручного слияния. Но опять же, не 2 раза.
            4. Спасибо, я в курсе.


        1. vedenin1980
          21.11.2015 21:41

          всё решает эксперимент. Результаты могут различаться в несколько раз в любую сторону.

          Если хотите проведите эксперимент, код для ручного объединения на вскидку будет примерно таким
          Код
                  List<String> result = new ArrayList<>(6);
                  List<String> list1 = Arrays.asList("1","4","7");
                  List<String> list2 = Arrays.asList("1", "2", "6");
                  Iterator<String> iterator1 = list1.iterator();
                  Iterator<String> iterator2 = list2.iterator();
                  String first = iterator1.next();
                  String last = iterator2.next();
                  for(int i =0;i< list1.size() + list2.size(); i++) {
                      if((last == null || (first != null && first.compareTo(last) < 0))) {
                          result.add(first);
                          first = iterator1.hasNext()? iterator1.next(): null;
                      } else {
                          result.add(last);
                          last = iterator2.hasNext()? iterator2.next(): null;
                      }
                  }
          

          Для соединения через сортировки, как я понимаю, таким:
                  List<String> result = new ArrayList<>(6);
                  List<String> list1 = Arrays.asList("1","4","7");
                  List<String> list2 = Arrays.asList("1", "2", "6");
                  result.addAll(list1); 
                  result.addAll(list2); 
                  Collections.sort(result);
          

          Проверять нет желания, но первый код раза в 3-4 должен быть быстрее, особенно если списки будут не из трех значений.


          1. Mrrl
            21.11.2015 21:59

            Увы, у меня Java не установлена ни на одной из доступных машин.
            А почему вы решили сортировать именно string, а не int?


          1. Mrrl
            21.11.2015 22:42

            Проверил на C#. Слияние списков из 10^8 целых чисел через промежуточное копирование в массив идёт в 3 раза быстрее, чем прямое слияние, а в случае списков строк — на 30% медленнее.


          1. relgames
            23.11.2015 12:21

            Вот результаты для 3х элементов:

            Benchmark                Mode  Cnt         Score        Error  Units
            MyBenchmark.libSort     thrpt   20   8237393,323 ± 165506,734  ops/s
            MyBenchmark.manualSort  thrpt   20  11939532,372 ± 359279,303  ops/s
            

            gist.github.com/relgames/ad4ce8251bf69ebd391a

            А вот для 1 000 000 элементов в каждом списке:
            Benchmark                Mode  Cnt  Score   Error  Units
            MyBenchmark.libSort     thrpt   20  6,091 ± 0,430  ops/s
            MyBenchmark.manualSort  thrpt   20  8,738 ± 0,500  ops/s
            

            gist.github.com/relgames/5a300229150420abf83f

            Да, немного быстрее, но не в разы. В 1.3-1.5 раз.

            Является ли это критическим? Каждый решает сам. Однако я бы не стал использовать manualSort, пока есть другие способы ускорить работу. Например, в этом конкретном случае можно использовать не строки, а Integer. Или вообще 2 массива int.
            Вариант с библиотечной функцией короче и легче читается. Ручной вариант читается хуже.

            Я выше уже написал, что неверно выразился. Не «поставил бы минус за незнание», а «поставил бы плюс за знание библиотечной функции» — так правильней.


            1. vedenin1980
              23.11.2015 23:50

              Вы померили не правильно, вы создание списков из 200 тыс. строк поместили в Benchmark что забивало весь результат, правильный код будет таким:

              Код
              package com.company;
              
              import org.openjdk.jmh.annotations.Benchmark;
              import org.openjdk.jmh.runner.Runner;
              import org.openjdk.jmh.runner.RunnerException;
              import org.openjdk.jmh.runner.options.Options;
              import org.openjdk.jmh.runner.options.OptionsBuilder;
              
              import java.util.ArrayList;
              import java.util.Collections;
              import java.util.Iterator;
              import java.util.List;
              
              public class MyBenchmark {
                  private static final int N = 1000000;
                  static List<String> list1 = list1();
                  static List<String> list2 = list2();
                  @Benchmark
                  public List<String> manualSort() {
                      List<String> result = new ArrayList<>(3*N);
                      Iterator<String> iterator1 = list1.iterator();
                      Iterator<String> iterator2 = list2.iterator();
                      String first = iterator1.next();
                      String last = iterator2.next();
                      for (int i = 0; i < list1.size() + list2.size(); i++) {
                          if ((last == null || (first != null && first.compareTo(last) < 0))) {
                              result.add(first);
                              first = iterator1.hasNext() ? iterator1.next() : null;
                          } else {
                              result.add(last);
                              last = iterator2.hasNext() ? iterator2.next() : null;
                          }
                      }
              
                      return result;
                  }
              
                  @Benchmark
                  public List<String> libSort() {
                      List<String> result = new ArrayList<>(3*N);
                      result.addAll(list1);
                      result.addAll(list2);
                      Collections.sort(result);
                      return result;
                  }
              
              
              
                  public static List<String> list1() {
                      List<String> result = new ArrayList<>(N);
                      for (int i = 0; i < N; i++) {
                          result.add(String.valueOf(i*2));
                      }
                      return result;
                  }
              
                  public static List<String> list2() {
                      List<String> result = new ArrayList<>(N);
                      for (int i = 0; i < N; i++) {
                          result.add(String.valueOf(i*2 + 1));
                      }
                      return result;
                  }
              
                  public static void main(String[] args) throws RunnerException {
                      Options opt = new OptionsBuilder()
                              .include(MyBenchmark.class.getSimpleName())
                              .forks(1)
                              .build();
              
                      new Runner(opt).run();
                  }
              }
              


              1. relgames
                24.11.2015 00:12

                Да, действительно. Я ошибался про 1.3 раза.


      1. relgames
        22.11.2015 18:40

        Ваши рассуждения про O(N) неверны.

        If the input array is nearly sorted, the implementation requires approximately n comparisons.

        The implementation takes equal advantage of ascending and descending order in its input array, and can take advantage of ascending and descending order in different parts of the the same input array. It is well-suited to merging two or more sorted arrays: simply concatenate the arrays and sort the resulting array.

        docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort(java.lang.Object[])


        1. vedenin1980
          22.11.2015 20:06

          Почему? Я в курсе что в лучшем случае sort дает O(N), в среднем O(N log N), я бы предположил что будет несколько выше чем N и меньше N log N так как идеальный результат на то и идеальный что редко достижим. В любом случае учитывая затраты на объединение двух списков, копирование в массив, сортировку и копирование из массива в список это все не принципиально, ну будет алгоритм выполнятся не в 5 раз, а в 4 раза медленнее, это уже не так важно…


          1. Mrrl
            22.11.2015 20:56

            Что значит — «несколько выше, чем N»? Медленнее, чем O(N)? Или больше, чем N операций? Во втором случае — какие операции вы учитываете — ассемблерные команды? Их будет намного больше, чем N как для ручного слияния, так и для TimSort, а константа зависит от реализации. А также от сложности операций копирования и сравнения (которые для чисел и для строк совсем разные).
            Про O(N log N) — вы хорошо разобрались в деталях алгоритма TimSort? Как он будет работать, когда массив состоит из двух отсортированных частей, и какая у него будет сложность?


            1. vedenin1980
              22.11.2015 22:03

              Эээ, вы понимаете что значит O(N) и почему это никак не связано с ассемблерными командами? Выше это O(N log N) например, а не кол-во элементарных операций.

              Про O(N log N) — вы хорошо разобрались в деталях алгоритма TimSort? Как он будет работать, когда массив состоит из двух отсортированных частей, и какая у него будет сложность?

              Да, если даны два списка (1,2,3) (4,5,6) то сложность будет близка к N(работает метод галопа), если даны списки (1, 5, 7) и (2, 6, 8), то сложность будет вероятнее всего O(N log N), либо что-то среднее между O(N) и O(N log N), но не чистое O(N). Если даны другие варианты, то и сложность будет другой, но не меньше O(N) и не больше O(N log N)


              1. Mrrl
                22.11.2015 22:22

                Я понимаю, что это значит. И понимаю, что фраза «если даны списки (1, 5, 7) и (2, 6, 8), то сложность будет вероятнее всего O(N log N)» смысла не имеет: чтобы говорить, что сложность равна O(N) или O(N log N), надо, чтобы исходные данные зависели от N, и это N можно было сделать сколь угодно большим. Например, слить списки (1,3,5,...,2*N-1) и (2,4,6,...,2*N). И, что удивительно, с этими данными TimSort справится ровно за O(N): он найдёт два упорядоченных фрагмента и применит к ним функцию слияния.


                1. vedenin1980
                  23.11.2015 00:48

                  что удивительно, с этими данными TimSort справится ровно за O(N): он найдёт два упорядоченных фрагмента и применит к ним функцию слияния.

                  Увы, только в идеальном случае. Да, функция слияния это O(N), но ведь забыли тот факт что найти два упорядоченных фрагмента это не бесплатно, положим TimSort найдет два упорядоченных фрагмента за sqrt(N), то сложность будет O(N + sqrt(N)), даже если представить что он так найдет два упорядоченных фрагмента за log N, то все равно как бы не была близка сложность O(N + log N) к O(N) это не чистое O(N). А если списки не равны по размеру и скажем первый список в 3,14 раза больше или меньше чем второй, то сложность поиска упорядоченных фрагментов будет, скорее всего, ещё выше. Вывод: в идеальном случае TimSort даст O(N), в реальном сложность будет выше чем O(N), может быть совсем немного, но выше.


                  1. Mrrl
                    23.11.2015 00:52

                    Извините, но O(N+sqrt(N)), O(N+log(N)), и даже O(1000*N) — это то же самое, что O(N). Так что сложность будет O(N), даже если он будет искать фрагменты линейным поиском. А другого выхода у него нет: списки могут «зацепиться» только одним элементом (как [1,2,3,5] и [4,6,7,8]), и, чтобы найти переставленную пару, сортировке придётся просмотреть весь массив.


                    1. vedenin1980
                      23.11.2015 01:04

                      Да, сори написал ерунду, согласен. Хотя это не отменяет того факта, что на практике разные O(n) могут очень сильно отличаться друг от друга.


                      1. relgames
                        23.11.2015 12:23

                        На практике нужно измерять. И «очень сильно», оцененное на глаз, оказывается не так уж и сильно.


                        1. vedenin1980
                          23.11.2015 23:51

                          Ну вот на практике, в 4.5 раза разница. Это не очень сильно?


                          1. relgames
                            24.11.2015 00:13

                            Синтетическая разница. На практике же будет ближе к моим результатам. На практике, если это не узкая ниша, библиотечные функции лучше.


                            1. vedenin1980
                              24.11.2015 00:44

                              Что значит на практике? Если нам приходят два упорядоченных списка из разных источников, почему на практике функция sort будет лучше? Во многих случаях производительность важна. На практике важно знать когда можно и лучше использовать библиотечные функции, а когда их использовать нельзя, перекос в любую сторону всегда вреден.


                              1. relgames
                                24.11.2015 00:48

                                Данные откуда-то читаются и куда-то пишутся. Может так оказаться, что сортировка — это лишь малая часть. Даже в моем примере, где данные генерируются из памяти, именно это заняло большую часть времени.


          1. relgames
            23.11.2015 12:22

            Мы и говорим про «лучший» случай — когда сливаются два сортированных массива. Про это написано в JavaDoc, который я выше цитировал.
            Не в 4-5 раз, а в 1.3 раза — я выше привел результаты теста.


    1. Mrrl
      23.11.2015 00:02

      Кстати, на второй задаче TimSort покажет намного лучший результат, чем тот код, что приведён в статье: если сливается K потоков длины N, то TimSort справится за O(N*K*log(K)), а код из статьи за O(N*K^2*log(K)). Правда, про потребление памяти лучше не вспоминать: ручное слияние требует O(K), а слияние через сортировку — O(K*N),


  1. AlexZaharow
    21.11.2015 19:35

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

    P.S. Ну почему на хабре никто не сделал кнопку перемотки к месту где я могу оставить комментарий? Только кнопка «вверх». Но это не единственное желаемое направление перемещения… :) или я её не вижу?


  1. aspcartman
    22.11.2015 03:07

    Я считаю, что задавать стоит вопросы по инструментам и сторонним проектам, которые используются на искомой позиции. Ищем iOS разработчика — так и гоняем его по хитростям UIKit, Autolayout, Core-Data и популярным сторонним проектам. Смотрим уровень его понимания, сколько человек вынес из своего опыта. Если ищется девелопер — так и стоит с него спрашивать то, что от него будет требоваться на рабочем месте. Вопросы вроде «как сделать мердж» или какой-либо другой алгоритм, you name it, стоит спрашивать у джуниора.


    1. Rasifiel
      22.11.2015 03:21

      Вы считаете самым ценным в разработчике знания каких-то конкретных инструментов, но далеко не все с вами по этому вопросу согласны. Многие считают, что надо найти хорошего разработчика в целом, а не специалиста по каким-то иструментам. Потому что инструментов куча, они меняются постоянно и у всех свои наборы, а хороший разработчик в том числе быстро переключается.
      Я до своей текущей работы на С++ не написал ни строчки помимо лабораторных работ и тем не менее вполне себе устраиваю работодателя.


      1. aspcartman
        22.11.2015 04:09

        Нельзя охватить все случаи. У меня есть проект на Go, и если я буду искать на его поддержку другого разработчика, я буду руководствоваться общими принципами, просто потому, что найти Go-разработчика достаточно трудоемко, а полноценно зашарить этот язык можно, по моей субьективной оценке, можно за дни-неделю. Тут случай сложной задачи и простого инструмента -> искать хорошего программиста (гонять по алгоритмам и general вопросам, возможно специфичным для сферы, тут это будет многопоточность и бэкенд разработка), пусть и не знакомого с инструментом.

        Учитывая, что вы устраиваете работодателя в качестве С++ разработчика, имея за спиной пару лабораторных работ (и вспоминая обьем документа-спецификации языка С++, превышающий более чем в 10 раз онный для Си), то перед вами ставится как разработчиком ставится относительно простая задача с точки зрения С++ разработки, не требующая глубоких знаний инструмента (пока речь была только про язык, возможно Вы используете еще, например, boost, или qt). Простая задача, сложный инструмент -> (я) буду искать просто адекватного разработчика (простые алгоритмические задачи и простой-средней сложности общие вопросы) и немного знакомого с инструментом.

        Однако, возвращаясь к iOS разработке, я говорил о сложной задаче (большое приложение с активным использованием advanced инструментов и сторонних популярных проектов) и сложном инструменте. Девелоперов — пруд прудей. И даже очень хороший Java\С++\Whatever разработчик, потратит очень уж много времени на то, чтобы на достаточном уровне въехать в тему. Я просто об этом не оговорился, my bad, но будь задача простая (маленькое тривиальное приложение), то я бы и не спрашивал про все эти инструменты, я думаю это логично. Так вот, тут сложная задача, сложный инструмент -> гоняем по инструментам в первую очередь, общие знание второчны и быстрее усваиваются, чем инструменты.


      1. relgames
        23.11.2015 12:27

        Иногда конкретные инструменты используются годами, если не десятилетиями. Если компания использует какой-то фреймворк во всех проектах (скажем, Spring), то если человек имеет опыт именно в этом фреймворке, это будет большой плюс.


        1. Rasifiel
          23.11.2015 12:56

          Никто не спорит, что плюс. Но вопрос компенсирует ли этот плюс плохую базу?


  1. baldr
    23.11.2015 00:38

    Задавая «задачки» на собеседованиях интервьюер должен быть готов к тому, что его точно так же могут попросить решить «задачку»:
    «Мне бы хотелось представлять с кем я собираюсь работать, поэтому пока я пишу ответ на вашу задачку про потоки, пожалуйста, напишите решение для вот этой задачки». И там тоже может быть все что угодно.

    Я ненавижу писать код когда у меня из-за плеча кто-то смотрит. И пусть даже выходит из комнаты, но в таком стрессе человек нормально не реагирует. Если вам нужны программисты, которые будут работать в стрессовых условиях — ну что ж, ваше право. Но я предпочитаю работать спокойно — вот в таких условиях и надо давать задачи. в идеале — дайте задачу на дом, пусть пришлет решение по почте. Пусть поищет на stackoverflow, у друзей, где угодно. Вам же важен результат, а не как он потеет? Сумел найти решение интересующей вас проблемы из вашей области за день-два? Что вам еще надо?

    Я на собеседованиях никогда не даю задач на «напишите программу вот на этой бумажке». Пока человек рассказывает о своем опыте — уже можно составить впечатление о задачах, которые он решал. Задайте парочку вопросов по его теме — будет понятно насколько глубоко он «в теме».
    Хотите поумничать — спросите парочку общих вопросов из теории типа «что такое нормализация», «когда вы применяете наследование, а когда нет», и тп. Спросите что первым делом он настроит в MySQL когда поставит сервер. Или PostgreSQL.
    И все без бумажек, простыми вопросами, ожидая простые ответы.
    И он не должен ждать, что вы вдруг прицепитесь: «а у вас не запустится программа! Что тут не так?? А точка с запятой не стоит в конце!!!».

    Как человек думает — видно и так. Как он отвечает на вопросы — присмотритесь — так он и будет работать в вашей команде.
    Я выбирал людей «под себя» и под команду — сработается ли, будет ли обсуждать проблемы или замкнется и будет молча что-то делать? Будет ли принимать критику и готов ли будет, например, принимать мои замечания? Я сам достаточно авторитарен и приходилось отказываться от людей с опытом, но, по которым было видно, что с ними у меня могут быть конфликты (даже из-за меня).


    1. Rasifiel
      23.11.2015 12:55

      А вы не предполагали, что не у всех могут быть такие же условия, как у вас? Например, если у компании своя инфраструктура, то ей предыдущий опыт и знания потаенных секретов совершенно не интересны. Ну и разговоры это прекрасно, вот только код это то, что работник будет писать. Есть люди которые очень хорошо говорят, но с кодом у них беда.


      1. vedenin1980
        23.11.2015 13:35

        Хмм, лучше спрашивать не код, а скажем как бы вы решили какую-то задачу. Например, у вас есть данные о маршруте городского транспорта, как бы вы решили задачу оптимизации времени пути человека от точки А до Б, просто словами без кода, тут будет сразу видно насколько человек умеет решать задачи и вообще как он походит к разработке алгоритмов.

        А код на бумажке… ну вот не помню я как точно называется функция, которая находит тангенс, или которая округляет вниз. При этом в IDE я напишу Math. и найду нужную функцию за пару секунд. Как часто у вас программисты решают реальные задачи программирования на бумажки на время в условиях стресса и без интернета? Если уж вы хотите давать задачи на программирование, дайте мне IDE, интернет и время на нормальное обдумывание и программирование (программист редко в реальной работе должен решать задачи из разряда, «а напиши решение бинома Ньютона за 90 секунд), иначе совершенно непонятно что пытаются замерить такими задачами.

        Самое интересное, что интервьюер готовит задачи с IDE, интернетом и кучей времени (а то и вообще берет чужие задачи и решения), а потом чешет свое ЭГО, смотря как его головоломные задачи пытаются решить на бумажке из головы за 1 минуту в условиях стреса.


        1. Rasifiel
          23.11.2015 14:40

          Преимущество кода в качестве решения — единообразное, легко оцениваемое решение и главное документирование размышлений о решении. И если вы забыли название функции никто не расстреляет и не выбросит с собеседования. Главное понимать что вы делаете и объяснить это интервьюеру.
          Типичные хорошие задачи с собеседования это пара-тройка задач строк на 10-15 кода (чтобы к ним подготовиться не надо IDE) минут на 45 интервью. Потом пообщаться на тему как адаптировать решение к каким-то новым условиям.
          Вы зачем-то демонизируете интервьюера как будто он не хочет нанимать никогда, а хочет самоутверждаться. Я не могут сказать, что таких нет, но зачем на них равняться?


          1. vedenin1980
            23.11.2015 15:49

            Преимущество кода в качестве решения — единообразное, легко оцениваемое решение и главное документирование размышлений о решении.

            Нет, выше был спор что лучше объединить списки вручную или вызывать sort. Кто-то пишет в стиле чистого кода, без комментариев, кто-то требует комментарии к каждой строчке, кто-то везде вставляет использования функционального стиля, кто-то наоборот. Интервьюер может ждать что кандидат вставит проверки во все возможные случае, а кандидат решил что надо просто реализовывать алгоритм по-простому в одном случае. Интервьюер легко может «зарубить» кандидата только потому что его решение не совпадает с тем что он написал бы сам (или его понимания как надо писать). Ещё хуже если кандидат окажется выше уровнем чем интервьюер, тогда вообще «что за фигня тут у вас написана»

            А документированность тут причем? У вас кандидаты что подают апелляции на решение интервьюера? Вряд ли, если интервьюер скажет что кандидат не тянет, код кандидата будет кто-то ещё изучать.

            Вы зачем-то демонизируете интервьюера как будто он не хочет нанимать никогда, а хочет самоутверждаться. Я не могут сказать, что таких нет, но зачем на них равняться?

            Проблема в том, что сознательно интервьюер хочет найти хорошего сотрудника, но подсознательно любой человек хочет самоутвердиться. Очень сложно делать скидку на стресс, отсутствие компьютера, другой стиль программирования, и «уж я бы точно вспомнил бы функцию арктангенса!», «что это за старший программист который не помнит досконально принцип балансировки красно-черного дерева и шестую нормальную форму?».

            И если вы забыли название функции никто не расстреляет и не выбросит с собеседования

            Зато у меня возникнут сомнения в том что мне нужно в эту фирму.

            Проблема в таких задачках, что их отлично проходят джуниоры/студенты/школьники, участвующие во всяких олимпиадах, при этом не факт что они смогут нормально работать, зато старшие программисты с огромным опытом без IDE и инета могут «плавать», так как они давно не писали быстрой сортировки руками, разработать архитектуру огромной корпортативной системы они могут легко, а быструю сортировку могут давно уже забыть за полной ненадобностью в реальной работе.


            1. Rasifiel
              23.11.2015 17:52

              Все ваши претензии к возможному искажению результатов собеседования интервьюером точно так же можно применить к любому виду собеседования. Если вы не доверяете интервьюеру, то никакого успешного собеседования не будет.
              А насчет старших программистов — никто же не говорит, что надо для всех вакансий вообще делать одинаковые вопросы? Можно задавать такие же задачи на архитектуру с довольно свободным полетом мысли. Но так же все равно разработчик должен уметь писать код и решать задачи.


              1. vedenin1980
                23.11.2015 23:21

                Не совсем, по моему опыту большого количества код ревью в разных фирмах — анализ качества чужого кода вещь очень субъективная, а вот знание конкретных вещей — объективная. Если мне задают вопросы по коллекциям, патернам, базам данных, orm, nosql я либо на них отвечаю, либо нет. Это вполне объективный критерий c которым сложно спорить (если конечно интервьюер сознательно не пытается завалить кандидата), с кодом все сложнее — не так называл переменные — минус, использовал императивный подход вместо функционального — минус, не сделал проверку граничных условий — ещё один минус, написал не производительный код — минус, написал производительный код — минус за преждевременную оптимизацию (при этом интервьюер может даже не замечать своей субъективности). Наоборот, оценка кода как раз очень субъективна, она похожа на оценку рассказов (была такая байка что как-то Лев Толстой, тогда уже знаменитый писатель, решил проверки ради отправить один из своих рассказов от лица молодого автора — его все редакторы разнесли в пух и прах в самых уничижительных выражениях).

                ИМХО, для программистов без опыта пара задач на кодирования может быть неплохая идея, но для опытных программистов слишком простые задачи ничего не скажут о умении программировать и стиле программирования (ну, напишет программист list1.addAll(list2); Collections.sort(list1); что это скажет о том как он умеет кодировать на Java? Проще просто спросить как можно отсортировать список), а слишком сложные — будут случайным образом отсеивать хороших кандидатов. Но это лишь мое личное мнение.


      1. baldr
        23.11.2015 14:32

        Очень редко удается найти человека, который до этого работал с *точно таким же* стеком технологий. Поэтому, практически всегда, ваша компания будет для него чем-то новым. И сразу требовать от него чтобы он разбирался досконально во всех ваших нюансах — не очень правильно. Если вы не готовы учить человека первые два-три месяца, то вы, конечно, можете требовать «все и сразу», но и будьте готовы платить ему в 2 раза больше.
        А про код — повторюсь — можете дать задачу на дом. У вас в офисе он будет писать код точно так же — без человека за спиной и самостоятельно как минимум по день-два до очередного ревью.
        Я сначала давал задачки на дом, но потом понял что даже они мало что определяют. Маленький кусочек кода ничего не покажет — работать он будет, а в большом проекте налажать может любой, в конце концов.

        Почаще ставьте себя на место собеседуемого и смотрите на себя его глазами. Вам бы хотелось вот так сидеть и готовиться услышать вопрос «сколько в этой комнате поместится шариков» или «а ну-ка напишите за три минуты быструю сортировку»?
        Ну вот он не написал, ошибся. А вы про себя сидите и думаете: «мда, обмельчала молодежь… Опять я очередного уделал. Какой я крутой!».

        Это все, конечно, мое мнение. Возможно, в каких-то компаниях обязателен более строгий отбор, чтоб только «лучшие из лучших, которые помнят все алгоритмы, которые 100% соответствуют нашей вакансии и уже через три дня сделают все хорошо». Ок, возможно.


        1. Rasifiel
          23.11.2015 14:48

          Дык поэтому и наплевать на стек технологий, главное чтобы было общие навыки и культура разработчка и способность к обучению и адаптируемости.
          Задача на дом так же не показывает динамики решения и как человек идет к решению. Как он реагирует на усложнения условий. Способен ли он на поиск ошибок. И если человек сходу не может решить, то это не ужасная беда. Хороший интервьюер может дать толчок в нужную сторону и посмотреть как разработчик будет реагировать и как он понимает подсказки.


    1. Fibril
      24.11.2015 07:42

      Ответная задачка интервьюеру — хорошая и совершенно справедливая идея, что-то вроде мести. Думаю, что все интервьюеры, которые отбирают кандидатов подобными задачками, получив такую же задачу в ответ от кандидата, сразу поймут насколько это плохой способ отбора. Вот только на практике такой поворот скорее всего будет воспринят как неимоверная наглость, что приведет к моментальному прощанию с кандидатом. Сложно представить себе интервьюера, который опустится до решения такой задачки.


      1. Mrrl
        24.11.2015 10:07

        Представить легко. Например, такого, который либо уже знает решение, либо может решить за несколько секунд. Он, скорее, похвастается своим мастерством, чем обидится.


        1. Fibril
          24.11.2015 23:03

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


          1. Mrrl
            25.11.2015 21:06

            Ну, и почему интервьюер не может оказаться опытнее кандидата (и знать аналоги большинства задач, которые кандидат может предложить)?


            1. Fibril
              26.11.2015 07:08

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


          1. strannik_k
            25.11.2015 22:12

            Думаю, интервьюер от задачи скорее всего откажется.
            Вопросы лучше по задавать. Из-за разных наборов знаний может выйти смешная ситуация, когда сначала интервьюер завалит вопросами кандидата, а потом кандидат интервьюера :)