Форум программистов, компьютерный форум, киберфорум
Наши страницы
C++
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 432, средняя оценка - 4.73
CyBOSSeR
Эксперт С++
2309 / 1682 / 148
Регистрация: 06.03.2009
Сообщений: 3,675
#1

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

31.05.2011, 10:02. Просмотров 53899. Ответов 42
Метки нет (Все метки)

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

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

Просьба решения выкладывать под CUT'ом.
http://www.cyberforum.ru/cpp-builder/thread1298698.html
15
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.05.2011, 10:02
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Практические задания из собеседований (C++):

Где можно найти практические задания по с++
где можно найти практические задания по си и с++?

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

практические работы
блин ребят помогите задали практические делать а я вообще в c# не шарю над по...

Практические работы
Практическая 1 1)Узнать, содержится ли в строке, введенной пользователем...

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

42
Nameless One
Эксперт С++
5785 / 3434 / 351
Регистрация: 08.02.2010
Сообщений: 7,448
31.05.2011, 10:12 #2
1. Для натуральных чисел
C
1
2
3
4
int isExpOf2(int cand)
{
    return !(cand & (cand - 1));
}
Для неотрицательных чисел нужно рассмотреть особый случай - 0
15
niXman
Эксперт С++
3202 / 1451 / 73
Регистрация: 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 часов.
4
Nameless One
Эксперт С++
5785 / 3434 / 351
Регистрация: 08.02.2010
Сообщений: 7,448
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;
}


Есть более интересные решения?
7
CyBOSSeR
Эксперт С++
2309 / 1682 / 148
Регистрация: 06.03.2009
Сообщений: 3,675
10.06.2011, 19:54  [ТС] #5
Nameless One, есть, для решения этой задачи не нужна дополнительная памать, кроме двух указателей на узел списка ничего не потребуется.
2
ForEveR
В астрале
Эксперт С++
7994 / 4753 / 651
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 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;
}
0
fasked
Эксперт С++
4976 / 2556 / 241
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
10.06.2011, 22:44 #7
Цитата Сообщение от CyBOSSeR Посмотреть сообщение
для решения этой задачи не нужна дополнительная памать, кроме двух указателей на узел списка ничего не потребуется.
Кажется, это называется циклом Флойда.
5
CyBOSSeR
Эксперт С++
2309 / 1682 / 148
Регистрация: 06.03.2009
Сообщений: 3,675
10.06.2011, 23:03  [ТС] #8
fasked, в точку.
0
ValeryLaptev
Эксперт С++
1049 / 828 / 60
Регистрация: 30.04.2011
Сообщений: 1,659
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;
1
fasked
Эксперт С++
4976 / 2556 / 241
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 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.

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

Разработать потокобезопасную реализацию паттерна "Одиночка".
4
niXman
Эксперт С++
3202 / 1451 / 73
Регистрация: 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;
10
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1306 / 1221 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
24.08.2011, 11:06 #14
Цитата Сообщение от niXman Посмотреть сообщение
static std::shared_ptr<T> object;
Концептуально правильнее будет на scoped_ptr заменить, ведь копироваться он не может по определению.

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

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

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

http://liveworkspace.org/code/2c74477bc27650b2066d0315eeab593d
0
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1306 / 1221 / 72
Регистрация: 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 )
           {
                  ...
           }
      }
};
0
MikeSoft
Эксперт С++
3917 / 1782 / 183
Регистрация: 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);
};
Думаю, код приводить не нужно, всё и без него будет ясно
0
ForEveR
В астрале
Эксперт С++
7994 / 4753 / 651
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 3
06.07.2012, 19:25 #19
MikeSoft, Ну свитч по типам крайне рекомендуют не использовать. Не дело это в языке высокого уровня свитч по типам устраивать)
2
MikeSoft
Эксперт С++
3917 / 1782 / 183
Регистрация: 21.11.2009
Сообщений: 2,540
07.07.2012, 15:16 #20
Цитата Сообщение от ForEveR Посмотреть сообщение
MikeSoft, Ну свитч по типам крайне рекомендуют не использовать. Не дело это в языке высокого уровня свитч по типам устраивать)
А вот тут не согласен. Добавлением значения в список занимается перегруженная ф-ция Add.
Она же и переписывает значение типа eItemType (перечисление из трёх элементов). Далее switch используется лишь для проверки "а какой же из перегруженных функций было выполнено добавление?", что совсем не запрещено.
0
07.07.2012, 15:16
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.07.2012, 15:16
Привет! Вот еще темы с решениями:

Практические задания по C#
Здравствуйте. Полный новичок. Начал изучать C# неделю назад , решил начать с...

Практические задания C#
Изучаю C# по &quot;Герберт Шилдт &quot;C# 3.0, 4.0. Полное руководство&quot;&quot;, но там нету...

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

Изучение C# и практические задания
Здравствуйте, изучаю С# по книге &quot;Герберт Шилдт - C# 4.0&quot;. Еще параллельно...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru