Комментарии 249
Дана упорядоченная последовательность чисел от 1 до N. Из нее удалили одно число, а оставшиеся перемешали. Найти удаленное число.
В первой странная постановка задачи. Нигде не говорится, что оригинальная коллекция доступна.
Вначале думаешь что доступна только измененная коллекция. И ни про какие суммы и вычитания не думаешь.
Ещё не сказано, что в коллекции ровно N чисел и нет повторений ,) Ессно, на реальном собеседовании на уточнение достаточно 10 секунд
Первая коллекция недоступна — Вы имеете ввиду, что N неизвестно? Это почти никак не меняет решение.
Не соответствует условию. Если вы предполагали, что N равно трем, то "упорядоченная последовательность чисел от 1 до N" это: 1, 2, 3.
Если N=3, то чем упорядоченная последовательность чисел от 1 до N это например не 1,3, или 1,1,3?
1 1 1
1, корень из двух, 2
или просто 1 ( это тоже упорядоченная последовательность числе от 1 до 3 )
ну и удачи в поиске решений
Если N_{i+1} = N_{i}+1 — то да.
Но можно же и, например, N_{i+1} = N_{i} + 2*i :-)
Хотя, по умолчанию я бы считал первое — но это, ИМХО, вопрос заслуживающий уточнения.
Ну, "последовательность чисел от 1 до N", это, если не задано дополнительных условий, записанные последовательно числа от 1 до N. Да, разумеется, можно докапываться каждого слова в поисках скрытых смыслов, то можно напридумывать много чего. Но это всё из серии, — а если бы он вёз патроны… Зачем ввдумывать сущности без необходимости?
Зы. Ваш случай, кстати, вообще не подходит под формулировку. Значения чисел из набора довольно быстро превысят N.
Фраза "упорядоченная последовательность чисел от 1 до N" в тексте математических задач должна читаться как 1, 2, ..., N, а не как "упорядоченная последовательность чисел, принадлежащих отрезку [1, N]". Для этого есть два основания:
- При втором варианте прочтения не определяется тип чисел (целые, рациональные, действительные). В первом варианте прочтения считывается тип "целые положительные".
- При втором варианте прочтения не обозначается сколько этих чисел. В первом варианте прочтения считывается, что их ровно N.
Естественно, что при общении с заказчиком или на собеседовании, где Вы подозреваете подвох, надо уточнить. Естественно, для математической задачи лучше требовать формальную запись постановки, а не текстовую. Но столь же естественно, что при прочих равных существует определённая традиция прочтения текстовых формулировок.
В первой странная постановка задачи. Нигде не говорится, что оригинальная коллекция доступна.
Вначале думаешь что доступна только измененная коллекция. И ни про какие суммы и вычитания не думаешь.
Это проблема многих подобных задач:
Не оговариваются условия и допустимые операции.
Исходная коллекция доступна или же вначале она копируется, или из копии удаляется число?
А если не копируется, можно ли перед ее модифицикацией провести немодицицирующие вычисления (получить сумму?)
А числа у нас как в математике — без переполнения, или с переполнением (а при переполнении креш, или просто переполнение — которое может быть и вполне допустимо при решении задачи)?
Также сбивают с толку ненужные условия (в данном случае — "коллекция упорядочена"). Но эти условия могут быть важны, если задача будет решается при выборе других дефолтных значений условий, которые в задаче не проговорены явно.
Кстати, в задаче про взвешивание 8 монет тоже есть подвох — т.к. для 8-ми монет для минимального кол-ва взвешиваний, монеты нужно взвешивать по 3, то из 9 монет, монета с отличным весом будет найдена за то же число взвешиваний, что и 8.
И кстати, что есть взвешивание (число которых нужно подсчитать)? Если мы взвесили 3 + 3 монеты, и потом начинаем взвешивать монеты их тройки, где есть дефектная, то получается, часть монет взвешивается дважды.
Такая операция (повторное взвешивание) допустима в задаче? Если да — то, повторное взвешивание одной и той же монеты увеличивает счетчик взвешиваний или нет?
Пример непроговоренных допустимых операций — в задаче в 4-мя таблетками.
Чтобы ее решить, нужно ввести допустимую операцию, что таблетка может быть разделена пополам.
Если эти не заданные явно условия и не определенные явно допустимые операции задуманы ради проверки сообразительности и проверки хода мышления, то почему у отдельных интервьюеров уточняющие вопросы могут вызывать раздражение?
Есть ощущение, что в таких случаях человек мог заготовить такие задачи, прочитав их в интернете, и ожидать решения, исходя из предполагаемых умолчаний.
В итоге, из моей личной практики — такие задачи я решаю или вообще сходу (вообще сразу), правильно уловив все умолчания, правильно откинув лишние условия с подвохом, и правильно определив допустимые операции (а если их явно проговорить в условиях задачи, то и задача теряет смысл — ответ очевиден),
либо, если в звездах что-то не сошлось (жарко/холодно/душно/вечер/устал), то начинаю тупить, даже если незадолго до этого решил такую же задачу мигом и впервые ее увидев.
1. Наполнить пятилитровый кувшин водой
2. Из пятилитрового кувшина наполнить трёхлитровый кувшин (в пятилитровом останется 2 литра воды)
3. Вылить всю воду из трёхлитрового кувшина и перелить 2 литра воды из пятилитрового кувшина.
4. Наполнить пятилитровый кувшин водой
5. Наполнить заполненый на 2 литра трёхлитровый кувшин водой из полного пятилитрового кувшина (потребуется 1 литр воды)
В итоге, в пятилитровом кувшине останется 4 литра воды.
Нет условия "пользоваться только кувшинами". Потому:
- Наливаем 5 литровый кувшин
- Отливаем 3 литра во второй.
- Оставшиеся 2 литра сливаем в target.
- Повторяем :)
1. Наливаем 5-и литровый кувшин
2… (тут что угодно: запой, распилы, откаты, etc)
3. Берем кучу камней. Проводим экспертизу для определения их плотности.
4. Рассчитываем необходимую массу камней для заполнения объема в 1 кубический дециметр.
5. Берем весы, отмериваем необходимое кол-во камней.
6. Вываливаем камни в кувшин (как мы помним — наливали в 5-и литровый). По закону Архимеда камни вытесняют необходимое кол-во (1л) воды из кувшина.
7. profit! На вопрос — какого х*я в воде камни — делаем круглые глаза и говорим, что в условиях задачи ничего не сказано о том, что вода должна быть чистой. Просим еще денег на очистку воды от камней.
А если без шуток, перенося на програмерский быт: такие вещи встречаются сплошь и рядом, называются они красивым словом «костыль».
В итоге получаем в 3-литровом сосуде 1,5 литра, а в 5-литровом 2,5 литра.
Переливаем из трехлитрового в пятилитровый и у нас получилось 4 литра.
задачки очень простые и легко решаемы, особенно если прорешивали кучу подобных задач в школьные/университетские годы
Мне пока самое сложное, что попалось — это задачка посчитать количесво вагонов в составе
Условие: есть состав вагонов, закольцованный, можно переходить от вагона к вагону, в обоих направлениях. Скажем, что окна закрыты и видите только текущий вагон.
В каждом вагоне определено понятие света — горит или нет
У Вас, при заходе на очередной вагон, есть две возможности: посмотреть, горит ли в этом вагоне свет, и включить/выключить свет(без ограничений)
Вопрос: как посчитать точное количесто вагонов с наименьшим количеством их посещений?
Включаем свет в том вагоне, в который зашли. Идёми считаем, пока не дойдём до вагона с включенными светом. А как ещё?
А теперь представьте, что в вагонах состояние свет включен/выключен изначально случайное.
… Не, я знаю, что переменные положено инициализировать. Но все же..
Нормальная олимпиадная задача. Правда, не скажу за какой класс ,)
Изначално все вагоны случайном образом проинициализированы(включен свет или выключен)
понятия круг не существует
для Вас это как List<вагон>. Вы можете только next(), prev().
Чтобы "сделать круг", надо понять, что Вы дошли опять туда, где и были. Все вагоны — идентичны, не отличаются друг от друга, поэтому круг сделать не получится
Потому что говорю, что на первый взгляд, при неограниченном по условию количестве вагонов задача решения не имеет: при создании любой сигнатуры для определения начала состава (точки входа) у нас нет гарантии, что она банально не продублирована (конечно, совершенно случайно).
ближе к ответу)
решение есть, и да, количество вагонов в составе — конечное
Да даже если мы будем запоминать весь наш код и встретим его 50 раз думая что идем по кругу, не факт что дальше на 51 раз будет что то другое.
При бесконечном числе вагонов задача на их подсчёт как-то теряет смысл. :)
Если мы найдём ещё один вагон с выключенным светом — значит обнуляем счёт, включаем свет на предыдущем и начинает отсчитывать вагоны с новой точки(с выключенным светом)
В первом выключили свет и идём вправо до тех пор, пока не наткнёмся на вагон с выключенным светом. Включаем его и возвращаемся назад на пройденное ранее число вагонов, снова в первый. Если свет в нем горит, то мы сделали полный круг и задача решена. Если не горит, то круг ещё не завершён и мы снова идём вправо в поисках выключенного света. Задача решена, но в оптимальности решения я совсем не уверен.
ага, верное решение, за O(N^2) в худшем случае
За O(N log N) есть решение. Основная идея та же. Изначально k=1. Включаем свет в первом вагоне. Идем вправо k шагов, гася свет во всех вагонах. Возвращаемся назад, сколько прошли. Если свет погас в первом вагоне — Ясно что всего их не больше k, переходим ко второй фазе. Иначе, мы знаем, что вагонов больше k. Умножаем k на 2 и повторяем все сначала.
Вторая фаза — мы уже знаем, что вагонов больше k/2, но меньше k+1. Бинарным поиском в этом промежутке ищем минимальное i такое, что сделав i шагов вправо, гася везде свет, мы выключим свет и в первом вагоне тоже.
Каждая итерация пройти вправо выключая свет и вернуться назад не более 4N шагов (потому что мы не будем проверять k>2N иначе бы k/2 подошло уже). Всего итераций логарифм N найти минимальный k и еще один логарифм на бинарный поиск.
class Train:
set(on/off) # включить/выключить свет в текущем вагоне
test(on/off) # свет горит/не горит
left() # идем налево
right() # идем направо
function get_train_length:
k = 1
set(on)
while test(on):
k = k*2
for i in 0..k:
right()
set(off)
for i in 0..k:
left()
# теперь свет нигде не горит, и мы в вагоне, в котором начали
set(on)
right()
count = 1
while test(off):
count = count + 1
right()
return count
В моем решении в худшем случае придется сделать не более 9n переходов между вагонами (т.е. все равно О(n)), и кроме пары счетчиков дополнительной памяти не нужно, то есть O(1) дополнительной памяти. Возможно, можно оптимальней.
Если считать, что свет в вагонах инициализирован случайным образом, сходу подумалось о том, чтобы искать самую длинную повторяющуюся последовательность в свете вагонов, таким образом можно найти с некоторой долей вероятности повтор за 2*N вагонов, и увеличивать уверенность в результате за большее количество кругов. Но, с другой стороны, это не сработает, если у вагонов паттерн света повторяется. Мы можем менять один бит в паттерне, как только мы его обнаружили, и начинать отсчет от этого вагона, и идти вперед, пока мы не обнаружим паттерн с измененным битом. Но это не сработает, если поезд "умный" и знает о нашей стратегии, и неизведанные вагоны повторяют наш предыдущий паттерн, каким бы он ни был — поэтому вводить случайную компоненту бессмысленно. Плюс у такого решения очень неоптимальные затраты по памяти — нужно хранить весь трек, и еще и считать автокорреляцию для каждой из промежуточных позиций.
Значит, мы можем изменить трек таким образом, чтобы для его хранения требовался минимум памяти. Например, мы можем зажечь текущий вагон, и затем идти в любом направлении, пока текущий вагон не включен, и считать, сколько будет вагонов до первого горящего. Теперь у нас есть оценка длины цикла. Мы выключаем зажженный вагон, который мы встретили, и продолжаем идти вперед ранее подсчитанное количество шагов. Если встреченный вагон выключен, то с какой-то долей вероятности мы нашли цикл, и можно продолжать идти дальше.
Хотя можно сделать еще лучше. Как только мы нашли первый зажженный вагон, кроме того, с которого мы начали, мы его выключаем, и идем назад требуемое количество шагов. Если изначальный вагон, к которому мы вернулись, еще горит, значит мы погасили не тот вагон, и нам нужно начать заново.
У меня некоторые трудности с тем, чтобы определить временную сложность этого алгоритма, но время растет медленнее, чем O(N^2), но быстрее, чем O(N * log(N)). Сложность по памяти такого решения — O(1).
Если вагонов будет четное количество и последние 2 вагона будут иметь состояние 0 и 1, то мы посчитаем неправильно.
Например 10 вагонов: хх хх хх хх 01.
Пройдя 8 вагонов, получим такое состояние: 01 01 01 01 01.
Пройдя еще 8 вагонов, убедимся, что последовательность повторяется, и будем считать, что что вагонов всего 8.
Ошибемся с вероятностью 1/4.
Можно подсчитать сложность такого решения: логарифмическая сложность сортировки
Это как? Расскажите, мне интересно, как вы потеряли сравнение с каждым элементом (и, соответственно, N log N в результате).
A, B = B, A
А вот вопрос, сколько промежуточных переменных создается при выполнении этой операции. Мне кажеться, что их там чуть ли не 2 лишних будет. И присваиваний там 4, наверно, вместо 3-х для стандартного с одной переменной или с XOR.
Я тут посмотрел на «дизассемблер», получается, что я не прав: для функции
def foo(a, b):
a, b = b, a
from dis import disassemble as daдизассемблер (da(foo.__code__) для Python 3.4.5, da(foo.func_code) для 2.7.12) выдаёт
2 0 LOAD_FAST 1 (b)
3 LOAD_FAST 0 (a)
6 ROT_TWO
7 STORE_FAST 0 (a)
10 STORE_FAST 1 (b)
13 LOAD_CONST 0 (None)
16 RETURN_VALUEТ.е. кортеж оптимизатор убрал. Но если считать за «присваивания» те операции, которые вызывают инкремент/декремент счётчика ссылок, то их тут действительно четыре — LOAD_FAST вызывает инкремент загружаемого объекта, STORE_FAST вызывает декремент у объекта, который перезаписывается. Считать, сколько там внутренних временных переменных будет использовано, по‐моему, нет смысла, да и сложно: к примеру, я не удивлюсь, если окажется, что компилятор превращает код ROT_TWO (использующий две временные переменные) в три xor. А вот манипуляции со счётчиком ссылок вряд ли куда‐то денутся.
Ага. Только не забывайте, что в вашем примере участвуют две переменные, но три объекта (A, B и кортеж B, A).
В таком случае можно сумму заменить на XOR.
так как A XOR A == 0, и XOR ассоциативная операция, то можно посчитать XOR между элементами из массива и XORнуть её с 1..N
Влоб это будет конечно дольше чем если вычислить сумму по формуле.
Кстати, интересно бы попробовать вывести формулу для суммы по модулю 2, сдается мне она не будет шибко сложной…
А мне предложенный способ решить первую задачу решительно не нравится с технической точки зрения, сумма может выйти за пределы разрядности например.Может. Но получите ли вы в этом случае неверный ответ?
Кстати, интересно бы попробовать вывести формулу для суммы по модулю 2, сдается мне она не будет шибко сложной…Ээээ… Вы тут вообще о чём тут говорите?
2) XOR, он же сумма по модулю 2. Вопрос был в том что существует формула для быстрого вычисления суммы арифметической прогрессии, и я высказал идею что вполне себе просто должна выводиться аналогичная формула для побитового XOR арифметической прогрессии.
Собственно пятью минутами после того как я написал сообщение я её вывел, но написать уже не смог, ограничение read-only аккаунта :(
Собственно ответ тов. Nostr чуть ниже совпадает с тем что получил я
int xor(int n)
{
if (n % 4 == 0)
return n;
if (n % 4 == 1)
return 1;
if (n % 4 == 2)
return n + 1;
return 0;
}
Подробнее: stackoverflow
Или можно ещё проще:
1 ^ ... ^ n = (n >> 1) & 1 ^ (n&1 ? 1 : n)
int value = N
for(int i = 0; i<N-1; i++ ){
value = value + i - a[i]
}
int value = N
...
value = value xor a[i]
N = 4
V = 4
было 1, 2, 3, 4 стало 4, 1, 2 (после перемешивания)
V = v + 0 — 4 // 4+0-4=0
V = v + 1 — 1 // 0+1-1=0
V = v + 2 — 2 // 0+2-2=0
4й раз цикл не прогнать, т.к. a[i] не доступно!
Или я что-то напутал?
В этом решении есть большой минус: возможность переполнения. Поэтому лучше использовать поразрядную операцию XOR.
В первом и втором способах есть свои плюсы и минусы. Минус для первого указали, а для второго — нет. Например, второй способ не подойдет для float/double.
xor вполне себе подойдёт для float и double, только кода будет больше, чтобы убедить компилятор делать побитовый xor на double «как если бы это было просто N‐битовое беззнаковое целое». А вот арифметические операции для float и double не подойдут совсем. Подумайте, что будет, если в одном или другом числе окажутся такие интересные значения, как +∞, −∞, NaN (кстати, NaN может быть тоже два варианта). Или в одном числе будет 1 × 10100, а в другом — 1 × 10−100.
xor вполне себе подойдёт для float и double, только кода будет больше, чтобы убедить компилятор делать побитовый xor на double «как если бы это было просто N‐битовое беззнаковое целое».
Второй способ не подходит, если данные разной размерности (т.е. например, одна переменная float, вторая double), при этом можно их складывать с потерей точности. Что интересно, в случае целочисленных типов ксорить будет правильно, если более длинный тип привести к правильному размеру, правда, старшие биты придется занулить вручную.
Хотите мозговыносной вариант задачи? Дано две бочки по 20 литров. Обычные типичные дубовые бочки. Требуется: пользуясь только ими, отмерять 10 литров. Не "на глазок" естественно. Бонус поинтс тому, кто не прольёт ни капли.
Это не подстава, задача решаема.
Налить полностью одну, потом переливать из нее во вторую, пока уровни не сравняются.
Начать с одной полной и одной пустой, соединить шлангом, подсосать и сделать сообщающиеся сосуды, уровни воды выравняются и получим по десять литров
a = [b, b = a][0];
Правда, доп. переменная всё равно создаётся в памяти. Но не в языке.
Эм, а что, где-то еще предлагают такие задачи? Это же для джунов.
Я в своё время на Turbo Pascal мог сделать вообще всё. Вплоть до того, что знал что и где поправить чтобы стандартная библиотека и Turbo Vision с руссими буквами работали. Но если меня сейчас писать на нём программу писать… придётся не один месяц привыкать.
А если человек прекращает программировать совсем — то вернуться назад ещё сложнее. Но многие — этого не осознают, увы. Отсюда и берутся подобные задачки на собеседованиях. Как первичный фильтр, не более. Будет глупо решать — брать кого-то или нет только на основании таких задачек. Но «для разминки» они как раз подходят — а дальше можно плавно перейти на разные типы данных кеши, компиляторы и прочее, прочее, прочее.
Да в каждом есть свои уникальные трюки, технологии. В некоторых из них «элементарной» могут быть вполне себе сложные задачи(к примеру в Matlab многие весьма мудреные операции можно считать «элементарными», к примеру решение задачи линейного программирования). Разница между уровнями тех самых общепрограммистских навыков будет неплохо коррелировать со скоростью освоения подобных технологий.
В общем, такие вот задачки по мне — вполне себе позволительная вещь даже на собеседования синьоров, но конечно не все собеседование из них состоит. Для толкового человека это будет «разминочка», возможность почувствовать себя в своей тарелке. Хотя если человек приходящий на должность синьора такую задачу не щелкнет или того хуже будет в качестве решения первой задачи предлагать O(N^2)… Я бы все таки задумался, это ведь должен быть человек самостоятельно принимающий технические решения, не бегающий проконсультироваться с начальником на каждый чих. Понастроит ведь потом велотренажеров
Безусловно хорошо если человек может решить задачу тремя разными способами 2 из которых никто кроме него не придумал, но если бы у меня был выбор: работать с командой из очень талантливых и творческих оболтусов или же с командой которая пишет нормальный код (нормальный это понятный блин, а не короче на 3 строчки чем у соседа) и делает это в срок — я бы даже думать не стал.
Поэтому, с моей точки зрения, если кто то решит ее не, уточнив у рекрутера доступна ли она но при этом использовав ее, то это «звоночек» что человек не умеет делать поправки на то что вокруг него существуют не только программисты.
И следовательно, возможно, он будет сношать мозг окружающим своей «точностью формулировок» вместо того чтобы засовывать свое чувство превосходства куда нибудь подальше и сосредоточиваться на том чтобы сделать дело.
А что за переполнение такое? У нас же в условиях нет ограничений на память/разрядность/и т.д.
Поясню мысль.
Первая задачка (с последовательностью без числа) в реальности может встретиться, например, при работе с БД. Есть список каких-то записей (юзеры, товары, транзакции — не важно), у них есть ID от 1 до N (autoincrement), есть некая функция, которая их удаляет, нам нужно узнать, что было удалено.
Тут стоит заметить, что во-первых, обычно используется не удаление, а установка какого-нибудь status: disabled (или установка null в поле, если прямо так необходимо избавится от информации). Удаление может вызвать кучу проблем и головной боли в последствии, не надо так.
Во-вторых, обычно всё-таки не должно возникать ситуации «у нас в БД что-то пропало, неизвестно что». ID удалённого объекта должен записываться в момент удаления и обрабатываться сразу же.
Но ок, допустим, какое-то вероисповедание нам не позволяет исключить возникновение такой ситуации. Тогда в-третьих: даже если мы делаем проверку суммы сразу после удаления чего-то, никогда нет гарантии, что в самом деле что-то было удалено, или что была удалена только одна запись. Даже если сегодня это так, завтра функцию могут переписать.
В итоге, человек, который считает, что ответ с суммой — окончательный и достаточный для продакшена будет просто не прав. Тут либо переделка структуры, либо полный перебор ID'ов.
Вторая задачка (кувшины) — ну ок, лёгкая, математическая, чтобы решающий почувствовал себя увереннее. К IT отношения не имеет от слова «совсем».
Но вообще в реальных задачах такого типа (когда есть возможность что-то решить, нестандартно используя существующие объекты), нужно в первую очередь начать задавать вопросы.
Почему такая задача вообще возникла и к ней не готовы? Может, в ТЗ опечатка и нужно всё-таки 3 литра?
Почему у нас нет кувшина на 4 литра? Может, он всё-таки есть и стоит его поискать? Чтобы не занимать те два кувшина, которые явно уже предназначены для других целей и могут понадобиться остальным.
А если скоро опять возникнет такая задача? А если в следующий раз — 1/4 литра? Может, стоит озаботиться покупкой кувшина с литровыми отметками, а не тратить своё время на «костыльные» переливания?
Третья задачка (поменять переменные местами) — да, задачка интересная. В реальности встречается, но крайне редко. Тут только нужно пояснить, в этой самой реальности для решения используют встроенную функцию (обычно называется Swap), либо (на худой конец) третью переменную. А за неожиданный уход в побитовые операции пускают лучи неневисти (те, кому потом придётся поддерживать такой код).
Получается, что они не просто оторваны от реальности, они заставляют искать костыльное ad hoc решение, которое годится только для данного конкретного случая. Мне кажется, опытный программист уже на подкорке отсекает такие решения (и на работу его не берут...)
Вторая задачка к IT и правда мало отношения имеет, кроме разве того, что в голове приходится проигрывать алгоритм.
Третья задача проверяет
Задача про вагоны из комментов вполне похожа на некоторые задачи биоинформатики с их кольцевыми ДНК.
Это далеко не самые оторванные от жизни в IT задачи, я вам скажу. Другое дело, что они банальные и задаются повсюду, отчего их ценность как каких-то индикаторов сходит на нет.
Другое дело, что они банальные и задаются повсюду, отчего их ценность как каких-то индикаторов сходит на нет.Вы не поверите, но несмотря на то, что «они банальные и задаются повсюду» — соискатели про них, в подавляющем большинстве, не знают. А если человек, в ответ на одну из них тут же говорит «да-да, знаю, можно и два „потерянных“ числа найти и общий алгоритм для работы с этими кувшинами есть» — то это, в общем-то, хороший признак…
Из первого списка первая задача — zip+flatten, называть её merge не очень, если не предполагать имплицитно специальный компаратор, базирующийся на индексах в коллекциях.
Во втором SAX/StAX вполне должен укладываться в нужные характеристики. DOM и использование XSLT с большой вероятностью не взлетит.
3.1 — внешняя сортировка по вкусу. В 3.2 явная хрень в условии, тут либо использовать общепринятые термины (архивация/компрессия, ибо тот же tar — архиватор, но не компрессор), либо явно указывать что понимается под каждым термином…
4 — опять внешняя сортировка с парсингом, вполне нормальный вариант на поговорить. Хотя 4 часа выглядят сильно избыточно, если не нужно писать в блокноте.
задача для собеседования
Стоит четырехэтажный дом, в каждом этаже по восьми окон, на крыше — два слуховых окна и две трубы, в каждом этаже по два квартиранта. А теперь скажите, господа, в каком году умерла у швейцара бабушка? (Из Гашека)
А он выводится из исходных данных хоть как-то?
Швейк рассказал свою задачу в 1914 году. Год кончины бабушки равен произведению общего числа окон этого дома на число труб и на возраст (в 1914 году) одного из квартирантов, лично присутствовавшего на похоронах. Итак, в каком же году умерла у швейцара бабушка?
На самом деле, это такой своеобразный фольклор про странные задачи.
Про "на самом деле" — это было ещё прямо в книге. А вот приведенное вами решение требует дополнительных данных, которых в исходной постановке нет (про квартиранта — про него Швейк в книге не сказал ЕМНИП ничего). Значит, задача не является математической. (А вот примером странной задачи — является, ещё как.)
Спасибо, кстати, за решение, мне ещё не попадалось.
В остальном же прав Arastas: это классика идиотских задач и тут решения из исходных заведомо нет. Хотя можно собрать материальчик на историческое расследования, чтобы вычислить наиболее вероятный диапазон: как уже сказано, задача рассказана в 1914 году, вероятно несколькими днями позже 28-го июня, действие происходит в Праге и исходя из характера Швейка можно с большой долей вероятности утверждать, что дом этот — именно в Праге, а время — немногим ранее… и т.д… но зачем? если правильный ответ: 1894, и тут уж ничего не поделаешь!
А где в первой задаче сказано что доступны обе коллекции — исходная и перемешанная?
Про задачу с обменом чисел:
опять же, много допущений: в варианте со сложением вычитанием нужно исходить из того, что отключен креш при переполнении;
в варианте с XOR — исходим из того, что вычисление производятся на компьютере с бинарной логикой (а где вообще в задаче сказано, что вычисления будут производиться на компьютере, а не на листе бумаги или компьютере с троичной логикой?).
И самое главное — сбивает с толку то, что кажется, что задача поставлена из соображений оптимизации (скорость, экономия памяти), и начинаешь искать это "оптимальное" решение.
Получаем то, что называется "преждевременной оптимизацией":
При введении переменной-буфера мы всего лишь вводим одну переменную, и операция копирования значения — из одной ячейки памяти в другую — весьма быстрая (если речь о переменной 32/64 бита, а не BigInteger — а где это оговорено в условии?).
Давайте не забывать, что операции сложения/вычитания, битового маскирования явно помедленнее — нужно поместить значения из памяти в регистры процессора, выполнить собственно операции, считать это обратно в память.
И еще надо разобраться, не введет ли при этом компилятор промежуточные переменные на стеке (а тогда за что боролись)?
И что значит два числа? Где оговорено, что это int, не float? Для float результат сложения/вычитания будет вообще долгим и неточным, а XOR для float вообще будет неприменим (хотя, конечно, можно интерпретировать float как бинарные данные и привести с int, а потом обратно к float — это тоже куча лишний операций, в результате которых теряется смысл задачи).
Эти неверные постановки задачи. Первая задача — найдите число. Но не уточнили — нам нужна ссылка на удаленное число в первом списке\массиве или просто значение этого числа. Во втором случае конечно достаточно разницы сумм, но вот я к примеру подумал, что прежде всего по смыслу задачи нужно найти позицию индекс удаленного числа в первом списке, и в этом случае сортировка и линейная сверка один из оптимальных и быстрейших решений.
Скажем так, если бы формулировка была — вычислить, тогда вопросов бы вообще не возникло. Там написано — найти удаленное число. Для меня это двояко.
Программист, который не пытается понять бизнес-задачу клиента, будет решать свои программистские проблемы, а не проблему клиента.
В результате это ведет к множественным недопониманием друг друга, заваливание сроков и реализации некорректной логики.
Логические задачки для того и нужны, чтобы их решать логически.
найдите удаленное число
Вот читаю и вижу одно и то же.
То что по разному выглядит для вас, одинакого может выглядеть для других, и наоборот. Люди разные, ничего страшного.
Больше того, в таких задачах просят подчеркнуть слово, а не просто написать его, т. е. все таки найти позицию.
Заметьте, я не утверждал что условие именно найти позицию, я указал что есть такой вариант, и в этом варианте решение будет более общим, хоть и алгоритмически более медленным.
Привычка уточнять дух задачи, а не формулировку, обдумывание наперед того, какие задачи возникнут в будущем — хорошая привычка.
— Надо слово или позицию? Какие еще метаданные к этому слову нужны?
— Только слово
— Ок, но если понадобится что-то еще, придется полностью переписать алгоритм с нуля.
И тут вдруг менеджер начинает действительно думать, а не понадобится ли что-то еще.
Если не понадобится, то
— Нет, только слово
— Ок.
А что касается задумываний менеджера и системы которую надо переписывать с нуля, это как раз относилось к задаче.
Если мы будем решать задачу через суммы, а в будущем окажется, что нам все таки где-то нужна не только сумма, но и сам объект, который ее содержал до этого, возникнет новая задача, в которой таки придется сортировкой и перебором искать искомый объект (с вашей точки зрения новая задача). Но это вполне очевидный и обыденный кейс для меня — сразу узнать будущие кейсы и уточнить с менеджером более удачную реализацию, подходящую для дальнейших хотелок. Такие ситуации у меня на работе штатные, и не поверите — бывают и такие формулировки как в этой задаче, и именно со смыслом находить объект, чтобы потом как-то работать с статистикой по нему.
Действия согласно семантике программы совершаются над значениями, согласно семантике языка — над объектами, а реально оптимизатор может много чего повыкидывать и совершать действия над регистрами и памятью вплоть до того, что новый объект числа создастся только на строчке return missing_number. «Найти число» в смысле «найти [ссылку на] число» — вполне допустимая интерпретация, «ссылку на» при разговоре часто опускают, хотя обычно это делают только когда идёт речь о более «сложных» объектах, что почти всегда передаются по ссылке.
Интерпретировать вполне можно и так, как Shifty_Fox. Другое дело, что большинству программистов (включая меня) это действительно не придёт в голову: почти во всех языках программирования, даже если число является объектом, всё определено так, что разница между числом x в объекте по адресу A и разница между тем же числом x в объекте по адресу B настолько мала, что нормальный программист о ней вспомнит разве что после того, как у него начнутся проблемы с производительностью на большом количестве чисел.
Но именно такая интерпретация мне пришла бы в голову, если бы «число», к примеру, было «клиентом».
Я бы решил первую задачу вычитанием двух множеств: вычтем из первого множества со всеми числами 1..N второе множество без одного числа, получим это недостающее во втором множестве число.
* 4 человека, с разной скоростью передвижения (1, 2, 5, 10 мин)
* нужно перебраться всем по мосту
* по мосту могут идти только 2 одновременно
* по мосту можно идти только с фонариком, фонарик один
За какое минимальное время можно перебраться всем на другую сторону?
А доказательство, что данное время минимально, без полного перебора вариантов существует?
Очевидно, вперед всегда идут двое, потом кто-то один возвращается с фонариком. Минимальное количество ходок — 5 (3 туда, 2 обратно). Покажем, что нет решения за 16 и меньше. Из трех ходок туда, хотя бы одна будет с 10, оставшиеся стоят не меньше 2 (ибо там 2 человека идут). Еще 2 ходки назад стоят не меньше 1 каждая. Т.е. теоретически минимальное время 16. Это только если оба раза назад идет 1. Но в этом случае туда всегда идет 1 с кем-то (и они все разные) и 3 ходки вперед стоят не 10+2+2, а 10+5+2 — уже больше 16.
10> +1< +5> +1< +2> = 19
5 действительно может быть спрятанно за 10. Но в этом случае, как уже сказано, нельзя оба раза вернуть назад 1. При этом не обязательно, что назад идет кто-то из пары, только что пришедших. В этом случае 5 не обязано идти назад. Выше я показал, что 16 вообще оценка снизу, к тому же не достижимая. Доказать, что ответ 17 можно только приведя и сам ответ:
> 1 2
< 1
> 10 5
< 2
> 1 2
У меня меньше 19 не получается.
В вашем решении учтено, что по крайней мере два раза кто-то с фонариком должен будет ещё и возвращаться к началу?
Хитрость в том, чтобы с 10-кой, которая обязательно посчитается, пустить максимальный из оставшихся — 5. Таким образом, мы исключаем 5 вообще из суммы. Чтоб ему назад не идти потом, 10 и 5 идут вперед не первыми. Тогда кто-то другой уже будет на другой стороне, чтоб вернуться назад.
< 1
> 5 + 10
< 2
> 1 + 2
Знал о нем давно, но нагуглить без названия не получилось. Основан на равенстве суммы высот для всех точек равностороннего треугольника
Но я не так ее решал
1. Наполняем 3х литровую и переливаем в 5ти
2. Повторяем 1й шаг, в результате после 2й итерации у нас в 3х литровой останется 1 литр
3. Опустошаем 5ти литровую и переливаем туда 1литр с 3х литровой
4. Наполняем 3х литровую и переливаем в 5ти. Получаем 4 литра
Встречаются два приятеля — математика:
— Ну как дела, как живешь?
— Все хорошо, растут два сына дошкольника.
— Сколько им лет?
— Произведение их возрастов равно количеству голубей возле этой скамейки.
— Этой информации мне недостаточно.
— Старший похож на мать.
— Теперь я знаю ответ на твой вопрос.
Сколько лет сыновьям? (Ответ логичный и однозначный)
Почему не 1 и 9 или 2 и 8? Или автор лукавит про однозначность.
1) Дошкольники. Значит им от 1 до 7 лет.
2) Их произведение равно известному только математикам X
3) Старший похож на мать. Именно этот факт дал второму математику ответ, из чего мы знаем что, до вопроса — число голубей раскладывалось как на два одинаковых числа, так и на два разных, и тот факт то возрасты не равны — отсек вариант с одинаковыми числами, оставив два разных — 1 и 4
Задача решается перебором и проверкой каждого варианта на все эти условия.
Согласен, я упустил, что дошкольники.
(Ответ логичный и однозначный)
Это часть условия
«Этой информации мне недостаточно.»
1 х 3 = 3
2 х 5 = 10
Это единственные разложения при числах меньше 7, а нужно, чтобы было ровно два варианта, один из которых — одинаковые множители.
Здесь по сути вообще работают только квадраты, которые раскладываются как-то еще
2х2 = 4, 3х3 = 9, 4х4 = 16, 5х5=25, 6х6=36, 7х7=49
только в случае 2х2 подходит вариант 1 и 4, а вот все что дальше — получается 1 и 9, 1 и 16 и т. д., уже не дошкольники.
Хотя не сказано, что им целое число лет. Например 6 лет и полтора года дадут те же 9 голубей, что и два по три года. Да и то, вдруг они возраст в днях считают.
1) В фразе «мне не хватает информации» означало, что произведение X можно было получить несколькими способами.
Оставляем только варианты, где произведение можно получить хотя бы двумя способами,
остается
1x4=4, 2x2=4
1x6=6, 2x3=6
2x6=12, 3x4=12
2) В фразе «Старший похож на мать», ключевое слово «старший», по поводу количества голубей эта фраза ничего не уточняла, но мы теперь знаем, что дети разного возраста.
Убираем варианты с перемножением одинаковых чисел, остается:
1x4=4
1x6=6, 2x3=6
2x6=12, 3x4=12
Поскольку решение задачи должно быть логичным и однозначным, логично, что единственная пара из этих вариантов, у котороых было отобран вариант с одинаковым возрастом, осталась 1 и 4
И в чём будет отличие от использования переменной?
по факту, можно считать, что они уже там лежат
Насчет ответа — такой ответ означает, что у вас на интервью не системный программист, а математик. Математики тоже нужны, но в других местах обычно. А ещё он прав изначально — очень много допущений возможно в задаче. Их надо разбирать прямо на интервью, причем интервьюер должен это уметь, иначе даже хороший программист не пройдет такое интервью.
Насчет ответа — такой ответ означает, что у вас на интервью не системный программист, а математик.Такой ответ обозначает, что этого человека брать не следует. Потому что он, в общем, кое-что знает о системном программирования — но неправильно, а главное он использует свои знания не для того, чтобы решить задачу, а для того, чтобы «отбиться» и обьяснить вам почему он ничего не хочет делать.
в варианте со сложением вычитанием нужно исходить из того, что отключен креш при переполнении;… что, впрочем, является стандартым поведением, описанным в стардатах C/C++ для чисел без знака и, соответственно, поддерживается всеми современными процессорами.
в варианте с XOR — исходим из того, что вычисление производятся на компьютере с бинарной логикойКто-нибудь видел в XXI веке компьютеры с другой логикой?
И самое главное — сбивает с толку то, что кажется, что задача поставлена из соображений оптимизации (скорость, экономия памяти), и начинаешь искать это «оптимальное» решение.Ну да — это такой способ экономии регистра при кодогенерации. Но так ли это важно? Того, что написано в условии — достаточно.
При введении переменной-буфера мы всего лишь вводим одну переменную, и операция копирования значения — из одной ячейки памяти в другую — весьма быстраяОбращение в память в современной архитектуре — выполняются медленнее, чем вычисления. Задержка даже пре обращении в L1 кеш — 4-5 циклов, вычисления же делаются за 0.25-0.5 цикла. И то и другое, конечно, накладывается на разные другие эффекты, так что всё не так однозначно — но сходу заявлять что эти алгоритмы «никуда не годятся» нельзя, они реально используются на практике даже сейчас.
если речь о переменной 32/64 бита, а не BigInteger — а где это оговорено в условии?Вот как раз для BigInteger этого делать не нужно, так как «удава можно перемещать по частям»
хотя, конечно, можно интерпретировать float как бинарные данные и привести с int, а потом обратно к float — это тоже куча лишний операций, в результате которых теряется смысл задачиВот это — просто шик-блеск. Да, это аргумент. Для компьютеров 70х-80х годов. Современные же архитектуры (SSE, NEON) позволяют смотреть на одни и те же регистры либо как на состоящие из целых чисел (сторого говоря PXOR/VEOR рассматривают регистры просто как последовательность битов, не вдаваясь в детали о том, что там такое внутри).
А ещё он прав изначально — очень много допущений возможно в задаче.А вы что — думаете что в реальной работе вам будут все задичи «разжёванными на блюдечке» поступать? Да, конечно, недоговорки будут и прямые ошибки. Ваша задача — попытаться понять-таки и решить задачу несмотря на всё это. В совсем сложных случаях — не зазорно спросить. Но в любом случае нужно помнить — вас берут на работу, чтобы вы решали задачи, которые работающие там люди, в общем-то, и так могут решить — но у них на это нет времени. Чем меньше они потратять на вас времени обьясняя что вам нужно сделать — тем лучше. При условии, что им потом то, что вы сотворили не придётся переделывать.
Никому не интересно взять на работу сотрудника, который великолепно, блестяще, будет решать задачи — но на обьясниение условий у вас уйдёт больше времени, чем на решение задачи самостоятельно.
Их надо разбирать прямо на интервью, причем интервьюер должен это уметь, иначе даже хороший программист не пройдет такое интервью.Хороший программист не будет привлекать вещи, в которых он не до конца разбирается для того, чтобы потешить своё ЧСВ. Наоборот — он постарается придумать-таки разумную интерпретацию задачи, а уже после этого — начнёт задавать уточняющие вопросы.
function (a,b) {
return b,a;
}
у меня вот недавно на собеседовании спросили задачку отсортировать inplace последовательность целых чисел(числа могут повторяться) быстрее чем nlogn.
короче за 1.5 часа я изобрел сортировку подсчетом, при том что принцип я не помнил практически. и мне абсолютно не помогали.
несмотря на правильное решение меня не взяли, но это уже другая история…
Сортировка подсчетом inplace? Это как?
Дак как оно inplace когда целый массив counters создается? В таком виде вторую часть можно упростить — не надо никаких элементов менять местами — просто можно перезаписать массив нужными числами. Число i записывается на позиции counters[i-1]+1..counters[i],
по поводу перезаписывания — не пойдет. ибо там массив не просто чисел а структура, по полю которого нужно сортировать
counters := []int{}
for i := range unsorted_array {
look_from_pos := i
for {
final_pos := counters[look_from_pos]
if final_pos != look_from_pos {
tmp := unsorted_array[final_pos]
unsorted_pos[final_pos] = unsorted_pos[i]
unsorted_pos[i] = tmp
tmp := counters[i]
counters[i] = counters[final_pos]
counters[final_pos] = tmp
look_from_pos = final_pos
} else {
break
}
}
}
"Сложная" задача про кувшин в чуть другой формулировке (ведро и банка там кажется были) была в советском учебнике по математике, кажется, за 5-й класс. Причём просто задача, не "со звёздочкой".
Мне очень понравилась задача (не из этих 2-х компаний), которая, на мой взгляд, тоже простая математически, но очень хорошо проверяет тип мышления. Если он «программистский» — человек решит задачу быстро. Вот задача: в ящик положили бактерию, через минуту их стало 2, через минуту 4 и так далее. Один раз в минуту каждая бактерия делится на 2. Чтобы заполнить ящик им нужен час. За сколько они заполнят ящик, если положить в него изначально 2, а не 1 бактерию?
59 минут? В чём тут суть "программисткого" мышления?
N_1(t) = 2^{t_1-1}
N_2(t) = 2^t_2
N_1(60) = N_2(t) -> t = log_2(N_1(60)) = log_2(2^{59}) = 59
Но это такое себе, да :-)
В условиях второй задачи нет ограничений на силу тяжести. Предположим, что мы находимся в невесомости ))
Аккуратно выливаем содержимое 5-литрового кувшина в пространство. Зачерпываем из этой капли 3 литра, получам в остатке 2. Повторяем операцию. Объединяем остатки. Готово.
2-я на состав числа — для начальной школы. Сыну давал в 6 лет. Справился.
3-я для тех, кто изучает арифметические операции и не раз мне попадалась в различных учебниках. За красивый вариант с XOR спасибо.
5*2 — 3*2 = 4
Задачи с собеседований. Три адекватные задачки на «подумать»