*** ВНИМАНИЕ: Блог переехал на другой адрес - demin.ws ***
Показаны сообщения с ярлыком собеседование. Показать все сообщения
Показаны сообщения с ярлыком собеседование. Показать все сообщения

четверг, 20 января 2011 г.

Вопросы на интервью, на которые нельзя не знать ответы

Так сложилось, что за последние полгода, я активно участвовал в процессе интервьирования программистов в компании Bloomberg.

Также на многократном личном опыте знаю, что когда тебе оказывают – это всегда обидно и досадно, какой бы причина там ни была. Но это случается почти со всеми.

К сожалению, отказывать приходится порой из-за радикально тривиальных вещей, незнание которых просто несовместимо с профессией.

У меня накопилось несколько вопросов, незнание ответа на которые является почти стопроцентной причиной, когда я в своем отчете писал отказ.

Интервьюирование было на позицию "Senior C/C++ developer”.

Ответы приведу тут же, так как они очевидны.

  1. Сколько примерно будет 2^32? (обычно задается по телефону)

Ответ "Около четырех миллиардов" является исчерпывающим.

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

  1. Как сравнить две переменные типа double или float на равенство? (обычно задается по телефону)

Ответ "Вычесть одно из другого и сравнить результат на больше/меньше с каким-то малым числом, например 10E-6" является исчерпывающим. Конечно, много зависит от используемой библиотеки работы с числами с плавающей точкой, но смысл, в целом, одинаков.

Увы, количество неотвечающих тоже весьма значительно.

  1. (Хит!) Что распечатает данная программа? (не забываем, что собеседование на позицию разработчика на C/C++). В принципе, его тоже можно задать по телефону.
char* f() {
  char buf[100];
  strcpy(buf, "TEST”);
  return buf;
}

int main() {
  char* s = f();
  /* (1) */
  printf("%s\n", s);
}

Ответ: "Нельзя сказать с уверенностью, скорее всего мусор, но в целом это неопределенное поведение, так как локальный буфер формально прекращает существование после выхода из функции f()" является почти исчерпывающим.

Почему "почти"? Потому что обычно за ним дополнительный вопрос: "Что именно может с высокой вероятностью затирать заветное слово TEST и приводить к выводу мусора? Для конкретности: платформа x86, 32-bit, компилятор Visual Studio. Если остановить программу отладчиком в точке (1) и посмотреть, на что указывает указатель "s", то очень высока вероятность, что там будет таки "TEST", а вот printf() таки с высокой вероятностью распечатает мусор. Почему?".

Более половины собеседований, в которых я участвовал, заканчивались со знаком "минус", так как человек даже не делал попытку сказать что-то типа "В данных условиях скорее всегда слово TEST будет перезатерто параметрами функции printf(), которые передаются через стек и ложатся на то место, где был раньше размещен буфер "buf". Конечно, многое зависит от режимов оптимизации, так как аргументы могут быть переданы через регистры."

Фактически, произнесенные слова "стек" и "параметры функции" являются достаточным ответом на вопрос.

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

Но все же есть такая черта, ниже которой уже нельзя.

А у вас есть вопросы, "неответы" на которые вы лично можете считать поводом для практически однозначного отказа?

Самые глупые ответы на интервью, что я когда-либо давал

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

  1. Как-то яростно пытался доказать, что тип int является за 100% атомарным без каких-либо гвоздей на платформе x86. Не доказал (и вот почему).
  2. Вопрос: «При множественном виртуальном наследовании в С++, кто и как должен заботиться о правильном однократном вызове конструктора базового класса (подразумевается, что у этого конструктора есть параметр)?». Я сказал, что это компилятор, и вдобавок еще не смог объяснить почему.
  3. Ну и лидер нашего хит-парада. Вопрос: «В С++ таблица виртуальных функций принадлежит классу или экземпляру класса?» Барабанная дробь: я сказал, что каждый экземпляр одного класса имеет собственную копию таблицу. Почему я так сказал, я до сих пор не знаю.

Все это еще раз подтверждает факт того, что на нервах можно сморозить такое, что потом сам будешь думать о причинах сказанного.

среда, 31 марта 2010 г.

Веселые перестановки

Вдогонку к вопросу о векторе предлагаю еще блиц вопрос (ни разу не претендую на оригинальность, но вопрос родился лично у меня в процессе обдумывания алгоритма формирования таблиц market depth): есть некоторая произвольная конечная последовательность (массив, строка и т.д.). Повторения значений возможны. Также задана вторая последовательность такой же длины, состоящая в точности из тех же элементов, что и первая, но расположенных в другом порядке.

Вопрос: как на месте преобразовать первую последовательность во вторую, если в плане перемещения/копирования элементов есть только одна функция - обмен двух соседних элементов. Произвольный доступ к одиночным элементам есть только на чтение. Для перезаписи/изменения элементов надо пользоваться данной функцией обмена.

Конечно, интересно иметь и оценку сложности.

Мой ответ, если кому интересно, будет завтра.

Добавление элементов в std::vector

На собеседованиях по С++ задают много вопросов про контейнеры STL. И самый безобидный из них, как думал, std::vector. Но вот и по нему попался интересный вопрос.

Представим, что стратегия управления внутренним буфером контейнера std::vector (в реальности, она иная) такова: изначально размер буфера равен нулю, и он будет увеличивается вдвое каждый раз, когда в нем уже нет места под следующий элемент.

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

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

На всякий случай: мой ответ будет завтра.

А сейчас мини эксперимент с реальным std::vector (компилятор, и сообразно STL — Sun C++ 5.9 SunOS_sparc) для выяснения реальной стратегии роста буфера в векторе:

#include <vector>
#include <iostream>
#include <iomanip>
#include <cstdlib>

int main() {
  int last = -1;
  std::vector<int> a;
  std::cout << std::setw(12) << "Capacity" << " " 
            << std::setw(12) << "Size"
            << std::setw(12) << "Ratio" << std::endl
            << std::setw(12) << std::setfill('-') << "-" << " " 
            << std::setw(12) << "-" << " "
            << std::setw(12) << "-" << std::endl;

  std::cout << std::setfill(' ') << std::fixed;
  while (1) {
    if (a.capacity() != last) {
      last = a.capacity();
      std::cout << std::setw(12) << a.capacity() << " "
                << std::setw(12) << a.size() << " "
                << std::setw(12) << std::setprecision(6)
                << (float)a.capacity() / a.size() << std::endl;
    }
    a.push_back(std::rand());
  }
  return 0;
}

А вот и результат:

    Capacity         Size       Ratio
------------ ------------ ------------
           0            0          NaN
          32            1    32.000000
          64           33     1.939394
         103           65     1.584615
         166          104     1.596154
         268          167     1.604790
         433          269     1.609665
         700          434     1.612903
        1132          701     1.614836
        1831         1133     1.616064
        2962         1832     1.616812
        4792         2963     1.617280
        7753         4793     1.617567
       12544         7754     1.617746
       20296        12545     1.617856
       32838        20297     1.617875
       53131        32839     1.617924
       85965        53132     1.617952
      139091        85966     1.617977
      225049       139092     1.617987
      364129       225050     1.617992
      589160       364130     1.617994
      953260       589161     1.617996
     1542374       953261     1.617998
     2495561      1542375     1.617999
     4037817      2495562     1.617999
     6533187      4037818     1.617999
    10570696      6533188     1.618000
    17103386     10570697     1.618000
    27673278     17103387     1.618000
    44775363     27673279     1.618000
    72446537     44775364     1.618000
   117218496     72446538     1.618000
   189659526    117218497     1.618000
   306869113    189659527     1.618000

Выходит, что для моей STL - это какой-то магический коэффициент 1.618.

Update: В комментариях подсказали хорошую ссылку на тему стратегии управления размером вектора.

Update 2: Лично мой ответ на тему вычислительной сложности последовательного добавления элементов в вектор, если вектор будет удваивать размер буфера при переполнении.

Так как мы добавляем k элементов, то это как минимум O(k). А так как по условию вектор удваивает буфер каждый раз, когда нет места, то произойдет log2(k) раз (так как по условию элементы поступают последовательно).

Получаем в этоге: O(k*log2(k)).

Update 3: В комментариях меня поправили: O(k + log2(k)) или просто O(k)