На этой неделе мы выбрали вопросы и задачи, с которыми сталкиваются соискатели на собеседовании на должность инженера-разработчика в Ebay. 
При приеме на работу на Ebay вам могут задать не только технические вопросы, но и логические проблемы.
Ниже приведены некоторые такие вопросы и задачи разного уровня сложности: от простого до сложного.
Вопросы
- Дни месяца с использованием 2 кубиков
Как можно представить дни месяца с помощью двух шестигранных игральных костей? Вы можете написать одно число на каждой грани кубика от 0 до 9 и должны обозначать дни от 1 до 31, например, для 1 на одном кубике должно быть 0, а на другом 1, аналогично для 29 на одном кубике должно быть 2. а другой должен показать 9.
Перевод Как бы вы представили дни месяца, используя два шестигранных кубика? На каждой стороне кубика можно написать цифры от 0 до 9, при этом нужно отметить цифры от 1 до 31. Например, для 1-го числа один кубик можно повернуть стороной с «0», а другое с «1»; аналогично для числа 29 – один кубик с «2», второй с «9». - С завязанными глазами и монеты
Вам завязывают глаза и перед вами на столе кладут 10 монет. Вам разрешено прикасаться к монетам, но вы не можете на ощупь определить, в каком положении они находятся.
Перевод У вас завязаны глаза, и перед вами на столе лежит 10 монет. Их можно трогать, но на ощупь нельзя определить, в какую сторону они повернуты.Вам говорят, что есть 5 монет лицом вверх и 5 монет решкой, но не сообщаете, какие из них какие.
Можете ли вы собрать две стопки монет с одинаковым количеством решек вверх? Вы можете подбрасывать монеты любое количество раз.
Также утверждается, что 5 монет лежат лицом вверх, 5 — решкой.
Как сделать 2 стопки с одинаковым количеством монет лицевой стороной вверх? Вы можете подбрасывать монеты неограниченное количество раз.
Задания
- Перетягивание каната
Учитывая набор из n целых чисел, разделите этот набор на два подмножества размером n/2 каждое так, чтобы разница суммы двух подмножеств была как можно меньше.
Перевод Дан набор из n целых чисел, необходимо разделить его на 2 подмножества, каждое размером n/2, так, чтобы разница между суммами этих подмножеств была минимальна.Если n четное, то размеры двух подмножеств должны быть строго n/2, а если n нечетное, то размер одного подмножества должен быть (n-1)/2, а размер другого подмножества должен быть (n+1)/2. .
Например, пусть данный набор равен {3, 4, 5, -3, 100, 1, 89, 54, 23, 20}, размер набора равен 10. Выходные данные для этого набора должны быть {4, 100, 1, 23, 20} и {3, 5, -3, 89, 54}.
Оба выходных подмножества имеют размер 5, а сумма элементов в обоих подмножествах одинакова (148 и 148).
Давайте рассмотрим другой пример, когда n нечетно.
Пусть данный набор равен {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}.
Выходные подмножества должны быть {45, -34, 12, 98, -1} и {23, 0, -99, 4, 189, 4}.
Суммы элементов в двух подмножествах равны 120 и 121 соответственно.
Если n четное, то размеры подмножеств должны быть ровно n/2, а если n нечетное, то размер одного подмножества должен быть (n-1)/2, второго — (n+1)/2. .
Например: Ввод: {3, 4, 5, -3, 100, 1, 89, 54, 23, 20} Выход: {4, 100, 1, 23, 20} и {3, 5, -3, 89, 54}.
Размеры обоих подмножеств равны 5, а суммы — 148. Ввод: {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4} Вывод: {45, -34, 12, 98, -1} и {23, 0, -99, 4, 189, 4}.
Суммы подмножеств равны 120 и 121 соответственно.
- Максимальная сумма, при которой никакие два элемента не являются соседними
Учитывая массив положительных чисел, найдите максимальную сумму подпоследовательности с ограничением, что никакие два числа в последовательности не должны быть соседними в массиве.
Перевод Дан массив положительных чисел.Таким образом, 3 2 7 10 должно вернуть 13 (сумма 3 и 10) или 3 2 5 10 7 должно вернуть 15 (сумма 3, 5 и 7).
Ответьте на вопрос наиболее эффективным способом.
Примеры: Ввод: arr[] = {5, 5, 10, 100, 10, 5} Выход: 110 Ввод: arr[] = {1, 2, 3} Выход: 4 Ввод: arr[] = {1, 20, 3} Выход: 20
Найдите максимальную сумму подпоследовательности при условии, что никакие 2 элемента подпоследовательности не находятся в соседних ячейках массива.
Итак, 3 2 7 10 должно вернуть 13 (сумма 3 и 10), а 3 2 5 10 7 должно вернуть 15 (сумма 3 5 7).
Код должен быть максимально эффективным.
Примеры: Ввод: arr[] = {5, 5, 10, 100, 10, 5} Выход: 110 Ввод: arr[] = {1, 2, 3} Выход: 4 Ввод: arr[] = {1, 20, 3} Выход: 20
- Программа для определения количества воды в заданном стакане.
Есть несколько стаканов емкостью 1 литр.
Перевод Несколько литровых банок располагаются пирамидкой вот так:Очки хранятся следующим образом:
1 2 3 4 5 6 7 8 9 10Воду можно наливать только в верхний стакан.Если в 1-й стакан налить более 1 литра воды, вода перельется и одинаково заполнит и 2-й, и 3-й стаканы.
В стакан 5 будет поступать вода как из второго, так и из третьего стакана и так далее.
Если у вас есть Х литров воды и вы налили эту воду в верхний стакан, сколько воды будет содержаться в j-м стакане? Напишите программу для его поиска.
Пример.
Если сверху положите 2 литра.
1-й – 1 литр 2-й – 1/2 литра 3-й – 1/2 литра
1 2 3 4 5 6 7 8 9 10Воду можно наливать только в самую верхнюю банку.Когда банка переполнится, вода начнет равномерно поступать в нижние (2 и 3).
В кувшин 5 будет поступать вода из кувшинов 2 и 3 и т. д. Если в верхнюю банку налить X литров воды, сколько воды перейдет в банку j? Напишите программу, решающую эту задачу.
Пример.
Если налить 2 литра, то: 1-й – 1 литр 2-й – 1/2 литра 3-й – 1/2 литра
Удачи!
Решения
- Вопрос 1 Ответ был быстрым найденный .
- вопрос 2 Rsa97 предложил правильную вещь решение .
- Проблема 1 Оригинальное решение:
#include <iostream> #include <stdlib.h> #include <limits.h> using namespace std; // function that tries every possible solution by calling itself recursively void TOWUtil(int* arr, int n, bool* curr_elements, int no_of_selected_elements, bool* soln, int* min_diff, int sum, int curr_sum, int curr_position) { // checks whether the it is going out of bound if (curr_position == n) return; // checks that the numbers of elements left are not less than the // number of elements required to form the solution if ((n/2 - no_of_selected_elements) > (n - curr_position)) return; // consider the cases when current element is not included in the solution TOWUtil(arr, n, curr_elements, no_of_selected_elements, soln, min_diff, sum, curr_sum, curr_position+1); // add the current element to the solution no_of_selected_elements++; curr_sum = curr_sum + arr[curr_position]; curr_elements[curr_position] = true; // checks if a solution is formed if (no_of_selected_elements == n/2) { // checks if the solution formed is better than the best solution so far if (abs(sum/2 - curr_sum) < *min_diff) { *min_diff = abs(sum/2 - curr_sum); for (int i = 0; i<n; i++) soln[i] = curr_elements[i]; } } else { // consider the cases where current element is included in the solution TOWUtil(arr, n, curr_elements, no_of_selected_elements, soln, min_diff, sum, curr_sum, curr_position+1); } // removes current element before returning to the caller of this function curr_elements[curr_position] = false; } // main function that generate an arr void tugOfWar(int *arr, int n) { // the boolen array that contains the inclusion and exclusion of an element // in current set. The number excluded automatically form the other set bool* curr_elements = new bool[n]; // The inclusion/exclusion array for final solution bool* soln = new bool[n]; int min_diff = INT_MAX; int sum = 0; for (int i=0; i<n; i++) { sum += arr[i]; curr_elements[i] = soln[i] = false; } // Find the solution using recursive function TOWUtil() TOWUtil(arr, n, curr_elements, 0, soln, &min_diff, sum, 0, 0); // Print the solution cout << "The first subset is: "; for (int i=0; i<n; i++) { if (soln[i] == true) cout << arr[i] << " "; } cout << "\nThe second subset is: "; for (int i=0; i<n; i++) { if (soln[i] == false) cout << arr[i] << " "; } } // Driver program to test above functions int main() { int arr[] = {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}; int n = sizeof(arr)/sizeof(arr[0]); tugOfWar(arr, n); return 0; }
- Проблема 2 Вариант решения:
#include<stdio.h> /*Function to return max sum such that no two elements are adjacent */ int FindMaxSum(int arr[], int n) { int incl = arr[0]; int excl = 0; int excl_new; int i; for (i = 1; i < n; i++) { /* current max excluding i */ excl_new = (incl > excl)? incl: excl; /* current max including i */ incl = excl + arr[i]; excl = excl_new; } /* return max of incl and excl */ return ((incl > excl)? incl : excl); } /* Driver program to test above function */ int main() { int arr[] = {5, 5, 10, 100, 10, 5}; int n = sizeof(arr) / sizeof(arr[0]); printf("%d n", FindMaxSum(arr, n)); return 0; }
- Проблема 3 Вариант решения:
// Program to find the amount of water in j-th glass // of i-th row #include <stdio.h> #include <stdlib.h> #include <string.h> // Returns the amount of water in jth glass of ith row float findWater(int i, int j, float X) { // A row number i has maximum i columns. So input // column number must be less than i if (j > i) { printf("Incorrect Inputn"); exit(0); } // There will be i*(i+1)/2 glasses till ith row // (including ith row) float glass[i * (i + 1) / 2]; // Initialize all glasses as empty memset(glass, 0, sizeof(glass)); // Put all water in first glass int index = 0; glass[index] = X; // Now let the water flow to the downward glasses // till the row number is less than or/ equal to i (given row) // correction : X can be zero for side glasses as they have lower rate to fill for (int row = 1; row <= i ; ++row) { // Fill glasses in a given row. Number of // columns in a row is equal to row number for (int col = 1; col <= row; ++col, ++index) { // Get the water from current glass X = glass[index]; // Keep the amount less than or equal to // capacity in current glass glass[index] = (X >= 1.0f) ? 1.0f : X; // Get the remaining amount X = (X >= 1.0f) ? (X - 1) : 0.0f; // Distribute the remaining amount to // the down two glasses glass[index + row] += X / 2; glass[index + row + 1] += X / 2; } } // The index of jth glass in ith row will // be i*(i-1)/2 + j - 1 return glass[i*(i-1)/2 + j - 1]; } // Driver program to test above function int main() { int i = 2, j = 2; float X = 2.0; // Total amount of water printf("Amount of water in jth glass of ith row is: %f", findWater(i, j, X)); return 0; }
-
Анонс Первого Собрания Java User Group Lv
19 Oct, 24 -
Безопасность В Современных Корпорациях
19 Oct, 24 -
Альфа-Версия Qutim 0.2 Ждет Вас
19 Oct, 24
