При устройстве на работу в Ebay Вам могут задать не только вопросы технического характера, но и логические задачи. Ниже приведены некоторые такие вопросы и задачи, с различным уровнем сложности, от простых до сложных.
Вопросы
- Days of month using 2 dice
How can you represent days of month using two 6 sided dice? You can write one number on each face of the dice from 0 to 9 and you have to represent days from 1 to 31, for example for 1, one dice should show 0 and another should show 1, similarly for 29 one dice should show 2 and another should show 9.
ПереводКак бы вы представили дни месяца с помощью 2-х шестигранных кубиков? Вы можете написать числа от 0 до 9 на каждой грани кубика, при этом Вам необходимо обозначить числа от 1 до 31. Например для 1-го числа, один кубик может быть повернут гранью с «0», а другой — с «1»; аналогично для числа 29 — один кубик с «2», второй — с «9».
- Blindfolded and coins
You are blindfolded and 10 coins are place in front of you on table. You are allowed to touch the coins, but can’t tell which way up they are by feel. You are told that there are 5 coins head up, and 5 coins tails up but not which ones are which.
Can you make two piles of coins each with the same number of heads up? You can flip the coins any number of times.
ПереводУ Вас завязаны глаза, а на столе перед Вами 10 монет. Вам разрешено их трогать, но на ощупь Вы не можете сказать какой стороной они повернуты. Также утверждается, что 5 монет лежат орлом вверх, 5 — решкой.
Как сделать 2 стопки с равным количеством монет, повёрнутых орлом вверх? Вы можете переворачивать монеты неограниченное число раз.
Задачи
- Tug of War
Given a set of n integers, divide the set in two subsets of n/2 sizes each such that the difference of the sum of two subsets is as minimum as possible. If n is even, then sizes of two subsets must be strictly n/2 and if n is odd, then size of one subset must be (n-1)/2 and size of other subset must be (n+1)/2.
For example, let given set be {3, 4, 5, -3, 100, 1, 89, 54, 23, 20}, the size of set is 10. Output for this set should be {4, 100, 1, 23, 20} and {3, 5, -3, 89, 54}. Both output subsets are of size 5 and sum of elements in both subsets is same (148 and 148).
Let us consider another example where n is odd. Let given set be {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}. The output subsets should be {45, -34, 12, 98, -1} and {23, 0, -99, 4, 189, 4}. The sums of elements in two subsets are 120 and 121 respectively.
ПереводДан набор n целых чисел, необходимо разделить его на 2 подмножества, размерностью n/2 каждое, так, чтобы разница между суммами этих подмножеств была минимальной. Если 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 соответственно.
- Maximum sum such that no two elements are adjacent
Given an array of positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7).Answer the question in most efficient way.
Examples:
Input: arr[] = {5, 5, 10, 100, 10, 5}
Output: 110
Input: arr[] = {1, 2, 3}
Output: 4
Input: arr[] = {1, 20, 3}
Output: 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
- Program to find amount of water in a given glass
There are some glasses with equal capacity as 1 litre. The glasses are kept as follows:
1 2 3 4 5 6 7 8 9 10
You can put water to only top glass. If you put more than 1 litre water to 1st glass, water overflows and fills equally in both 2nd and 3rd glasses. Glass 5 will get water from both 2nd glass and 3rd glass and so on.
If you have X litre of water and you put that water in top glass, how much water will be contained by jth glass? Write a program to find it.
Example. If you will put 2 litre on top.
1st – 1 litre
2nd – 1/2 litre
3rd – 1/2 litre
ПереводНесколько банок емкостью 1 литр выстроены пирамидой вот так:
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 литра
Ответы будут даны в течение следующей недели — успейте решить. Удачи!
Комментарии (26)
Rsa97
28.03.2018 14:47+1Вопрос 1Первая кость — 0, 1, 2, 3, 4, 5
Вторая кость — 0, 1, 2, 6, 7, 8
Шестёрка также работает как девятка.
almaredan
28.03.2018 16:18Прошу извинить за корявый рунглиш
Задача 3:class glass(): def __init__(self, name, left=None, right=None): self.name = str(name) self.litre = 0 self.right = right self.left = left def _fill(self): if self.litre > 1: if self.right != None and self.left != None: self.right.fill((self.litre - 1)/2) self.left.fill((self.litre - 1)/2) self.litre = 1 def fill(self, litre): self.litre += litre self._fill() def print_val(self): if self.litre > 0: return(" and {:.2f} litres".format(float(self.litre))) else: return('') def __str__(self): if self.right != None and self.left != None: return(self.name + " glass contains childs: " + self.left.name + " and " + self.right.name + self.print_val()) else: return(self.name + " glass has no childs" + self.print_val()) layers= [] layers.append([glass(7+i) for i in range(0,4)]) layers.append([glass(4+i, layers[0][i], layers[0][i+1]) for i in range(0,3)]) layers.append([glass(2+i, layers[1][i], layers[1][i+1]) for i in range(0,2)]) layers.append([glass(1+i, layers[2][i], layers[2][i+1]) for i in range(0,1)]) layers = layers[::-1] gl1 = layers[0][0] gl1.fill(10) for i, lay in enumerate(layers): print("\nLayer " + str(i)) for gl in lay: print(gl)
Layer 0
1 glass contains childs: 2 and 3 and 1.00 litres
Layer 1
2 glass contains childs: 4 and 5 and 1.00 litres
3 glass contains childs: 5 and 6 and 1.00 litres
Layer 2
4 glass contains childs: 7 and 8 and 1.00 litres
5 glass contains childs: 8 and 9 and 1.00 litres
6 glass contains childs: 9 and 10 and 1.00 litres
Layer 3
7 glass has no childs and 0.38 litres
8 glass has no childs and 1.00 litres
9 glass has no childs and 1.00 litres
10 glass has no childs and 0.38 litres
kardan2
28.03.2018 20:31Традиционно мои варианты:
Вопрос 1При использовании 2 костей, всего граней 12, причем на обоих костях должны быть грани 0 1 2. Осталось по 3 грани на каждой кости, их заполняем 3 4 5 и 6 7 8. Не хватает грани для 9. Но если перевернуть 6, то можно юзать её как 9. Это не работает на некоторых шрифтах, но этим мы пренебрежем.Rsa97
28.03.2018 23:15Вопрос 2Просто отделим половину монет и перевернём их. Получим две группы монет, в которых одинаковое количество орлов.
Изначально у нас по пять орлов и решек. После разделения на две группы в первой N орлов и (5-N) решек, во второй — (5-N) орлов и (5-(5-N)) = N решек. После переворачивания всех монет второй группы в ней будет (5-(5-N)) = N орлов и (5-N) решек.IIvana
29.03.2018 00:28Задача 1 — мой кот находит не то решение, которое приведено, но тоже правильное — при нечетном количестве 0 можно кидать в любое множество
Котg 0 _ = [[]] g _ [] = [] g n (x:xs) = map (x:) (g (n-1) xs) ++ g n xs c l = snd . minimum . map (\x -> (abs (2 * sum x - s), x)) $ g n l where s = sum l n = length l `div` 2 main = do print $ c [3, 4, 5, -3, 100, 1, 89, 54, 23, 20] print $ c [23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4] ........ [3,5,-3,89,54] [23,-99,4,189,4]kardan2
29.03.2018 18:35Ради интереса, сколько будет работать ваш Кот при длине массива всего в 60? Сгенерируйте такой массив из 60 элементов например от 1000 до 9999.
IIvana
30.03.2018 03:02При длине массива 22 он выполняется 5 секунд, дальше — больше.
Но я и не утверждал что это оптимальный алгоритм. Это наивный перебор даже без отсечений, которые тут несложно добавить. Я посмотрел на тестовые данные и понял, что такого кота вполне хватит. А преждевременная оптимизация, как известно, зло :)
IIvana
29.03.2018 00:36Задача 2 — децкий сат
Котg [] = 0 g [x] = x g (x:y:xs) = max (x + g xs) $ g (y:xs) main = do print $ g [3, 2, 7, 10] print $ g [3, 2, 5, 10, 7] print $ g [5, 5, 10, 100, 10, 5] print $ g [1, 2, 3] print $ g [1, 20, 3] ......... 13 15 110 4 20IIvana
29.03.2018 01:48Задача 3 — если под "попадет" понимать "останется" — то надо просто взять максимум 1 и результата функции.
Котrc i = go i 1 1 where go i r b | i < b + r = (p, q) | otherwise = go i (r+1) (b+r) where p | i<=b = 0 | otherwise = i-r q | i>=b+r-1 = 0 | otherwise = i-r+1 g x = go where go 1 = x go i = p l + p r where (l, r) = rc i p 0 = 0 p i = (go i - 1) / 2 main = print $ g 2 3 ........ 0.5IIvana
29.03.2018 01:49Вопрос 1 — 6*6 > 31 так что задача решаема. Вариантов — море, простейший — 6-ричная система.
lastuniverse
29.03.2018 08:23в первом вопросе есть решение без переворачивания 6и-9и. Просто не нужен 0 на обоих кубиках)
smer44
29.03.2018 08:291 задача — какое там к чёрту n!, там навскидку O( n^3 * log n [ / 8]):
разбиваем на два подмножества {3, 4, 5, -3, 100}{ 1, 89, 54, 23, 20}, разница -78, считаем все разницы между числами O( n^2) помещаем в матрицу size(n^2) одновременно имея связь матрицы с отсортированным массивом чисел из неё. Каждый раз ищем бинарным поиском число как можно более близкое к разнице, при нахождении меняем местами соответствующие числа. гарантировано каждый раз разница уменьшается перестановок n(худший случай: будут переставлены все)* n^2 (размер массива для поиска) * log n (каждый раз бинарным поиском) / 8 (потому что n — половина)
но это так сдуру придумалось, может кто лучше придумает. А то вообще через перебор комбинацией глупо как то.
2) сперва тоже сортируем наверно, что потом- подумаю… а стоп kardan2 решил в один проход
3) там просто отдельная формула для каждой банки потому что наполняются по разному по условию
kardan2
29.03.2018 19:04По первой задаче.
Здесь можно привести аналогию с поиском минимума на 2d карте. Есть такой алгоритм — движение в направлении градиента. Но вот проблема, вы можете попасть в ловушку ЛОКАЛЬНОГО минимума, и не сможете дойти до абсолютного.
Например у вас есть такая разбивка:
1000 1100 (+100)
2111 2000 (-111)
3005 3000 (-5)
4404 4000 (-404)
5000 5200 (+200)
6000 6200 (+200)
— (-20)
Я специально взял такие цифры, чтобы замена чисел разными строчками давали большую разницу. По вашей логике мы находим в таблице переходов найти число, близкое к -20. Очевидно, что это -5 (3-я строка). После обмена значениями в 3-1 строке, разница станет -10, и больше вы ничего заменить не сможете, т.к. все остальные числа в таблице переходов гораздо большие, чем -10 по модулю.
Но если вместо 3-й строки провести обмен в 1 и 2 строках сразу, то в итоге мы получим разницу всего в +2.
Поэтому утверждение «гарантировано каждый раз разница уменьшается» не приводит к нахождению минимума.
Поэтому пока остается полный перебор. Это означает С(n, n/2)=n!/((n/2)!*(n/2)!).
При n=60 получаем примерно 10^17, а при n=100 уже примерно 10^23. Это при том, что мы увеличили значение меньше, чем в 2 раза (100 против 60) результат возрос очень сильно.smer44
30.03.2018 01:18а да ты прав.
тогда можно не заморачиваться а решить двумя greedy- сумками.
сортируем O (n log n ) и вкладываем в сумки пытаясь уравнять.
на практике то задачу можно считать решённой если разница намного меньше суммы.
Nick_mentat
29.03.2018 13:36дайсы{1,2,0,4,5,6}, {1,2,3,0,7,8}, 9 получаем перевернув 6z1024
29.03.2018 15:20Tug Of WarЭто походу известная NP-hard CS проблема: en.wikipedia.org/wiki/Partition_problem
У которой есть разнообразные решения, только по-моему это не формат для интервью.kardan2
29.03.2018 19:09По всей видимости вы правы. Много раз встречался с похожей задачей на практике, но прикидывал примерное решение, ничего не находил и старался обойти этот момент. Т.е. Задача не выдуманная, а вполне реальная.
Однозначно ей делать нечего на собеседовании из-за её сложности. Я так понимаю, что все «быстрые» методы не дают гарантированное решение.z1024
29.03.2018 22:11Ну может разве только что бы послушать как кандидат бьется об стену — что бы излагал ход своих мыслей )
prika148
Во второй задаче, если я не ошибаюсь, не совсем точный перевод фразы:
reci Автор
Спасибо, принято.
gottalottarock
Он принципиально меняет задачу. В нынешней русской формулировке она или непонятна или нерешаема.
reci Автор
Мне, наверное, как автору, кажется простым.
Предложите свой вариант.
Ju1ius
Как сделать 2 стопки, с равным количеством монет повернутых орлом вверх?
gottalottarock
Я бы заменил вопрос на:
«Как сделать 2 стопки монет, с равным количеством орлов в каждой стопке?»
Задача простая, конечно.