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

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

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

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

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

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

@Nameless One · 31.05.2011, 10:12

1. Для натуральных чисел

C
1
2
3
4
int isExpOf2(int cand)
{
    return !(cand & (cand - 1));
}

Для неотрицательных чисел нужно рассмотреть особый случай - 0

@niXman · 31.05.2011, 14:40

из собеседования в Samsung.

1. Реализовать упрощенный вариант boost.bind с поддержкой плейсхолдеров(до трех).
2. На основе контейнеров boost.mpl(list, vector) реализовать алгоритм compile-time сортировки Хоара для int и double типов с возможностью указания предиката. Алгоритм boost.mpl.sort не использовать.
3. Реализовать список типов и аксессоры для него(вставка и удаление в начало/конец, получение элемента с головы/хвоста, определить размер). Разрешается использовать препроцессор.
4. На основании пункта 3, реализовать compile-time контейнер "множество", с возможностью генерации compile-time-assert при попытке сохранения уже имеющегося типа. Разрешается использовать boost.static_assert.

заданий на самом деле больше.
на все отводилось 6 часов.

@Nameless One · 10.06.2011, 17:49

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

Если решать в лоб - односвязный список не содержит циклов, если все указатели (которые получаются при последовательном обходе узлов списка в одну сторону) на его узлы уникальны:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <cstdlib>
#include <iostream>
#include <set>
#include <tuple>
 
template <class T>
struct node
{
    T value;
    node<T>* next;
    node(T, node<T>*);
};
 
template <class T>
node<T>::node(T v, node<T>* n)
    : value(v), next(n)
{
}
 
template <class T>
class singly_linked
{
    node<T>* first;
    node<T>* last;
    size_t sz;
    
public:
    singly_linked();
    singly_linked<T>& push(const T& val);
 
    // "Зацикливает" последний указатель на указатель node_no
    // (или на последний, если число указателей меньше node_no - 1)
    singly_linked<T>& make_circular(size_t node_no = 0);
 
    // Проверка на наличие циклов
    bool has_cycles() const;
 
    ~singly_linked();
};
 
template <class T>
singly_linked<T>::singly_linked()
    : first(NULL), last(NULL), sz(0)
{
}
 
template <class T>
singly_linked<T>& singly_linked<T>::push(const T& val)
{
    node<T>* new_node = new node<T>(val, NULL);
 
    if(!first)
    first = new_node;
    else
    last->next = new_node;
    last = new_node;
 
    ++sz;
    
    return *this;
}
 
template <class T>
singly_linked<T>& singly_linked<T>::make_circular(size_t node_no)
{
    node<T>* node = first;
 
    if(!node)
    throw 42;
    
    while(node->next && node_no--)
    node = node->next;
 
    last->next = node;
    
    return *this;
}
 
template <class T>
bool singly_linked<T>::has_cycles() const
{
    bool new_key;
    
    std::set<node<T>*> nodes;
 
    for(node<T>* pn = first; pn; pn = pn->next)
    {
    std::tie(std::ignore, new_key) = nodes.insert(pn);
    if(!new_key)
        return true;
    }
 
    return false;
}
 
template <class T>
singly_linked<T>::~singly_linked()
{
    while(sz--)
    {
    node<T>* del_node = first;
    first = first->next;
    delete del_node;
    del_node = NULL;
    }
}
 
 
#define CHECK(EXP) std::cout << #EXP ": " << std::boolalpha << (EXP) << std::endl
 
int main()
{
    singly_linked<int> lst;
 
    CHECK(lst.has_cycles());
    CHECK(lst.push(3).has_cycles());
    CHECK(lst.push(8).push(3).has_cycles());
    CHECK(lst.push(9).make_circular().has_cycles());
    
    return 0;
}

Есть более интересные решения?

@CyBOSSeR · 10.06.2011, 19:54 **[ТС]**

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

@ForEveR · 10.06.2011, 19:59

Nameless One, Пожалуй вот тут бы можно было бы и проще.

C++
1
2
3
4
5
6
7
8
9
10
11
12
template <class T>
bool singly_linked<T>::has_cycles() const
{   
    std::set<node<T>*> nodes;
 
    for(node<T>* pn = first; pn; pn = pn->next)
    {
        if(nodes.insert(pn).second == false)
          return true;
    }
    return false;
}

@fasked · 10.06.2011, 22:44

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

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

Кажется, это называется циклом Флойда.

@CyBOSSeR · 10.06.2011, 23:03 **[ТС]**

fasked, в точку.

@ValeryLaptev · 10.06.2011, 23:48

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

Nameless One, Пожалуй вот тут бы можно было бы и проще.

C++
1
2
3
4
5
6
7
8
9
10
11
12
template <class T>
bool singly_linked<T>::has_cycles() const
{   
    std::set<node<T>*> nodes;
 
    for(node<T>* pn = first; pn; pn = pn->next)
    {
        if(nodes.insert(pn).second == false)
          return true;
    }
    return false;
}

Подобный цикл режет глаз!
Лучше так:

C++
1
2
3
4
5
6
node<T>* pn = first;
while(pn)
{ if(nodes.insert(pn).second) pn = pn->next;
  else return true;
}
return false;

@fasked · 11.06.2011, 12:38

Еще парочка на алгоритмы:

Имеется n винтов и n гнезд, расположенных в произвольном порядке. Каждому винту соответствует по диаметру только одно гнездо. Все винты имеют разные диаметры.

Требуется расставить все винты по гнездам. Разрешено только одно действие - попытка вставить винт i в гнездо j. В результате такой операции можно выяснить: (1) винт тоньще гнезда - не подходит, (2) винт толще гнезда - не подходит, (3) или винт точно входит в гнездо - подходит.

Сравнивать винты или гнезда между собой нельзя.

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

Существует функция (уже реализована):
bool first_knows_second(int first, int second);
Эта функция возвращает true, если first знает second, в противном случае, возвращает false.

Какого количество вызовов этой функции необходимо и достаточно, что бы найти в этой группе звезду?

@fasked · 20.08.2011, 16:05

Недавно побывал на собеседовании. Многие вопросы были из разряда не особо интересных, такие как написать функцию добавления значения в упорядоченный список, перевод строки в число и т.д.
Один из вопросов относился к программированию на С/С++ меньше, но отличался от других. Звучал примерно так: "Что такое мьютекс? Как бы Вы реализовали мьютекс. Формальные описания не обязательны".

@CyBOSSeR · 21.08.2011, 13:40 **[ТС]**

Вспомнил одно из заданий на многопоточность:

Разработать потокобезопасную реализацию паттерна "Одиночка".

@niXman · 21.08.2011, 14:04

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

Разработать потокобезопасную реализацию паттерна "Одиночка".

банально

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
template<typename T>
struct thread_safe_singleton: private boost::noncopyable {
   static T& instance() {
      boost::call_once(&init, flag);
      return *object;
   }
 
protected:
   thread_safe_singleton() {}
 
private:
   static boost::shared_ptr<T> object;
   static boost::once_flag flag;
 
   static void init() {
      object.reset(new T());
   }
};
 
template<typename T>
boost::shared_ptr<T> thread_safe_singleton<T>::object;
 
template<typename T>
boost::once_flag thread_safe_singleton<T>::flag = BOOST_ONCE_INIT;

или так, при использовании std

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <thread>
#include <memory>
 
template<typename T>
struct thread_safe_singleton {
   static T& instance() {
      std::call_once(&init, flag);
      return *object;
   }
 
protected:
   thread_safe_singleton() {}
 
private:
   static std::shared_ptr<T> object;
   static std::once_flag flag;
 
   static void init() {
      object.reset(new T());
   }
};
 
template<typename T>
std::shared_ptr<T> thread_safe_singleton<T>::object;
 
template<typename T>
std::once_flag thread_safe_singleton<T>::flag;

@Deviaphan · 24.08.2011, 11:06

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

static std::shared_ptr<T> object;

Концептуально правильнее будет на scoped_ptr заменить, ведь копироваться он не может по определению.

Добавлено через 3 минуты
Скорее бы поддержка C++0x в MSVC появилась...

@MikeSoft · 08.06.2012, 17:15

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

Недавно побывал на собеседовании. Многие вопросы были из разряда не особо интересных, такие как написать функцию добавления значения в упорядоченный список, перевод строки в число и т.д.
Один из вопросов относился к программированию на С/С++ меньше, но отличался от других. Звучал примерно так: "Что такое мьютекс? Как бы Вы реализовали мьютекс. Формальные описания не обязательны".

Тоже недавно был на собеседовании... Вопрос был ещё чуть коварнее: "Чем отличается мьютекс от семафора"... Много скучных вопросов по ООП.
А потом вот такое задание:

Реализовать двусвязный список. Каждый элемент списка может содержать один объект. Объект может быть трех типов: "целое число", "вещественное число", "строка". В разных узлах одного списка может быть любой объект одного из допустимых типов. Каждый объект должен иметь возможность вывести свое содержимое на консоль. У списка должен быть метод, выводящий все элементы.

Класс списка реализовать с "нуля" (не используя темплейты, std::list или аналоги) При реализации класса "строка" можно использовать std::string.

@ForEveR · 08.06.2012, 21:05

MikeSoft, Без темплейтов конечно печально, но: базовый класс, содержащий чисто-виртуальный метод print() или что-нибудь вроде, три производных класса от данного, в списке хранится указатель на базовый класс. Или реализовать нечто вроде boost::variant.

http://liveworkspace.org/code/... 15eeab593d

@Deviaphan · 09.06.2012, 06:28

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

Или реализовать нечто вроде boost::variant.

Или, чтобы не думать

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
enum DataType { T_int, T_double, T_string };
struct NodeData
{
      DataType type;
      int dataInt;
      double dataDuble;
      std::string dataString;
 
      void Print()
      {
           switch( type )
           {
                  ...
           }
      }
};

@MikeSoft · 06.07.2012, 09:57

ForEveR, собственно говоря, да, но меня что-то толкнуло на путь, примерно такой, как предложил Deviaphan.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//---------------------------------------------------------------------------
enum eItemType { itInteger, itDouble, itString };
//---------------------------------------------------------------------------
struct TDataList {
  void *pData;
  TDataList *Prev;
  TDataList *Next;
  eItemType ItemType;
};
//---------------------------------------------------------------------------
class TVarList {
  private:
    TDataList *First, *Temp, *Last;
    TDataList *GetNodeByIndex(unsigned int Index);
    bool AddData(void *Data, eItemType CurrentItemType);
    bool InsertData(unsigned int Index, void *Data, eItemType CurrentItemType);
  public:
    unsigned int Count;
    TVarList();
    ~TVarList();
 
    bool Add(int *Data);
    bool Add(double *Data);
    bool Add(std::string *Data);
    bool Add(int Data);
    bool Add(double Data);
    bool Add(std::string Data);
 
    bool Insert(unsigned int Index, int *Data);
    bool Insert(unsigned int Index, double *Data);
    bool Insert(unsigned int Index, std::string *Data);
 
    bool Insert(unsigned int Index, int Data);
    bool Insert(unsigned int Index, double Data);
    bool Insert(unsigned int Index, std::string Data);
 
    void Delete(unsigned int Index);
 
    void Get(unsigned int Index);
    void PrintAll(bool WithFormatting);
};

Думаю, код приводить не нужно, всё и без него будет ясно

@ForEveR · 06.07.2012, 19:25

MikeSoft, Ну свитч по типам крайне рекомендуют не использовать. Не дело это в языке высокого уровня свитч по типам устраивать)

@MikeSoft · 07.07.2012, 15:16

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

MikeSoft, Ну свитч по типам крайне рекомендуют не использовать. Не дело это в языке высокого уровня свитч по типам устраивать)

А вот тут не согласен. Добавлением значения в список занимается перегруженная ф-ция Add.
Она же и переписывает значение типа eItemType (перечисление из трёх элементов). Далее switch используется лишь для проверки "а какой же из перегруженных функций было выполнено добавление?", что совсем не запрещено.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	Установка Emscripten SDK (emsdk) и CMake на Windows для сборки C и C++ приложений в WebAssembly (Wasm) 8Observer8 30.01.2026 Чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. Система контроля версиями Git. . .	Подключение Box2D v3 к SDL3 для Android: физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .
Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	Влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .

@CyBOSSeR 2348 / 1721 / 149 Регистрация: 06.03.2009 Сообщений: 3,675

	Практические задания из собеседований 31.05.2011, 10:02. Показов 75088. Ответов 44 Метки нет (Все метки) Предлагаю в данной теме выкладывать интересные и не очень практические задачи, которые попадаются на собеседованиях. Я начну: 1. Написать функцию, определяющую является ли заданное число степенью двойки. 2. Написать функцию, определяющую содержит ли односвязный список циклы (например, последний ссылается на второй). Просьба решения выкладывать под CUT'ом. 15

@CyBOSSeR 2348 / 1721 / 149 Регистрация: 06.03.2009 Сообщений: 3,675
	10.06.2011, 19:54 [ТС]
	Nameless One, есть, для решения этой задачи не нужна дополнительная памать, кроме двух указателей на узел списка ничего не потребуется. 2

@CyBOSSeR 2348 / 1721 / 149 Регистрация: 06.03.2009 Сообщений: 3,675
	10.06.2011, 23:03 [ТС]
	fasked, в точку. 0

@fasked 5045 / 2624 / 241 Регистрация: 07.10.2009 Сообщений: 4,310 Записей в блоге: 5
	20.08.2011, 16:05
	Недавно побывал на собеседовании. Многие вопросы были из разряда не особо интересных, такие как написать функцию добавления значения в упорядоченный список, перевод строки в число и т.д. Один из вопросов относился к программированию на С/С++ меньше, но отличался от других. Звучал примерно так: "Что такое мьютекс? Как бы Вы реализовали мьютекс. Формальные описания не обязательны". 4

@CyBOSSeR 2348 / 1721 / 149 Регистрация: 06.03.2009 Сообщений: 3,675
	21.08.2011, 13:40 [ТС]
	Вспомнил одно из заданий на многопоточность: Разработать потокобезопасную реализацию паттерна "Одиночка". 4

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	08.06.2012, 21:05
	MikeSoft, Без темплейтов конечно печально, но: базовый класс, содержащий чисто-виртуальный метод print() или что-нибудь вроде, три производных класса от данного, в списке хранится указатель на базовый класс. Или реализовать нечто вроде boost::variant. http://liveworkspace.org/code/... 15eeab593d 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	06.07.2012, 19:25
	MikeSoft, Ну свитч по типам крайне рекомендуют не использовать. Не дело это в языке высокого уровня свитч по типам устраивать) 2