Комментарии 49
Это тест на адекватность?
Если убрать из рассмотрения этот момент, то скорость одного поезда относительно другого — 50+70 = 120 км\ч. 100 км они пройдут за 100\120 = 5\6 часа. За это время пчела пролетит (сама траектория не важна, она сама по себе летает) 5\6часа*40км\ч=100\3км. Т.е. чуть больше 33 км.
Если бы по другому построили вопрос, тогда. решение такое. Мы можем разделить все бочки на 6 групп. Каждый раб выпивает только из одной своей группы все бочки. Если раб умирает, тогда бочка находится в его группе (если не умирает никто, то бочка в той группе, в которой никто не пил). Но тогда мы приходим к 240\6=40 бочкам и 4-м рабам на вторую попытку. Значит нужно действовать иначе.
Делим все бочки на N групп, каждый раб выпивает из 2-х своих групп, так чтобы из каждой группы пили 2 раба. Понятно, что таких групп у нас (6*5\2=) 15. Тогда ценой потери 2-х рабов мы сократили перебор до 240\15 = 16 бочек и имеем 3-х рабов минимум. Теперь нумеруем каждую бочку, и переводим число в 2-е счисление. Теперь, нумеруем рабов. Каждый раб пьет из бочки с номером таким-то, если бит этого номера соответствует номеру раба. По состоянию рабов мы можем понять в какой из (2^3=) 8-ми бочек яд. Но нам надо протестить 16 бочек. Значит нужно поделить бочки на группы не в равном количестве, чтобы больше приходилось на ту группу, где гибнет меньшее число рабов.
Итак, за вторую попытку если у нас осталось жить m рабов, мы можем определить ядовитую среди 2^m бочек.
Делим все бочки на 32 группы. Из бочки группы пьем раб, если он соответствует биту номера группы. Итого, в 1 случае гибнут все рабы, в 5 случаях 4 раба, в 10 случаях 3 раба, 10 случаях 2 раба, в 5 случаях 1 раб и в 1 случае ни одного. Следовательно мы можем определить бочку из 1*1+5*2+10*4+10*8+5*16+1*32 = 243.
Согласен, однако, если отрешиться от морали — задача интересная. Завернул в другую обёртку.
Проходим по массиву. Изначально счетчик с=0. Если встречаем 1, то прибавляем 1, если встречаем 0, то вычитаем 1. Далее по адресу c+n заносим значение текущей позиции.
Второй проход, делаем тоже самое, но вместо записи во второй массив считываем значение из ячейки c+n и вычитаем текущую позицию. И находим максимум вычисленного значения.
Можно сократить размер массива до n+1 если номер ячейки вычислять как с%(n+1)
Пока в голову приходит что сумма битов чисел от 1 до (2^n)-1 равно (2^n)*n/2.
Задачу 2 можно решить и в один цикл :)
Можно посчитать, сколько раз каждый бит (с номером 0,1,2...) будет встречаться в значении 1 в числах от 1 до n.
Если выписать в двоичном виде числа 0,1,2,3,4,5..., то можно увидеть, что:
0-й бит встречается в каждом втором числе, паттерн: 0,1,0,1,0,1,0,1,…
1-й бит встречается дважды в каждой четвёрке чисел, паттерн: 0,0,1,1,0,0,1,1,…
2-й бит встречается четырежды в каждой восьмёрке чисел, паттерн: 0,0,0,0,1,1,1,1,…
…
n-й бит встречается (2^n) раз в каждой полной группе из (2^(n+1)) чисел.
Дополнительно нужно обработать "остатки" от деления числа n на степени 2-ки.
Допустим, число 14 дало остаток 6 при делении на 8. При этом, в числах от 9 до 14 второй бит встретится в значении 1 трижды (числа 12,13,14), и эти 3 единичных бита тоже добавляем к результату.
using System;
class Solution
{
static void Solve(int n)
{
int result = 0;
for (int k = 1; k <= n; k = k << 1)
{
result += k * (n / (k << 1));
result += Math.Max(((n % (k << 1)) + 1) - k, 0);
}
Console.WriteLine($"n = {n}, result = {result}");
}
static void Main(string[] args)
{
foreach (int n in (new int[] { 3, 6, 7, 8 }))
Solve(n);
}
}public static int[] largestSubarray(int[] array){
final int n = array.length+1;
int[] secondArray = new int[n];
int c = 0;
// Первый проход - заполняем массив
for(int i=0; i<array.length; i++){
if(array[i]==1){
c++;
}else{
c--;
}
secondArray[c%n]=i;
}
// Второй проход - ищем максимальную длинну подмассива
c = 0;
int index = -1;
int maxValue = secondArray[0]+1;
for(int i=0; i<array.length; i++){
if(array[i]==1){
c++;
}else{
c--;
}
if(secondArray[c%n]-i>maxValue){
maxValue = secondArray[c%n]-i;
index = i;
}
}
// Если найден подмассив
if(maxValue>1){
int result[] = new int[2];
result[0] = index+1;
result[1] = index+maxValue;
return result;
}
return null;
}public static int totalBits(int value){
int count =0;
int mask = 1;// 0001, 0010, 0100, 1000 ...
int mask2 =0;// 0000, 0001, 0011, 0111 ...
while(value>mask){
count+=(value&mask2);
count+=(value -(value&(mask+mask2)) )/2;
mask2+=mask;
mask = mask + mask;
}
return count;
}
public static int[] findRepeatingMissing(int[] array){
int a =0;
long b =0;
for(int i=0; i<array.length; i++){
a+=array[i]-i;
b+=array[i]*array[i]-i*i;
}
int result[] = new int[2];
result[0] = (int)(a+b/a)/2;
result[1] = a - result[0];
return result;
} public static int totalBits(int value){
int count =0;
int mask = 1;// 0001, 0010, 0100, 1000 ...
int mask2 =0;// 0000, 0001, 0011, 0111 ...
while(value>=mask){
if((value&mask)>0){
count+=(value&mask2)+1;
}
count+=(value -(value&(mask+mask2)) )/2;
mask2+=mask;
mask = mask + mask;
}
return count;
}Обидно, что перед отправкой проверял, но попал именно на те значения, на которых ошибки не было.
Обозначим Si суммарное кол-во единичек минус суммарное кол-во ноликов от начала последовательности до позиции i (не включая саму i).
Тогда нужный нам подмассив, начинающийся с позиции i и заканчивающийся на j, обладает свойством Si = Sj+1. Нам нужно найти сами индексы i и j. Можно использовать «жадный» алгоритм, что если Si = Sj+1 для разных i, j, мы берём минимальный i и максимальный j.
В массив R (secondArray) положим индекс j, такой, что R[Sj] = j.
Причём, если для разных j1 < j2 одинаковое Sj1 = Sj2, то в массив R положим последний j2 (т.е. больший). Это обеспечивается тем, что первый цикл, который последовательно вычисляет Si, замещает в массиве R ранее записанное значение i на следующее, большее.
Второй проход снова последовательно считает Si, и сразу для рассчитанного Si из массива R получает индекс j — максимальный индекс, такой, что Si=Sj.
Извращение с Si mod n нужно, чтобы привести значения Si, которые используются для индекса к X, из диапазона [-n;n] к [0;2*n] (кстати, не очень понял, почему для secondArray достаточно длины n).
(кстати, не очень понял, почему для secondArray достаточно длины n
Достаточно длины (n+1), если n — длина исходного массива. Если у нас например все 1, то счетчик дойдет до n, и так как n%(n+1)=n, то последний элемент все равно не совпадет с первым элементом, у которого индекс 0. Также верно и в обратную сторону.
Как может пчела со скоростью 40 км\ч летать между поездами, когда у обоих скорость больше?
Хорошее замечание. Надо было написать «пытается летать» — по тому правилу, которое сформулировано дальше. При этом результат не изменится.
Было бы имхо больше пользы, если бы IT сообщество просто поделилось бы опытом о своих собеседованиях на ресурсах типа Jobingood.
Ну и мне лично интересно порешать их после рабочей недели :)
Вопрос — какое отношение имеет физическая задача про муху к программированию — то есть что оценивается
Я такие задачи решал еще в школе (как и про яд)
На собеседовании по програмиированию ожидаешь более профессиональные вопросы в рамках профессиональных требований — типа а почему NoSQL — в чем преимущество.
Или как-то меня спрашивали про оценки времени запроса к серверу.
То есть ответы должны отражать имеющийся профессиональный уровень по отношению к ожидаемому
Я проходил достаточное количество собеседований в разные фирмы — и появление в них задач подобного плана оценивал, как пустую трату времени — тем более я мог задать подобную задачу задающему ее сотруднику, и не думаю. что он мог бы ее решить.
А причины указанные вами надуманные. Ход рассуждений никто не спрашивает. реакцию никто не оценивает — интересует ответ.
Возможно, другая сторона думает совсем иначе.
Да, есть вакансии, где нужен конкретный спец под конкретное дело с учетом того, что выбранный инструмент — это надолго.
Но посмотрите с другой стороны, сейчас всё очень быстро меняется, через полгода ваш любимый фреймворк или любимая база данных (в которой вы спец и можете ответить на любой технический вопрос) устареет и будет заменена на другую. И компания получит бесполезного работника в виде вас.
А вот если человек не знает технических тонкостей, но соображает (хорошо решает подобные задачи), то он быстро разберется в технологии и по ходу разберется что и как.
Конечно, важно и умение соображать и знание конкретной технологии, но я бы оценивал их как 2 к 1.
тем более я мог задать подобную задачу задающему ее сотруднику
Смысл? Проверяются ваши качества, а не того сотрудника.
В лучшем случае у вас будет материал для беседы, в худшем минус бал (или 2) для вас за сомнительное поведение.
Вот меня часто просят рассказать «ход рассуждений». Так, что вот вам пример (в виде меня), опровергающий ваше мнение.
Как говорится в юриспруденции — ваше слово на мое слово ничего не опровергает, как и мое слово на ваше слово.
Интересн контекст.
Я работал сотрудником и работал руководителем, проводил собеседования и оценивал результаты собеседования по работе принятого сотрудника.
То есть для меня за моими словами стоит мой опыт — видимо он не пересекается с вашим опытом, но все же я уважаю ваше мнение и не опровергаю его — я высказываю свое мнение.
Кстати, ради интереса — а в чем изюминка задачи про муху
Ещё есть класс задач, которые легко решают дети, но не могут решить взрослые люди. Т.е. будет лучше, если кандидат не сможет решить такую задачу. www.lprobs.ru/prob37solve.html
Ещё был случай, когда на собеседовании после 9 чисто технических вопросов по языку дали простую задачу по геометрии. Зачем это сделали — не знаю. Видимо я много ещё чего не понимаю в собеседованиях.
изюминка задачи про муху заключается в том, что она включает в себе две школьные задачи, ответ одной используется для решения другой.
Основная задача собеседования — легитмитизировать отсев — то есть даже если вы удачно ответили на все вопросы, всегда можно сказать, что есть еще более удачный кандидат — для упрощения этой задачи и используются всякие абстрактные задачи и вопросы
Не понял ваше замечание про муху — она всегда летит навстречу одному или другому поезду, то есть не догоняет, а встречает один или другой в полете.
Даю подобную задачу — я нахожусь около трамвайных путей и имею возможность остановить трамвай в любой точке пути. Место, куда мне нужно прибыть, достаточно далеко, так что при движении пешком трамвай обязательно появится. Вопрос — в каком направлении выгодно двигаться: навстречу трамваю, чтобы быстрее его встретить или по ходу движения трамвая. чтобы меньше осталось расстояния до нужной точки. Ясно, что скорость трамвая больше, чем моя скорость движения.
Делим бутылки поровну между заключенными: 48 на каждого. Каждый пьет из новой бутылки раз в 30 минут, закончит через 23 часа 30 минут. Ждем пока умрет заключенный, замеряем сколько минут прошло с момента начала эксперимента. Отравленная бутылка будет иметь номер (время-23.5*60) div 30.
Уменьшая задержку между бутылками можно увеличить количество бутылок для проверки.
The poison when taken has no effect on the prisoner until exactly 24 hours later when the infected prisoner suddenly dies.
Как минимум 24 часа. Если больше, а не ровно, то решений уже нет: два раза по больше чем 24 превысит 48
Автор?
Русские варианты не читал вообще, но для английского «exact» получается довольно тривиальное решение: один смертник пьёт все 240 бутылок с перевывом в 5 минут. Если смерть наступает ровно через 24 часа, часы нам покажут, какая бутылка сработала.
Есть формулировка получше: волшебный яд действует ровно в 12:00 (в полдень), поэтому до дедлайна есть только 2 попытки проверить бутылки на каждом смертнике.
Помогите довести
Подсчитаем для каждого 2^n числа сумму всех бит чисел до него включительно:
Для 0: 0;
Для 1: 0, 1, s=1
Для 2^n = s[2^(n-1)] * 2 + 2^n; // так как на порядок ниже все числа повторяются, с 1
Далее имеем: {0..10100} = {0..10000} + 10{0..100}
Если это добить, получится решение, которое работает ~за кол-во бит операций
Вроде бы никто не писал такое решение задачи 2. Занумеруем бутылки в системе счисления по основанию 3. Дальше думаю все понятно. 3^5=243 как раз.
Как по мне решение простое и эффективное.
У эксперимента 2 исхода: умер или нет.
Смертнику можно дать N-ю бутылку или нет.
На этом основано решение с двоичной нумераций.
Как переложить на троичную нумерацию?
Если нумеровать бутылки троично то можно 5-ю разрядами занумеровать. Трактовать следующим образом
0 — не пить из бутылки
1 — выпить из бутылки
2 — *** (пока удалил т.к. возможно кто-то еще захочет решить)
Я почему-то думал, что если 2%3=2, 1%3=1, 0%3=0, то и -1%3 даст опять 2. Но нет, -1%3=-1.
Поэтому в моем решении нужно перед взятием по модулю прибавлять то самое n (или n+1).
Выпуск#8: ITренировка — актуальные вопросы и задачи от ведущих компаний