Комментарии 27
Во второй задаче, если я не ошибаюсь, не совсем точный перевод фразы:
Can you make two piles of coins each with the same number of heads up?
Вопрос 1
Первая кость — 0, 1, 2, 3, 4, 5
Вторая кость — 0, 1, 2, 6, 7, 8
Шестёрка также работает как девятка.
Вторая кость — 0, 1, 2, 6, 7, 8
Шестёрка также работает как девятка.
Прошу извинить за корявый рунглиш
Задача 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
Традиционно мои варианты:
Вопрос 2. Не понял условия. Что можно делать с монетами, точнее что может дать нам ощупывание монет? Попробовал на ощупь сравнить 2 монеты — не получается.
Задача 1. Не решена. Не вижу способа, кроме полного перебора, но там сложность порядка n! Такие решение рассматривать не имеет смысла.
Вопрос 1
При использовании 2 костей, всего граней 12, причем на обоих костях должны быть грани 0 1 2. Осталось по 3 грани на каждой кости, их заполняем 3 4 5 и 6 7 8. Не хватает грани для 9. Но если перевернуть 6, то можно юзать её как 9. Это не работает на некоторых шрифтах, но этим мы пренебрежем.
Вопрос 2. Не понял условия. Что можно делать с монетами, точнее что может дать нам ощупывание монет? Попробовал на ощупь сравнить 2 монеты — не получается.
Задача 1. Не решена. Не вижу способа, кроме полного перебора, но там сложность порядка n! Такие решение рассматривать не имеет смысла.
Задача 2
Ведем максимальную сумму ряда у которой последний элемент не задействован, и максимальную сумму без ограничения. Добавление нового элемента вполне очевидно.
Итого получаем линейный проход, без доп. памяти.
public static int maxSum(int[] _array){
int sum_0 =0;
int sum_1 =0;
for(int i=0; i<_array.length; i++){
int value = _array[i];
int sum_0_next = sum_1;
sum_1 = Math.max(sum_1, sum_0+value);
sum_0 = sum_0_next;
}
return sum_1;
}
public static void main(String[] _ar){
int[] mayarray = {15,1,2,3,4,15,6};
System.out.println(maxSum(mayarray));
}Ведем максимальную сумму ряда у которой последний элемент не задействован, и максимальную сумму без ограничения. Добавление нового элемента вполне очевидно.
Итого получаем линейный проход, без доп. памяти.
Задача 3
Пока без кода. По номеру рюмки мы должны вычислить ряд в котором она стоит и номер в этом ряду. Далее выделяем «ромб» (ну как бы ромб, параллелограмм) верхняя вершина совпадает с первой рюмкой, нижняя с целевой чашкой, а грани идут параллельно боковым сторонам треугольника. Этот «ромб» охватывает все кружки, которые имеет смысл вычислять.
Пусть имеем «ромб» со сторонами 7 и 3. Выбираем меньшее 3. Выделяем массив размером с 3. Вычисляем не сложными действиями количество воды прошедшие через кружки (w, (w-1)/2, ((w-1)/2-1)/2). Потом в цикле (всего 7 итераций или точнее 6=7-1) сдвигаем ряд по второй стороне, и вычисляем кол-во воды в кружках, так мы доходим до целевой кружки.
Если воды там больше чем 1, то возвращаем 1.
Пусть имеем «ромб» со сторонами 7 и 3. Выбираем меньшее 3. Выделяем массив размером с 3. Вычисляем не сложными действиями количество воды прошедшие через кружки (w, (w-1)/2, ((w-1)/2-1)/2). Потом в цикле (всего 7 итераций или точнее 6=7-1) сдвигаем ряд по второй стороне, и вычисляем кол-во воды в кружках, так мы доходим до целевой кружки.
Если воды там больше чем 1, то возвращаем 1.
Код для задачи 3
Оставил вывод поэтапной информации, чтобы легче было отследить правильность.
public static float waterFall(int _position, float _water){
int level = getLevelPosition(_position);
int firstCup = (level-1)*level/2+1;
int numberAtLevel = _position-firstCup+1;
if(numberAtLevel*2>level){
numberAtLevel = level - numberAtLevel+1;
}
int steps = level - numberAtLevel+1;
float[] array = new float[numberAtLevel];
array[0]= _water;
for(int i=0; i<steps; i++){
if(i!=0){
array[0]=Math.max(0f, (array[0]-1f)/2f);
System.out.print(" 0 = "+array[0]);
}
for(int k =1; k<numberAtLevel; k++){
array[k]=Math.max(0f, (array[k-1]-1f)/2f)+Math.max(0f, (array[k]-1f)/2f);
System.out.print(" | * = "+array[k]);
}
if(array[numberAtLevel-1]<=0f){
return 0f;
}
System.out.println();
}
return Math.min(1f, array[numberAtLevel-1]);
}
public static int getLevelPosition(int _position){
int level = (int)Math.round((-1+Math.sqrt(1+8*_position))/2.f);
int lastCup = (level+1)*level/2;
if(_position<=lastCup){
return level;
}else{
return level+1;
}
}
public static void main(String[] _a){
float b = waterFall(8, 8f);
System.out.println(" "+b);
}Оставил вывод поэтапной информации, чтобы легче было отследить правильность.
Days of month using 2 dice:
запишу в 6-ричной системе.
запишу в 6-ричной системе.
Вопрос 2
Просто отделим половину монет и перевернём их. Получим две группы монет, в которых одинаковое количество орлов.
Изначально у нас по пять орлов и решек. После разделения на две группы в первой N орлов и (5-N) решек, во второй — (5-N) орлов и (5-(5-N)) = N решек. После переворачивания всех монет второй группы в ней будет (5-(5-N)) = N орлов и (5-N) решек.
Изначально у нас по пять орлов и решек. После разделения на две группы в первой N орлов и (5-N) решек, во второй — (5-N) орлов и (5-(5-N)) = N решек. После переворачивания всех монет второй группы в ней будет (5-(5-N)) = N орлов и (5-N) решек.
Задача 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]Ради интереса, сколько будет работать ваш Кот при длине массива всего в 60? Сгенерируйте такой массив из 60 элементов например от 1000 до 9999.
При длине массива 22 он выполняется 5 секунд, дальше — больше.
Но я и не утверждал что это оптимальный алгоритм. Это наивный перебор даже без отсечений, которые тут несложно добавить. Я посмотрел на тестовые данные и понял, что такого кота вполне хватит. А преждевременная оптимизация, как известно, зло :)
Задача 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
20Задача 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.5Вопрос 1 — 6*6 > 31 так что задача решаема. Вариантов — море, простейший — 6-ричная система.
в первом вопросе есть решение без переворачивания 6и-9и. Просто не нужен 0 на обоих кубиках)
1 задача — какое там к чёрту 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) там просто отдельная формула для каждой банки потому что наполняются по разному по условию
разбиваем на два подмножества {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) там просто отдельная формула для каждой банки потому что наполняются по разному по условию
По первой задаче.
Здесь можно привести аналогию с поиском минимума на 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) результат возрос очень сильно.
Здесь можно привести аналогию с поиском минимума на 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) результат возрос очень сильно.
дайсы
{1,2,0,4,5,6}, {1,2,3,0,7,8}, 9 получаем перевернув 6
2
отобрать любые 5 и перевернуть
Над первой задачей я задумался буквально недавно, глядя на счастливые билетики. Предлагаю более интересный вопрос: оценить долю «счасливых» наборов чисел (таких, кторые можно разделить на 2 части с равной суммой), среди всех возможных наборов, с суммой меньше N.
3
Тут надо считать литры по мере построения графа. Обходить в ширину. Не наполненый до конца стакан — заглушка в графе, тупик лабиринта.
Tug Of War
Это походу известная NP-hard CS проблема: en.wikipedia.org/wiki/Partition_problem
У которой есть разнообразные решения, только по-моему это не формат для интервью.
У которой есть разнообразные решения, только по-моему это не формат для интервью.
По всей видимости вы правы. Много раз встречался с похожей задачей на практике, но прикидывал примерное решение, ничего не находил и старался обойти этот момент. Т.е. Задача не выдуманная, а вполне реальная.
Однозначно ей делать нечего на собеседовании из-за её сложности. Я так понимаю, что все «быстрые» методы не дают гарантированное решение.
Однозначно ей делать нечего на собеседовании из-за её сложности. Я так понимаю, что все «быстрые» методы не дают гарантированное решение.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Выпуск#15: ITренировка — актуальные вопросы и задачи от ведущих компаний