Топ 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 (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; }