Interesting C/C++ interview questions

[A. Fig Lee]

Есть
при i++ создается временная преременая.

А оптимизация на что?

Ну если оптимизация еще както.. То endl() - уж точно никаким боком - мож так задумано?

[Izh]

вот мне недавно задали вопрос, что произойдёт при попытке выполнения вот этого кода:

Code: Select all

typedef struct {
    char a;
    char b;
} someStruct;

int
main ( int, char** )
{
    someStruct     ss;
    someStruct* pSS;

     pSS = ( someStruct* ) ss;
     pSS->a = 'a';
     printf ( "%c\n", ss.a );

     return 0;
}

указания на факт, что statement pSS = ( someStruct* ) ss; в принципе -бессмыслица не принимаются.

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

Допустим имеется следующий код:

Code: Select all

typedef
struct
    {
    char a;
    } SomeStruct;

int main()
{
    SomeStruct  ss;

    printf( "ss = 0x%08x\n", &ss ); 

    return 0;
}

GNU C, например, генерит следующий ассемблер в случае, когда вызывается
printf( "ss = 0x%08x\n", &ss ):

Code: Select all

       ...
       leal    -2(%ebp), %eax  ; Получаем адрес ss
       pushl   %eax               ; ...и записываем его в стек
       pushl   $.LC0
       ...

Когда, же вызывается printf( "ss = 0x%08x\n", ss ), ассемблер получается такой:

Code: Select all

       ...
       pushw   -2(%ebp)        ; Совсем не то, что нужно
       pushl   $.LC0            
       ...   

[Шоколадина]

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

1. На вход программы должно поступить ((2 в 32-ой) - 1) положительных целых чисел размером 4 байта. Известно заранее, что все они разные. Задача: написать программу, использующую МИНИМУМ ПАМЯТИ, которая определяет, какое именно число (а оно, как понятно, ровно одно) НЕ поступало на вход программы.

2. Есть массив, состоящий из M+N элементов.

[A1] [A2] .... [Am] [Am+1] .... [Am+n]

Задача: за МИНИМУМ ВРЕМЕНИ и используя КОНЕЧНУЮ (т.е. не зависящую от M и N) ПАМЯТЬ, переставить части массива местами (см. рис.).

[Am+1] [Am+2] .... [Am+n] [A1] [A2] .... [Am]

3. Даны результаты выборов, на которых (10 в 9-ой) избирателей проголосовали за (10 в 6-ой) кандидатов - каждый, естественно, голосовал за кого-то одного. Есть (10 и 3-ей) свободных ячеек памяти (результаты выборов, разумеется, менять нельзя - задачка не российская). Определить кто победил в такой ситуации нельзя, но можно, ПРОЙДЯ МАССИВ (10 в 9-ой) МИНИМУМ РАЗ, узнать, выиграл ли кто-то из кандидатов уже в первом туре (т.е., проще говоря, определить, кто набрал более 50% всех голосов).

4. Есть некая операционная система, в которой определены следующие функции, ответственные за аллокацию памяти:

void* OS_alloc(unsigned int);
void OS_free(void*, unsigned int);

Надо написать оптимальную имплементацию следующих функций:

void* alloc(unsigned int);
void free(void*);

5. Дан односвязный список элементов, причем возможно, что этот список замкнут в "петлю", т.е. один из элементов списка указывает на один из предшествующих ему элементов. Используя КОНЕЧНЫЙ объем памяти, найти "соединение" этой петли или конечный элемент списка.

Если кому нужны ответы, предоставим с открытой душой.

[SlaMin]

1. На вход программы должно поступить ((2 в 32-ой) - 1) положительных целых чисел размером 4 байта. Известно заранее, что все они разные. Задача: написать программу, использующую МИНИМУМ ПАМЯТИ, которая определяет, какое именно число (а оно, как понятно, ровно одно) НЕ поступало на вход программы.

Если следовать условиям задачи, и домыслить, что требуется найти то число, из диапазона НЕОТРИЦАТЕЛЬНЫХ чисел представимых четырмя байтами, которое не поступило на вход программы, то результат известен сразу - ноль

Ну а если не умничать, то МИНИМУМ ПАМЯТИ это 4-ре байта (записываем туда ноль и XORим со всеми по очереди).

[Hamster]

2) решается рекурсией, хотя немного мутно. Три случая:
(а) m = n. Делаем m swap'ов, задача решена.
(b) m > n. Делаем n swap'ов, m' = m-n, n' = n, повторяем.
(c) m < n. Делаем m swap'ов, m' = m, n' = n-m, повторяем.
3) hash-table, два прохода.
4) Определить, есть петля или нет, можно в линейное время с фиксированным объемом памяти. А вот найти "соединение"? ... Пока вижу только решение в квадратичное время.
P.S. А, нет, можно и в линейное.

[olg2002]

2) решается рекурсией, хотя немного мутно. Три случая:
(а) m = n. Делаем m swap'ов, задача решена.
(b) m > n. Делаем n swap'ов, m' = m-n, n' = n, повторяем.
(c) m < n. Делаем m swap'ов, m' = m, n' = n-m, повторяем.

Простого цикла достаточно:
next = cur + m mod m+n;
A[idx] = A[next];
idx = next;

добавлено> OK, двух циклов: второй по 1...GCD(m,n)

[Sullen]

Если класс не задумывался как базовый, почему бы не использовать struct?

Так ведь объявление типа через struct не запрещает наследование.

Оно объясняет смысл данного элемента данных.
99% что никому не прийдет в голову наследоваться от struct в дальнейшем

Неужели нельзя "запечатать" класс собственными средствами С++? Не верю.

А как интересно? Можно конечно не использовать виртуальных функций и protected членов (о чем уже упоминалось) и тогда от наследования не будет особого толку, хотя сама возможность и будет присутствовать.
Как запретить наследование от данного класса - разве что сделать все конструкторы приватными и создавать обьекты статической функцией?

Ну зачем же? Достаточно сделать private destructor.
Ваше предложение более подходит для создания singleton. Причем если верить Мейерсу для создания экземпляра класса, в этом случае, лучше использовать friend function.
Понятно, что она вне области видимости класса. Но она фактически является элементом его интерфейса, что улучшать инкапсуляцию класса.

[Sullen]

Посмотрел вопросы для чайников и понял, что я даже в чайники не гожусь. xотя я пограмаю на C ++ более 5 лет и, главное, это меня кормит, приносит "башки" моей компании и удовлетворение клиентам.

Вот например, первый вопрос из http://v.psiola.ru/cpp/index.htm для чайников.


Cколько символов "A" выведет на экран следующая программа:

#include <iostream>
using namespace std;
struct A
{A(){cout << "A";}; ~A(){cout << "A";};};
struct B : public A
{B(){cout << "B";}; ~B(){cout << "B";};};
struct C : public B
{C(){cout << "C";}; ~C(){cout << "C";};};
int main() {C c;return 0;}



Я не знаю ответ, а главное и знать не хочу
Я не доумеваю, для чего нужны такие тесты?! Зачем их используют при приеме на работу?
Может кто-нибудь занает ответы ...
Паша

Что бы было понятно, программирует человек хотя бы 5 месяцев на С++ или нет.

[Hamster]

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

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

[Sullen]

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

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

А у private constructor, никаких побочных эффектов не предвидится?

[roadman]

Есть
при i++ создается временная преременая.

А оптимизация на что?

Если i это int, то компилятор оптимизирует. А вот если это, как в примере, целый класс - iterator, то разница большая. Посмотрите на реализацию STL контейнера list:
iterator operator++() { _ptr = _ptr->_next; return *this; }
iterator operator++(int) { iterator tmp = _ptr; _ptr = _ptr->_next; return tmp; }
происходит полная копия объекта iterator. А если Вы переопределили эти операторы для более "тяжелого" класса?

[roadman]

Вот ещё пример из реальной практики
template < typename T1, typename T2, typename С >
T1 do_something(T1 var1, T2 var2)
{
С convertor;
return convertor.convert(var1, var2);
}

template < typename T1, typename T2 >
class RIntAdd
{
public:
T1 convert(T1 var1, T2 var2) { return var1 + var2; }
};

template < typename T1, typename T2 >
class RIntSub
{
public:
T1 convert(T1 var1, T2 var2) { return var1 - var2; }
};


int main()
{
int resAdd = do_something< int, int, RIntAdd< int, int > >(5, 3);
int resSub = do_something< int, int, RIntSub< int, int > >(5, 3);
return 0;
}

Вопрос, чему будут равны resAdd и resSub?

[roadman]

Достоинства и недостатки двух методов обработки exception
class exep
{
public:
exep(int err) : _error(err) {}
int get_code() const { return _error; }
private:
int _error;
};

int main()
{
try
{
throw new exep(1);
}
catch (exep* x)
{
cout << x->get_code();
delete x;
}

try
{
exep x(1);
throw x;
}
catch (exep& x)
{
cout << x.get_code();
}

[roadman]

Что "лучше" работает

If (x == 0)
cout << "step 0";
else if (x == 1)
cout << "step 1";
else if (x == 2)
cout << "step 2";
else if (x == 10)
cout << "step 10";
else
cout << "step unknown";

или

switch (x)
{
case 0:
cout << "step 0";
break;
case 1:
cout << "step 1";
break;
case 2:
cout << "step 2";
break;
case 10:
cout << "step 10";
break;
default:
cout << "step unknown";
}


Это любителям "C"

[Tango]

А я вот иногда задаю такой вопрос по 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?"