Мы подготовили для вас новый сет задач и вопросов, задаваемых на собеседованиях в ведущих IT-компаниях.
В подборку вошли задачи для соискателей в Amazon. Вопросы задаются, в том числе и логистические, только не с дронами, а с верблюдами :)
Мы постарались подобрать задачи различного уровня сложости, но, в любом случае, их решение будет хорошим упражнением для мозга.
Pythagorean Triplet
Anti-clockwise rotated array
Ответы будут даны в течение следующей недели — успейте решить. Удачи!
В подборку вошли задачи для соискателей в Amazon. Вопросы задаются, в том числе и логистические, только не с дронами, а с верблюдами :)
Мы постарались подобрать задачи различного уровня сложости, но, в любом случае, их решение будет хорошим упражнением для мозга.
Вопросы
- Transport the bananas
A person has 3000 bananas and a camel. The person wants to transport maximum number of bananas to a destination which is 1000 KMs away, using only the camel as a mode of transportation. The camel cannot carry more than 1000 bananas at a time and eats a banana every km it travels. What is the maximum number of bananas that can be transferred to the destination using only camel (no other mode of transportation is allowed).
ПереводУ человека есть 3000 бананов и верблюд. Он хочет отвезти максимум бананов в пункт назначения, находящийся в 1000 км, используя верблюда в качестве транспорта. Верблюд не может перевозить более 1000 бананов за раз и ест по одному банану за каждый километр пути.
Какое наибольшее количество бананов удастся доставить таким способом (другие способы перевозки не разрешены)?
- Measure forty-five minutes using wires
How do we measure forty-five minutes using two identical wires, each of which takes an hour to burn. We have matchsticks with us. The wires burn non-uniformly. So, for example, the two halves of a wire might burn in 10 minute and 50 minutes respectively.
ПереводИмеется 2 идентичных шнура, каждый из которых сгорает за час. Спички у нас с собой, шнуры сгорают неравномерно. Так, например, половина может сгореть за 10 минут и оставшаяся половина за 50 минут. Как, используя эти шнуры, нам отсчитать 45 минут?
Задачи
- Elephants lifetime
Given life time of different elephants. Find the period when maximum number of elephants were alive.
Input: [2005, 2010], [2006, 2015], [2002, 2007]
Output: [2006, 2007] .ПереводДано время жизни нескольких слонов. Найти период, в который жило наибольшее количество слонов.
Вход: [2005, 2010], [2006, 2015], [2002, 2007]
Выход: [2006, 2007] .
Pythagorean Triplet
Given an array of integers, write a function that returns True if there is a triplet (a, b, c) that satisfies a^2 + b^2 = c^2.
Example:
Input: arr[] = {3, 1, 4, 6, 5}
Output: True
There is a Pythagorean triplet (3, 4, 5).
Input: arr[] = {10, 4, 6, 12, 5}
Output: False
There is no Pythagorean triplet.
Перевод
Дан массив целых чисел, нужно написать функцию, возвращающую True, если в массиве содержится тройка чисел (a, b, c), так, что a^2 + b^2 = c^2
Пример:
Вход: arr[] = {3, 1, 4, 6, 5}
Выход: True
Пифагорова тройка — (3, 4, 5).
Вход: arr[] = {10, 4, 6, 12, 5}
Выход: False
Пифагоровской тройки в массиве нет.
Пример:
Вход: arr[] = {3, 1, 4, 6, 5}
Выход: True
Пифагорова тройка — (3, 4, 5).
Вход: arr[] = {10, 4, 6, 12, 5}
Выход: False
Пифагоровской тройки в массиве нет.
Anti-clockwise rotated array
Consider an array of distinct integers sorted in increasing order. The array has been rotated (anti-clockwise) k number of times. Given such an array, find the value of k.
Array rotation:
* * 0 1 5 1 => 0 2 4 2 5 3 3 4
Examples:
Input: arr[] = {15, 18, 2, 3, 6, 12}
Output: 4
Initial array must be {2, 3, 6, 12, 15. 18}. We get the given array after rotating the initial array twice.
Input: arr[] = {7, 9, 11, 12, 5}
Output: 1
Input: arr[] = {7, 9, 11, 12, 15};
Output: 0
Перевод
Предположим, имеется массив целых чисел, отсортированный по возрастанию. Массив был «повернут» против часовой стрелки k раз. Найти k.
Поворот массива означает:
Примеры:
Вход: arr[] = {15, 18, 2, 3, 6, 12}
Выход: 4
Исходны массив должен быть — {2, 3, 6, 12, 15. 18}. Мы получим входной массив, если повернем исходный 2 раза.
Вход: arr[] = {7, 9, 11, 12, 5}
Выход: 1
Вход: arr[] = {7, 9, 11, 12, 15};
Выход: 0
Поворот массива означает:
* *
0 1
5 1 => 0 2
4 2 5 3
3 4
Примеры:
Вход: arr[] = {15, 18, 2, 3, 6, 12}
Выход: 4
Исходны массив должен быть — {2, 3, 6, 12, 15. 18}. Мы получим входной массив, если повернем исходный 2 раза.
Вход: arr[] = {7, 9, 11, 12, 5}
Выход: 1
Вход: arr[] = {7, 9, 11, 12, 15};
Выход: 0
Ответы будут даны в течение следующей недели — успейте решить. Удачи!
Andy_U
Второй вопрос простой:
1) Сначала зажигаем первую веревку с обоих концов, а вторую с одного.
2) Когда первая сгорит (а это произойдет ровно через 30 минут!) зажигаем вторую веревку с другого конца. Как догорит, так и 45 минут.
DaneSoul
Rsa97
Не сработает. Поджигание верёвки одновременно с концов и посередине не гарантирует, что каждая половина сгорит за одно и то же время. Первая половина может сгореть за 5 минут, а вторая за 25.
DaneSoul
Да, согласен, не предусмотрел этот момент
kemply
Есть ещё другой способ:
При условии, что обе веревки имеют неравномерные сгорания одинаково, то поджечь первую с обеих сторон, а вторую с обеих сторон и с точно того же места, где догорела первая. Так 30+15=45
Andy_U
В комменарии автора (где-то ниже ) написано, что концы неотличимы, но, по условиям задачи, веревки одинаковые.
Но вот чего нет в условии, так это утверждения, что локальная скорость горения веревки не зависит от направления горения. Ну, это кажется очевидным, однако, если таки зависит, то нет никакой гарантии, что веревка, подожженная с двух концов, сгорит за 30 минут.
Вот тут бы и помогла идентификация концов — 30 мин можно было бы померять положив веревки «навстречу» друг други и зажечь их опять же навстречу друг другу. Как точки горения совпадут так и 30 мин. Потом опять их сдвигаем конец к началу и опять ждем совпадения точек горения. Но вот если концы таки неотличимы, я пока не понимаю, что делать.
IgnisDeus
0. 3000 бананов
100км. 2500 бананов (взял 1000 бананов с отметки 0 привез 900 бананов, взял 100 бананов, поехал на отметку 0, повторил)
200км. 2000 бананов
300км. 1700 бананов
400км. 1400 бананов
500км. 1100 бананов
Далее берем 1000 бананов и едем в конечный пункт
600км. 900 бананов
700км. 800 бананов
800км. 700 бананов
900км. 600 бананов
1000км. 500 бананов
Andy_U
А почему это максимум?
Andy_U
Ага, можно больше довезти таким способом, а именно:
1) Тащим бананы на отметку 200 км за 5 ходок, где окажется 3000-200*5=2000 бананов.
2) Тащим бананы далее на 333 км за 3 ходки до отметки 533 км, где окажется 1001 банан.
3) Тащим 1000 бананов до конца. Дистанция 467 км. Итого довозим 1000-467 = 533.
Но я все равно не уверен, что и это — максимум.
zarfaz
На х километров возможно перевезти только (1000-2х) бананов, при условии что нужно возвращаться. Стоимость перевозки при этом окажется 2х бананов, которые будут съедены.
Целевая функция оптимизации — это количество полезной нагрузки делить на количество съеденных бананов.
f(x)= (1000-2x)/2x -> max
Берем производную, приравниваем к нулю и находим х
Это — обычная гипербола, которая стремиться к бесконечности около нуля. Ответ — максимальная производительность при минимальном шаге. Проверим численно:
Едем на 500 километров — получаем 0 полезной нагрузки и 1000 бананов съедено
Едем на 1 километр — получаем 998 полезной нагрузки и 2 съеденных банана.
Получается, все итерационные циклы выгоднее всего делать с минимальным шагом. Допустим, наш минимальный шаг будет 1 (в случае дробного шага результат будет почти таким же — но об этом в конце)
Дальше — excel, хотя сейчас я понимаю, что можно и мысленно было:
Этап 1 — перевозим все доступные бананы за 3 ходки на 1 километр за каждый шаг.
Этап 1. Шаг 1. Перевозим все бананы на 1-ый километр. Расход — 6 бананов за три ходки. Итог — доступно 2994, все находятся на 1-ом километре.
Этап 1. Шаг 2. Перевозим все доступные бананы с 1-ого на 2-ой километр. Расход — 6 бананов. Итог — доступно 2988, все находятся на 2-ом километре.
…
Этап 2. На 167 километре у нас будет доступно 1998 бананов. С этого момента, стоимость перевозки всех бананов на следующий километр будет 4 банана.
Этап 2. Шаг 1. Перевозим все бананы с 167-ого на 168-ой километр. Расход — 4 банана, итог — доступно 1986 бананов.
…
Этап 3. На 666 километре у нас остается 1000 бананов. С этого момента вся модель перестает работать, потому что нам больше не нужно возвращаться. Это то самое краевое условие, которым мы пренебрегли. Берем все бананы и едем до конца.
Расход — 334 банана, итог — 666 бананов на 1000-ом километре.
Если бы бананы были бесконечно делимы, то с почти нулевым шагом мы бы перевезли 2/3 всех бананов как предел ряда. Точно ряд сейчас не сформулирую, но думаю ход мысли понятен.
GrigorGri
"На 666 километре у нас остается 1000 бананов". Почему? На 167 было было 1986. Перевоз на 1км занимает 4 банана. Тогда 986/4=246 км, то есть 1к можно доставить только до 167+246=413км
zarfaz
Ваша правда, спасибо. В таком случае, ответ 533, который уже был озвучен ранее. Смысл целевой функции сохраняется, получается просто теоретическое обоснование максимального результата
Andy_U
Ну, на этом шаге Вы посчитали один лишний банан, потому что, чтобы увезти все 3000 бананов на 1 км верблюд пройдет 5 км — 3 раза туда и 2 обратно.
На 200-м километре останется 2000 бананов, далее километр будет стоить 3 банана.
Это как??? 10001 банан останется на отметке 200+333=533 км. Даже если начинать с 200 км…
Suntechnic
Итого 534/533 банана в зависимости от алгоритма верблюда. Кстати везти можно не по километру, а до точки слома модели. Т.е. первых три перехода в точку 200км, тогда от первой и второй 1000 остается 600, а от третьей 800.
Далее два перехода в точку 533 км.
Остается вопрос — нет ли точки где выгодно выбросить часть бананов. Точнее не возвращаться за ними. Имеется ввиду что мы изменим длины переходов как-то таким образом, что при последнем переходе в целевую точку, на предыдущей точке останется бананов столько же сколько стоит доставка из нее. Можно подумать что выбрав такие точки мы можем увеличить полезную загрузку.
Предположим что есть такой участок в пределах первых 200км и в точку 200км можно прийти не 3, а 2 раза. Но придя два раза, при любой загрузке невозможно получить более 1998 бананов, а у нас уже есть решение которое позволяет получить в этой точке 2000 бананов, что больше. Аналогичные рассуждения можно привести и для точки 533 км. И того максимум это 533 или 534 банана в зависимости от алгоритма верблюда, так как в точке 533 км становится важным ест ли верблюд свой банан авансом.
GrigorGri
Тут можно было получить 534 банана: не обязательно давать верблюду банан после того как он достиг километра 1000
Andy_U
Это зависит, от от того, как устроен верблюд: «утром деньги, вечером стулья» или «утром стулья — вечером деньги» :)
GrigorGri
Если он сперва ест а потом идет, то пре переходе из шага 2 в 3 сьест банан номер 1001 на старте и потратит 466 на остаток пути
Andy_U
Он еще может только на половине километра его есть. Или непрерывно есть. А по условиям задачи бананы могут ехать только на верблюде. Так что, как повезет.
inpost
Так-то
1) 200 км за 5 ходок = 200*5*2, верблюду надо возвращаться и его надо тоже кормить. За 200км мы теряем 2000 бананов, а не 1000.
Andy_U
Моя «ходка» — это в одну сторону, Т.е верблюду надо пройти 200*5=1000 км и сожрет он при этом именно что 1000 бананов.
inpost
Согласно задаче у нас есть только 1 верблюд. Чтобы вторую ходку сделать, ему надо вернуться. Это стоит учитывать.
Andy_U
Все учтено.
Еще раз, туда 200 км, обратно 200 км, туда 200 км, обратно 200 км, туда 200 км. Итого 5 раз по 200 км. Что не так то?
ADR
Если идти по одному километру то получається 533 банана.
Andy_U
Не понимаю, как так получается, потому что при таком подходе верблюд значительную часть времени будет недогруженным (как решении IgnisDeus), а жрать все равно по банану на километр, в то время как у меня получились те же 533 банана при 100% загрузке верблюда.
Хотя результаты моего первого шага совпадают с результатом 2-х первых шагов решения IgnisDeus, где верблюд тоже в конце второго шага тащил лишь 500 бананов.
m03r
А верблюд потребляет бананы только тогда, когда ходит нагруженный? Когда ходит пустой — не потребляет?
Andy_U
По условиям задачи — всегда. 1 банан на 1 километр.
An_private
А неважно какой именно отрезок проходить. Важно то, что пока бананов больше 2000 расход 5 бананов на километр. Больше 1000 — 3 банана на километр.
Следовательно, на первой тысяче бананов верблюд пройдёт 1000/5= 200 км. На второй тысяче — 1000/3= 333.(3) километров. После чего у него останется идти 1000 — 533 = 467 км, на которые он потратит 467 бананов. Значит останется 533 банана. Всё. По сколько именно идти в пределах этих километров значения не имеет.
apapacy
Этот вариант мне каженся самым простым решением. Если задасться вопросом об оптимальном расстоянии то тут важны точки излома. То есть првое перемещение должно быть 0 < X <=200. Если например перенести на 201 км. то мы потеряем на нем два банана (5 — 3) т.к. ходок на последнем километре будет 5 а могло уже быть три.
andrey6498
А если взять эталонную дистанцию в районе 300-400кма затем каждую следующую часть переносить на несколько меньшую дистанцию.? Верблюд все равно будет есть в процессе а значит можно будет попутно добирать бананы с чекпоинтов.
sadPacman
В вашем варианте верблюд будет по дороге съедать свой груз. Полностью он загружен только в начале каждого этапа, а, например, в точке 100км на первом этапе он будет нести 900 бананов.
Rsa97
Всё просто. Первые 200 км верблюду нужно пройти пять раз, независимо от того, будет он делать ходки по 200 или по одному километру. Следующие 333? километра необходимо пройти три раза, и остаток пути — один раз. Таким образом, пройденное расстояние будет 200?5 + 333??3 + (1000 — 200 — 333?) = 2466? километра. Если за последние ? км верблюду банан не дать, то в конечный пункт прибудет 534 банана.
m03r
1. Берём 1000 бананов, каждый километр один банан съедаем, один кладём. На 500 км поворачиваем назад
2. Берём 1000 бананов, проходим 500 км (остаётся 500 бананов), раскладываем бананы ещё на 250 бананов ещё на 250 км.
3. Берём последнюю тысячу бананов, первые 750 км питаемся разложенными бананами, последние 250 съедаем, 750 доносим.
m03r
1. Идём 333 ? км, оставляем каждый километр по два банана (на отметке 333 ? оставляем две трети банана, треть съедаем), идём назад пустые
2. Проходим 333 ? на оставленных бананах (один остаётся лежать), далее раскладываем ещё на 500 км вперёд по одному банану на километр
3. Проходим 833 ? на оставленных бананах, съедаем 166 ? банана на оставшиеся километры, доносим 833 ?
GrigorGri
С таким предположением можно и больше: двигаемся по 1 км до 333км. Получаем 2001 банан. Выкидываем 1. Движемся на км 833 (сейчас км стоит 2 банана). Получаем 1000. Движемся оставшиеся 167км. Доставляем 834 банана (последний банан верблюду не даем т.к. мы уже у цели).
ikakus
А на возвращение верблюд не тратит бананы?
ITMatika
533/534 банана
Пока бананов больше 2000, расход идёт 5 бананов/км. Проходим 200 км.
Пока бананов больше 1000, расход идёт 3 банана/км. Проходим ещё 333 км.
Итого на точке 533 км остаётся 1001 банан и остаётся пройти 467 км.
Andy_U
Первая задача тоже была бы легкая, если бы было указано, что все даты (годы?) разные — тогда надо смешать годы рождения и смерти в общий список и отсортировать его по возрастанию года (не забывая, это год рождения или смерти) а потом пробежаться по списку, прибавляя или отнимая единицу от изначально нулевого счетчика в зависимости от того, что это за дата. Ответ ищется в том же проходе. Пока счетчик растет, запоминаем/передвигаем начало периода, как упадет, запоминаем период и число живых слонов. И так далее (может встретиться второй максимум)…
А вот если год смерти одного слона совпадает с годом рождения другого слона, тут непонятно, был ли момент времени, что оба слона были живы?
apapacy
Задача не до конца определена как мне кажется. Но есть пример который показывает как поступать с границами периодов. Поэтому я бы решал так. В сначала пришёлся бы по всем слонам и создал бы массив год -> число слонов. Потом нашёл бы в этом массиве максимум возможно не один и представил уже в виде интервалов. Если быть уже совсем строгим то год рождения и смерти нужно исключать т.к. мы показывает в интервале период о 0101 00:00:00 и рождениеслона в этот момент невероятно.
Andy_U
А что такого сложного в третьей задаче? Идем по массиву, как i-й элемент оказался меньше предыдущего, так и все. Если дошли до конца, ответ — 0
P.S. Ну, можно еще после нахождения k дойти до конца, для проверки валидности входных данных…
tr4rex
думаю, что важно упомянуть о том, что решений может быть бесконечно много с периодом, равным длине массива
kardan2
Думаю, что нет. В примерах к 3-й задачи есть ответы. И в этих ответах (то чего хотят поручить) есть всего 1 значение. Поэтому и мы должны давать 1 значение в качестве ответа.
reci Автор
Предположим, 2-й элемент оказался меньше предыдущего, тогда каков будет ответ?
kardan2
Ответ 1.
apapacy
Наверное предполагалось что будет небольшая оптимизация. Фактически нужно сравнивать границы последовав ателье ости если сортировка нарушена то делить пополам или другим способом и брать отрезок где сортировка опять же нарушена. Пока не останется отрезок длинной два.
kardan2
Вопрос 2. — Видел задачу в другом месте (хотя сам не решил)
Задача 3. — Поиск минимума? Или пары рядом стоящих чисел, когда первое больше второго.
Задача 2. За 1 проход заносим в Хэш значения квадратов элементов. А далее двойным циклом складываем квадраты элементов и проверяем наличие такого же значения в Хэше.
Задача 1. Необходимо определиться, как интерпретировать [2000,2010],[2010,2020], т.е. случай когда год смерти одного слона совпадает с годом рождения другого слона. Можно ли считать, что [2000,2020] жил ровно 1 слон, или же [2010,2010] жило 2 слона.
Предположим первое. Заводим Хэш, где год — ключ, а значение — +1 если это дата рождения, -1 если это дата смерти. Если в 1 год родилось 5 слонов, а умерло 2, тогда в хеше будет 5-2=3. Затем выгружаем все не нулевые значения Хэша в массив, сортируем его, и за 1 проход получаем решение. Сложность O(n*lon(n)) за счет сортировки.
Можно по иному пойти, выгрузить даты рождения в 1 массив, а смерти в другой массив. Отсортировать оба, и совместным прохождением по обоим массивам найти ответ. Сложность та же.
Про бананы и верблюда ещё думаю.
DaneSoul
Если работать с массивами дат, то наглядней перевести их в множества (set в Python) и найти результирующее множество сделав пересечение множеств. Потом берем минимум и максимум из этого результирующего множества.
dmrt
У меня получилось максимум всего лишь 416 бананов.
Сначала забрасываем бананы на 250-ый километр в три этапа, итого там будет 1500 бананов, половину мы потеряем, скормили прожорливому верблюду.
Затем закидываем на 416-ый километр остальные 1000 бананов, потеряв 500 бананов.
Основная цель — это найти максимальный километр, куда можно закинуть 1К бананов.
Дальше грузим всю тысячу и идем до конца, в итоге довозим всего лишь 416 бананов.
apapacy
Если забрасывать бананы сразу на 250км то теряется лишние 100=(250-200)*2 банана
dmrt
Хотя я чуть неправильно посчитал, на 250 у меня будет 1750.
Ну да, если на 200-ый, то мы там будем иметь там 2000 бананов.
Едем на 333 км еще, оставляем на 533-ем 333 банана, возвращаемся, берем 1К, в итоге привозим 533 банана.
По моей схеме имеем 1750 на 250-ом км.
Отвозим еще на 250 км, на 500-й 250 бананов, возвращаемся за 1К, едем в конечную точку, подбираем на 500-ом 250 бананов, в итоге получается привезем 500 бананов.
Да, получается, что на 200-ый лучше сначала.
apapacy
Важны только точки когда кончается очередная тысяча бананов. То есть можно везти до 200 через несколько перевалочных пунктов
dmrt
Anti-clockwise rotated array
По-моему у вас ошибка в примерах ответа: в первом случае ответ — 4, во втором — 1 и в третьем все правильно — 0
reci Автор
Вы правы, почему-то мысленно поворачивал по часовой, поэтому не заметил расхождения условий с примером. Исправлено.
Andy_U
Да, зря я поленился написать код с unit-тестами, в результате чего, чего, честно говоря, тоже «решил» задачу про поворот по часовой стрелке. Т.е. правильный ответ будет что-то типа n-i, где i — результат «моего» вчерашнего алгоритма.
P.S. Ваш код, наверное (я даже язык не могу угадать) правильный, но сильно неэффективный. Сначала сортировка массива, а потом в цикле еще и циклический сдвиг. Т.е. сложность типа O(N^2). А можно O(N).
dmrt
Язык Perl.
Сортировка — это O(log N) один раз.
А дальше стандартные функции для работы с массивами, со списками добавление элемета в начало массива и выталкивание последнего. Не могу точно сказать какая тут сложность, но если это динамический массив, то тоже O(N) получается.
Andy_U
Сортировка O(log N)? Скорее O(N*log N). а это уже больше O(N)…
Ну, стоимость прокрутки массива, если это не плоский массив, а список, действительно может стоить фиксированное время, но уж сравнение двух массивов длиной N на равенство (в прошлый раз не заметил), опять N/2 раз, это уж точно получится O(N^2).
dmrt
Хотя сортировка — это O(n log n)
А сравнение двух массивов — это O(2N), причем по сортированному не нужно было мне проходится в цикле каждый раз, можно было бы join его вычислить перед циклом, так что сложность сравнения тут O(N)
Итого O(n log n) + k * O(N)
Andy_U
Да, но в худшем случае k=N, в среднем k=N/2. А ответ ищется одним линейным проходом по массиву. Как нашли a[i-1] > a[i], так и ответ нашли (N-i, если индексация начинается с нуля). Если не нашли, ответ 0.
apapacy
В задаче кажется требовался только ответ с числом в условии. Но линейный проход не обязателен можно искать делением массива пополам.
Andy_U
А можно на код посмотреть?
apapacy
Буду рядом с компьютером напишу. А что есть подозрение что будут проблемы?
Andy_U
Были. Я по scientific computing специализируюсь, А тут, вроде и не поиск корня, или экстремума у выпуклой функции, поэтому и самому в голову не пришло, и в Вашем подходе, мягко говоря, засомневался.
Только после третьего вашего сообщения решил на всякий случай картинку на бумажке нарисовать и теперь на могу с Вами не согласиться. Действительно O(log N), причем независимо ни от чего. Снимаю шляпу.
P.S. А код напишите для фиксации рекорда.
apapacy
Код я имел в виду такой. Но теперь я понимаю что Ваш вариант был правильный а мой нет. Весь вопрос как трактовать тексо возрастающая последовательность. Я могу ошибаться но кажется возрастающая и неубывающая это разные вещи. То есть возрастающая не подразумевает повторения значений. Но не сказана что последовательность возрастающая а сказано отсортирована по возрастанию. То есть она неубывающая в строгом смысле. Если значения будут повторяться (неубывающая) то вот такой массив будет проанализировать проще протым перебором при этом от начала и до конца
[5,5,5,5,5,5,5,5,5]
[5,5,5,5,5,2,5,5,5].
Я так понимаю что давая такую задачу тестирующий хочет понять какие у тестируемого будут варианты проверки и будет ли он проходить массив от начала и до конца и остановится ли на первом равестве 5 = 5 значит ротация была 0.
Хотя может быть и другой вариант например что в условии сказано что «по возрастанию» значит это буквально равных быть не может.
apapacy
и кстати для массива [5,5,5,5,5,5,5,5] задача как бы вырождается и вариантов будет от 0 до длины массива минус один. А может быть это тест на адекватность? Если тестируемый начинает задавать тестирующему такие вопросы то он в каждой задаче будет видеть проблемы там где их нет?
Andy_U
Все нормально, в условии задачи сказано, что все числа разные.
apapacy
Да посмотрел — of distinct integers. Я читал только русский перевод. И немного затормозил на этом.
dmrt
Да, вы правы, вот так гораздо эффективнее:
ads83
По условию задачи, массив был отсортирован и потом «повернут» несколько раз. Т.к. он отсортирован, первый элемент — минимальный. Каждый поворот смещает первый элемент на 1 влево (первый раз — в конец массива). Таким образом, за один проход ищем минимальный элемент и запоминаем его позицию. Ответ n-k+1. Отдельно обрабатывается случай когда минимальный — первый элемент, значит поворотов не было (или было n).
Для поворота в другую сторону ответ k-1.
P.S. Возможно, я неправильно понял условие задачи, но мне непонятно зачем в решении поворачивать входной массив. Нам ведь не надо восстановить отсортированный? Также мое решение исходит из того, что на входе — корректные данные, т.е. это действительно отсортированный массив, который «повернули». Для восстановления исходного массива достаточно сделать еще один проход (в копию ставим элементы на нужный индекс), для проверки сортировки — тоже один с попарным сравнением с предыдущим элементом.
dmrt
Да, вы правы, переставлять элементы тут лишнее.
dmrt
У меня вопросы по шнурам:
1. То что одна половина горит 10 мин, а другая 50 мин — это конкретные условия задачи или просто как пример, на самом деле время может отличаться и оно не известно?
2 Если целиком шнур горит неравномерно, то половины горят равномерно?
3. Можно ли отличить концы шнуров, т.е. с какой стороны быстрее, а с какой медленнее сразу же, до зажигания?
Andy_U
1. Функция длины сгоревшей части шнура — монотонно возрастающая непрерывная функция, равная нулю при T=0 и равная длине шнура при T=1 час. Все.
2. Половины по длине? Нет. См. п.1
3. Нет. см. п.1
reci Автор
1. Точное время горения половин неизвестно. Может быть 15/45, например. А могут и равномерно, я думаю.
2. Нет.
3. Нет.
dmrt
И как же нам тогда решать такую задачу прикажите? Может быть вы что-то не договариваете?
Даже если ее и можно решить, то решение на порядок не очевидней, по сравнению с другими задачами, у них ответ лежит почти на поверхности.
Andy_U
Так она уже решена. См. первый комментарий.
vesper-bot
Задачу с массивом можно решить за O(log N) бинарным поиском. Сначала берем первый элемент и средний (в одну из сторон, тут неважно), если средний больше первого, минимум в верхней части массива, если меньше, то в нижней. Продолжаем, пока длина массива не станет 2, тогда тот элемент, что меньше из двух, и будет минимальным. Индексы считаем параллельно нахождению минимума, и выдаем индекс наружу, потом если он 0, то массив не сдвинут, если не ноль, то вычитаем его из длины (так как массив сдвигался влево), получаем ответ.
ads83
Возможно, я неправильно понял алгоритм, но мне кажется он сломается на примерах {2,3,4,5,1} и {5,1,2,3,4}.
Проблема с бинарным поиском в том, что числа расположены не монотонно. Например, для {3,4,5,1,2} ряд возрастает до третьего элемента, а потом убывает.
Поправьте меня, если я ошибся.
Andy_U
См. код выше:
apapacy
В данном случае бинарный поиск как раз ищет это расхождение но не прямым перебором а делением отрезка на два. Процесс заканчивается когда отрезок будет иметьровно два элемента. Из них правый элемент это и будет бывший первый эемент списка.
megamih
Задачу с верёвкой я бы решал «сложением» :)
Нужно сложить одну верёвку пополам, а вторую — вчетверо.
Когда первая верёвка полностью сгорит, пройдёт 30 минут. Когда вторая — ещё 15 минут.
vivlav
Про бананы мне кажется можно проще объяснить, чем через функции. Пока условно предположим, что перевозим максимум на 1 км. потом возвращаемся. На первые километры тратится по 5 бананов на километр (пока не останется 2000, или потратить 1000), затем по 3 (пока не останется 1000 или снова потратить 1000) и дальше по одному.
Итого первую тысячу (5 бананов на км) мы потратим за 200 км. вторую за 333 (1 банан теряем так как его перевозка дороже его самого) ну и последнюю 1000 везем оставшиеся 467км, значит с тысячи довезем 533.
apapacy
Расстояния не обязательно кратны километра и нет уверенности что такой ответ действительно максимум и не даёт ключа к решению в общем случае. Например сколько будет от 3007 бананов.
vesper-bot
На семь бананов при макс.загрузке 1000 проехать удастся только 1км., т.е. привезем на один банан больше (534).
Как раз дает, но если расстояния кратны километру. Если не кратны, то вопрос, как мы считаем нецелые бананы, а также как считается половина банана во рту у верблюда при расчете его грузоподъемности. По мне, такие вопросы позволяют "закопать" исходную задачу без какого-либо изменения понимания того, как думает собеседник, решивший задачу в целых числах.
Почему максимум — а потому, что каждый километр мы преодолеваем, используя наименьшую возможную стоимость километра в бананах, которая зависит от того, сколько неполных тысяч бананов у нас есть на текущий момент. При 3007 бананов их 4, и стоимость километра оказывается 7.
apapacy
Целый банан не означает целого километра в одну сторону. Это мтожет быть три ходуи по 1/3 километра. Я просто мог немного подготовить данные так чтобы эти части бананов накапливались и у вашего способа получилось расхождение. Но даже не это главное. Главное что в общем методе все решается проще и точнее.
vivlav
Согласен — такое объяснение сработает только в целых числах. В случае деления километров и бананов превратиться в:
Итого первую тысячу (5 бананов на км) мы потратим за 200 км. вторую за 333.(3), ну и последнюю 1000 везем оставшиеся 466.(6) км, значит с тысячи довезем 533,(3). При условии «непрерывного потребления» в конце.
Nick_mentat
Про бананы прочитал несколько неправильных решений. Почему-то многие забывают кормить верблюда на обратном пути в промежуточных ходках…
Suntechnic
В чем ошибка такого решения: habrahabr.ru/company/spice/blog/348122/#comment_10653124 (533.5 банана)?
apapacy
Все верблюды накормлены. Были правда попытки зажать полбанана после работы но это уже наш менталитет. Нести бананы на треть пути сразу невыгодно ту передаются лишние бананы. Первая остановка должна быть максимум на 200 км