Мы отобрали вопросы и задачи, встречающиеся соискателям на собеседованиях в ведущие ИТ-компании мира.
![КДПВ](https://habrastorage.org/r/w1560/webt/dy/is/pu/dyispuv_iv86inxi36s3rwat3ne.png)
В подборку попали задачи, задаваемые на собеседованиях должность инженера-разработчика. Задачи различного уровня сложности, начиная от простых. Предлагаем Вам попробовать свои силы и постараться решить задачи самостоятельно — тогда вопросы на собеседовании вряд ли застанут Вас врасплох.
Ответы будут даны в течение следующей недели — успейте решить. Удачи!
![КДПВ](https://habrastorage.org/webt/dy/is/pu/dyispuv_iv86inxi36s3rwat3ne.png)
В подборку попали задачи, задаваемые на собеседованиях должность инженера-разработчика. Задачи различного уровня сложности, начиная от простых. Предлагаем Вам попробовать свои силы и постараться решить задачи самостоятельно — тогда вопросы на собеседовании вряд ли застанут Вас врасплох.
Вопросы
- 2 kind of pills
A man has a medical condition that requires him to take two kinds of pills, call them A and B. The man must take exactly one A pill and exactly one B pill each day. The pills are taken by first dissolving them in water.
The man has a jar of A pills and a jar of B pills. One day, as he is about to take his pills, he takes out one A pill from the A jar and puts it in a glass of water. Then he accidentally takes out two B pills from the B jar and puts them in the water. Now, he is in the situation of having a glass of water with three dissolved pills, one A pill and two B pills. Unfortunately, the pills are very expensive, so the thought of throwing out the water with the 3 pills and starting over is out of the question. How should the man proceed in order to get the right quantity of A and B while not wasting any pills?
ПереводОдному больному, согласно медицинским показаниям, необходимо принимать два лекарства, A и Б, причем нужно ежедневно принимать ровно 1 таблетку A и 1 таблетку Б. Таблетки принимаются в растворенном виде.
У больного есть склянка с А и склянка с Б. Однажды он, растворив таблетку А в стакане, бросил туда 2 таблетки из склянки с Б и получил стакан с раствором из 1 А и 2 Б. К сожалению, лекарства дорогие, поэтому он отбросил мысль вылить этот раствор и приготовить новый. Как этому больному продолжить приём назначенных лекарств, не потеряв при этом ни таблетки?
- Avg Salary
Three Employees want to know average of their salaries. They are not allowed to share their individual salaries. How can they calcalate average salary?
ПереводТри сотрудника хотят узнать среднюю зараплату (среди них троих), при том, что им запрещено озвучивать индивидуальную зарплату. Как им посчитать среднюю з/п?
Задачи
- Find possible compositions of a natural number
Given a natural number n, write a program to find the number of ways in which n can be expressed as a sum of natural numbers when order is taken into consideration. Two sequences that differ in the order of their terms define different compositions of their sum.
Examples:
Input: 4
Output: 8
Explanation
All 8 position composition are:
4, 1+3, 3+1, 2+2, 1+1+2, 1+2+1, 2+1+1 and 1+1+1+1
Input: 8
Output: 128
ПереводДано натуральное число n, напишите программу для поиска количества комбинаций чисел, сумма которых даёт в результате n, с учётом порядка. Две последовательности, которые отличаются порядком — считаются разными комбинациями.
Примеры:
Вход: 4
Выход: 8
Объяснение: 4, 1+3, 3+1, 2+2, 1+1+2, 1+2+1, 2+1+1 и 1+1+1+1
- Count numbers that don’t contain 3
Given a number n, write a function that returns count of numbers from 1 to n that don’t contain digit 3 in their decimal representation.
Examples:
Input: n = 10
Output: 9
Input: n = 45
Output: 31
// Numbers 3, 13, 23, 30, 31, 32, 33, 34,
// 35, 36, 37, 38, 39, 43 contain digit 3.
Input: n = 578
Ouput: 385
ПереводДано число n. Напишите программу, которая будет считать количество чисел, не содержащих 3 в десятичной записи от 1 до n.
Примеры:
Вход: n = 10
Выход: 9
Вход: n = 45
Выход: 31
// Числа 3, 13, 23, 30, 31, 32, 33, 34,
// 35, 36, 37, 38, 39, 43 содержат 3.
Вход: n = 578
Выход: 385
- Boolean Array Puzzle
Write a program according with following specifications:
Input: A array arr[] of two elements having value 0 and 1
Output: Make both elements 0.
Requirements: Following are the specifications to follow.
1) It is guaranteed that one element is 0 but we do not know its position.
2) We can’t say about another element it can be 0 or 1.
3) We can only complement array elements, no other operation like and, or, multi, division, …. etc.
4) We can’t use if, else and loop constructs.
5) Obviously, we can’t directly assign 0 to array elements.
ПереводНапишите программу, удовлетворяющую следующим требованиям:
Вход: массив arr[] из 2-х элементов, имеющих возможные значения 1 или 0
Выход: Сделать оба элемента равными 0
Требования:
1) Известно, что один элемент равен 0, но неизвестна его позиция
2) Про второй элемент мы этого не можем сказать, он может быть 0 или 1.
3) Мы можем только дополнять элементы массива, никакие другие операции, такие как or, and, умножение, деление и др. не разрешены.
4) Нельзя использовать условные конструкции, циклы.
5) Нельзя явно записать 0 в элементы массива.
Ответы будут даны в течение следующей недели — успейте решить. Удачи!
Решения
- Вопрос 1Верный ответ был дан в комментариях:
Нужно добавить ещё одну таблетку А в стакан, перемешать и выпить полстакана, оставив половину на следующий день.
- Вопрос 2Было предложено много вариантов решения, один, например, в этом комментарии.
- Задача 1Верное решение также было найдено в комментариях.
Путем небольшого анализа можно выяснить и доказать, что количество комбинаций равно 2n-1.
#include<iostream> using namespace std; #define ull unsigned long long ull countCompositions(ull n) { // Return 2 raised to power (n-1) return (1L) << (n-1); } // Driver Code int main() { ull n = 4; cout << countCompositions(n) << "\n"; return 0; }
- Задача 2Рекурсивный вариант решения:
#include <stdio.h> /* returns count of numbers which are in range from 1 to n and don't contain 3 as a digit */ int count(int n) { // Base cases (Assuming n is not negative) if (n < 3) return n; if (n >= 3 && n < 10) return n-1; // Calculate 10^(d-1) (10 raise to the power d-1) where d is // number of digits in n. po will be 100 for n = 578 int po = 1; while (n/po > 9) po = po*10; // find the most significant digit (msd is 5 for 578) int msd = n/po; if (msd != 3) // For 578, total will be 4*count(10^2 - 1) + 4 + count(78) return count(msd)*count(po - 1) + count(msd) + count(n%po); else // For 35, total will be equal to count(29) return count(msd*po - 1); } // Driver program to test above function int main() { printf ("%d ", count(578)); return 0; }
- Задача 3Правильный ответ предложен в комментарии