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

@CyBOSSeR · Регистрация: 06.03.2009

Author24 — интернет-сервис помощи студентам

Предлагаю в данной теме выкладывать интересные и не очень практические задачи, которые попадаются на собеседованиях.
Я начну:

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

Просьба решения выкладывать под CUT'ом.

@ForEveR · 07.07.2012, 15:51

MikeSoft, Итого для добавления нового типа нам нужно.
1) Добавить значение в перечисление.
2) Сделать реализацию четырех функций Add(type), Add(type*), Insert(int, type), Insert(int, type*).
3) Поправить свитч.

Не слишком много?) Не, я не говорю ничего против, как локальное решение свитч по типам годится, но только как локальное и практически не расширяемое.

@Deviaphan · 07.07.2012, 16:59

Сообщение от ForEveR

Не слишком много?)

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

@MikeSoft · 08.07.2012, 17:59

Сообщение от Deviaphan

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

Шаблоны изначально запрещены.

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

Специально открыл исходник своего варианта и нашёл функцию Insert:

C++

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 · 08.07.2012, 18:28

Сообщение от MikeSoft

Шаблоны изначально запрещены.

Тогда плохое задание на собеседовании это было.) Лишать С++ шаблонов это то же самое, что кастрировать программиста. Не хорошо.)
Скорее всего такие ограничения ставят те, кто хорошо знает Си и не смог разобраться в шаблонах.)))

@MikeSoft · 08.07.2012, 18:45

Сообщение от Deviaphan

Скорее всего такие ограничения ставят те, кто хорошо знает Си и не смог разобраться в шаблонах.)))

Нет. Такие задания ставят те, кто хочет убедится, что программист, которого они берут, сможет сделать всё с нуля, а не воспользоваться готовым (сотрудникам концерна Microsoft запрещено смотреть в чей либо код... почему? только потому, что потом возможны претензии к тому, что этот код был украден или нарушил лицензионное соглашение и им приходится всё писать с нуля).

Можно также обратить внимание на задание с собеседования в Samsung, которое прислал niXman. Казалось бы, зачем переписывать то, что уже реализовано?
Но ведь нужно как-то проверять понимание алгоритмов...

@Deviaphan · 08.07.2012, 20:22

Я к тому, что при помощи шаблонов многое реализовать проще и ещё проще поддерживать. Глупо связывать себе руки только из-за того, что считаешь программистов неумехами, которые только и умеют, что копипастить... Но корпорациям виднее, конечно.
Всё таки одно дело, когда запрещено использование библиотек (кроме STL) и совсем другое, когда запрещено использовать часть СТАНДАРТНЫХ и ОСНОВНЫХ преимуществ языка. Потмоу Windows Мастдаем и кличат.

@CyBOSSeR · 08.07.2012, 22:21 **[ТС]**

Согласен с Deviaphan, задание действительно не очень, не удивлюсь если в этой конторе еще и исключения запрещены

.

Добавлено через 1 час 41 минуту
Кстати, относительно задачи о потокобезопасной одиночке. Все, кого я собеседовал, приводили решение с использованием паттерна Double-checked locking в таком духе:

C++

class Singleton : noncopyable {
private:
  static Singleton* instance_;
 
  Singleton()
  { /* ... */ }
 
public:
  static Singleton* instance() {
    if (!instance) {
      lock();
      if (!instance_)
        instance_ = new Singleton();
    }
    return instance_;
  }
};

Эта реализация небезопасна в многопоточной среде. Почему и как это исправить?

@ForEveR · 09.07.2012, 01:17

CyBOSSeR,

Предположение

Полагаю либо сделать переменную instance volatile, либо сделать как всегда - локнуть и затем сделать проверку на !instance. Небезопасна потому что один поток может начать инициализацию, а второй в это время проверить, instance окажется не 0, итого вернется не полностью сконструированный объект.
http://ru.wikipedia.org/wiki/D... ed_locking

@MikeSoft · 09.07.2012, 01:25

Сообщение от 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 · 09.07.2012, 02:51 **[ТС]**

ForEveR,

неа

если мы сделаем только указатель volatile, то тем самым лишь защитимся от переупорадовачивания операций компилятором с указателем, но кроме операций с самим указателем у нас есть операции инициализации в констукторе.

ForEveR, для упрощения, будем считать, что в конструкторе просто инициализируется некое поле типа int:

C++

1
2
3

Singleton()
  : field(0)
{}

@CyBOSSeR · 09.07.2012, 02:57 **[ТС]**

ForEveR,

неа

не спасет. У нас две операции: присваивание указателю _instance адреса выделенной памяти и присваивание полю field значения 0. Тут важно то, что квалификатор volatile вступает в силу только после полной инициализации объекта, поэтому field не может быть volatile в конструкторе по определению, поэтому операции присваивания instance_ и field могут быть переупорядочены компилятором.

@ForEveR · 09.07.2012, 16:18

CyBOSSeR,

#2

C++

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... evised.pdf

@Deviaphan · 09.07.2012, 16:30

Сообщение от ForEveR

CyBOSSeR, #2

А что мешает, вместо указателя, завести флажок и устанавливать его при помощи атомарных операций? Будет та же блокировка с двойной проверкой, но без побочных эффектов.

@ForEveR · 09.07.2012, 16:38

Deviaphan, Насколько я понимаю, тут не говорилось об использовании С++11, буста или же конкретных либах, позволяющих использовать потоки, а так по идее ничего не мешает

@Deviaphan · 09.07.2012, 16:42

Сообщение от ForEveR

тут не говорилось об использовании С++11, буста или же конкретных либах,

Это WinAPI функция вроде.

@ForEveR · 09.07.2012, 17:25

Deviaphan, Ну тут ведь не только о винде полагаю)

@CyBOSSeR · 09.07.2012, 23:34 **[ТС]**

ForEveR, все таки хотелось бы увидеть код инициализации поля, о котором я говорил.

Сообщение от Deviaphan

А что мешает, вместо указателя, завести флажок и устанавливать его при помощи атомарных операций?

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

Добавлено через 28 минут
И еще один вопрос: как бы вы реализовали потокобезопасный singleton в рамках C++11?

@ForEveR · 10.07.2012, 00:16

cut

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

C++

class Singleton
{
   Singleton()
   {
      static_cast<volatile int&>(field) = 0;
   }
   int field;
};

А на тему потокобезопасного синглтона, никсман уже вроде давал ответ на этот вопрос в сообщении №13
Ну и еще вариант в рамках С++11 http://stackoverflow.com/quest... ton-in-c11

@CyBOSSeR · 10.07.2012, 01:32 **[ТС]**

ForEveR,

ок.

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

Сообщение от ForEveR

А на тему потокобезопасного синглтона, никсман уже вроде давал ответ на этот вопрос в сообщении №13

Да, это отличноее решение, работающее и в C++03, но C++11 дает нам гарантии, которые позволяют решить задачу

проще.

C++

class Singleton : noncopyable {
private:
  Singleton() {
    / * ... */
  }
public:
  static Singleton& instance() {
    static Singleton instance_;
    return instance_;
  }
};

Да, это старый добрый Meyers singleton

.

@Deviaphan · 10.07.2012, 13:02

Сообщение от CyBOSSeR

Хотелось бы увидеть код

Так, я потерял нить дискуссии.
Почему этот код будет работать не правильно?

C++

1
2
3

if (!instance_) {
      lock();
      if (!instance_) {

Или речь про то, что адрес в кэше будет висеть и для второго потока не обновится?

@Deviaphan Делаю внезапно и красиво 1313 / 1228 / 72 Регистрация: 22.03.2011 Сообщений: 3,744
	08.07.2012, 20:22	26
	Я к тому, что при помощи шаблонов многое реализовать проще и ещё проще поддерживать. Глупо связывать себе руки только из-за того, что считаешь программистов неумехами, которые только и умеют, что копипастить... Но корпорациям виднее, конечно. Всё таки одно дело, когда запрещено использование библиотек (кроме STL) и совсем другое, когда запрещено использовать часть СТАНДАРТНЫХ и ОСНОВНЫХ преимуществ языка. Потмоу Windows Мастдаем и кличат. 2

@MikeSoft 3953 / 1808 / 184 Регистрация: 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**. 0

@CyBOSSeR 2347 / 1720 / 148 Регистрация: 06.03.2009 Сообщений: 3,675
	09.07.2012, 02:57 [ТС]	31
	ForEveR, неа не спасет. У нас две операции: присваивание указателю _instance адреса выделенной памяти и присваивание полю field значения 0. Тут важно то, что квалификатор volatile вступает в силу только после полной инициализации объекта, поэтому field не может быть volatile в конструкторе по определению, поэтому операции присваивания instance_ и field могут быть переупорядочены компилятором. 2

@Deviaphan Делаю внезапно и красиво 1313 / 1228 / 72 Регистрация: 22.03.2011 Сообщений: 3,744
	09.07.2012, 16:30	33
	Сообщение от ForEveR CyBOSSeR, #2 А что мешает, вместо указателя, завести флажок и устанавливать его при помощи атомарных операций? Будет та же блокировка с двойной проверкой, но без побочных эффектов. 0

@Deviaphan Делаю внезапно и красиво 1313 / 1228 / 72 Регистрация: 22.03.2011 Сообщений: 3,744
	09.07.2012, 16:42	35
	Сообщение от ForEveR тут не говорилось об использовании С++11, буста или же конкретных либах, Это WinAPI функция вроде. 0

@CyBOSSeR 2347 / 1720 / 148 Регистрация: 06.03.2009 Сообщений: 3,675
		1
	Практические задания из собеседований 31.05.2011, 10:02. Показов 70209. Ответов 44 Метки нет (Все метки) Предлагаю в данной теме выкладывать интересные и не очень практические задачи, которые попадаются на собеседованиях. Я начну: 1. Написать функцию, определяющую является ли заданное число степенью двойки. 2. Написать функцию, определяющую содержит ли односвязный список циклы (например, последний ссылается на второй). Просьба решения выкладывать под CUT'ом. 15

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	07.07.2012, 15:51	21
	MikeSoft, Итого для добавления нового типа нам нужно. 1) Добавить значение в перечисление. 2) Сделать реализацию четырех функций Add(type), Add(type), Insert(int, type), Insert(int, type). 3) Поправить свитч. Не слишком много?) Не, я не говорю ничего против, как локальное решение свитч по типам годится, но только как локальное и практически не расширяемое. 0

@Deviaphan Делаю внезапно и красиво 1313 / 1228 / 72 Регистрация: 22.03.2011 Сообщений: 3,744
	07.07.2012, 16:59	22
	Сообщение от ForEveR Не слишком много?) В принципе не сложно заменить свитч на мэп и вместо перечисления использовать RTTI ключ в мэпе. Функции добавления сделать шаблонными. Тогда вообще ничего не нужно будет добавлять. Но реализация может выглядеть чуть сложнее и, что более важно, крайне сложно будет сделать кроссплатформенную/кросскомпиляторную сериализацию для такого решения. Но с точки зрения ООП вариант с переключением типов не самый лучший, разумеется. Но по заданию требуется поддержка всего трёх типов и делать сложнее чем требуется, тоже не желательно.) 3

@Deviaphan Делаю внезапно и красиво 1313 / 1228 / 72 Регистрация: 22.03.2011 Сообщений: 3,744
	08.07.2012, 18:28	24
	Сообщение от MikeSoft Шаблоны изначально запрещены. Тогда плохое задание на собеседовании это было.) Лишать С++ шаблонов это то же самое, что кастрировать программиста. Не хорошо.) Скорее всего такие ограничения ставят те, кто хорошо знает Си и не смог разобраться в шаблонах.))) 0

@MikeSoft 3953 / 1808 / 184 Регистрация: 21.11.2009 Сообщений: 2,540
	08.07.2012, 18:45	25
	Сообщение от Deviaphan Скорее всего такие ограничения ставят те, кто хорошо знает Си и не смог разобраться в шаблонах.))) Нет. Такие задания ставят те, кто хочет убедится, что программист, которого они берут, сможет сделать всё с нуля, а не воспользоваться готовым (сотрудникам концерна Microsoft запрещено смотреть в чей либо код... почему? только потому, что потом возможны претензии к тому, что этот код был украден или нарушил лицензионное соглашение и им приходится всё писать с нуля). Можно также обратить внимание на задание с собеседования в Samsung, которое прислал niXman. Казалось бы, зачем переписывать то, что уже реализовано? Но ведь нужно как-то проверять понимание алгоритмов... 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	09.07.2012, 01:17	28
	CyBOSSeR, Предположение Полагаю либо сделать переменную instance volatile, либо сделать как всегда - локнуть и затем сделать проверку на !instance. Небезопасна потому что один поток может начать инициализацию, а второй в это время проверить, instance окажется не 0, итого вернется не полностью сконструированный объект. http://ru.wikipedia.org/wiki/D... ed_locking 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	09.07.2012, 16:38	34
	Deviaphan, Насколько я понимаю, тут не говорилось об использовании С++11, буста или же конкретных либах, позволяющих использовать потоки, а так по идее ничего не мешает 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	09.07.2012, 17:25	36
	Deviaphan, Ну тут ведь не только о винде полагаю) 0

@CyBOSSeR 2347 / 1720 / 148 Регистрация: 06.03.2009 Сообщений: 3,675
	09.07.2012, 23:34 [ТС]	37
	ForEveR, все таки хотелось бы увидеть код инициализации поля, о котором я говорил. Сообщение от Deviaphan А что мешает, вместо указателя, завести флажок и устанавливать его при помощи атомарных операций? Хотелось бы увидеть код, для Windows или нет, не важно, можно использовать все что угодно. Добавлено через 28 минут И еще один вопрос: как бы вы реализовали потокобезопасный singleton в рамках C++11? 0