среда, 1 августа 2012 г.

Как я провалил собеседование по теме C/C++/Linux

Подробности того, как я провалил простое собеседование

Предисловие

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

Сегодня состоялось собеседование по скайпу с сотрудниками компании. Собеседование я, с большой долей вероятности, провалил. Прежде всего из-за элементарного недостатка знаний по некоторым деталям. Хотя, пару-тройку вопросов я элементарно не додумал. Так часто бывает в обстановке экзамена :)

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

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

Как бы там не было, думаю, что многим интересны будут вопросы, которые могут задать по профилю C/C++/Linux. Именно этим профилем занимаюсь я, и именно по этому профилю было проведено собеседование, отчёт о котором я хочу здесь представить.

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

Практические вопросы

Системный вызов fork(), стандартные потоки ввода/вывода

  1. Что вы можете сказать о следующем фрагменте кода? Есть ли в нем ошибки? Дайте максимальные комментарии о работе этого кода.
  2. Откомпилируется ли представленный фрагмент кода? Если откомпилируется, то что будет при запуске?
  3. Нужно ли изменить программу в строке с вызовом fprintf(), чтобы надпись "Hello" печаталась два раза? Если нужно, то как?
  4. Нужно ли изменить программу в строке с вызовом fprintf(), чтобы надпись "Hello" печаталась один раз? Если нужно, то как?
#include <stdio.h>

int main()
{
  fprintf(0, "Hello");
  fork();
  return 0;
}

Знаковые и беззнаковые типы разной ёмкости

Что будет лежать в A после исполнения следующего фрагмента кода?

int  A = 128;
char B = A;
  A = B;

Виртуальный деструктор

Что будет напечатано при исполнении следующего фрагмента кода? Максимально прокомментируйте этот код. Есть ли в нем принципиальные ошибки и, если есть, то как их исправить?

#include <iоstreаm>

using nаmespаce std;

class Fаther
{
    public:
 Fаther() {}
        ~Fаther() 
        {
         cоut << "~Father" << endl;
        } 
};
 
class Sоn : public Fаther
{
    public:
 Sоn() : Fаther() 
 { 
 }
 ~Sоn() 
        { 
         cоut << "~Son" << endl;
        }
};

int mаin()
{
    Fаther* оbject = new Sоn();
    delete оbject;
}

Игры с указателями

Что будет содержаться в массиве a после исполнения представленного ниже кода?

char a[]="111111111111";
*((int*)a+1) = 0;

Односвязный список

Представьте себе односвязный список. Если у вас есть указатель на произвольный элемент этого списка, то сможете ли вы написать алгоритм корректного удаления этого элемента из списка? Т.е. такого удаления, при котором не нарушается связанность левой и правой частей списка.

Теоретические вопросы

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

  1. Что такое виртуальная память? Что в процессоре ответственно за реализацию виртуальной памяти?
  2. Что вы можете рассказать об архитектурах CISC и RISC? Основные особенности и различия.
  3. Как работают системные вызовы? Как переносятся параметры системного вызова?
  4. Расскажите о системном вызове fork(). Что передается в копию процесса?
  5. Что такое виртуальный конструктор?
  6. Сколько таблиц виртуальных методов может быть в объекте класса? От чего это зависит? Что можно сказать о размещении указателей на них?
  7. Можно ли в конструкторе вызывать виртуальные методы?
  8. Что вы можете рассказать о различиях между std::vector и std::list в плане их внутренней реализации?
  9. Как должен быть оформлен класс, чтобы его объекты могли храниться в std::vector?
  10. Чем отличается процесс от потока?
  11. Разделяют ли потоки стек?
  12. Что такое мьютекс? Что такое семафор? Можно ли семафор использовать для синхронизации процессов?
  13. Какие вы знаете средства взаимодействия процессов? Могут ли процессы иметь общую память?

Хочу дать единственный комментарий к вопросу о количестве таблиц виртуальных методов. Прежде чем отвечать наверняка вспомните и подумайте о множественном наследовании. Здесь вас могут легко запутать.

Комментарии к практическим вопросам

Системный вызов fork(), стандартные потоки ввода/вывода

#include <stdio.h>

int main()
{
  fprintf(0, "Hello");
  fork();
  return 0;
}

Конечно же в представленном коде есть ошибки. Прежде всего, нулевой указатель на поток не приведет ни к чему хорошему, учитывая, что здесь, очевидно, хотят сделать вывод строки в поток. Такой код откомпилируется, так как синтаксически он корректен, но приведет к segmentation fault.

Если в качестве потока вывода указать поток stdout, т.е. написать fprintf(stdout, "Hello"), то надпись будет выведена два раза, так как поток stdout буферизируется и при создании копии процесса, также будет сделана копия буферов stdout. Поэтому, при завершении обоих процессов, буферы каждого будут сброшены и на терминале появятся две надписи "Hello".

Если в качестве потока вывода указать поток stderr, т.е. написать fprintf(stderr, "Hello"), то надпись будет выведена только один раз, так как поток stderr не буферизован и поступившие в него данные сразу будут выброшены на устройство вывода связанное с данным потоком. Функция fork() будет выполнена только после этого.

Знаковые и беззнаковые типы разной ёмкости

Что будет лежать в A после исполнения следующего фрагмента кода?

int  A = 128;
char B = A;
  A = B;

Тип char представляет собой знаковый однобайтовый тип, поэтому число 128, которое будет в него записано будет интерпретироваться как отрицательное число в дополнительном коде. Следовательно, при обратном присвоении мы получим число (-128).

Виртуальный деструктор

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

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

Игры с указателями

char a[]="111111111111";
*((int*)a+1) = 0;

Имя массива в C/C++ является адресом его начального элемента. Приведя этот адрес к указателю на целое число мы получаем указатель на следующие четыре байта целого (для вычислительных систем, где int занимает четыре байта). Инкремент этого указателя сдвигает адрес указателя на четыре байта (столько занимает начальный элемент массива из элементов типа int). Следовательно разыменуемый адрес указывает на четыре байта памяти, сдвинутые относительно исходного адреса на четыре байта. После обнуления этих четырех байт мы получим, что в массиве a будет лежать "1111\000\000\000\0001111". В этой записи, согласно стандарту Си, литерал '\000' представляет собой восьмиричную запись однобайтового значения.

Односвязный список

Вот по поводу этого вопроса я ничего сказать не могу. Априори был уверен, что сделать это нельзя. На собеседовании меня уверили, что можно. Буду думать. Если придумаю, то может найду время написать об этом.

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

И еще один момент. Я специально спрашивал насчёт указателя на начало списка. Указатель не дали. И ещё раз уточнили. Дан односвязный список и указатель только на тот внутренний элемент списка, которые требуется корректно удалить. В общем, выглядит задачка как полный бред. Как заметил один мой коллега, Дубровин Алексей, за эту задачу компании должна быть назначена премия Тьюринга по теме "Как утечку памяти превратить в связанный список" :).

Спустя неделю. Прошла неделя с момента публикации этого сообщения и я подумал, что имеет смысл опубликовать размышление моих коллег по этой задаче. Сначала коллеги из "Мирантис", потом Михаил Сёмичев из "ЕПАМ" (все это наши местные отделения распределенных аутсортинговых компаний) и, наконец, Владимир Легкий из компании "Волга-софт" предположили, что возможно речь идет о следующем решении. Если не заниматься движениями указателей, а выполнить смещение данных относительно удаляемого элемента, то решение получается простое, но имеет одно ограничение. Оно не работает для случая, если указатель задачи указывает на последний элемент.

Поясню решение. Оно может быть в нескольких вариантах, но в одной сути.

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

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

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

oscar fox комментирует...

По поводу односвязного списка. Возможно тут игра слов - вам дали не АДРЕС элемента, а УКАЗАТЕЛЬ на элемент который нужно удалить. Если указатель *p, тогда *p_tmp = p,
p=p->next, free(p_tmp).

vbuldakov комментирует...

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

Мазитов Евгений комментирует...

По условию был дан элемент из середины односвязного списка. та что не последний. ;)

Андрей Белозор комментирует...

Компания наверное была Samsung?^_^

Bilokur Sergiy комментирует...

T *p; // указатель на объект, который нужно удалить
T *pNext = p->next;
std::swap(*p,*p->next); // меняем местами объекты
delete pNext;
// теперь pNext уазывает на объект, на который указывал раньше p, и наоборот p уже указывает на следующий объект в списке
// тоесть указатель next предыдущего объекта будет указывать на ту же область памяти, что и раньше, но в ней уже будет другой объект
// тоесть целостность списка не нарушилась
// и мы имеем указатель на pNext? который указывает на перемещенный объект, который нужно удалить