Вот уже десять лет специалисты холдинга DZ Systems занимаются разработкой ПО и созданием информационных систем на самом высоком уровне — за это время их клиентами успели стать такие киты российского бизнеса и мегапроекты государства Российского, как Юлмарт, Яндекс, Мосводоканал, Олимпиада-2014, Mail.Ru Group, Wikimart, Raiffeisen Bank, KFC и BMW.

Офисы группы компаний расположены в пяти городах России: Москве, Санкт-Петербурге, Казани, Ульяновске и Саранске. Поскольку по странному стечению обстоятельств там же обитают наиболее активные читатели нашего журнала :), думаю, тебе будет интересно посмотреть на задачи, которые в DZ Systems ставят перед кандидатами на трудоустройство. Тем более что нигде, кроме нашего журнала, ты их не найдешь.

 

Как проходит собеседование в DZ Systems

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

Программист, который хорошо написал тестовое задание, после беседы с HR-специалистом проходит техническое собеседование с ведущими разработчиками. Наши офисы находятся в разных городах, поэтому второе собеседование может проводиться по скайпу. Например, мобильные разработчики у нас в Санкт-Петербурге и Казани, а Java-разработчики — в Казани и Ульяновске.

В DZ Systems есть типовые наборы задач и вопросов для технического собеседования, рассчитанного на один час. Такие задачи мы и предлагаем для решения читателям «Хакера». Победители получат возможность бесплатно пройти новый игровой квест от наших друзей из компании «Клаустрофобия» — ограбление банка. В этом квесте ты получишь возможность на час попасть в банковское хранилище и, еще раз проявив логические способности, вынести оттуда ценную реликвию.

Задача 1

При использовании очевидного представления данных для сохранения даты требуется 8 байт (ДДММГГГГ), а имя человека занимает примерно 25 байт (14 на фамилию, 10 на имя и 1 на первую букву отчества). Насколько вы сможете уменьшить эти числа, если перед вами стоит задача экономии памяти?

Задача 2

Написать (на любом языке программирования) функцию вывода n-го числа последовательности Фибоначчи.

pic1

Задача 3

В массиве натуральных чисел [1..1001], содержащем все числа от 1 до 1000 включительно, есть элемент, повторяющийся дважды. Найти его. К каждому элементу можно обращаться только один раз. Язык программирования — любой.

Задача 4

Заданы два числа a, b. Поменять их значения местами без использования промежуточной переменной (то есть использовать можно только a, b и арифметические операции).

Задача 5

Что такое полиморфизм? Приведите примеры.

Задача 6

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

Перекидывать фонарик, идти навстречу, переплывать, останавливаться — нельзя. Задача решаема.

Задача 7

Дана реляционная база данных, которая состоит из трех таблиц (см. картинку).

Написать на SQL программу, которая выведет все компании, где не работает Developer c ID = 3.

database

 

Решение задач из школы программистов HeadHunter

Задача 1. Количество разбиений на k слагаемых

Задача является стандартным примером задачи на динамическое программирование. Обозначим интересующее нас количество разбиений через F(n, k). Часть из разбиений содержит единицу в качестве слагаемого. Все такие разбиения можно получить из разбиений числа n – 1 на k – 1 слагаемое добавлением единицы в качестве k-го слагаемого. Те разбиения, которые единицу не содержат, получаются из разбиения числа n – k на k слагаемых прибавлением единицы к каждому из k слагаемых. Таким образом, получается рекуррентная формула: F(n, k) = F(n – 1, k – 1) + F(n – k, k). Объединяя ее с граничными условиями F(n, k) = 1 при n = k либо k = 1 и F(n, k) = 0 при n < k, получаем решение задачи. Пример кода на Java:

public class PartitionNumberCounter {
 private int[][] table;
  private PartitionNumberCounter(int number, int itemsCount) {
    this.table = new int[number][itemsCount];
  }
  private int countPartitions(int number, int itemsCount) {
    if (number == itemsCount || itemsCount == 1) {
      return 1;
    } else if (itemsCount &gt; number) {
      return 0;
    }
    if (table[number - 1][itemsCount - 1] == 0) {
      table[number - 1][itemsCount - 1] = countPartitions(number - 1, itemsCount - 1) + countPartitions(number - itemsCount, itemsCount);
    }
    return table[number - 1][itemsCount - 1];
  }
  public static int countNumberOfPartitions(int number, int itemsCount) {
    return new PartitionNumberCounter(number, itemsCount).countPartitions(number, itemsCount);
  }
}

Задача 2. Медиана

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

Для получения медианы массива A = [2, 1, 5, 0, 10] отсортируем массив, получим A_sorted = [0, 1, 2, 5, 10]. Медианой массива является третий элемент массива, то есть 2.

Для нахождения медианы массива с четным числом элементов существуют различные соглашения. Для решения задачи примем следующее соглашение: медианой массива A с четным числом элементов 2N является (A_sorted[N] + A_sorted[N + 1]) / 2.

Самым популярным и при этом самым неоптимальным способом решения этой задачи является конкатенация массивов, сортировка результирующего массива и получение среднего от n и n + 1 элементов. Такой способ решения имеет алгоритмическую сложность O(n log n). Второй по популярности метод решения этой задачи — использование сортировки слиянием (merge sort), в этом случае мы получаем алгоритмическую сложность O(n). Рассмотрим способ решения, использующий парадигму «разделяй и властвуй», сложностью O(log n).

 

Решение:

Главная идея состоит в том, что для данных массивов a1 и a2 можно проверить, является ли a1[i] медианой за константное время. Предположим, что a1[i] — медиана. Так как массив отсортирован, a1[i] больше i предыдущих значений в массиве a1. Если он является медианой, он также больше, чем j = n – i – 1 элементов массива a2.

Необходимо константное время для проверки, что a2[j] <= a1[i] <= a2[j + 1]. Если a1[i] не является медианой, в зависимости от того, a1[i] больше или меньше, чем a2[j] и a2[j + 1], мы знаем, что a1[i] больше или меньше медианы. Исходя из этого, мы можем найти медиану бинарным поиском за O(log n) в худшем случае.

Для двух массивов a1 и a2 сначала пройдем бинарным поиском по a1. Если мы достигнем конца (левого или правого) первого массива и не найдем медиану, начнем искать ее во втором массиве a2.

 

Алгоритм

  1. Получим средний элемент a1. Положим индекс среднего элемента i.
  1. Посчитаем индекс j массива a2: j = n – i – 1.
  1. Если a1[i] >= a2[j] и a1[i] <= a2[j + 1], то a1[i] и a2[j] — средние элементы. Искомая медиана (a1[i] + a2[j]) / 2.
  1. Если a1[i] больше, чем a2[j] и a2[j + 1], то ищем в левой части массива.
  1. Если a1[i] меньше, чем a2[j] и a2[j + 1], то ищем в правой части массива.
  1. Если мы достигли конца списка a1, то осуществляем бинарный поиск в массиве a2.
 

Пример

a1 = [1, 5, 7, 10, 13]

a2 = [11, 15, 23, 30, 45]

Средний элемент a1 — 7. Сравним 7 с 23 и 30, исходя из того, что 7 меньше, чем 23 и 30, сдвинемся вправо по a1. Продолжая бинарный поиск в [10, 13], на этом шаге возьмем 10. Сравним 10 с 15 и 23. Так как 10 меньше 15 и 23, снова сдвинемся вправо. 13 больше, чем 11, и меньше, чем 15, заканчиваем работу. Искомая медиана — 12 (среднее от 11 и 13).

 

Имплементация

def get_median(a1, a2, left, right, n):
if left &gt; right:
        return get_median(a2, a1, 0, n-1, n)
    i = (left + right) / 2
    j = n - i - 1
    if a1[i] &gt; a2[j] and (j == n - 1 or a1[i] &lt;= a2[j+1]):
        if i == 0 or a2[j] &gt; a1[i-1]:
            return (a1[i] + a2[j])/2
        else:
            return (a1[i] + a1[i-1])/2
    elif a1[i] &gt; a2[j] and j != n-1 and a1[i] &gt; a2[j+1]:
        return get_median(a1, a2, left, i - 1, n)
    else:
        return get_median(a1, a2, i + 1, right, n)
if __name__ == "__main__":
    a1 = [1.0, 10.0, 17.0, 26.0]
    a2 = [2.0, 13.0, 15.0, 30.0]
    n = len(a1)
    print get_median(a1, a2, 0, n - 1, n)
 

Задача 3. Пересекающиеся прямоугольники

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

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

Имплементация

def compute_length(segments):
length, left, right = 0, 0, 0
segments.sort(key=lambda v: v[0])
for l, r in segments:
    if l &gt; right:
        length += right - left
        left, right = l, r
    elif r &gt; right:
        right = r
return length + (right - left)
def compute_area(rectangles):
queue = []
area = 0
for x1, y1, x2, y2 in rectangles:
    queue.append((x1, True, (y1, y2)))
    queue.append((x2, False, (y1, y2)))
queue.sort(key=lambda v: v[0])
segments = []
last = queue[0][0]
for x, status, size in queue:
    area += (x - last) * compute_length(segments)
    last = x
    if status:
        segments.append(size)
    else:
        segments.remove(size)
return area
 

Структура DZ Systems

Digital Zone специализируется на создании масштабируемых web-систем, рассчитанных на проекты федерального масштаба. Компания на 14-м месте в рейтинге ведущих веб-разработчиков страны за 2014 год. E-Legion — разработчик мобильных приложений, в 2014 году компания вышла на первое место в рейтинге Рунета по мобильной разработке.

 

IT-компании, шлите нам свои задачки!

Миссия этой мини-рубрики — образовательная, поэтому мы бесплатно публикуем качественные задачки, которые различные компании предлагают соискателям. Вы шлете задачки на lozovsky@glc.ru — мы их публикуем. Никаких актов, договоров, экспертиз и отчетностей. Читателям — задачки, решателям — подарки, вам — респект от нашей многосоттысячной аудитории, пиарщикам — строчки отчетности по публикациям в топовом компьютерном журнале.

 

Читатели, шлите ваши ответы!

Правильные ответы принимает Анна Новомлинская (anna.novomlinskaya@dz.ru). Она же распределяет призы — билеты на офлайн-квест. Не теряйся!

35 комментариев

  1. 02.04.2015 at 23:55

    8 байт ДДММГГГГ =
    2 байта
    9 бит на число 365 дней и 7 на 128 лет начиная с 1970

  2. 03.04.2015 at 04:15

    У 3-й задачи довольно много решений. Можно посчитать сумму арифметической прогрессии, посчитать сумму всех чисел в массиве, отнять из второго первое.

  3. 03.04.2015 at 08:57

    [8:54] xxx: у меня таких задач на работе хватает
    [8:55] yyy: Часто строишь последовательность Фибоначчи для начальства?

  4. 03.04.2015 at 08:58

    Ребята, не выкладывайте решения.

  5. 03.04.2015 at 11:14

    No 1

    считать в днях от начала нашей эры

    No 4
    a=a*b
    b=a/b
    a=a/b

    No 6

    ↑1 и 5 = 5
    ↓1 = 6
    ↑1 = 7
    ↑10 и 5 = 17

    • 03.04.2015 at 12:15

      Как это у тебя первый вернулся к пятому без фонарика? И куда делся второй? И как 10-й оказался с пятым, если первый отвёл пятого на ту сторону?

      • 03.04.2015 at 14:50

        да, там не 10 и 5, а 10 и 2. про фонарик точно забыл, поэтому все неправильно 🙂 вот так надо:
        ↑1 и 2 = 2
        ↓1 = 3
        ↑10 и 5 = 13

        ↓2 = 15
        ↑1 и 2 = 17

      • 03.04.2015 at 14:52

        да, там не 10 и 5, а 10 и 2. про фонарик точно забыл, поэтому все неправильно :). лоханул, но уже написали как надо.

    • 03.04.2015 at 13:26

      всё не правильно)

    • 03.04.2015 at 23:18

      >считать в днях от начала нашей эры
      Мне кажется кокраз в таких провтыках и кроетца, ошибка написания серверов)

      — в сервере нельзя писать под все случаи жизни — ни памяти ни cpu не хватит
      есть узкая специализация колонок для БД

      допустим если это дата рождения пользователя то от 1950
      — до 2050 за глаза хватит, у кого меньше ставишь 1950 — будут писать жалобы в отдельную БД пользователей в ней больше тысячи врядли наберется

      а выделять 4 байта под год потому что кто-то вздумает туда впихнуть 30 000 лет до нашей эры, ужасное и болезненное расточительство если у тебя база на миллионы пользователей,

      Хотя =)
      (по факту даже если там будет миллиард : это + 4ТБ винт + Raid что в общих рамках мелоч и потому на данную оптимизацию можно даже время не тратить ^^)

      • 04.04.2015 at 00:13

        >в ней больше тысячи врядли наберется
        да загнул) но смысл уловим

        p.s просто ужос сколько всего надо расписывать чтоб не было хая, а он будет ^^

      • 06.04.2015 at 13:25

        4 байта вместо двух — это два добавочных байта. Для миллиарда записей это 2 гиагабайта. Откуда 4 ТБ?

    • unfear

      22.10.2015 at 13:58

      А если в задаче №4 одним из чисел будет 0 ?

      a=a+b
      b=a-b
      a=a-b

  6. 03.04.2015 at 15:27

    Ну вот, промодерировалось, теперь стало два сообщения.

  7. 03.04.2015 at 17:11

    6 задача.
    1+2 = 2 мин
    <-1 = 1 мин
    5+10 = 10 мин
    <-2 = 2 мин
    1+2 = 2 мин
    ————————
    2+1+10+2+2 = 17 минут

  8. 03.04.2015 at 23:35

    Ну я расчитывал на дату для сообщений и файлов изменений,
    (так как не было точно описано что туда будут пихать)
    потому с 1970, а вы тут влезли в БД для даты файлов с датами до нашей эры XD

    • 03.04.2015 at 23:37

      Про часы, минуты и секунды не спрашивать, их нет в Задаче ^^

    • 03.04.2015 at 23:40

      Короче протупил с 1970 но так как у нас 128 лет лимит можно начать с 1900

      • 04.04.2015 at 00:09

        Если любознательным читателям покажется что 13 лет запаса(от 2015 мало)
        то во первых врядли даже у гугла есть надежда что она продержится ещё 13 лет(и не будет реформации БД)
        ну, а во вторых если паранойя таки превысит то
        берем short и
        для года делаем
        *numb / 365
        для дня
        *numb % 365
        179 лет — запас 64)

        • 06.04.2015 at 13:22

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

    • 06.04.2015 at 13:23

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

  9. 06.04.2015 at 11:07

    10,1,2 — 5
    10,1 —>

    2 — 5,10,1

    5 — 10,2,1

  10. 06.04.2015 at 11:35

    (3)

    for (i = 0; i < 1001; i++)
    {
    if (a[i] != i + 1)
    {
    return i + i;
    }
    }

    • 06.04.2015 at 13:25

      Ну и кто тебе сказал, что массив отсортирован? Читай условия задачи дословно, не придумывай ничего своего.

Оставить мнение

Check Also

Как Apple обходит стандарты, заставляя тебя платить. Колонка Олега Афонина

Иногда сложные вещи начинаются с простых: планшет iPad Pro 10.5 вдруг перестал заряжаться …