Вопросы программисту C/C++ на собеседовании с ответами

Заметил, что на собеседовании часто задают одни и те же вопросы по программированию. Если бы брали на работу водителя, то некоторые вопросы звучат примерно так:

  • В какую сторону надо крутить руль, чтоб повернуть направо?
  • За что отвечает педаль сцепления/тормоза/газа?

Такое конечно случается далеко не всегда, но первые пару вопросов обычно такого рода («А какую надо давить педаль, чтоб автомобиль остановился?»). Публикую свои ответы на некоторые вопросы для программистов. Вдруг кому пригодится.. Возможно, здесь много ошибок и помарок — при составлении этого списка я не пользовался интернетом. Старался выдать, что знаю сам.

Как можно оптимизировать данный цикл?

void func(int *array, int len)
{
    for (int i = 0; i < len; i++)
    {
        array[i] = array[i] * array[i];
    }
}

Вот таким образом:

void func(int *array, int len)
{
    const int *end = array + len;
 
    while (array != end)
    {
        const int value = *array;
        *array++ = value * value;
    }
}

В исходном цикле каждый раз происходит вычисление позиции элемента в массиве array. Переписав функцию мы избавляемся от этого вычисления.

В чем отличие std::list<T> от std::vector<T>?

std::vector<T> — это обертка над обычным С/C++ массивом. Соответственно:

  • если std::vector<T> заполнен, то при добавлении нового элемента, массив удаляется целиком и создается заново с бОльшим размером
  • любой элемент массива можно получить моментально, потому что позиция элемента вычисляется банальным прибавлением индекса к первому элементу (array[i] = array + i)
  • удаление любого элемента из массива, кроме последнего, приведет к перемещению всех элементов справа от удаляемого на одну позицию влево (при соблюдении некоторых условий, можно воспользоваться хаком)
  • занимает неразрывный блок памяти

std::list<T> — это список элементов, которые связаны между собой указателями prev (предыдущий элемент) и next (следующий элемент). Внутри себя std::list<T> хранит указатель на первый элемент и последний (зависит от реализации). Исходя из этого:

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

В языке Java различия между ArrayList и LinkedList практически такие же.

Почему в C++ нужно использовать new вместо теплого лампового malloc()?

Потому что malloc() тупо выделяет блок памяти и возвращает этот блок программисту. А new выделяет память и вызывает конструктор объекта. Тоже самое относится к delete и free(). delete вызывает деструктор и освобождает память. free() просто освобождает память. Также есть размещающий new, который создает объект в уже выделенной вами памяти.

Кстати, изначально конструкторы и деструкторы классов в C++ назывались new и delete и выглядели вот так:

class SomeClass
{
    // Конструктор
    void new();
 
    // Деструктор
    void delete()
};

В чем отличие между new/delete и new[]/delete[]?

new выделяет память для одного элемента и вызывает конструктор для него, в то время как new[] выделяет память для массива элементов и вызывает конструктор для каждого из них. delete должен вызываться для объекта выделенного с помощью new, а delete[] для массива, выделенного с помощью new[]. От проблем соответствия new/delete вас могут избавить классы std::auto_ptr<T> (для одного элемента) и std::tr1::scoped_array<T> (для массива элементов). Которые сами вызывают правильный delete в деструкторе.

Для чего нужен тип std::auto_ptr<T>?

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

bool func()
{
    Stream *stream = new Stream;
 
    if (0 != stream->open("some stream"))
    {
        delete stream;
        return false;
    }
 
    if (0 != stream->load())
    {
        delete stream;
        return false;
    }
 
    // Выполняем полезную работу
    // Закончили полезную работу
    delete stream;
    return true;
}

После появление std::auto_ptr<T> стало возможным переписать функцию таким образом:

bool func()
{
    std::auto_ptr<Stream> stream(new Stream);
 
    if (0 != stream->open("some stream"))
    {
        // Здесь "delete stream" вызывается автоматически
        return false;
    }
 
    if (0 != stream->load())
    {
        // Здесь "delete stream" вызывается автоматически
        return false;
    }
 
    // Выполняем полезную работу
    // Закончили полезную работу
 
    // Здесь "delete stream" вызывается автоматически
    return true;
}

И еще очень важный момент: std::auto_ptr<T> владеет объектом единолично. Вы не сможете шарить объект между двумя std::auto_ptr<T> (используйте в таких случаях std::shared_ptr<T>):

void func() 
{
    Object *object = new Object;
 
    std::auto_ptr<Object> ptr1(object); // object теперь живет внутри ptr1
    std::auto_ptr<Object> ptr2(ptr1); // ptr1 опустел, object внутри ptr2
 
    // здесь деструктор ptr2 удалит object
    // а здесь вызовется деструктор ptr1 впустую
}

И помните: std::auto_ptr<T> не подходит для массивов выделенных с помощью new[]. Для этих целей используйте std::tr1::scoped_array<T> или boost::scoped_array<T>.

Что такое RAII?

Это переводится как «Получение ресурса есть инициализация». Идея вкратце такая: в конструкторе открываем/блокируем ресурс, в деструкторе закрываем/освобождаем ресурс. Вот пример:

class FILEWrap
{
public:
    FILEWrap( const char *fileName )
        : f_(fopen(fileName, "rb"))
    {
    }
 
    ~FILEWrap()
    {
        if (f_)
        {
            fclose(f_);
        }
    }
 
private:
    FILE *f_;
};

Или более каноничный пример (блокирование мьютекса или критической секции):

class MutexLock
{
public:
    MutexLock(Mutex &mutex)
        : mutex_(mutex)
    {
        mutex.lock();
    }
 
    ~MutexLock()
    {
        mutex.unlock();
    }
 
private:
    Mutex &mutex_;
};

Зачем нужен виртуальный деструктор?

Попробуем обойтись без него:

#include <stdio.h>
 
class A
{
public:
    A() 
    { 
        printf("construct A\n"); 
    }
 
    ~A() 
    { 
        printf("destruct A\n"); 
    }
};
 
 
class B : public A
{
public:
    B() 
    { 
        printf("construct B\n"); 
    }
 
    ~B() 
    { 
        printf("destruct B\n"); 
    }
};
 
 
int main()
{
    B *b = new B;
    A *a = b;
    delete a;
}

Вывод:

construct A
construct B
destruct A

Как можно заметить деструктор B не вызвался. Сделаем деструктор класса A виртуальным и посмотрим что получится:

#include <stdio.h>
 
class A
{
public:
    A() 
    { 
        printf("construct A\n"); 
    }
 
    virtual ~A() 
    { 
        printf("destruct A\n"); 
    }
};
 
 
class B : public A
{
public:
    B() 
    { 
        printf("construct B\n"); 
    }
 
    ~B() 
    { 
        printf("destruct B\n"); 
    }
};
 
 
int main()
{
    B *b = new B;
    A *a = b;
    delete a;
}

Теперь все отлично:

construct A
construct B
destruct B
destruct A

В каком порядке инициализируются члены класса?

Члены класса создаются в порядке их объявления в классе. Уничтожаются они в обратном порядке. Давайте проверим:

#include <stdio.h>
 
class Printer
{
public:
    Printer( const char *n ) 
        : n_(n)
    {
        printf("+%s ", n_);
    }
 
    ~Printer() 
    {
        printf("-%s ", n_);
    }
 
private:
    const char *n_;
};
 
 
class A : public Printer
{   
public:
    A() 
        : Printer("A") 
    {
    }
};
 
 
class B : public Printer
{
public:
    B() 
        : Printer("B") 
    {
    }
};
 
 
class C : public Printer
{
public:
    C() 
        : Printer("C") 
    {
    }
};
 
 
class Test
{
private:
    A A_;
    B B_;
    C C_;
};
 
 
int main()
{
    Test test;
}

Запустим:

+A +B +C -C -B -A

Все правильно.

Порядок объявления очень важен, если один член класса во время инициализации использует данные другого члена. Кстати, компилятор gcc выдает warning (с флагом -Wall), если вы описали инициализацию членов класса в другом порядке. И это еще одна причина в пользу использования настройки компилятора «считать предупреждения ошибками» (в gcc это флаг -Werror).

Отвратительно!Ужасно.НормальноХорошо.Отлично! (12 оценок, среднее: 4.75 из 5)
Загрузка...

Ваши комментарии к статье:

  1. задан массив символов вывести на печать те из них которые являются символами!

    • Странное ТЗ. Решение: поскольку это массив символов, то каждый элемент массива является символом, значит надо вывести все элементы. :)

      • видимо он имел в виду массив типа char и из него выводить только символы, являющиеся буквами )

        Евгений, спасибо за интересную статью!

        Я вот хожу на собеседования (и успешно их проваливаю кстати, т.к. ++ для меня, увы, новый язык, хотя и очень интересный)

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

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

        Так же я заметил, что в инете — много теоритических вопросов с краткими ответами, но я пока не находил примеров тестовых задач для собеседований Си++.. Вот если у вас такие имеются — то очень здорово было бы выложить их (хотя бы сами задания (без решения) (а лучше с решением ;) )

        спасибо Вам)

        Вот например в 2gis, перед приглашением на собеседование — дают задачу (тестовое задание перед собеседовнием) напечатать чек сумму файла (там тематика машинного слова и порядка байтов встречается), так же программа может считать кол-во слов в файле и смещение слов в файле (видимо это для того что бы можно было сделать один базовый класс и 3 производных класса для чексуммы, подсчета и смещений) ну и парсинг аргументов — например если делать свой — то поставят минус за этот пункт, если использовать gnu getopt (поставят +/- — т.к. не свой но и не ооп) — ну а как правильно я не знаю (предполагаю что boost::program_options)

        • Спасибо за добрые слова!

          Статья написана в далеком 2012 году под впечатлением от походов на собеседования. Каждый раз, после начала нашего общения с тимлидом, практически сразу был вопрос: чем отличается std::vector от std::list (а в голове в этот момент: «ну йоп твою мать, шо опять?!»).

          На текущем месте работаю уже шестой год подряд, на собеседования не хожу, поэтому не знаю как там сейчас. Наверно, сейчас в моде стандарт C++11x.

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

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

          Одному нравится вставлять всегда и везде boost, который весь такой шаблонный и C++11x (ждать компиляции часами и героически бороться с разбуханием кода), другому нравится использовать легкие сторонние си-библиотеки (между прочим GNU getopt не кросс-платформенный, поэтому Win32 идет лесом), третий хочет разбор командной строки своими силами и чтоб при этом не было аллокаций памяти (и еще учитывать порядок байтов и юникод), четвертому нравится девственно чистый WinAPI и функции с 15-ю аргументами лесенкой.

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

          Спрашивайте, что вас конкретно интересует и я постараюсь ответить (я ведь только с виду такой умный, на самом деле — нет).

          • может надо было спросить что не так с ответом у того кто проводил тестирование?

          • Может надо было, а может не надо.

Оставить комментарий: