Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 94, средняя оценка - 4.88
Мимино
180 / 151 / 5
Регистрация: 22.05.2013
Сообщений: 435
Записей в блоге: 1
#1

Тестовое задание на Junior C++ dev - C++

26.07.2013, 18:40. Просмотров 13047. Ответов 60
Метки нет (Все метки)

Доброго времени суток.
Неделю назад ради интереса отправил свое резюме в одну компанию, куда требуются с++ юниоры. Получил от них тестовое задание. Я ожидал, что они мне откажут (опыта то у меня действительно мизер), но хотелось бы узнать у более опытных людей, какое решение задач "ожидает" компания от соискателя для продолжения с ним отношений.
Далее идет 4 задачи и мой вариант решения каждой из них.

1. Распечатать произвольное число в двоичной системе исчисления.

Описание.
Написать функцию, принимающую на вход произвольное целочисленное значение и возвращающую строку, содержащую его представление в двоичной системе исчисления.

Декларация.
voidNumberAsBinary(
char* _result,// строка с результатом
unsignedint _number// произвольное число
)

Ожидаемый результат.
Например, для числа 13 данная функция должна вернуть строку "1101".

Проверка работы.
Решение должно демонстрировать работу функции на примере 10 случайных чисел в диапазоне 0 до 512.
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
#include <iostream>
#include <stdlib.h>
#include <time.h>
using std::cout;
using std::endl;
 
void numberAsBinary(char *_result, unsigned int _number); 
 
int main()
{
    setlocale(LC_ALL, "Russian");
    char *result = new char[11];
    unsigned int number;
    
    srand((unsigned)time(NULL));
    for (int i = 1; i <= 10; i++)
    {
        number = rand() % 513;
        numberAsBinary(result, number);
        cout << "Число " << number << " в двоичной системе счисления равно " << result << endl;
    }
 
    delete [] result;
    system("pause");
    return 0;
}
 
void numberAsBinary(
char *_result,
unsigned int _number
    )
{
    static int i;
    i = 0;
 
    if (_number != 1)
        numberAsBinary(_result, _number / 2);
 
    _result[i] = (_number % 2) + '0';
    i++;
    _result[i] = '\0';
}

2. Сгенерировать неупорядоченный массив целых чисел от 1 до N.

Описание.
Написать функцию, принимающую на вход произвольное целочисленное значение и возвращающую массив, содержащий последовательность чисел от 1 до этого значения, в котором каждое число последовательности находится в заведомо случайной позиции.

Декларация.
void GenerateRandomArray(
int * _result, // возвращаемыймассив
unsignedint _maxValue// максимальное число в последовательности
)

Ожидаемый результат.
Например, 2 последовательных запуска данной функции с параметром 7 могут сгенерировать последовательности вида
{2, 5, 7, 3, 4, 1, 6}
{5, 1, 3, 4, 6, 2, 7}

Проверка работы.
Решение должно демонстрировать работу функции на примере 4 случайных чисел в диапазоне от 5 до 15.
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
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <iomanip>
using std::cout;
using std::endl;
 
void generateRandomArray(int *_result, unsigned int _maxValue);
 
int main()
{
    setlocale(LC_ALL, "Russian");
    unsigned int maxValue;
    
    srand((unsigned)time(NULL));
    for (int i = 1; i <= 4; i++)
    {
        maxValue = 5 + rand() % 11;
        int *result = new int[maxValue];
        generateRandomArray(result, maxValue);
    
        cout << "Неупорядоченные числа от 1 до " 
             << std::setw(2) << maxValue << ": ";
        for (unsigned int i = 0; i < maxValue; i++)
            cout << result[i] << ' ';
        cout << endl;
        delete [] result;
    }
 
    system("pause");
    return 0;
}
 
void generateRandomArray(
int *_result, 
unsigned int _maxValue
    )
{
    int ind1, ind2, tmp;
 
    for (unsigned int i = 0, j = 1; i < _maxValue; i++, j++)
        _result[i] = j;
 
    for (int i = 1; i <= 20; i++)
    {
        ind1 = rand() % _maxValue;
        ind2 = rand() % _maxValue;
        tmp = _result[ind1];
        _result[ind1] = _result[ind2];
        _result[ind2] = tmp;
    }
}

3. Сортировка массива.

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

Декларация.
voidSort(
int* _values,// сортируемый массив
unsignedint _count// количество элементов в массиве
)

Ожидаемый результат.
Например, массив вида {2, 5, 7, 3, 4, 1, 6} будет преобразован данной функцией в {1, 2, 3, 4, 5, 6, 7}.

Проверка работы.
Решение должно демонстрировать работу функции на примере результатов, полученных при решении задачи 2 (последовательностей, сгенерированных для 4 случайных чисел в диапазоне от 5 до 15).
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
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <iomanip>
using std::cout;
using std::endl;
 
void generateRandomArray(int *_result, unsigned int _maxValue);
void Sort(int *_values, unsigned int _count);
 
 
int main()
{
    setlocale(LC_ALL, "Russian");
    unsigned int maxValue;
    
    srand((unsigned)time(NULL));
    for (int i = 1; i <= 4; i++)
    {
        maxValue = 5 + rand() % 11;
        int *result = new int[maxValue];
        generateRandomArray(result, maxValue);
    
        cout << "Неупорядоченные числа от 1 до " 
             << std::setw(2) << maxValue << ": ";
        for (unsigned int i = 0; i < maxValue; i++)
            cout << result[i] << ' ';
        cout << endl;
 
        Sort(result, maxValue - 1);
 
        cout << "Упорядоченные числа от 1 до " 
             << std::setw(2) << maxValue << ":   ";
        for (unsigned int i = 0; i < maxValue; i++)
            cout << result[i] << ' ';
        cout << endl << endl;
 
        delete [] result;
    }
 
    system("pause");
    return 0;
}
 
void generateRandomArray(
int *_result, 
unsigned int _maxValue
    )
{
    int ind1, ind2, tmp;
 
    for (unsigned int i = 0, j = 1; i < _maxValue; i++, j++)
        _result[i] = j;
 
    for (int i = 1; i <= 20; i++)
    {
        ind1 = rand() % _maxValue;
        ind2 = rand() % _maxValue;
        tmp = _result[ind1];
        _result[ind1] = _result[ind2];
        _result[ind2] = tmp;
    }
}
 
void Sort(
int *_values,
unsigned int _count
    )
{
    int i = 0, j = _count; 
    int temp, p;
 
    p = _values[_count >> 1]; 
 
    do
    {
        while (_values[i] < p) i++;
        while (_values[j] > p) j--;
 
        if (i <= j) 
        {
            temp = _values[i];
            _values[i] = _values[j];
            _values[j] = temp;
            i++;
            j--;
        }
 
    } while (i <= j);
 
    if (j > 0) 
        Sort(_values, j);
    if (_count > (unsigned)i)  
        Sort(_values+i, _count-i);
}
4. Определить недостающее число в неупорядоченной последовательности целых чисел.

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

Декларация.
intGetMissingValue(
constint * _values,// неупорядоченный массив целых чисел от 1 до _count
unsignedint _count// количество элементов в массиве
)

Ожидаемый результат.
Например, для последовательности {5, 7, 8,3, 1, 9, 2, 6, 4} данная функция должна вернуть 4.

Проверка работы.
Решение должно демонстрировать работу функций на примере результатов, полученных при решении задачи 2 (последовательностей, сгенерированных для 4 случайных чисел в диапазоне от 5 до 15).
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
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <iomanip>
using std::cout;
using std::endl;
 
void generateRandomArray(int *_result, unsigned int _maxValue);
void Sort(int *_values, unsigned int _count);
int getMissingValue(const int *_values, unsigned int _count);
 
 
int main()
{
    setlocale(LC_ALL, "Russian");
    unsigned int maxValue;
    
    srand((unsigned)time(NULL));
    for (int i = 1; i <= 4; i++)
    {
        maxValue = 5 + rand() % 11;
        int *result = new int[maxValue];
        generateRandomArray(result, maxValue);
    
        cout << "Неупорядоченные числа от 1 до " 
             << std::setw(2) << maxValue << ": ";
        for (unsigned int i = 0; i < maxValue; i++)
            cout << result[i] << ' ';
 
        cout << endl << "Значение последнего элемента:     " 
             << getMissingValue(result, maxValue) << endl;
 
        Sort(result, maxValue - 1);
 
        cout << "Упорядоченные числа от 1 до " 
             << std::setw(2) << maxValue << ":   ";
        for (unsigned int i = 0; i < maxValue; i++)
            cout << result[i] << ' ';
        cout << endl << endl;
 
        delete [] result;
    }
 
    system("pause");
    return 0;
}
 
void generateRandomArray(
int *_result, 
unsigned int _maxValue
    )
{
    int ind1, ind2, tmp;
 
    for (unsigned int i = 0, j = 1; i < _maxValue; i++, j++)
        _result[i] = j;
 
    for (int i = 1; i <= 20; i++)
    {
        ind1 = rand() % _maxValue;
        ind2 = rand() % _maxValue;
        tmp = _result[ind1];
        _result[ind1] = _result[ind2];
        _result[ind2] = tmp;
    }
}
 
void Sort(
int *_values,
unsigned int _count
    )
{
    int i = 0, j = _count; 
    int temp, p;
 
    p = _values[_count >> 1]; 
 
    do
    {
        while (_values[i] < p) i++;
        while (_values[j] > p) j--;
 
        if (i <= j) 
        {
            temp = _values[i];
            _values[i] = _values[j];
            _values[j] = temp;
            i++;
            j--;
        }
 
    } while (i <= j);
 
    if (j > 0) 
        Sort(_values, j);
    if (_count > (unsigned)i)  
        Sort(_values+i, _count-i);
}
 
int getMissingValue(
const int *_values,
unsigned int _count
    )
{
    unsigned int checkSum = 0, sum = 0;
 
    for (unsigned int i = 0; i < _count - 1; i++)
    {
        checkSum += i + 1;
        sum += _values[i];
    }
 
    return checkSum + _count - sum;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Мимино
180 / 151 / 5
Регистрация: 22.05.2013
Сообщений: 435
Записей в блоге: 1
26.07.2013, 21:19  [ТС]     Тестовое задание на Junior C++ dev #31
Цитата Сообщение от Хулиган Посмотреть сообщение
там некоторые задания на 5 строчек кода.
прям таки на 5? и условию соответствуют?
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
26.07.2013, 21:20     Тестовое задание на Junior C++ dev #32
В первой задаче от вас ожидали работу с битами памяти с красивым алгоритмом, а может и не одним, во второй это модификация сортировки выбором в один цикл, а вы намудрили, конечно, в четвертой банально вычислить
http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{n(n+1)}{2}-a[0]-...-a[n-2]. Да и программы нечетабельны, конечно, тоже, наверное, бросилось в глаза.
Мимино
180 / 151 / 5
Регистрация: 22.05.2013
Сообщений: 435
Записей в блоге: 1
26.07.2013, 21:22  [ТС]     Тестовое задание на Junior C++ dev #33
Цитата Сообщение от Thinker Посмотреть сообщение
Да и программы нечетабельны, конечно, тоже, наверное, бросилось в глаза.
Почему нечитабельны?
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
26.07.2013, 21:25     Тестовое задание на Junior C++ dev #34
Цитата Сообщение от Мимино Посмотреть сообщение
Почему нечитабельны?
код плохо отформатирован, например
C++
1
2
3
void numberAsBinary(
char *_result,
unsigned int _number
ну что это такое, да и черточки зачем эти
Мимино
180 / 151 / 5
Регистрация: 22.05.2013
Сообщений: 435
Записей в блоге: 1
26.07.2013, 21:26  [ТС]     Тестовое задание на Junior C++ dev #35
Цитата Сообщение от Thinker Посмотреть сообщение
код плохо отформатирован, например
C++
1
2
3
void numberAsBinary(
char *_result,
unsigned int _number
ну что это такое, да и черточки зачем эти, вы же классы не создаете.
Это требования работодателя, надо вот так оформить функции. Я от этого сам не в восторге
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
26.07.2013, 21:27     Тестовое задание на Junior C++ dev #36
Цитата Сообщение от Мимино Посмотреть сообщение
Это требования работодателя, надо вот так оформить функции. Я от этого сам не в восторге

Не по теме:

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

0x10
2459 / 1631 / 238
Регистрация: 24.11.2012
Сообщений: 4,012
26.07.2013, 21:28     Тестовое задание на Junior C++ dev #37
Цитата Сообщение от Мимино Посмотреть сообщение
Это требования работодателя
Мало ли как у них форматирование в письме ползет) Да и за подчеркивания уже был тут им выговор)
Мимино
180 / 151 / 5
Регистрация: 22.05.2013
Сообщений: 435
Записей в блоге: 1
26.07.2013, 21:35  [ТС]     Тестовое задание на Junior C++ dev #38
Цитата Сообщение от Thinker Посмотреть сообщение
Не по теме:
...значит алгоритмы им не понравились
Я вот поэтому и хочу устроиться куда нить в подмастерье, чтобы руку набить. Самостоятельное изучение и решение тонн задач не заменит живую практику.

Всем спасибо, ошибки учел, буду работать над собой
DU
1482 / 1058 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
26.07.2013, 21:50     Тестовое задание на Junior C++ dev #39
на что я смотрю:
сперва поверхностно. тут на первом плане форматирование кода. в целом аккуратненько. но
int ind1, ind2, tmp; переменные желательно юзать поближе к месту, где они понадобились. и инициализировать.
не экономте на строчках. глазу сложнее выцепить из кода место появления переменной, если они вот так в куче.
while (_values[i] < p) i++; - то же самое. условие цикла и тело в одной строке. неудобно читать, неудобно дебажить.
далее увидел new int *result = new int[maxValue]; тут имеем возможность получить утечку. всегда используйте RAII.
отсутствует проверка входных данных. есть потенциальные обращения по нулевому укзателю, и деление на ноль.
не использование STL считаю минусом.

C++
1
2
3
4
      cout << "Неупорядоченные числа от 1 до " 
             << std::setw(2) << maxValue << ": ";
        for (unsigned int i = 0; i < maxValue; i++)
            cout << result[i] << ' ';
и чуть ниже похожий кусок. - копипаста. можно было оформить в отдельную функцию.

Задания дурацкие, мало что по ним можно понять о кандидате. отказать могли по разным причинам, не обязательно из-за кода.
Olivеr
412 / 408 / 13
Регистрация: 06.10.2011
Сообщений: 831
26.07.2013, 22:11     Тестовое задание на Junior C++ dev #40
1, 2 и 4 в кратце решил бы так:
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
#include <iostream>
#include <vector>
#include <string>
#include <chrono>
#include <random>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cstdint>
 
std::string to_binary(uint64_t x)
{
    std::string str;
    uint64_t mask = 1ull << 64 - 1;
    do {
        str.push_back( (x & mask ? '1' : '0') );
    } while ( mask >>= 1 );
    return str;
}
 
template <class T>
std::vector<T> generateUnique(T highest)
{
    static_assert(std::is_arithmetic<T>::value, "T must be arithmetic");
    std::vector<T> v(highest);
    std::iota(begin(v), end(v), T(1));
    std::shuffle(begin(v), end(v),
        std::mt19937(std::chrono::system_clock::now().time_since_epoch().count()));
    return v;
}
 
template <class T>
T getMissingValue(const std::vector<T> &v)
{
    static_assert(std::is_arithmetic<T>::value, "T must be arithmetic");
    return (1 + v.size()) * v.size() / 2 -
        std::accumulate(begin(v), end(v) - 1, T(0), std::plus<T>());
}
 
int main()
{
    std::cout << to_binary(255) << std::endl;
    auto v = generateUnique<int>(20);
    for (auto x : v)
        std::cout << x << ", ";
    std::endl(std::cout);
    v = {5, 7, 8, 3, 1, 9, 2, 6, 4};
    std::cout << getMissingValue(v);
    return 0;
}
gray_fox
What a waste!
1446 / 1175 / 61
Регистрация: 21.04.2012
Сообщений: 2,463
Завершенные тесты: 3
26.07.2013, 22:15     Тестовое задание на Junior C++ dev #41
Olivеr, у них же там свои прототипы, с С-строками и указателями...
nonedark2008
889 / 628 / 126
Регистрация: 28.07.2012
Сообщений: 1,697
26.07.2013, 22:39     Тестовое задание на Junior C++ dev #42
Нуу, так как нет определенных условий, то первую задачу можно решить используя std::bitset в несколько строк. Ну или по хорошему вначале посчитать кол-во лидирующих нулей, выделить память под массив, а далее побитовыми операциями достать нужные биты.
Со вторым я солидарен - нужно создать массив и перемешать его.
Третье - числа в диапазоне от 5 до 15? Тут тупо можно использовать любой алгоритм, но наверно эффективнее будет сортировка вставками, хотя по хорошему было бы родить алгоритм, который для мелких значений сортирует вставками, а для больших например быстрой или слиянием.
Ну в четвертом тоже все просто - уже рассказали.
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
26.07.2013, 22:45     Тестовое задание на Junior C++ dev #43
Цитата Сообщение от nonedark2008 Посмотреть сообщение
первую задачу можно решить используя std::bitset в несколько строк. Ну или по хорошему вначале посчитать кол-во лидирующих нулей, выделить память под массив, а далее побитовыми операциями достать нужные биты.
массив то зачем еще здесь, сразу забракуют

Цитата Сообщение от nonedark2008 Посмотреть сообщение
Третье - числа в диапазоне от 5 до 15? Тут тупо можно использовать любой алгоритм, но наверно эффективнее будет сортировка вставками, хотя по хорошему было бы родить алгоритм, который для мелких значений сортирует вставками, а для больших например быстрой или слиянием.
как раз таки эффективной будет сортировка подсчетом в два прохода по массиву
TimeToWork
4 / 4 / 0
Регистрация: 13.04.2013
Сообщений: 25
26.07.2013, 23:19     Тестовое задание на Junior C++ dev #44
Оставлю и я свой комментарий, хотя, возможно, что-то из этого уже прозвучало.

Задача 1. Наверняка для проверки представления о работе с битами. Твоё решение было бы нормальным, если бы вместо рекурсии сделать обычный цикл, всё же на скорость это влияет катастрофически.

Задача 2. Это даже близко не рандом. Контрпример к твоему решению - запусти свою программу для массива на 1000 элементов, 20 перестановок на неё не особо то и повлияют.

Задача 3. Сортировка. Много кода, не стал вчитываться. Возможно там и всё хорошо. Но, в любом случае, основным критерием выступает не сделанная сортировка, а метод, который употребил человек. По этому вопросу пример куча, и то, разобрался ли опрашиваемый в более быстрых и интересных способах реализации задачи, или сделал "в лоб", очень многое показывает о его стремлении к красивому.

Задача 4. Стандартная олимпиадная задачка, решается в 4 строчки. Не пишу ответ, дабы не портить никому кайф. Маленькая подсказка
Кликните здесь для просмотра всего текста
сложность алгоритма О(N)



Судя по результатам теста ТС 2 задачи из 4 завалил (вторая и 4ая). А при 50% результате отказ действительно предсказуем. Как-никак, а опыт имеет огромное значение, если действительно хотите работать по данной специальности - нужно больше практиковаться.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.07.2013, 23:25     Тестовое задание на Junior C++ dev
Еще ссылки по теме:
Задание на массив и задание на матрицу. C++
C++ Библиотеки cpp для junior
C++ Для языка С++ больше всего вакансий Junior?
C++ Ранги разработчиков. Что означает Junior, Middle и Senior Developer
C++ Dev C

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

Или воспользуйтесь поиском по форуму:
nonedark2008
889 / 628 / 126
Регистрация: 28.07.2012
Сообщений: 1,697
26.07.2013, 23:25     Тестовое задание на Junior C++ dev #45
Цитата Сообщение от Thinker Посмотреть сообщение
массив то зачем еще здесь, сразу забракуют
Ну дык нужно же где-то хранить битовый результат, хотя все на усмотрение программиста.
Цитата Сообщение от Thinker Посмотреть сообщение
как раз таки эффективной будет сортировка подсчетом в два прохода по массиву
Для этой сортировки понадобятся два временных массива, что ИМХО не хорошо. Или если брать простой алгоритм пдсчета, то это та же фигня, что просто взять массив и заполнить сразу его числами от 1 до N(самый быстрый алгоритм получается - массив любой длины сортируется в один проход ^_^).
Yandex
Объявления
26.07.2013, 23:25     Тестовое задание на Junior C++ dev
Ответ Создать тему
Опции темы

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