Interesting C/C++ interview questions

roadman · Post by **roadman** » 15 Apr 2004 06:48

Как сделать так, чтобы объект класса можно было создавать
1. только динамически.
2. только статически.

Rookie · Post by **Rookie** » 15 Apr 2004 13:17

Tango wrote:"Now, how to access the n-th bit of a word without a bit-shift operation?"

Умножением единицы на 2 необходимое число раз, пока не получится нужная маска?

Tango wrote:....а уже на десерт:
"How to access the n-th bit of a word without a bit-shift or mask operation?"

Делить на 2 пока нужный бит не станет LSB, а потом взять результат модулю 2?

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

Rookie · Post by **Rookie** » 15 Apr 2004 15:00

Tango wrote:А я вот иногда задаю такой вопрос по C:
"How to access the n-th bit of a word?"

а после того как интервьюируемый ответит (well, если ответит ):
"Now, how to access the n-th bit of a word without a bit-shift operation?"

....а уже на десерт:
"How to access the n-th bit of a word without a bit-shift or mask operation?"

На эту тему есть еще задачка: как посчитать количество бит в слове, установленных в единицу, за время, линейно растущее с количеством таких бит (а не с общим размером слова, как было бы в случае прохода маской)?

Mongush · Post by **Mongush** » 15 Apr 2004 16:13

Hamster wrote:
Sullen wrote:Ну зачем же? Достаточно сделать private destructor.

У private destructor будет побочный эффект - объекты можно будет создавать только динамически через new и потом удалять только через функцию-член класса.

По моему лучший вариант, это иметь такой класс

Code: Select all

template <typename T>
class FinalMaker
{
private:
  ~FinalMaker() { };
  friend T;
};

И всякий раз, когда хочеться запретить наследоваться от каково либо класса делать так

Code: Select all

class FinalClass : virtual public FinalMaker<FinalClass>
{
};

A. Fig Lee · Post by **A. Fig Lee** » 15 Apr 2004 16:32

Rookie wrote:
Tango wrote:А я вот иногда задаю такой вопрос по C:
"How to access the n-th bit of a word?"

а после того как интервьюируемый ответит (well, если ответит ):
"Now, how to access the n-th bit of a word without a bit-shift operation?"

....а уже на десерт:
"How to access the n-th bit of a word without a bit-shift or mask operation?"

На эту тему есть еще задачка: как посчитать количество бит в слове, установленных в единицу, за время, линейно растущее с количеством таких бит (а не с общим размером слова, как было бы в случае прохода маской)?

Использовать ((x)&((x)-1))

adb · Post by **adb** » 15 Apr 2004 16:46

roadman wrote:Вот ещё пример из реальной практики
....
Вопрос, чему будут равны resAdd и resSub?

Ответ 8 и 2. А то, что MSVC 6.0 на этом спотыкается, так это проблема MSVC6 (точнее одна из многих его проблем с шаблонами). Intel 8.0 выдает корректный результат.

AndreyT · Post by **AndreyT** » 15 Apr 2004 18:24

Hamster wrote:В assert'ах нужно поставить >=.

Да, это так.

Обращаться к элементам после reserve() не следует. В теории это приводит к undefined behavior.

В общем случае это так. Но в данном конкретном случае - нет. Т.к. в данном случае элементами вектора являются объекты POD типа (int), с ними можно полноценно работать сразу после выделения памяти.

На практике, разумеется, работать с элементами вектора зха пределами его 'size' не стоит, даже если это POD элементы.

На практике у вас, скорее всего, просто потеряются значения в 0 & 1 при втором вызове reserve().

Значения, разумеется, потеряются. Также цикл еще до второго 'reserve' ничего не напечатает потому, что у этого вектора 'begin() == end()'.

< можно использовать для итераторов с произвольным доступом, к каковым относится итератор в векторе.

Да, это так.

В данном случае нет никакой разницы, использовать i++ или ++i.

Функционально - нет. С точки зрения теоретической производительности - есть. С точки зрения практической производительности - обычно опять нет, ибо у вектора итератор обычно реализуется указателем.

После cout'ов в середине забыли endl.

А может и не хотели?

Два раза повторять for(vector<int>::iterator i=... ) нежелательно, так как некоторым старым ( и не очень старым ) компиляторам эта конструкция не нравится.

Желательно, желательно. А с подобными глюками конкретных компляторов борются отдельно. Через

#define for if (false); else for

например. Или еще как.

AndreyT · Post by **AndreyT** » 15 Apr 2004 18:41

Обращаться к элементам после reserve() не следует. В теории это приводит к undefined behavior.

В общем случае это так. Но в данном конкретном случае - нет. Т.к. в данном случае элементами вектора являются объекты POD типа (int), с ними можно полноценно работать сразу после выделения памяти.

Хотя скорее всего я неправильно понял, о каком именно undefined behavior ты ведешь речь. Сам факт доступа к элементам за пределами 'size' при помощи '[]' порождает undeifned behavior.

AndreyT · Post by **AndreyT** » 15 Apr 2004 18:53

Rookie wrote:На эту тему есть еще задачка: как посчитать количество бит в слове, установленных в единицу, за время, линейно растущее с количеством таких бит (а не с общим размером слова, как было бы в случае прохода маской)?

Вообще-то если время и завязано на размер слова, то оно не обязательно завязано на него именно линейно. Классический алгоритм подсчета единичных битов завязан на размер слова логарифмически, а не линейно. Например, для восьмибитного байта 'n'

Code: Select all

n = (n & 0x55) + ((n >> 1) & 0x55);
n = (n & 0x33) + ((n >> 2) & 0x33);
n = (n & 0x0f) + ((n >> 4) & 0x0f);
// Теперь 'n' содержит кол-во единичных битов в
// изначальном значении 'n'

aleh · Post by **aleh** » 15 Apr 2004 19:37

Rookie wrote:
Tango wrote:"Now, how to access the n-th bit of a word without a bit-shift operation?"

Умножением единицы на 2 необходимое число раз, пока не получится нужная маска?

Tango wrote:....а уже на десерт:
"How to access the n-th bit of a word without a bit-shift or mask operation?"

Делить на 2 пока нужный бит не станет LSB, а потом взять результат модулю 2?

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

Так деление или умножение тот же шифт и есть даже хуже.
А на последний вопрос можно еще и union предложить создать
с переменной на каждый бит

nastya12 · Post by **nastya12** » 15 Apr 2004 20:36

roadman wrote:Как сделать так, чтобы объект класса можно было создавать
1. только динамически.
2. только статически.

Сделать private default constructor - объект будет можно создать только статически...

А что нехорошего надо сделать чтобы, наоборот, можно было только динамически? Разве что сделать class abstract (и возможно virtual, for other purposes), но тогда, на самом деле, динамически можно будет создать все равно только instance subclassа

muzhik · Post by **muzhik** » 15 Apr 2004 20:51

nastya12 wrote:
roadman wrote:Как сделать так, чтобы объект класса можно было создавать
1. только динамически.
2. только статически.

Сделать private default constructor - объект будет можно создать только статически...

Ммм... по-моему, это не совсем то.Какая вообще связь? Если это единственный конструктор - то объекты вообще будет невозможно создавать; а если есть другие - то можно будет создавать и динамически... (Или я чего-то не понял в вопросе или ответе...?...)

На 1) решение простое - сделать конструкторы private и provide static member function returning pointer to the created new object.

muzhik · Post by **muzhik** » 15 Apr 2004 21:01

Настя, допёр наконец-то, что именно Вы имели в виду...

Code: Select all

class A {
private:
    A() {}
public:
    static A m_a;
};

A A::m_a;

А я совсем иначе понял условие... подумал было, что "статически" = "нединамически", и долго недоумевал, какая с точки зрения конструктора разница между A a; и A* p = new A;....

nastya12 · Post by **nastya12** » 15 Apr 2004 21:10

Я так поняла что никаких больше конструкторов нет в классе, так как объекты создаются только статически...

А где вы memory deallocate? (Ту которя была дана динамически (?) в вашем псевдоконструкторе, который reference возвращает)

PS> А, Вы просто по-другому поняли условие.. :gen1:

PPS> Нет, я не совсем это имела в виду... Я _не_ имела в виду сделать какие-то static data members. Просто, если конструктор сделать private, A a возможно, a A *a = new A() - нет...

PPPS> А СтасаП брат-близнец появился?

...

muzhik · Post by **muzhik** » 15 Apr 2004 21:20

nastya12 wrote:Я так поняла что никаких больше конструкторов нет в классе, так как объекты создаются только статически...

А где вы memory deallocate? (Ту которя была дана динамически (?) в вашем псевдоконструкторе, который reference возвращает)

Нет, он поинтер возвращает. Удалять можно либо такой же функцией, либо обычным delete - в зависимости от того, скрываем мы деструктор, или нет - полная аналогия с конструктором. Вот:

Code: Select all

class B {
public:
    static B* pseudo_ctor() { return new B; }
    static void pseudo_dtor(B* p) { delete p; }
private:
    B() {}
    ~B() {}
};

class C {
public:
    static C* pseudo_ctor() { return new C; }
    ~C() {}
private:
    C() {}
};

void main()
{
    B* p1 = B::pseudo_ctor();
    B::pseudo_dtor(p1);

    C* p2 = C::pseudo_ctor();
    delete p2;
}

PS> А, Вы просто по-другому поняли условие..

Угу, причём глупо попался в расставленую лингвистическую ловушку...