Форум программистов, компьютерный форум 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'ом.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nameless One
Эксперт С++
 Аватар для Nameless One
5759 / 3408 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
31.05.2011, 10:12     Практические задания из собеседований #2
1. Для натуральных чисел
C
1
2
3
4
int isExpOf2(int cand)
{
    return !(cand & (cand - 1));
}
Для неотрицательных чисел нужно рассмотреть особый случай - 0
niXman
Эксперт C++
 Аватар для niXman
3133 / 1445 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
31.05.2011, 14:40     Практические задания из собеседований #3
из собеседования в 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
Эксперт С++
 Аватар для Nameless One
5759 / 3408 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
10.06.2011, 17:49     Практические задания из собеседований #4
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
Эксперт C++
 Аватар для CyBOSSeR
2295 / 1665 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
10.06.2011, 19:54  [ТС]     Практические задания из собеседований #5
Nameless One, есть, для решения этой задачи не нужна дополнительная памать, кроме двух указателей на узел списка ничего не потребуется.
ForEveR
Модератор
Эксперт С++
 Аватар для ForEveR
7955 / 4717 / 318
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
10.06.2011, 19:59     Практические задания из собеседований #6
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
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
10.06.2011, 22:44     Практические задания из собеседований #7
Цитата Сообщение от CyBOSSeR Посмотреть сообщение
для решения этой задачи не нужна дополнительная памать, кроме двух указателей на узел списка ничего не потребуется.
Кажется, это называется циклом Флойда.
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2295 / 1665 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
10.06.2011, 23:03  [ТС]     Практические задания из собеседований #8
fasked, в точку.
ValeryLaptev
Эксперт С++
1012 / 791 / 46
Регистрация: 30.04.2011
Сообщений: 1,600
10.06.2011, 23:48     Практические задания из собеседований #9
Цитата Сообщение от 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
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
11.06.2011, 12:38     Практические задания из собеседований #10
Еще парочка на алгоритмы:
Имеется n винтов и n гнезд, расположенных в произвольном порядке. Каждому винту соответствует по диаметру только одно гнездо. Все винты имеют разные диаметры.

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

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

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

Какого количество вызовов этой функции необходимо и достаточно, что бы найти в этой группе звезду?
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
20.08.2011, 16:05     Практические задания из собеседований #11
Недавно побывал на собеседовании. Многие вопросы были из разряда не особо интересных, такие как написать функцию добавления значения в упорядоченный список, перевод строки в число и т.д.
Один из вопросов относился к программированию на С/С++ меньше, но отличался от других. Звучал примерно так: "Что такое мьютекс? Как бы Вы реализовали мьютекс. Формальные описания не обязательны".
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2295 / 1665 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
21.08.2011, 13:40  [ТС]     Практические задания из собеседований #12
Вспомнил одно из заданий на многопоточность:

Разработать потокобезопасную реализацию паттерна "Одиночка".
niXman
Эксперт C++
 Аватар для niXman
3133 / 1445 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
21.08.2011, 14:04     Практические задания из собеседований #13
Цитата Сообщение от 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
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1285 / 1219 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
24.08.2011, 11:06     Практические задания из собеседований #14
Цитата Сообщение от niXman Посмотреть сообщение
static std::shared_ptr<T> object;
Концептуально правильнее будет на scoped_ptr заменить, ведь копироваться он не может по определению.

Добавлено через 3 минуты
Скорее бы поддержка C++0x в MSVC появилась...
MikeSoft
Эксперт C++
 Аватар для MikeSoft
3787 / 1769 / 85
Регистрация: 21.11.2009
Сообщений: 2,540
08.06.2012, 17:15     Практические задания из собеседований #15
Цитата Сообщение от fasked Посмотреть сообщение
Недавно побывал на собеседовании. Многие вопросы были из разряда не особо интересных, такие как написать функцию добавления значения в упорядоченный список, перевод строки в число и т.д.
Один из вопросов относился к программированию на С/С++ меньше, но отличался от других. Звучал примерно так: "Что такое мьютекс? Как бы Вы реализовали мьютекс. Формальные описания не обязательны".
Тоже недавно был на собеседовании... Вопрос был ещё чуть коварнее: "Чем отличается мьютекс от семафора"... Много скучных вопросов по ООП.
А потом вот такое задание:

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

Класс списка реализовать с "нуля" (не используя темплейты, std::list или аналоги) При реализации класса "строка" можно использовать std::string.
ForEveR
Модератор
Эксперт С++
 Аватар для ForEveR
7955 / 4717 / 318
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
08.06.2012, 21:05     Практические задания из собеседований #16
MikeSoft, Без темплейтов конечно печально, но: базовый класс, содержащий чисто-виртуальный метод print() или что-нибудь вроде, три производных класса от данного, в списке хранится указатель на базовый класс. Или реализовать нечто вроде boost::variant.

http://liveworkspace.org/code/2c7447...6d0315eeab593d
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1285 / 1219 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
09.06.2012, 06:28     Практические задания из собеседований #17
Цитата Сообщение от 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
Эксперт C++
 Аватар для MikeSoft
3787 / 1769 / 85
Регистрация: 21.11.2009
Сообщений: 2,540
06.07.2012, 09:57     Практические задания из собеседований #18
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
Модератор
Эксперт С++
 Аватар для ForEveR
7955 / 4717 / 318
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
06.07.2012, 19:25     Практические задания из собеседований #19
MikeSoft, Ну свитч по типам крайне рекомендуют не использовать. Не дело это в языке высокого уровня свитч по типам устраивать)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.07.2012, 15:16     Практические задания из собеседований
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
MikeSoft
Эксперт C++
 Аватар для MikeSoft
3787 / 1769 / 85
Регистрация: 21.11.2009
Сообщений: 2,540
07.07.2012, 15:16     Практические задания из собеседований #20
Цитата Сообщение от ForEveR Посмотреть сообщение
MikeSoft, Ну свитч по типам крайне рекомендуют не использовать. Не дело это в языке высокого уровня свитч по типам устраивать)
А вот тут не согласен. Добавлением значения в список занимается перегруженная ф-ция Add.
Она же и переписывает значение типа eItemType (перечисление из трёх элементов). Далее switch используется лишь для проверки "а какой же из перегруженных функций было выполнено добавление?", что совсем не запрещено.
Yandex
Объявления
07.07.2012, 15:16     Практические задания из собеседований
Ответ Создать тему
Опции темы

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