Форум программистов, компьютерный форум CyberForum.ru

Практические задания из собеседований - C++

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 432, средняя оценка - 4.73
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2295 / 1665 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
31.05.2011, 10:02     Практические задания из собеседований #1
Предлагаю в данной теме выкладывать интересные и не очень практические задачи, которые попадаются на собеседованиях.
Я начну:

1. Написать функцию, определяющую является ли заданное число степенью двойки.
2. Написать функцию, определяющую содержит ли односвязный список циклы (например, последний ссылается на второй).

Просьба решения выкладывать под CUT'ом.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ForEveR
Модератор
Эксперт С++
 Аватар для ForEveR
7955 / 4717 / 318
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
07.07.2012, 15:51     Практические задания из собеседований #21
MikeSoft, Итого для добавления нового типа нам нужно.
1) Добавить значение в перечисление.
2) Сделать реализацию четырех функций Add(type), Add(type*), Insert(int, type), Insert(int, type*).
3) Поправить свитч.

Не слишком много?) Не, я не говорю ничего против, как локальное решение свитч по типам годится, но только как локальное и практически не расширяемое.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1285 / 1219 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
07.07.2012, 16:59     Практические задания из собеседований #22
Цитата Сообщение от ForEveR Посмотреть сообщение
Не слишком много?)
В принципе не сложно заменить свитч на мэп и вместо перечисления использовать RTTI ключ в мэпе. Функции добавления сделать шаблонными. Тогда вообще ничего не нужно будет добавлять. Но реализация может выглядеть чуть сложнее и, что более важно, крайне сложно будет сделать кроссплатформенную/кросскомпиляторную сериализацию для такого решения.
Но с точки зрения ООП вариант с переключением типов не самый лучший, разумеется. Но по заданию требуется поддержка всего трёх типов и делать сложнее чем требуется, тоже не желательно.)
MikeSoft
Эксперт C++
 Аватар для MikeSoft
3787 / 1769 / 85
Регистрация: 21.11.2009
Сообщений: 2,540
08.07.2012, 17:59     Практические задания из собеседований #23
Цитата Сообщение от Deviaphan Посмотреть сообщение
В принципе не сложно заменить свитч на мэп и вместо перечисления использовать RTTI ключ в мэпе. Функции добавления сделать шаблонными.
Шаблоны изначально запрещены.

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

Специально открыл исходник своего варианта и нашёл функцию Insert:
C++
1
2
3
4
5
6
bool TVarList::Insert(unsigned int Index, int Data)
{
  int *Stored = new int();
  *Stored = Data;
  return InsertData(Index, Stored, itInteger);
}
Функции AddData, InsertData исправлять не придётся, т.к. их работа от типа не зависит: void *Data, функция Add - вызов того же Insert'a с "крайним" индексом.
По-моему, если бы на собеседовании заставили добавить новый тип данных - ушла бы минута времени.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1285 / 1219 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
08.07.2012, 18:28     Практические задания из собеседований #24
Цитата Сообщение от MikeSoft Посмотреть сообщение
Шаблоны изначально запрещены.
Тогда плохое задание на собеседовании это было.) Лишать С++ шаблонов это то же самое, что кастрировать программиста. Не хорошо.)
Скорее всего такие ограничения ставят те, кто хорошо знает Си и не смог разобраться в шаблонах.)))
MikeSoft
Эксперт C++
 Аватар для MikeSoft
3787 / 1769 / 85
Регистрация: 21.11.2009
Сообщений: 2,540
08.07.2012, 18:45     Практические задания из собеседований #25
Цитата Сообщение от Deviaphan Посмотреть сообщение
Скорее всего такие ограничения ставят те, кто хорошо знает Си и не смог разобраться в шаблонах.)))
Нет. Такие задания ставят те, кто хочет убедится, что программист, которого они берут, сможет сделать всё с нуля, а не воспользоваться готовым (сотрудникам концерна Microsoft запрещено смотреть в чей либо код... почему? только потому, что потом возможны претензии к тому, что этот код был украден или нарушил лицензионное соглашение и им приходится всё писать с нуля).

Можно также обратить внимание на задание с собеседования в Samsung, которое прислал niXman. Казалось бы, зачем переписывать то, что уже реализовано?
Но ведь нужно как-то проверять понимание алгоритмов...
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1285 / 1219 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
08.07.2012, 20:22     Практические задания из собеседований #26
Я к тому, что при помощи шаблонов многое реализовать проще и ещё проще поддерживать. Глупо связывать себе руки только из-за того, что считаешь программистов неумехами, которые только и умеют, что копипастить... Но корпорациям виднее, конечно.
Всё таки одно дело, когда запрещено использование библиотек (кроме STL) и совсем другое, когда запрещено использовать часть СТАНДАРТНЫХ и ОСНОВНЫХ преимуществ языка. Потмоу Windows Мастдаем и кличат.
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2295 / 1665 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
08.07.2012, 22:21  [ТС]     Практические задания из собеседований #27
Согласен с Deviaphan, задание действительно не очень, не удивлюсь если в этой конторе еще и исключения запрещены .

Добавлено через 1 час 41 минуту
Кстати, относительно задачи о потокобезопасной одиночке. Все, кого я собеседовал, приводили решение с использованием паттерна Double-checked locking в таком духе:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Singleton : noncopyable {
private:
  static Singleton* instance_;
 
  Singleton()
  { /* ... */ }
 
public:
  static Singleton* instance() {
    if (!instance) {
      lock();
      if (!instance_)
        instance_ = new Singleton();
    }
    return instance_;
  }
};
Эта реализация небезопасна в многопоточной среде. Почему и как это исправить?
ForEveR
Модератор
Эксперт С++
 Аватар для ForEveR
7955 / 4717 / 318
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
09.07.2012, 01:17     Практические задания из собеседований #28
CyBOSSeR,
Предположение
Полагаю либо сделать переменную instance volatile, либо сделать как всегда - локнуть и затем сделать проверку на !instance. Небезопасна потому что один поток может начать инициализацию, а второй в это время проверить, instance окажется не 0, итого вернется не полностью сконструированный объект.
http://ru.wikipedia.org/wiki/Double_checked_locking
MikeSoft
Эксперт C++
 Аватар для MikeSoft
3787 / 1769 / 85
Регистрация: 21.11.2009
Сообщений: 2,540
09.07.2012, 01:25     Практические задания из собеседований #29
Цитата Сообщение от CyBOSSeR Посмотреть сообщение
Согласен с Deviaphan, задание действительно не очень, не удивлюсь если в этой конторе еще и исключения запрещены .
К конторе, кстати, я тоже отнёсся с подозрением. Офис свой они даже "постеснялись представить". К тому же, я не по их части. Им нужен был человек для работы с Cocoa. Кстати, это было моё первое собеседование (часто посещают мысли сменить текущее место работы) - и оно оставило не очень хорошие впечатления.

Не по теме:

Цитата Сообщение от Deviaphan Посмотреть сообщение
Потому Windows Мастдаем и кличат.
Называют исключительно завистники. Политику MS я понимаю. Кто бы из нас не хотел заработать денег на разработке, которая не была украдена? Почему-то та же компания Apple использует ядро Darwin (львиная доля которого составляет и без того стабильные моменты ОС FreeBSD + NeXTSTEP) и продаёт чью-то идею за хорошие деньги. Но их ворами не называют почему-то... Ладно, пожалуй дальше я разводить оффтоп не буду.



Цитата Сообщение от Deviaphan Посмотреть сообщение
Глупо связывать себе руки только из-за того, что считаешь программистов неумехами, которые только и умеют, что копипастить... Но корпорациям виднее, конечно.
Тут тоже можно разливаться по древу... Когда я начал знакомство с программированием - подвернулась IDE C++ Builder. И примеры из книг были в ней написаны, и в университете на ней работали. Собственно говоря, когда я захотел перейти к изучению оконных приложений, я не знал о WinAPI, слышал только краем уха. Начал пытаться освоится в VCL. Позже мне стало понятно, что если ты не знаешь как устроена схема сообщений в ОС, то такое программирование превращается в бездумное формошлёпство. К чему я это веду... представьте, что человеку, которому кажется, что окна создаются командой TForm *pFrm = new TForm(this); , попросят создать окно на чистом WinAPI...
Почти тоже самое и здесь: можно было использовать стандартные приблуды STL, Boost и им подобные... а нужно было просто продемонстрировать умение применять на практике ООП или RTTI.
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2295 / 1665 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
09.07.2012, 02:51  [ТС]     Практические задания из собеседований #30
ForEveR,
неа
если мы сделаем только указатель volatile, то тем самым лишь защитимся от переупорадовачивания операций компилятором с указателем, но кроме операций с самим указателем у нас есть операции инициализации в констукторе.

ForEveR, для упрощения, будем считать, что в конструкторе просто инициализируется некое поле типа int:
C++
1
2
3
Singleton()
  : field(0)
{}
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2295 / 1665 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
09.07.2012, 02:57  [ТС]     Практические задания из собеседований #31
ForEveR,
неа
не спасет. У нас две операции: присваивание указателю _instance адреса выделенной памяти и присваивание полю field значения 0. Тут важно то, что квалификатор volatile вступает в силу только после полной инициализации объекта, поэтому field не может быть volatile в конструкторе по определению, поэтому операции присваивания instance_ и field могут быть переупорядочены компилятором.
ForEveR
Модератор
Эксперт С++
 Аватар для ForEveR
7955 / 4717 / 318
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
09.07.2012, 16:18     Практические задания из собеседований #32
CyBOSSeR,
#2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Singleton : noncopyable {
private:
  static volatile Singleton* volatile instance_;
 
  Singleton()
  { /* ... */ }
 
public:
  static volatile Singleton* volatile instance() {
    if (!instance_) {
      lock();
      if (!instance_) {
        volatile Singleton* volatile tmp = new volatile Singleton();
        instance_ = tmp;
      }
    }
    return instance_;
  }
};
Было интересно почитать http://www.aristeia.com/Papers/DDJ_J...04_revised.pdf
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1285 / 1219 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
09.07.2012, 16:30     Практические задания из собеседований #33
Цитата Сообщение от ForEveR Посмотреть сообщение
CyBOSSeR, #2
А что мешает, вместо указателя, завести флажок и устанавливать его при помощи атомарных операций? Будет та же блокировка с двойной проверкой, но без побочных эффектов.
ForEveR
Модератор
Эксперт С++
 Аватар для ForEveR
7955 / 4717 / 318
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
09.07.2012, 16:38     Практические задания из собеседований #34
Deviaphan, Насколько я понимаю, тут не говорилось об использовании С++11, буста или же конкретных либах, позволяющих использовать потоки, а так по идее ничего не мешает
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1285 / 1219 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
09.07.2012, 16:42     Практические задания из собеседований #35
Цитата Сообщение от ForEveR Посмотреть сообщение
тут не говорилось об использовании С++11, буста или же конкретных либах,
Это WinAPI функция вроде.
ForEveR
Модератор
Эксперт С++
 Аватар для ForEveR
7955 / 4717 / 318
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
09.07.2012, 17:25     Практические задания из собеседований #36
Deviaphan, Ну тут ведь не только о винде полагаю)
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2295 / 1665 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
09.07.2012, 23:34  [ТС]     Практические задания из собеседований #37
ForEveR, все таки хотелось бы увидеть код инициализации поля, о котором я говорил.
Цитата Сообщение от Deviaphan Посмотреть сообщение
А что мешает, вместо указателя, завести флажок и устанавливать его при помощи атомарных операций?
Хотелось бы увидеть код, для Windows или нет, не важно, можно использовать все что угодно.

Добавлено через 28 минут
И еще один вопрос: как бы вы реализовали потокобезопасный singleton в рамках C++11?
ForEveR
Модератор
Эксперт С++
 Аватар для ForEveR
7955 / 4717 / 318
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
10.07.2012, 00:16     Практические задания из собеседований #38
cut
Судя по тому что я прочитал, есть только 1 вариант инициализации пожалуй.

C++
1
2
3
4
5
6
7
8
class Singleton
{
   Singleton()
   {
      static_cast<volatile int&>(field) = 0;
   }
   int field;
};


А на тему потокобезопасного синглтона, никсман уже вроде давал ответ на этот вопрос в сообщении №13
Ну и еще вариант в рамках С++11 http://stackoverflow.com/questions/6...ngleton-in-c11
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2295 / 1665 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
10.07.2012, 01:32  [ТС]     Практические задания из собеседований #39
ForEveR,
ок.
про необходимость защиты от переупорядовачивании в железе, думаю, говорить не стоит, т.к. это упомянуто в документе по ссылке, которую ты выложил


Цитата Сообщение от ForEveR Посмотреть сообщение
А на тему потокобезопасного синглтона, никсман уже вроде давал ответ на этот вопрос в сообщении №13
Да, это отличноее решение, работающее и в C++03, но C++11 дает нам гарантии, которые позволяют решить задачу
проще.

C++
1
2
3
4
5
6
7
8
9
10
11
class Singleton : noncopyable {
private:
  Singleton() {
    / * ... */
  }
public:
  static Singleton& instance() {
    static Singleton instance_;
    return instance_;
  }
};
Да, это старый добрый Meyers singleton .
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.07.2012, 13:02     Практические задания из собеседований
Еще ссылки по теме:

C++ Builder Получить практические навыки реализации классов на С++
Задания по C++ C++
C++ Задания с++
C++ Задания C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1285 / 1219 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
10.07.2012, 13:02     Практические задания из собеседований #40
Цитата Сообщение от CyBOSSeR Посмотреть сообщение
Хотелось бы увидеть код
Так, я потерял нить дискуссии.
Почему этот код будет работать не правильно?
C++
1
2
3
if (!instance_) {
      lock();
      if (!instance_) {
Или речь про то, что адрес в кэше будет висеть и для второго потока не обновится?
Yandex
Объявления
10.07.2012, 13:02     Практические задания из собеседований
Ответ Создать тему
Опции темы

Текущее время: 08:22. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru