Топ 35 задач с собеседований по C++

Постановка: Бинарный поиск (Binary Search) - это эффективный алгоритм для поиска значения в отсортированном массиве. Принцип алгоритма очень прост. Мы всегда имеем дело с упорядоченным массивом. Это позволяет прибегать к хитрости - на каждой итерации цикла, который мы запускаем, мы вычисляем индекс среднего элемента. Этот элемент сравниваем с искомым. Если элемент из середины массива оказался меньше, чем тот, что мы ищем, значит нужный нам находится правее по массиву, ведь массив упорядочен. Соответственно, нам нужно перейти в следующую итерацию цикла, "оставляя" ей лишь правую часть массива - в ней снова будет найден средний элемент и алгоритм повторится. Если же элемент из середины массива оказался больше искомого, то мы переходим к следующей итерации, отбрасывая правую часть массива, а оставляя левую. Если же элемент совпадает с искомым, мы выходим из цикла. Дан отсортированный массив, найдите в нём искомый элемент. Решение: int binsearch_array(vector<int>& a, int val) { int l = 0, r = a.size() - 1; while (r > l) { int m = (l + r) / 2; if (a[m] < val) { l = m + 1; } else if (a[m] > val) { r = m - 1; } else { return m; } } if (a[l] == val) { return l; } else { return -1; } }

Постановка: Дано действительное число a и натуральное n. Вычислите корень n-й степени из числа a, используя вещественный бинарный поиск. С клавиатуры через пробел вводится два числа: 1. a – действительное, неотрицательное, не превосходит 1000, задано с точностью до 6 знаков после десятичной точки; 2. n – натуральное, не превосходящее 10. Требуется вывести число с точностью не менее 6 знаков после запятой. Решение: #include <iostream> #include <cmath> #include <iomanip> long double firBinSearch(double a, int n, double R) { double L = 0; while (R - L > 1e-10) { double M = (L + R) / 2; if (pow(M, n) < a) { L = M; } else { R = M; } } return R; } int main() { int n; double a; std::cin >> a >> n; if (a >= 1) { double result = firBinSearch(a, n, a); std::cout << std::fixed << std::setprecision(6) << res; } else { if(a < 1) { double result = secBinSearch(a, n, 1); std::cout << std::fixed << std::setprecision(6) << res; } } return 0; }

Постановка: Найдите такое число x, что x^2 + sqrt(x) = C, с точностью не менее 6 знаков после точки. В единственной строке содержится вещественное число C (1 ≤ C ≤ 10^10). Выведите одно число — искомый x. Решение: #include <iostream> #include <iomanip> #include <cmath> using namespace std; long double check(long double x) { return pow(x, 2) + sqrt(x); } long double binSearch(double c) { double R = 1e10, L = 0, M; while (fabs(R - L) > 1e-10) { M = (L + R) / 2; if (check(M) - c < 0) { L = M; } else { R = M; } } return R; } int main() { double c; cin >> c; double result = binSearch(c); cout << fixed << setprecision(6) << result; return 0; }

Постановка: Определите, сколько обменов сделает алгоритм пузырьковой сортировки по возрастанию для данного массива. На первой строке дано целое число n (1 ≤ n ≤ 1000) – количество элементов в массиве. На второй строке – сам массив. Гарантируется, что все элементы массива – различные целые числа, не превышающие по модулю 10^9. Выведите одно число – количество обменов пузырьковой сортировки. Решение: #include <iostream> #include <algorithm> using namespace std; const int MAX_SIZE = 1000; void input(int *a, int size) { for(int i = 0; i < size; ++i) { cin >> a[i]; // ввод массива } } void bubbleSort(int *array, int size) { int swap_counter = 0; for(int i = 1; i < size; ++i) { for(int j = 1; j <= size - i; ++j) { if(array[j - 1] > array[j]) { swap(array[j - 1], array[j]); swap_counter++; } } } cout << swap_counter; } int main() { int mainArray[MAX_SIZE], size; cin >> size; input(mainArray, size); bubbleSort(mainArray, size); return 0; }

Постановка: Продемонстрируйте работу метода сортировки вставками по возрастанию. Для этого выведите состояние данного массива после каждой вставки на отдельных строках. Если массив упорядочен изначально, не нужно ничего выводить. На первой строке дано целое число n (1 ≤ n ≤ 100) – количество элементов в массиве. На второй строке задан сам массив: последовательность натуральных чисел, не превышающих 10^9. В выходной файл выведите строки (по количеству вставок) по n чисел каждая. Решение: #include <iostream> #include <algorithm> const int MAIN_SIZE = 100; void input(int *array, int size) { for(int i = 0; i < size; ++i) { std::cin >> array[i]; } } void output(int *array, int size) { for(int i = 0; i < size; ++i) { std::cout << array[i] << " "; } std::cout << "\n"; } bool checker(int *array, int size) { for(int i = 0; i < size - 1; ++i) { if (array[i] > array[i + 1]) { return false; } } return true; } void insertionSort(int *array, int size) { for(int i = 1; i < size; ++i) { int j = i; if (j && array[j] < array[j - 1]) { while(j && array[j] < array[j - 1]) { std::swap(array[j], array[j - 1]); --j; } output(array, size); } } } int main() { int mainArray[MAIN_SIZE], size; std::cin >> size; input(mainArray, size); if (!checker(mainArray, size)) { insertionSort(mainArray, size); } return 0; }

Постановка: Дано N целых чисел, которые требуется отсортировать в порядке неубывания. Среди чисел не будет двух, различных больше чем на 10^7. В задаче необходимо использовать сортировку подсчётом. Первая строка входных данных содержит целое число N (1 ≤ N ≤ 100000), вторая строка – N целых чисел, не превышающих по модулю 2⋅10^9. Никакие два не различаются более, чем на 10^7. Выведите данные числа в порядке неубывания. Решение: #include <iostream> const int ARRAY_SIZE = 100000; const long long int MIN = -9223372036854775807; const long long int MAX = 9223372036854775807; void input(long long int *a, long long int size) { for(int i = 0; i < size; ++i){ std::cin >> a[i]; } } void output(long long int *a, long long int size) { for(int i = 0; i < size; ++i){ std::cout << a[i] << " "; } } long long int maxFinder(long long int *a, long long int size) { long long int max = MIN; for(int i = 0; i < size; ++i){ if (a[i] > max){ max = a[i]; } } return max; } long long int minFinder(long long int *a, long long int size) { long long int min = MAX; for(int i = 0; i < size; ++i){ if (a[i] < min){ min = a[i]; } } return min; } void zeroFill(long long int *zero, long long int size) { for (int i = 0; i < size; ++i){ zero[i] = 0; } } void counting_sort(long long int* vec, long long int len, long long int min, long long int max) { int *cnt = new int[max - min + 1]; for (int i = min; i <= max; ++i) { cnt[i - min] = 0; } for (int i = 0; i < len; ++i) { ++cnt[vec[i] - min]; } for (int i = min; i <= max; ++i) { for(int j = cnt[i - min]; j--;) { *vec++ = i; } } delete [] cnt; } int main(){ long long int mainArray[ARRAY_SIZE], zero[ARRAY_SIZE], size; std::cin >> size; input(mainArray, size); zeroFill(zero, size); long long int max = maxFinder(mainArray, size); long long int min = minFinder(mainArray, size); counting_sort(mainArray, size, min, max); output(mainArray, size); return 0; }

Постановка: Отсортируйте заданный массив с помощью быстрой сортировки. Первая строка входных данных содержит одно натуральное число n (1 ≤ n ≤ 10^5) – количество элементов в массиве. В следующей строке находятся элементы массива – n целых чисел, не превосходящих по абсолютной величине 10^9. Выведите элементы массива в порядке неубывания. Решение: #include <iostream> #include <algorithm> const int SIZE = 100000; void input(int *a, int size) { for(int i = 0; i < size; ++i) { std::cin >> a[i]; } } void output(int *a, int size) { for(int i = 0; i < size; ++i) { std::cout << a[i] << " "; } } void quickSort(int *tempArray, int first, int last) { int middle; middle = tempArray[(first + last) / 2]; int f = first, l = last; while (f < l) { while (tempArray[f] < middle) f++; while (tempArray[l] > middle) l--; if (f <= l) { std::swap(tempArray[f], tempArray[l]); f++; l--; } } if (first < l) quickSort(tempArray, first, l); if (f < last) quickSort(tempArray, f, last); } int main(){ int size, mainArray[SIZE]; std::cin >> size; input(mainArray, size); quickSort(mainArray, 0, size - 1); output(mainArray, size); return 0; }

Постановка: В неориентированном графе требуется найти длину минимального пути между двумя вершинами. Первым на вход поступает число N – количество вершин в графе (1≤N≤100). Затем записана матрица смежности («0» обозначает отсутствие ребра, «1» – наличие ребра). Далее задаются номера двух вершин – начальной и конечной. Выведите L – длину кратчайшего пути (количество ребер, которые нужно пройти). Если пути не существует, выведите одно число «-1». Решение: #include <iostream> #include <queue> #include <vector> using namespace std; const int SIZE = 100; int main() { int size; int start, end; cin >> size; vector<int> from(size, -1); vector<int> used(size, 0); vector<int> dist(size); int mainMatrix[SIZE][SIZE]; int way[SIZE]; int counter = 0; for(int i = 0; i < size; ++i) { for(int j = 0; j < size; ++j) { cin >> mainMatrix[i][j]; } } cin >> start >> end; --start; --end; queue<int> Queue; Queue.push(start); dist[start] = 0; used[start] = 1; while (!Queue.empty()) { int hold = Queue.front(); Queue.pop(); for (int i = 0; i < size; ++i) { if (mainMatrix[hold][i] && !used[i]) { dist[i] = dist[hold] + 1; from[i] = hold; Queue.push(i); used[i] = true; } } } if (used[end]) cout << dist[end]; else cout << -1; return 0; }

Постановка: В неориентированном графе требуется найти минимальный путь между двумя вершинами. Первым на вход поступает число N – количество вершин в графе (1≤N≤100). Затем записана матрица смежности (0 обозначает отсутствие ребра, 1 – наличие ребра). Далее задаются номера двух вершин – начальной и конечной. Выведите сначала L – длину кратчайшего пути (количество ребер, которые нужно пройти), а потом сам путь. Если путь имеет длину 0, то его выводить не нужно, достаточно вывести длину. Если пути между вершинами не существует, то требуется вывести одно число – «-1». Решение: #include <iostream> #include <queue> #include <vector> #include <algorithm> using namespace std; const int SIZE = 100; void matrix_input(int matrix[][SIZE], int size) { for(int i = 0; i < size; ++i) { for(int j = 0; j < size; ++j) { cin >> matrix[i][j]; } } } int main() { int size; int start, end; cin >> size; vector<int> from(size, -1); vector<int> used(size, 0); vector<int> dist(size); int mainMatrix[SIZE][SIZE]; int way[SIZE]; int counter = 0; matrix_input(mainMatrix, size); cin >> start >> end; --start; --end; queue<int> Queue; Queue.push(start); dist[start] = 0; used[start] = 1; while (!Queue.empty()) { int hold = Queue.front(); Queue.pop(); for (int i = 0; i < size; ++i) { if (mainMatrix[hold][i] && !used[i]) { dist[i] = dist[hold] + 1; from[i] = hold; Queue.push(i); used[i] = true; } } } if (used[end]) { if (dist[end] == 0) { cout << dist[end] << endl; } else { cout << dist[end] << endl; vector <int> way; for (int i = end; i != -1; i = from[i]) { way.push_back(i); } reverse (way.begin(), way.end()); for (int i = 0; i < way.size(); ++i) { cout << way[i] + 1 << " "; } } } else { cout << -1 << endl; } return 0; }