Interesting C/C++ interview questions

[A. Fig Lee]

Code: Select all

void f( vector<int>& v )
{
  v[0];      // A
  v.at(0);   // B
}

В чем разница между строчками А и Б?

А кто его знает. Не помню. Лень проверять.
По-моему, [] бросает ексептион если индекс аут оф баунд.

Или, вот, чуть поинтереснее:

Code: Select all

vector<int> v;

v.reserve( 2 );
assert( v.capacity() == 2 );
v[0] = 1;
v[1] = 2;
for( vector<int>::iterator i = v.begin();
     i < v.end(); i++ )
{
  cout << *i << endl;
}

cout << v[0];
v.reserve( 100 );
assert( v.capacity() == 100 );
cout << v[0];

v[2] = 3;
v[3] = 4;
// ...
v[99] = 100;
for( vector<int>::iterator i = v.begin(); i < v.end(); i++ )
{
  cout << *i << endl;
}

Что здесь неправильно? Покритикуйте стиль.

Ну во-первых, не уверен reserve ресервирует стоко скоко указано - может и больше(?) - в стандарт надо лезть, со стула вставать.
2. Not sure что корректно проверять итератор на <> а не != с begin(), end() - кто его знает, как там реализовано (есть в итераторе операторы "<>" - не припомню...). Опьять же, в стандарт лезть надо.
А что там?
P.S. reserve кстати, гарантирует сохранение данных?
Может еще чего?

[Mongush]

Кстати, по теме: я как-то наткнулся на интересный сайт - Guru of the Week. Там у них в архиве множество интересных статей из которых как мне кажется можно "наковырять" очень интересные практические вопросы. Вот для примера:

Code: Select all

void f( vector<int>& v )
{
  v[0];      // A
  v.at(0);   // B
}

В чем разница между строчками А и Б?

Или, вот, чуть поинтереснее:

Code: Select all

vector<int> v;

v.reserve( 2 );
assert( v.capacity() == 2 );
v[0] = 1;
v[1] = 2;
for( vector<int>::iterator i = v.begin();
     i < v.end(); i++ )
{
  cout << *i << endl;
}

cout << v[0];
v.reserve( 100 );
assert( v.capacity() == 100 );
cout << v[0];

v[2] = 3;
v[3] = 4;
// ...
v[99] = 100;
for( vector<int>::iterator i = v.begin(); i < v.end(); i++ )
{
  cout << *i << endl;
}

Что здесь неправильно? Покритикуйте стиль.

С первым примером понятно, at делает проверку, а [] нет.
Во втором примимере, что сразу бросается в глаза i++, лучше использовать ++i еще i<v.end() хотя для вектора это и скорее всего и будет работать, лучше i != v.end().
Ну и самое главное, резервирование памяти не создает элементов.

[Boriskin]

Приятно было увидеть!

void f( vector<int>& v )
{
v[0]; // A
v.at(0); // B
}

В чем разница между строчками А и Б?

Возможно, замечание несколько в стороне, но реализации STL зависят от платформы и компилера. Пришлось как то столкнуться с тем, что под мелкомягким все было тип-топ, а на Маке (под CodeWarrior) аппа издыхала... Из-за реализации STL.

[Hamster]

Предыдущие ораторы уже отметили часть ошибок в примере, хотя в основном неправильно.
В assert'ах нужно поставить >=.
Обращаться к элементам после reserve() не следует. В теории это приводит к undefined behavior. На практике у вас, скорее всего, просто потеряются значения в 0 & 1 при втором вызове reserve().
< можно использовать для итераторов с произвольным доступом, к каковым относится итератор в векторе.
В данном случае нет никакой разницы, использовать i++ или ++i.
После cout'ов в середине забыли endl.
Два раза повторять for(vector<int>::iterator i=... ) нежелательно, так как некоторым старым ( и не очень старым ) компиляторам эта конструкция не нравится.

[Mongush]

Предыдущие ораторы уже отметили часть ошибок в примере, хотя в основном неправильно.
В assert'ах нужно поставить >=.

Почему? Помоему reserve делает capacity именно равной аргументу reserve, если конечно она не была больше.

Обращаться к элементам после reserve() не следует. В теории это приводит к undefined behavior. На практике у вас, скорее всего, просто потеряются значения в 0 & 1 при втором вызове reserve().

reserve никак не влияет на имеющиеся елементы.

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

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

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

Разница есть.

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

Но стандарту это не противоречет, так что это проблемы компиляторов.

[Mongush]

Приятно было увидеть!

void f( vector<int>& v )
{
v[0]; // A
v.at(0); // B
}

В чем разница между строчками А и Б?

Возможно, замечание несколько в стороне, но реализации STL зависят от платформы и компилера. Пришлось как то столкнуться с тем, что под мелкомягким все было тип-топ, а на Маке (под CodeWarrior) аппа издыхала... Из-за реализации STL.

STL уже давно в стандарте, так что это разница в реализации просто разница в поддержке стандарта.
Можно написать, что то работающее под VC но не работающее под стандартом, и наоборот.

[A. Fig Lee]

Предыдущие ораторы уже отметили часть ошибок в примере, хотя в основном неправильно.
В assert'ах нужно поставить >=.

Почему? Помоему reserve делает capacity именно равной аргументу reserve, если конечно она не была больше.

Не-а. Page 485 Стандарта - не меньше! Но могет быть больше. И ето правильно!

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

Разница есть.

Нет.

А по остальным пунктам согласен.

[Mongush]

Не-а. Page 485 Стандарта - не меньше! Но могет быть больше. И ето правильно!

Посмотрел, убедился, согласен.

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

Разница есть.

Нет.

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

[A. Fig Lee]

[quote="MongushЕсть
при i++ создается временная преременая.[/quote]
Точно! Ничья - 1:1.

[Hamster]

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

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

[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. А, нет, можно и в линейное.