Мы подобрали новую порцию вопросов и задач, встречающихся соискателям на собеседованиях в ведущие ИТ-компании мира.
Задачи отобраны различного уровня сложности, начиная от очень простых. Но не все из них имеют очевидное, на первый взгляд решение, поиск которого поможет Вам держать мозг в тонусе, а кому-то, возможно, поможет не растеряться на собеседовании.
Ответы будут даны в течение следующей недели — успейте решить. Удачи!
Задачи отобраны различного уровня сложности, начиная от очень простых. Но не все из них имеют очевидное, на первый взгляд решение, поиск которого поможет Вам держать мозг в тонусе, а кому-то, возможно, поможет не растеряться на собеседовании.
Вопросы
- Black and white balls
You have 20 white and 13 black balls in a bag. You pull out 2 balls one after another. If the balls are of same color, then you replace them with a white ball – but if they are of different color, you replace them with a black ball. Once you take out the balls, you do not put them back in the bag – so the balls keep reducing. What would be the color of the last ball remaining in the bag?
ПереводУ Вас в мешке 20 белых и 13 черных шаров. Вы последовательно вытягиваете по 2 шара. Если они одного цвета — тогда вы заменяете их белым шаром, если же они разных цветов — вы заменяете их черным шаром. Шары в мешок не возвращаются, поэтому их количество там убывает. Каким будет цвет последнего оставшего в мешке шара?
- Count the eggs
The man who delivers eggs to my home everyday, did not turn up one day. So when he came the next morning I demanded an explanation from him. He told me the following story:
The previous morning when he just came out of the house carrying a basket full of eggs on his head to start his daily rounds and stepped on to the street, a car going full speed brushed against him and knocked down his basket destroying all the eggs. The driver, however, a thorough gentleman admitted his responsibility and offered to compensate him for damages. But peddler could not remember the exact number of eggs he had, but he estimated the number at between 50 and 100. He was also able to tell the gentleman that if the eggs were counted by 2’s and 3’s at a time, none would be left, but if counted by 5’s at a time, 3 would remain, and that he sold the eggs at 10 cent a piece. The gentleman made some quick calculations and paid peddler adequately.
How much did the gentleman pay for eggs?
ПереводОднажды разносчик, который приносит ежедневно мне свежие яйца, не пришёл. Он появился на следующий день и я попросил его объяснить причину отсутствия. Он рассказал следующую историю:
Накануне утром он вышел из дома с корзиной, полной яиц, чтобы сделать ежедневный обход улицы. Рядом с ним промчалась на полной скорости машина и задела корзину, так, что все яйца разбились. Водитель, однако, оказался джентельменом и предложил оплатить ущерб. Разносчик не мог вспомнить точное количество яиц в корзине, только то, что их было от 50 до 100. Он также припомнил, что если выбрать по 2 или по 3 яйца, то яиц в корзине бы не осталось, а если по 5, то должно было остаться 3 яйца. Он продавал яйца по 10 центов за штуку. Автомобилист быстро посчитал в уме и отдал разносчику точную сумму за разбитые яйца. Сколько он заплатил?
Задачи
- Find median in row wise sorted matrix
We are given a row wise sorted matrix of size r*c, we need to find the median of the matrix given. It is assumed that r*c is always odd.
Examples:
Input:
1 3 5
2 6 9
3 6 9
Output: Median is 5
If we put all the values in a sorted array A[] = 1 2 3 3 5 6 6 9 9
Input:
1 3 4
2 5 6
7 8 9
Output: Median is 5
ПереводДана матрица с элементами, отсортированными построчно, размера r*c. Нам необходимо найти медиану матрицы. Предполагается, что r*c всегда нечётное.
Примеры
Вход:
1 3 5
2 6 9
3 6 9
Выход: Медиана — 5
В виде отсортированного массива: A[] = 1 2 3 3 5 6 6 9 9
Input:
1 3 4
2 5 6
7 8 9
Output: Медиана — 5
- Smallest single digit expression
Given a number N and a digit D, we have to form an expression or equation that contains only D and that expression evaluates to N. Allowed operators in expression are +, -, *, and /. Find the minimum length expression that satisfy the condition above and D can only appear in the expression at most 10(limit) times.
Examples:
Input: N = 7, D = 3
Output: 3/3+ 3 + 3
Explanation: 3/3 = 1, and 1+3+3 = 7
This is the minimum expression.
Input: N = 7, D = 4
Output: (4+4+4)/4 + 4
Explanation: (4+4+4) = 12, and 12/4 = 3 and 3+4 = 7
Also this is the minimum expression. Although
you may find another expression but that
expression can have only five 4's
Input: N = 200, D = 9
Output: Expression not found!
Explanation: Not possible within 10 digits.
ПереводДано число N и цифра D. Небходимо составить выражение, дающее в результате N и содержащее только D. Допустимы операции +, -, *, /. Необходимо найти выражение минимальной длины, удовлетворяющее условия, с учётом того, что D может встречаться в выражении не более 10 раз.
Ввод: N = 7, D = 3
Вывод: 3/3+ 3 + 3
Объяснение: 3/3 = 1, and 1+3+3 = 7
Ввод: N = 7, D = 4
Вывод: (4+4+4)/4 + 4
Объяснение: (4+4+4) = 12, and 12/4 = 3 and 3+4 = 7
Ввод: N = 200, D = 9
Вывод: Expression not found!
Объяснение: Невозможно выполнить с ограничением в 10 цифр.
Прим.: третий пример выглядит как вызов
- Minimum swaps to bring them all together
Given an array of n positive integers and a number k. Find the minimum number of swaps required to bring all the numbers less than or equal to k together.
Input: arr[] = {2, 1, 5, 6, 3}, k = 3
Output: 1
Explanation:
To bring elements 2, 1, 3 together, swap element '5' with '3' such that final array will be:
arr[] = {2, 1, 3, 6, 5}
Input: arr[] = {2, 7, 9, 5, 8, 7, 4}, k = 5
Output: 2
ПереводДан массив n целых положительных чисел и число k. Найти количество перестановок, необходимое, чтобы собрать все элементны, меньшие или равные k, рядом.
Вход: arr[] = {2, 1, 5, 6, 3}, k = 3
Выход: 1
Объяснение:
Достаточно поменять 5 и 3 местами:
arr[] = {2, 1, 3, 6, 5}
Вход: arr[] = {2, 7, 9, 5, 8, 7, 4}, k = 5
Выход: 2
Ответы будут даны в течение следующей недели — успейте решить. Удачи!
niklisto
Вопрос 1 не совсем понятен. Заменяются пары на 1 шар. Этот один шар откуда? Из мешка тоже? Или отдельно?
reci Автор
Да, шар на замену достаётся из мешка, потом пара добирается оттуда же.
sena
А если только чёрные шары остались, то чем заменять?
phs233
2 черных меняются на 1 белый.
sena
Откуда брать белый, если остались только чёрные?
ozvenya
А разве, не наоборот — 2 достаются, шар-замена кладется обратно в мешок?
sena
Написано же что «шары в мешок не возвращаются». Это похоже специальная задача с неполным условием, чтобы проверить, как отреагирует кандидат. :)
ozvenya
Мне кажется проблема в переводе, имхо в оригинале задачи речь именно о тех шариках, которые достали:
se-chemodanov
phs233
в условиях от 50 до 100
se-chemodanov
Точно, упустил этот нюанс.
ThisMan
Решается в один цикл
vesper-bot
> Input: N = 200, D = 9
phs233
увы 999 и 99 не 9
alexluk86
Так ведь сказано, что нужно использовать цифру 9, а не число 9. В числе 99, используется только цифра 9, и ни какая другая, так что заданным условиям удовлетворяет. Но, возможно, придется объяснять интервьюеру разницу в понятиях.
brain_tyrin
> Input: N = 200, D = 9
vesper-bot
Левый плюс на первом уровне вложенности надо поменять на «умножить», иначе получится (10+10)*2 = 40. Равно как и правую часть на (9+9)/9 (экономим одну девятку), иначе «минимальное» выражение не получается.
Респект :)
brain_tyrin
Да, конечно, опечатался :)
vesper-bot
Хм, кстати, не минимальное получается. (99+9/9)*(9+9)/9 использует меньше девяток.
nasl
Input: N = 200, D = 9: (9*9+9+9+9/9)*(9+9)/9
ThisMan
Если я правильно понял задание с массивом, то нам нужно просто посчитать индексы значений, которые меньше k, получим массив (пример) [0, 1, 3, 4], а потом пройдем циклом по элементам и если следующий индекс больше предыдущего на 2 и больше, значит нужна перестановка.
Phaker
Одной перестановкой на каждый пропуск не отделаешься, за ней целый паровоз перестановок поползёт. Надо просто сначала посчитать количество "хороших" значений <= k, а потом пройтись окном размера k по всему массиву, считая количество попаданий "плохих" значений в каждое окно. Минимум и будет ответом — это значит, что в данном окне нужно перестановками заменить "плохие" значения "хорошими" снаружи окна.
phs233
Ну да, лучше такого алгоритма придумать не смог.
Phaker
Только пробегать заново по каждому окну не эффективно. Достаточно просто при сдвиге окна делать +1/0/-1 к текущему каунту в зависимости от того, добавилось ли новое "хорошее" значение к окну справа или, наоборот, ушло из окна слева. Ниже уже и реализацию соответствующую привели.
iBojarin
3-вопрос
(9+9+9/9+9/9+9/9+9/9)*9+9/9+9/9
Nick_mentat
vesper-bot
А ничего, что в начале есть 13 черных, а извлечь их можно только попарно?
Nick_mentat
Вовсе нет. Шары всегда извлекаются по одному. Вот взяли два чёрных — заменили на белый (т.е. оба чёрных остались в коробке, вместо них ушёл белый), взяли чёрный и белый — ушёл чёрный (один, белый остался в коробке).
vesper-bot
Читаем внимательно.
Ушли черный и белый — пришел черный, т.е. в сухом остатке ушел белый.
Nick_mentat
А… Я подумал что их заменяют не в коробке, а в руке. Мол, взяли два, а потом положили назад в коробку и взяли оттуда чёрный или белый, в зависимости от комбинации.
utor
99+99+9/9+9/9
vesper-bot
С учетом наличия в ответах (4+4+4)/4, скобки разрешены.
Rsa97
Если мы достали два чёрных шара, то заменяем их одним белым, чётность количества чёрных шаров не меняется.
Если мы достали два белых шара, то заменяем их одним белым, количество (и чётность) чёрных не меняется.
Если мы достали белый и чёрный шары, то заменяем их одним чёрным, количество (и чётность) чёрных не меняется.
Таким образом, в мешке всегда нечётное количество чёрных шаров, а значит, когда там останется всего один шар — он будет чёрным.
kardan2
Задачи понравились.
Мои решения:
kardan2
Можно постараться найти решение за r*c. Но r*c — это предел для данных без структуры. У нас же есть порядок по строкам, поэтому можно искать решения вида r*Log( c), или что-то типа того.
Если коротко, как в бинарном поиске храним верхнюю и нижнюю границы по значению. Кроме того, храним правую и левую границы для каждой строки. Каждый раз берем медиану по каждой строке (с учетом границ), находим среди этих медиан новую медиану и пробуем её, как искомое значение. Находим для каждой строчки положение этого значения бинарным поиском (с учетом границ). Для левой границы ищем положение значения меньше или равно, а для правой больше или равно. Если сумма по каждой строке больше половины всех элементов массива с обоих сторон, значит значение и есть искомое. Если нет, то в каждой строке передвигаем границу.
Нам нужно, чтобы за каждую итерацию отсеивать некий процент (у меня он =25%) оставшихся элементов. Поэтому медиану медиан нужно искать с учётом весов, где вес медианы равен кол-ву оставшихся значений в строке.
Т.е. пусть у нас остались следующие строки (16) (11, 15, 20) (17, 21,33,48,50,77,78) и соотвественно медианы 16, 15, 48 с весами 1-3-7. Если мы возмем просто медиану медиан, т.е. число 16, то отсеем малое значение элементов, т.к. оно произойдет в строках с малым количеством. Это нам не нужно. с другой стороны 3+1+7=11, и медиана приходится на значение 7, т.е. медиану, которая равна 48.
Поиск такой медианы можно делать через сортировку медиан с последующим проходом.
Сложность поиска такой медианы с весом равна r*Log( r). Внутри строк нужен бинарный поиск, и так как зона бинарного поиска сокращается на 25%, то Log( c)+Log(0.75*c)+Log(0.75*0.75*c)+… = O(Log( c)*Log( c)), как сумма арифметической прогрессии.
Итого, сложность всего алгоритма это O(r*Log( r)*Log( c)^2)
lenon
#3 — вроде как, тоже простой (решение за O(n)):
counter = 0
for i =0; i < array.size; i++
if array[i] <= k
lenon
Удалите мои комментарии, пожалуйста. Я случайно Enter, не дописав нажал.
reci Автор
Увы, это не так просто. Только редактировать и писать новые :)