С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

C++

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 432, средняя оценка - 4.73
CyBOSSeR
Эксперт С++
2305 / 1675 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
#1

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

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

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

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

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

Получить практические навыки реализации классов на С++ - C++ Builder
помогите пожалуйста люди )

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

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

Практические работы - C++
Практическая 1 1)Узнать, содержится ли в строке, введенной пользователем сочетание букв «ао»; 2)Запросить у пользователя массив из 7...

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

Задания с собеседований - C#
Покидайте, пожалуйста, практических заданий, которые вас просили реализовать на собеседованиях (или перед собеседованием). Хочется...

42
Nameless One
Эксперт С++
5777 / 3427 / 255
Регистрация: 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
Эксперт С++
3139 / 1451 / 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 часов.
4
Nameless One
Эксперт С++
5777 / 3427 / 255
Регистрация: 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
Эксперт С++
2305 / 1675 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
10.06.2011, 19:54  [ТС] #5
Nameless One, есть, для решения этой задачи не нужна дополнительная памать, кроме двух указателей на узел списка ничего не потребуется.
2
ForEveR
В астрале
Эксперт С++
7983 / 4742 / 321
Регистрация: 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
Эксперт С++
4952 / 2532 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
10.06.2011, 22:44 #7
Цитата Сообщение от CyBOSSeR Посмотреть сообщение
для решения этой задачи не нужна дополнительная памать, кроме двух указателей на узел списка ничего не потребуется.
Кажется, это называется циклом Флойда.
5
CyBOSSeR
Эксперт С++
2305 / 1675 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
10.06.2011, 23:03  [ТС] #8
fasked, в точку.
0
ValeryLaptev
Эксперт С++
1046 / 825 / 48
Регистрация: 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
Эксперт С++
4952 / 2532 / 180
Регистрация: 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
Эксперт С++
4952 / 2532 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
20.08.2011, 16:05 #11
Недавно побывал на собеседовании. Многие вопросы были из разряда не особо интересных, такие как написать функцию добавления значения в упорядоченный список, перевод строки в число и т.д.
Один из вопросов относился к программированию на С/С++ меньше, но отличался от других. Звучал примерно так: "Что такое мьютекс? Как бы Вы реализовали мьютекс. Формальные описания не обязательны".
4
CyBOSSeR
Эксперт С++
2305 / 1675 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
21.08.2011, 13:40  [ТС] #12
Вспомнил одно из заданий на многопоточность:

Разработать потокобезопасную реализацию паттерна "Одиночка".
4
niXman
Эксперт С++
3139 / 1451 / 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;
10
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1306 / 1221 / 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 появилась...
2
MikeSoft
Эксперт С++
3802 / 1778 / 85
Регистрация: 21.11.2009
Сообщений: 2,540
08.06.2012, 17:15 #15
Цитата Сообщение от fasked Посмотреть сообщение
Недавно побывал на собеседовании. Многие вопросы были из разряда не особо интересных, такие как написать функцию добавления значения в упорядоченный список, перевод строки в число и т.д.
Один из вопросов относился к программированию на С/С++ меньше, но отличался от других. Звучал примерно так: "Что такое мьютекс? Как бы Вы реализовали мьютекс. Формальные описания не обязательны".
Тоже недавно был на собеседовании... Вопрос был ещё чуть коварнее: "Чем отличается мьютекс от семафора"... Много скучных вопросов по ООП.
А потом вот такое задание:

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

Класс списка реализовать с "нуля" (не используя темплейты, std::list или аналоги) При реализации класса "строка" можно использовать std::string.
0
08.06.2012, 17:15
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.06.2012, 17:15
Привет! Вот еще темы с ответами:

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

Практические задания по C# - C#
Здравствуйте. Полный новичок. Начал изучать C# неделю назад , решил начать с книги Г.Шилдт &quot;C# 4.0 полное руководство&quot;. Много примеров,...

Html Практические задания - HTML, CSS
Нужна помощь с практическими заданиями, я не успеваю( Нужен код:

Практические задания, нейросети - Искусственный интеллект
Привет. Выбрала для себя две книги: Рассела С. &quot;ИИ: современный подход&quot; и Люгера Дж. Ф. По каким сайтам/книгам можно перейти к практике?...


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

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

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