суббота, 25 июня 2011 г.

Интересные задачки для собеседований по C++

Помимо выслушивания зазубренных ответов на стандартные вопросы типа

"Что такое полиморфизм?",
"Что представляет собой STL?",
"Какое отличие между std::auto_ptr и boost::shared_ptr?",

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

Вот чтобы выявлять таких вот нерадивых кандидатов, я решил помимо  списка вопросов составить список задачек, которые буду предлагать на собеседованиях. Приглашаю всех поучаствовать в составлении.
  • Заменить в битовом представлении числа самый правый ноль на единицу.
int ReplaceLastZeroWithOne( int i )
{
    return i | ( i + 1);
}

  • Вывести число как последовательность битов в прямом и обратном порядке.
// Решение в лоб
void OutputBitsReverse( int i )
{
    while( i )
    {
        if( i < 2 )
        {
            cout << i;
        }
        else
        {
            short bit = i % 2;
            cout << bit;
        }

        i /= 2;
    }
}
 
void OutputBitsReverse(unsigned val)
{
    unsigned reverseMask = 1;
    printf("%u = ", val);

    for( unsigned i = 1; i <= 32; i++)
    {
        putchar(val & reverseMask ? '1' : '0');
        val >>= 1 ;
    }   
}

void OutputBitsForward(unsigned val)
{
   unsigned forwardMask = 1 << 31;
   printf("%u = ", val);

   for( unsigned i = 1; i <= 32; i++)
   {
      putchar(val & forwardMask ? '1' : '0');
      val <<= 1 ;
   }
}
  • Реализовать функцию atoi() для целых неотрицательных чисел в десятичном формате.
// Решение в лоб, без дополнительных проверок на переполнение
int atoi_( const char* src )
{
    if( !src )
    {
        return 0;
    }
 
    int result = 0;
    int strlen = 0;
    const char* tmp = src;
    char ch;

    while( ch = *tmp++ )
    {
        if( ( '0' > ch ) || ( '9' < ch ) )
        {
            return 0;
        }

        ++strlen;
    }

    while( *src )
    {
        int digit = *src++ - '0';
        double base = 10;
        result += digit * pow( base, --strlen );
    }

    return result;
}

5 комментариев:

  1. Злобный СИшник троллит объектников :))))

    ОтветитьУдалить
  2. Ваш первый пример не работает. Попробуйте его исполнить с параметром 7. В результате получите 15. А правильный ответ 7.
    Вот исправленный вариант:
    int ReplaceLastZeroWithOne( int i )
    {
    return i | 1;
    }

    ОтветитьУдалить
  3. Дано: 7 = 0111
    Задание: ReplaceLastZeroWithOne(заменить крайний правый нулевой бит на единицу)
    Результат: 15 = 1111

    Что не так?

    ОтветитьУдалить
  4. Всё правильно. Я воспринял постановку задачи таким образом, что нужно заменить ноль в самом правом разряде. А вы имели ввиду самый правый ноль. Я попался в вашу ловушку.

    ОтветитьУдалить