И снова про собеседования. Некоторые простые задачи порой вызывают затруднение. В этом посте я хочу рассмотреть три задачки с собеседований, которые мне понравились, потому что к их решению можно прийти самим, но чуток подумать все равно придется.
С толку сбивает только одна фраза «упорядоченная последовательность», она-то и может натолкнуть на использование сортировки для решения данной задачи. Программисты довольно часто пользуются готовыми библиотеками и фреймворками, поэтому при решении задач автоматом обдумываешь, что будешь использовать из библиотеки. Для многих программистов единственным очевидным решением является сортировка полученной последовательности и далее поэлементное сравнение исходной и отсортированной последовательностей до первого несовпадения. Можно подсчитать сложность такого решения: сложность сортировки плюс линейная сложность поиска. Хм, может подойти к решению как-то иначе?
Это моя любимая задачка из разряда «головоломок». С одной стороны нужно немного подумать, а с другой – она действительно проста и адекватна.
Как потом оказалось, это довольно популярная задачка. Но я решила со значительным недочетом.
Решить задачу можно, используя арифметические или побитовые операции. Поскольку арифметические показались проще, то я решила использовать их.
Осталось только пожелать всем успешных собеседований!
А в комментариях можете написать, какие задачи встречались вам.
Задача 1. Проверьте, насколько вы избалованный программист
Дана упорядоченная последовательность чисел от 1 до N. Из нее удалили одно число, а оставшиеся перемешали. Найти удаленное число.
С толку сбивает только одна фраза «упорядоченная последовательность», она-то и может натолкнуть на использование сортировки для решения данной задачи. Программисты довольно часто пользуются готовыми библиотеками и фреймворками, поэтому при решении задач автоматом обдумываешь, что будешь использовать из библиотеки. Для многих программистов единственным очевидным решением является сортировка полученной последовательности и далее поэлементное сравнение исходной и отсортированной последовательностей до первого несовпадения. Можно подсчитать сложность такого решения: сложность сортировки плюс линейная сложность поиска. Хм, может подойти к решению как-то иначе?
Есть более простое решение
Давайте забудем о том, что последовательность упорядочена. Обе последовательности различаются всего одним числом, а значит, чтобы его найти нужно из суммы элементов исходной последовательности вычесть сумму полученной. И кстати, если все элементы уникальны, то в исходном массиве у нас арифметическая прогрессия и первую сумму можно вычислить как .
Задача 2. Жонглирование числами
У вас есть пятилитровый и трехлитровый кувшины и неограниченное количество воды. Как отмерить ровно 4 литра воды? Кувшины имеют неправильную форму, поэтому точно отмерить половину кувшина не получится.
Это моя любимая задачка из разряда «головоломок». С одной стороны нужно немного подумать, а с другой – она действительно проста и адекватна.
Решение
Здесь придется немного пожонглировать с простыми числами 5 и 3.
1. Заполняем трехлитровый кувшин. Переливаем эти 3 литра в пятилитровый кувшин.
2. Снова заполняем трехлитровый кувшин и переливаем из него в пятилитровый. Помним, что в пятилитровом кувшине сейчас 3 литра, до полного его заполнения из другого кувшина выливается 2 литра. В трехлитровом кувшине остался один литр.
3. Опустошаем пятилитровый кувшин. Переливаем в него отмеренный один литр. Снова заполняем трехлитровый кувшин и переливаем из него в пятилитровый. Теперь в большом кувшине у нас 4 литра воды.
1. Заполняем трехлитровый кувшин. Переливаем эти 3 литра в пятилитровый кувшин.
2. Снова заполняем трехлитровый кувшин и переливаем из него в пятилитровый. Помним, что в пятилитровом кувшине сейчас 3 литра, до полного его заполнения из другого кувшина выливается 2 литра. В трехлитровом кувшине остался один литр.
3. Опустошаем пятилитровый кувшин. Переливаем в него отмеренный один литр. Снова заполняем трехлитровый кувшин и переливаем из него в пятилитровый. Теперь в большом кувшине у нас 4 литра воды.
Задача 3. Без посредников
Имеется два числа. Можно ли поменять их местами без использования дополнительной переменной?
Как потом оказалось, это довольно популярная задачка. Но я решила со значительным недочетом.
Решить задачу можно, используя арифметические или побитовые операции. Поскольку арифметические показались проще, то я решила использовать их.
Решение
Пусть у нас есть A и B.
A = A + B
B = A – B // После этого B становится A, т.к. в действительности получаем (A + B) – B = A
A = A – B
В этом решении есть большой минус: возможность переполнения. Поэтому лучше использовать поразрядную операцию XOR.
A = A ^ B
B = A ^ B
A = A ^ B
Как это работает: в первой строке мы получаем маску на различающиеся биты, в этих разрядах будут стоять единички. Далее производится сброс и выставление нужных бит для обмена значений.
На примере будет наглядней. Рассмотрим обмен чисел 5 и 9.
A = 0101 ^ 1001 = 1100
B = 1100 ^ 1001 = 0101
A = 1100 ^ 0101 = 1001
A = A + B
B = A – B // После этого B становится A, т.к. в действительности получаем (A + B) – B = A
A = A – B
В этом решении есть большой минус: возможность переполнения. Поэтому лучше использовать поразрядную операцию XOR.
A = A ^ B
B = A ^ B
A = A ^ B
Как это работает: в первой строке мы получаем маску на различающиеся биты, в этих разрядах будут стоять единички. Далее производится сброс и выставление нужных бит для обмена значений.
На примере будет наглядней. Рассмотрим обмен чисел 5 и 9.
A = 0101 ^ 1001 = 1100
B = 1100 ^ 1001 = 0101
A = 1100 ^ 0101 = 1001
Осталось только пожелать всем успешных собеседований!
А в комментариях можете написать, какие задачи встречались вам.
Поделиться с друзьями
NYMEZIDE
В первой странная постановка задачи. Нигде не говорится, что оригинальная коллекция доступна.
Вначале думаешь что доступна только измененная коллекция. И ни про какие суммы и вычитания не думаешь.
MonkAlex
Кому как, я сразу про сумму подумал. Формулировка похожа на школьные задачки, там такого было полно.
Spiritschaser
Ок, так и запишем, задача на тренированность читать условия школьных задач.
alesto
Согласен с Вами.
grossws
Ещё не сказано, что в коллекции ровно N чисел и нет повторений ,) Ессно, на реальном собеседовании на уточнение достаточно 10 секунд
tgz
Еще не сказано что это целые числа.
Arastas
Первая коллекция недоступна — Вы имеете ввиду, что N неизвестно? Это почти никак не меняет решение.
sotnikdv
Вот вам последовательность, в соответствии с условиями задачи. 1 500 99999999
Какое число изьяли?
avost
Не соответствует условию. Если вы предполагали, что N равно трем, то "упорядоченная последовательность чисел от 1 до N" это: 1, 2, 3.
saboteur_kiev
Почему не соовтетствует?
Если N=3, то чем упорядоченная последовательность чисел от 1 до N это например не 1,3, или 1,1,3?
bogolt
упорядоченная последовательность чисел от 1 до 3 может быть такой
1 1 1
1, корень из двух, 2
или просто 1 ( это тоже упорядоченная последовательность числе от 1 до 3 )
ну и удачи в поиске решений
alex4321
Это зависит от того, как сформирована последовательность :-)
Если N_{i+1} = N_{i}+1 — то да.
Но можно же и, например, N_{i+1} = N_{i} + 2*i :-)
Хотя, по умолчанию я бы считал первое — но это, ИМХО, вопрос заслуживающий уточнения.
avost
Ну, "последовательность чисел от 1 до N", это, если не задано дополнительных условий, записанные последовательно числа от 1 до N. Да, разумеется, можно докапываться каждого слова в поисках скрытых смыслов, то можно напридумывать много чего. Но это всё из серии, — а если бы он вёз патроны… Зачем ввдумывать сущности без необходимости?
Зы. Ваш случай, кстати, вообще не подходит под формулировку. Значения чисел из набора довольно быстро превысят N.
alex4321
«Ваш случай, кстати, вообще не подходит под формулировку. Значения чисел из набора довольно быстро превысят N»
С чего бы? N — значение последнего элемента в наборе же.
avost
Э? N{i+1} = N{i} + 2i
пусть N=3, "последовательность чисел от 1 до 3" в вашем случае будет такая:
{ 1, 1+21, 3+2*2 } => {1, 3, 7} Не?
Arastas
Фраза "упорядоченная последовательность чисел от 1 до N" в тексте математических задач должна читаться как 1, 2, ..., N, а не как "упорядоченная последовательность чисел, принадлежащих отрезку [1, N]". Для этого есть два основания:
Естественно, что при общении с заказчиком или на собеседовании, где Вы подозреваете подвох, надо уточнить. Естественно, для математической задачи лучше требовать формальную запись постановки, а не текстовую. Но столь же естественно, что при прочих равных существует определённая традиция прочтения текстовых формулировок.
saboteur_kiev
В hpmor.ru, глава 8 в первой встрече Гарри и Гермионы была полностью раскрыта тема как плохо люди трактуют условия задачи. Именно на последовательностях чисел.
Deosis
Пол главы написано ради одного предложения.
Обычно люди предпочитают проводить эксперименты, которые подтвердят их гипотезы, а не те, которые их опровергнут.
sand14
Это проблема многих подобных задач:
Не оговариваются условия и допустимые операции.
Исходная коллекция доступна или же вначале она копируется, или из копии удаляется число?
А если не копируется, можно ли перед ее модифицикацией провести немодицицирующие вычисления (получить сумму?)
А числа у нас как в математике — без переполнения, или с переполнением (а при переполнении креш, или просто переполнение — которое может быть и вполне допустимо при решении задачи)?
Также сбивают с толку ненужные условия (в данном случае — "коллекция упорядочена"). Но эти условия могут быть важны, если задача будет решается при выборе других дефолтных значений условий, которые в задаче не проговорены явно.
Кстати, в задаче про взвешивание 8 монет тоже есть подвох — т.к. для 8-ми монет для минимального кол-ва взвешиваний, монеты нужно взвешивать по 3, то из 9 монет, монета с отличным весом будет найдена за то же число взвешиваний, что и 8.
И кстати, что есть взвешивание (число которых нужно подсчитать)? Если мы взвесили 3 + 3 монеты, и потом начинаем взвешивать монеты их тройки, где есть дефектная, то получается, часть монет взвешивается дважды.
Такая операция (повторное взвешивание) допустима в задаче? Если да — то, повторное взвешивание одной и той же монеты увеличивает счетчик взвешиваний или нет?
Пример непроговоренных допустимых операций — в задаче в 4-мя таблетками.
Чтобы ее решить, нужно ввести допустимую операцию, что таблетка может быть разделена пополам.
Если эти не заданные явно условия и не определенные явно допустимые операции задуманы ради проверки сообразительности и проверки хода мышления, то почему у отдельных интервьюеров уточняющие вопросы могут вызывать раздражение?
Есть ощущение, что в таких случаях человек мог заготовить такие задачи, прочитав их в интернете, и ожидать решения, исходя из предполагаемых умолчаний.
В итоге, из моей личной практики — такие задачи я решаю или вообще сходу (вообще сразу), правильно уловив все умолчания, правильно откинув лишние условия с подвохом, и правильно определив допустимые операции (а если их явно проговорить в условиях задачи, то и задача теряет смысл — ответ очевиден),
либо, если в звездах что-то не сошлось (жарко/холодно/душно/вечер/устал), то начинаю тупить, даже если незадолго до этого решил такую же задачу мигом и впервые ее увидев.
BuccapuoH
Вторую задачу можно решить и другим способом.
1. Наполнить пятилитровый кувшин водой
2. Из пятилитрового кувшина наполнить трёхлитровый кувшин (в пятилитровом останется 2 литра воды)
3. Вылить всю воду из трёхлитрового кувшина и перелить 2 литра воды из пятилитрового кувшина.
4. Наполнить пятилитровый кувшин водой
5. Наполнить заполненый на 2 литра трёхлитровый кувшин водой из полного пятилитрового кувшина (потребуется 1 литр воды)
В итоге, в пятилитровом кувшине останется 4 литра воды.
square
Я точно так же решил и у нас с вами 6 действий, а не 8, как у автора :)
Hydro
И я почему-то тоже сразу по такому пути пошел
Arastas
И объём вылитой воды меньше.
JeStoneDev
Зато объем потребления воды больше.
В случае решения ТС идет 3 раза заполенние по 3 литра и 1 раз выливание 5 литров.
В случае решения выше получаем 2 заполнения по 5 литров (на литр больше) и одно выливание 3 литров
fregate
У нас же неограниченное количество воды. Тут либо быстрей алгоритм, либо меньше воды.
kolu4iy
Нет условия "пользоваться только кувшинами". Потому:
Old_Chroft
Если можно пользоваться чем то еще — то ваш вариант крайне не спортивен :)
1. Наливаем 5-и литровый кувшин
2… (тут что угодно: запой, распилы, откаты, etc)
3. Берем кучу камней. Проводим экспертизу для определения их плотности.
4. Рассчитываем необходимую массу камней для заполнения объема в 1 кубический дециметр.
5. Берем весы, отмериваем необходимое кол-во камней.
6. Вываливаем камни в кувшин (как мы помним — наливали в 5-и литровый). По закону Архимеда камни вытесняют необходимое кол-во (1л) воды из кувшина.
7. profit! На вопрос — какого х*я в воде камни — делаем круглые глаза и говорим, что в условиях задачи ничего не сказано о том, что вода должна быть чистой. Просим еще денег на очистку воды от камней.
soniq
В менеджеры!
martin_wanderer
Так задача — отмерить. Мы вылили ровно четыре литра воды.
Old_Chroft
Нет, мы _пролили_ 1 кубический дециметр (а это и есть литр, если кто не в курсе) воды, заместив его равным количеством камней. Кувшин объемом 5 литров по прежнему полон, НО содержит 4 л. воды, что соответствует условиям задачи. Если же эта вода далее нужна для чего то еще — нет гарантии, что с водой не получим какое то количество камней. Или наоборот: нам в этом кувшине нужен свободный объем 1 л. для добавления чего то еще — а места то и нет.
А если без шуток, перенося на програмерский быт: такие вещи встречаются сплошь и рядом, называются они красивым словом «костыль».
martin_wanderer
Мы немного о разном. В условиях не только не сказано, что можно пользоваться чем-то еще ( камнями и т.п.), там еще и не сказано, что отмеренные четыре литра должны остаться в одном из кувшинов.
alvik48
Помнится, в университете проходили универсальный метод «математического бильярда», при помощи которого можно решать подобные задачи для любых размерностей сосудов и искомого количества оставшейся воды.
user4000
Решил так же…
VokaMut
А у меня сразу мыль была, что нужно наполнить оба сосуда до верха, потом наклонить и вылить воду так, чтобы нижний край горла и верхний край дна были параллельны земле.
В итоге получаем в 3-литровом сосуде 1,5 литра, а в 5-литровом 2,5 литра.
Переливаем из трехлитрового в пятилитровый и у нас получилось 4 литра.
ZyXI
Форма сосуда по условиям неправильная. А ваш вариант не пройдёт с любой даже правильной формой, если горло и основание имеют разную форму. Простейший вариант такой правильной формы — конус, горлышком является основание: вы просто выльете всю воду.
wzrd
В Задаче 1, если обе последовательности доступны, то, как вариант, можно решить линейно. Пробежаться по отсортированному списку и сравнивать с i-1 — ым элементом отсортированного. По идее это должно получиться оптимальнее решения предложенного автором.
square
Оптимальнее? Вы шутите? Т.е. сначала потратим время на сортировку, потом умножим на два занятую память, а потом проведем N сравнений, это оптимизация? Вместо того, чтобы взять n(n+1)/2 и вычесть из него все имеющиеся числа, и в остатке получить ответ.
wzrd
Нет, оптимальнее того, что было предложено изначально как решение. Но и тут я не прав. Мне почему-то показалось, что у нас доступна отсортированная последовательность и хотел предложить как вариант.
alesto
Вы забываете что она ещё и пермешана так что не выйдет
aliencash
где оптимальнее-то? в решении автора всего один цикл от 1 до n и единичные арифметические операции. У вас — вложенные циклы и n^2 операций сравнения. или я не понял что вы предлагаете.
wzrd
В решени автора логарифм и линейный обход. А у меня только линейный. Но я ошибься, последовательность даётся только одна, неотсортированная, поэтому мой вариант отпадает.
aliencash
Простите, мы говорим о решении автора, от том, что под спойлером, так? Там один цикл от 1 до n-1, в котором считаем сумму Sum элементов перемешанного массива. Искомое число будет
wzrd
Я подразумевал решение, которое было в основном тексте, пол самой задачей. Но я в любом случае не прав.
OldFisher
EmmGold
Мне для первой задачи первым всплыло решение брутфорсом. Берём 1 — ищем в последовательности; Берём 2 — ищем; Берём 3 — ищем… берём 34234 — не находим.
mwizard
ммм… квадратичная сложность.
VioletGiraffe
Мне тоже всплыло, только сложность — N^2.
ilnuribat
задачки очень простые и легко решаемы, особенно если прорешивали кучу подобных задач в школьные/университетские годы
Мне пока самое сложное, что попалось — это задачка посчитать количесво вагонов в составе
Условие: есть состав вагонов, закольцованный, можно переходить от вагона к вагону, в обоих направлениях. Скажем, что окна закрыты и видите только текущий вагон.
В каждом вагоне определено понятие света — горит или нет
У Вас, при заходе на очередной вагон, есть две возможности: посмотреть, горит ли в этом вагоне свет, и включить/выключить свет(без ограничений)
Вопрос: как посчитать точное количесто вагонов с наименьшим количеством их посещений?
kolu4iy
Включаем свет в том вагоне, в который зашли. Идёми считаем, пока не дойдём до вагона с включенными светом. А как ещё?
grossws
А теперь представьте, что в вагонах состояние свет включен/выключен изначально случайное.
ilnuribat
именно так и есть, забыл в условии это написать
kolu4iy
Это просто отвратительно со всех точек зрения, кроме олимпиадной задачи :) но в этом случае задача не имеет решения на бесконечном количестве вагонов.
vlreshet
Так на бесконечном количестве вагонов и не предполагается искать точное количество вагонов)) Вопрос то стоял так:
И этом случае самый банальный подход — сначала включить/выключить везде свет, и дальше по накатанной схемеAC130
А как вы поймёте что свет везде включен?
alix_ginger
А как определить, что мы выключили свет во всех вагонах?
vlreshet
Чёрт. А об этом я как-то даже не подумал.
kolu4iy
… Не, я знаю, что переменные положено инициализировать. Но все же..
grossws
Нормальная олимпиадная задача. Правда, не скажу за какой класс ,)
YuliyF
в вагоне с которого начинаем — выключаем свет, во всех остальных — включаем свет. Чтобы точно убедится в правильном кол-ве вагонов: придётся сделать 2 круга.
ilnuribat
Изначално все вагоны случайном образом проинициализированы(включен свет или выключен)
понятия круг не существует
для Вас это как List<вагон>. Вы можете только next(), prev().
Чтобы "сделать круг", надо понять, что Вы дошли опять туда, где и были. Все вагоны — идентичны, не отличаются друг от друга, поэтому круг сделать не получится
kolu4iy
Потому что говорю, что на первый взгляд, при неограниченном по условию количестве вагонов задача решения не имеет: при создании любой сигнатуры для определения начала состава (точки входа) у нас нет гарантии, что она банально не продублирована (конечно, совершенно случайно).
ilnuribat
ближе к ответу)
решение есть, и да, количество вагонов в составе — конечное
bro-dev
Решения нету, тоже самое что идти по числу пи в двоичном виде, как бы мы не закодировали наше начало, не факт что дальше не будет такого же кода еще бесконечное число раз, даже если количество и кончено оно все равно может стремится в бесконченсоть.
Да даже если мы будем запоминать весь наш код и встретим его 50 раз думая что идем по кругу, не факт что дальше на 51 раз будет что то другое.
CrazyNiger
Решение есть. Идем, гасим свет и считаем вагоны. Если дошли до вагона с выключенным светом — включаем в нем свет и идем назад на то количество вагонов, которое насчитали (т.е. в тот вагон с которого начали). Если в нем свет горит, значит это в нем мы его включили и решение найдено, если нет, то снова идем в перед до того вагона в котором включили свет продолжаем от него.
postgree
Например, при начале обработки последовательности с 20(+)20(-)1(+)n(±) ваш вариант ломается.
Для достоверного решения задачи необходимо иметь ограничение типа 2^(n-1)>x>2^n. Зная n
решение возможно. Иначе — вилами по воде. Тащемта.
postgree
Вот прям даже не знаю что ответить. Или вам Серёженька не нравится, например?
Arastas
При бесконечном числе вагонов задача на их подсчёт как-то теряет смысл. :)
YuliyF
«круг» — это наш логический круг с 1м найденным вагоном в котором свет выключен.
Если мы найдём ещё один вагон с выключенным светом — значит обнуляем счёт, включаем свет на предыдущем и начинает отсчитывать вагоны с новой точки(с выключенным светом)
Arastas
В первом выключили свет и идём вправо до тех пор, пока не наткнёмся на вагон с выключенным светом. Включаем его и возвращаемся назад на пройденное ранее число вагонов, снова в первый. Если свет в нем горит, то мы сделали полный круг и задача решена. Если не горит, то круг ещё не завершён и мы снова идём вправо в поисках выключенного света. Задача решена, но в оптимальности решения я совсем не уверен.
ilnuribat
ага, верное решение, за O(N^2) в худшем случае
wataru
За O(N log N) есть решение. Основная идея та же. Изначально k=1. Включаем свет в первом вагоне. Идем вправо k шагов, гася свет во всех вагонах. Возвращаемся назад, сколько прошли. Если свет погас в первом вагоне — Ясно что всего их не больше k, переходим ко второй фазе. Иначе, мы знаем, что вагонов больше k. Умножаем k на 2 и повторяем все сначала.
Вторая фаза — мы уже знаем, что вагонов больше k/2, но меньше k+1. Бинарным поиском в этом промежутке ищем минимальное i такое, что сделав i шагов вправо, гася везде свет, мы выключим свет и в первом вагоне тоже.
Каждая итерация пройти вправо выключая свет и вернуться назад не более 4N шагов (потому что мы не будем проверять k>2N иначе бы k/2 подошло уже). Всего итераций логарифм N найти минимальный k и еще один логарифм на бинарный поиск.
stetzen
Кажется, что можно обойтись без бинарного поиска во второй фазе. Если k больше реального числа вагонов, то по дороге обратно мы в какой-то момент пройдём через вагон, в котором мы переключили свет, то есть по дороге «туда» надо записывать состояние света в каждом пройденном вагоне, а по дороге «обратно» после переключения света в k-ом вагоне считать вагоны и сверяться со списком. Первый вагон, в котором свет не совпал — это тот вагон, с которого мы начинали обратный обход, всё, мы знаем, сколько вагонов.
FINTER
Список означает, что вы используете дополнительную память. Задачу можно решить за O(n) операций и O(1) дополнительной памяти. Фактически кроме пары переменных и выключателей в вагонах ничего не нужно.
user4000
Я могу пользоваться скотчем, стикерами и авторучкой?
ilnuribat
да, но нельзя помечать вагоны, можете себе на лоб допустим приклеить))
скотчем замотать себе что-нибудь)
ЗЫ: что-то меня поперло, простите)
mwizard
Если считать, что свет в вагонах инициализирован случайным образом, сходу подумалось о том, чтобы искать самую длинную повторяющуюся последовательность в свете вагонов, таким образом можно найти с некоторой долей вероятности повтор за 2*N вагонов, и увеличивать уверенность в результате за большее количество кругов. Но, с другой стороны, это не сработает, если у вагонов паттерн света повторяется. Мы можем менять один бит в паттерне, как только мы его обнаружили, и начинать отсчет от этого вагона, и идти вперед, пока мы не обнаружим паттерн с измененным битом. Но это не сработает, если поезд "умный" и знает о нашей стратегии, и неизведанные вагоны повторяют наш предыдущий паттерн, каким бы он ни был — поэтому вводить случайную компоненту бессмысленно. Плюс у такого решения очень неоптимальные затраты по памяти — нужно хранить весь трек, и еще и считать автокорреляцию для каждой из промежуточных позиций.
Значит, мы можем изменить трек таким образом, чтобы для его хранения требовался минимум памяти. Например, мы можем зажечь текущий вагон, и затем идти в любом направлении, пока текущий вагон не включен, и считать, сколько будет вагонов до первого горящего. Теперь у нас есть оценка длины цикла. Мы выключаем зажженный вагон, который мы встретили, и продолжаем идти вперед ранее подсчитанное количество шагов. Если встреченный вагон выключен, то с какой-то долей вероятности мы нашли цикл, и можно продолжать идти дальше.
Хотя можно сделать еще лучше. Как только мы нашли первый зажженный вагон, кроме того, с которого мы начали, мы его выключаем, и идем назад требуемое количество шагов. Если изначальный вагон, к которому мы вернулись, еще горит, значит мы погасили не тот вагон, и нам нужно начать заново.
У меня некоторые трудности с тем, чтобы определить временную сложность этого алгоритма, но время растет медленнее, чем O(N^2), но быстрее, чем O(N * log(N)). Сложность по памяти такого решения — O(1).
Gemorroj
Мне, когда задают подобную чушь, сразу хочется встать и уйти.
avost
Только хочется, или таки уходите? Если первое, то глупо, что вы это здесь говорите, если второе, то глупо, что вы это делаете.
Legion21
Спасибо, надеюсь выйдут еще подобные статьи… Будет чем развлечься, а то мозг иногда прикипает, а так и хабр почитал и мозг размял немного
grossws
Это как? Расскажите, мне интересно, как вы потеряли сравнение с каждым элементом (и, соответственно,
N log Nв результате).Neyury
Третья задача в python:
A, B = B, A
wataru
А вот вопрос, сколько промежуточных переменных создается при выполнении этой операции. Мне кажеться, что их там чуть ли не 2 лишних будет. И присваиваний там 4, наверно, вместо 3-х для стандартного с одной переменной или с XOR.
ZyXI
Я тут посмотрел на «дизассемблер», получается, что я не прав: для функции
дизассемблер (
da(foo.__code__)для Python 3.4.5,da(foo.func_code)для 2.7.12) выдаётТ.е. кортеж оптимизатор убрал. Но если считать за «присваивания» те операции, которые вызывают инкремент/декремент счётчика ссылок, то их тут действительно четыре — LOAD_FAST вызывает инкремент загружаемого объекта, STORE_FAST вызывает декремент у объекта, который перезаписывается. Считать, сколько там внутренних временных переменных будет использовано, по?моему, нет смысла, да и сложно: к примеру, я не удивлюсь, если окажется, что компилятор превращает код ROT_TWO (использующий две временные переменные) в три xor. А вот манипуляции со счётчиком ссылок вряд ли куда?то денутся.
ZyXI
Ага. Только не забывайте, что в вашем примере участвуют две переменные, но три объекта (A, B и кортеж
B, A).ZRas
А мне предложенный способ решить первую задачу решительно не нравится с технической точки зрения, сумма может выйти за пределы разрядности например.
В таком случае можно сумму заменить на XOR.
так как A XOR A == 0, и XOR ассоциативная операция, то можно посчитать XOR между элементами из массива и XORнуть её с 1..N
Влоб это будет конечно дольше чем если вычислить сумму по формуле.
Кстати, интересно бы попробовать вывести формулу для суммы по модулю 2, сдается мне она не будет шибко сложной…
khim
Ээээ… Вы тут вообще о чём тут говорите?
ZRas
1) Если сумма посчитана по формуле суммы арифметической прогрессии — вполне вероятно что с учетом переполнения ответ не совпадет.
2) XOR, он же сумма по модулю 2. Вопрос был в том что существует формула для быстрого вычисления суммы арифметической прогрессии, и я высказал идею что вполне себе просто должна выводиться аналогичная формула для побитового XOR арифметической прогрессии.
Собственно пятью минутами после того как я написал сообщение я её вывел, но написать уже не смог, ограничение read-only аккаунта :(
Собственно ответ тов. Nostr чуть ниже совпадает с тем что получил я
khim
Понял. Да, хорошая идея.
Nostr
Можно не считать XOR последовательности от 1 до N, а воспользоваться следующим выражением:
Подробнее: stackoverflow
Или можно ещё проще:
1 ^ ... ^ n = (n >> 1) & 1 ^ (n&1 ? 1 : n)
Vipous
Решение первой задачи без перерасхода памяти. Из условия дано, int N и int[N-1] a
int value = N
for(int i = 0; i<N-1; i++ ){
value = value + i - a[i]
}
Vipous
А вот идеальное решение первой задачи нужно xor все элементы массива между собой и ещё с N полученный результат и будет искомое число
int value = N
...
value = value xor a[i]
Rathil
Что-то я не въезжаю в Ваше решение:
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] не доступно!
Или я что-то напутал?
Vipous
В первом решении ошибка на +1, это нормально при решении на бумажке
V = V + i — a[i] + 1
V = 4
4 + 0 — 4 + 1 = 1
1 + 1 — 1 + 1 = 2
2 + 2 — 2 + 1 = 3
loginsin
В первом и втором способах есть свои плюсы и минусы. Минус для первого указали, а для второго — нет. Например, второй способ не подойдет для float/double.
ZyXI
xorвполне себе подойдёт для float и double, только кода будет больше, чтобы убедить компилятор делать побитовый xor на double «как если бы это было просто N?битовое беззнаковое целое». А вот арифметические операции для float и double не подойдут совсем. Подумайте, что будет, если в одном или другом числе окажутся такие интересные значения, как +?, ??, NaN (кстати, NaN может быть тоже два варианта). Или в одном числе будет 1???10100, а в другом — 1???10?100.khim
loginsin
Зачем так сложно? Есть инструкция процессор XCHG, тогда уж. :-)
khim
Векторной версии нету.
vesper-bot
Второй способ не подходит, если данные разной размерности (т.е. например, одна переменная float, вторая double), при этом можно их складывать с потерей точности. Что интересно, в случае целочисленных типов ксорить будет правильно, если более длинный тип привести к правильному размеру, правда, старшие биты придется занулить вручную.
Barafu
Хотите мозговыносной вариант задачи? Дано две бочки по 20 литров. Обычные типичные дубовые бочки. Требуется: пользуясь только ими, отмерять 10 литров. Не "на глазок" естественно. Бонус поинтс тому, кто не прольёт ни капли.
Это не подстава, задача решаема.
square
налить одну полную и переливать во вторую до тех пор, пока будучи наклоненной уровень воды не окажется одновременно у противоположных краев дна и поверхности, в итоге будет по 10 в каждой
lobzanoff
Налить полностью одну, потом переливать из нее во вторую, пока уровни не сравняются.
TheIseAse
Начать с одной полной и одной пустой, соединить шлангом, подсосать и сделать сообщающиеся сосуды, уровни воды выравняются и получим по десять литров
square
А откуда взялся шланг?
webfaker
Ключевое слово: подсосать…
Keyten
По поводу третьей задачи. В некоторых языках можно делать так:
Правда, доп. переменная всё равно создаётся в памяти. Но не в языке.
Armleo
Есть техника "переминования переменных" Если переменные в регистре то компилятор может просто отбросить swap и просто изменить внутреннее представление. Если в памяти и в регистре то xchg в один такт наш все :). Если оба в памяти то задача не решаема на типовых x86, x86-64.
akzhan
Эм, а что, где-то еще предлагают такие задачи? Это же для джунов.
AnROm
Только не смейтесь, но эту задачу дали моему знакомому, который собеседовался на старшего программиста. Обойдемся без указания компании, но название всем известное
khim
На самом деле как раз у «сеньоров» такие задачи и вызывают проблемы зачастую. Любой грамотный школьник их, как бы, должен решать, но если человек «засеньорил» настолько, что посление, скажем, три года не писал кода вообще — то у него будут проблемы.
dimka11
Такое вообще может быть? Он же все таки программист, а не тимлид/ менеджер.
khim
Это вакансия у нас для программиста, а люди приходят разные. Некоторые считают, что если они 10 лет назад код «во сне» могли написать, то и сейчас смогут. Не смогут, увы, навыки теряются.
Я в своё время на Turbo Pascal мог сделать вообще всё. Вплоть до того, что знал что и где поправить чтобы стандартная библиотека и Turbo Vision с руссими буквами работали. Но если меня сейчас писать на нём программу писать… придётся не один месяц привыкать.
А если человек прекращает программировать совсем — то вернуться назад ещё сложнее. Но многие — этого не осознают, увы. Отсюда и берутся подобные задачки на собеседованиях. Как первичный фильтр, не более. Будет глупо решать — брать кого-то или нет только на основании таких задачек. Но «для разминки» они как раз подходят — а дальше можно плавно перейти на разные типы данных кеши, компиляторы и прочее, прочее, прочее.
iig
Знание Turbo Pascal на уровне God вряд ли сильно поможет в программировании на любом другом языке.
ZRas
Решительно не соглашусь. Программист, особенно хороший программист, это в первую очередь образ мышления. Навыки выделения алгоритма из словесного описания задачи, разложение этого алгоритма на тот набор «элементарных» операций который доступен, поиск оптимальных структур данных для задачи, понимание о-нотации, дискретная математика. Эти навыки в целом общие для любых языков программирования.
Да в каждом есть свои уникальные трюки, технологии. В некоторых из них «элементарной» могут быть вполне себе сложные задачи(к примеру в Matlab многие весьма мудреные операции можно считать «элементарными», к примеру решение задачи линейного программирования). Разница между уровнями тех самых общепрограммистских навыков будет неплохо коррелировать со скоростью освоения подобных технологий.
В общем, такие вот задачки по мне — вполне себе позволительная вещь даже на собеседования синьоров, но конечно не все собеседование из них состоит. Для толкового человека это будет «разминочка», возможность почувствовать себя в своей тарелке. Хотя если человек приходящий на должность синьора такую задачу не щелкнет или того хуже будет в качестве решения первой задачи предлагать O(N^2)… Я бы все таки задумался, это ведь должен быть человек самостоятельно принимающий технические решения, не бегающий проконсультироваться с начальником на каждый чих. Понастроит ведь потом велотренажеров
iig
Я и не возражал ;). Я считаю, что знание, даже, офигенное, какого-то одного языка/фреймворка/IDE никак не связано с образом мышления.
ZRas
Тут видимо мы по разному воспринимаем слово «знание». Для меня «знание одного языка» == способности на этом языке написать все что угодно. Т. е. человек уже собаку съел в программировании на этом языке.
bamboom
Давно интересно почему на собеседованиях проверяют умение думать, но не проверяют способности к планированию и самоорганизации.
Безусловно хорошо если человек может решить задачу тремя разными способами 2 из которых никто кроме него не придумал, но если бы у меня был выбор: работать с командой из очень талантливых и творческих оболтусов или же с командой которая пишет нормальный код (нормальный это понятный блин, а не короче на 3 строчки чем у соседа) и делает это в срок — я бы даже думать не стал.
vintage
Тут такой момент — если человек не дурак, то научить его писать понятный код — можно. Если дурак, то научить его самостоятельно решать проблемы — проблемно. :-) Другое дело, что головоломки слабо коррелируют с сообразительностью: глупый мог знать ответ, умный мог не допереть за отведённый срок.
bamboom
Извините, не понял зачем вы это мне написали.
bamboom
В первой задачке 9 из 10 нормальных обычных людей посчитает что исходная последовательность недоступна.
Поэтому, с моей точки зрения, если кто то решит ее не, уточнив у рекрутера доступна ли она но при этом использовав ее, то это «звоночек» что человек не умеет делать поправки на то что вокруг него существуют не только программисты.
И следовательно, возможно, он будет сношать мозг окружающим своей «точностью формулировок» вместо того чтобы засовывать свое чувство превосходства куда нибудь подальше и сосредоточиваться на том чтобы сделать дело.
isden
> В этом решении есть большой минус: возможность переполнения.
А что за переполнение такое? У нас же в условиях нет ограничений на память/разрядность/и т.д.
Scf
Да много их. Про альпиниста и веревку, про утку и лису, про лампочки и стоэтажный небоскреб…
algotrader2013
По первой задаче есть замечание: сортировка Counting sort, которая туда просто сама просится, никак не NlogN займет, а N по времени, и N по памяти.
ef_end_y
Нет никакой проблемы, что в первой задачке программист не заметил простого решения ибо обычно таких халявных условий в жизни не бывает. А если так и случается, то программист находится в контексте и знает куда копать. Или заказчик ставит условия объясняет это нюанс. В любом случае, это не повод чтобы отсеять претендента если он просто не заметил подвоха.
AnROm
Полностью поддерживаю. Не хочется здесь устраивать споры «кто прав», но частенько именно так происходит отсев, возможно, кому-то действительно важно уметь решать подобные задачи.
i86com
Меня всегда в таких задачках напрягает их оторванность от реальности. Они, конечно, неплохо подойдут как «тема для разговора» на собеседовании, но делать прямое соответствие «кол-во правильных ответов — шанс на приём» я бы крайне не рекомендовал. Потому что в реальности многие эти «решения» неприменимы и ущербны.
Поясню мысль.
Первая задачка (с последовательностью без числа) в реальности может встретиться, например, при работе с БД. Есть список каких-то записей (юзеры, товары, транзакции — не важно), у них есть ID от 1 до N (autoincrement), есть некая функция, которая их удаляет, нам нужно узнать, что было удалено.
Тут стоит заметить, что во-первых, обычно используется не удаление, а установка какого-нибудь status: disabled (или установка null в поле, если прямо так необходимо избавится от информации). Удаление может вызвать кучу проблем и головной боли в последствии, не надо так.
Во-вторых, обычно всё-таки не должно возникать ситуации «у нас в БД что-то пропало, неизвестно что». ID удалённого объекта должен записываться в момент удаления и обрабатываться сразу же.
Но ок, допустим, какое-то вероисповедание нам не позволяет исключить возникновение такой ситуации. Тогда в-третьих: даже если мы делаем проверку суммы сразу после удаления чего-то, никогда нет гарантии, что в самом деле что-то было удалено, или что была удалена только одна запись. Даже если сегодня это так, завтра функцию могут переписать.
В итоге, человек, который считает, что ответ с суммой — окончательный и достаточный для продакшена будет просто не прав. Тут либо переделка структуры, либо полный перебор ID'ов.
Вторая задачка (кувшины) — ну ок, лёгкая, математическая, чтобы решающий почувствовал себя увереннее. К IT отношения не имеет от слова «совсем».
Но вообще в реальных задачах такого типа (когда есть возможность что-то решить, нестандартно используя существующие объекты), нужно в первую очередь начать задавать вопросы.
Почему такая задача вообще возникла и к ней не готовы? Может, в ТЗ опечатка и нужно всё-таки 3 литра?
Почему у нас нет кувшина на 4 литра? Может, он всё-таки есть и стоит его поискать? Чтобы не занимать те два кувшина, которые явно уже предназначены для других целей и могут понадобиться остальным.
А если скоро опять возникнет такая задача? А если в следующий раз — 1/4 литра? Может, стоит озаботиться покупкой кувшина с литровыми отметками, а не тратить своё время на «костыльные» переливания?
Третья задачка (поменять переменные местами) — да, задачка интересная. В реальности встречается, но крайне редко. Тут только нужно пояснить, в этой самой реальности для решения используют встроенную функцию (обычно называется Swap), либо (на худой конец) третью переменную. А за неожиданный уход в побитовые операции пускают лучи неневисти (те, кому потом придётся поддерживать такой код).
rg_software
Получается, что они не просто оторваны от реальности, они заставляют искать костыльное ad hoc решение, которое годится только для данного конкретного случая. Мне кажется, опытный программист уже на подкорке отсекает такие решения (и на работу его не берут...)
CheY
Первая задачка — явная прелюдия к вопросу о сложности алгоритмов. Особенно если соискатель «попался» на желании что-то сортировать. А разглядеть О(n*log n), O(n) и O(n^2) и знать разницу должен каждый джун.
Вторая задачка к IT и правда мало отношения имеет, кроме разве того, что в голове приходится проигрывать алгоритм.
Третья задача проверяет
на способность делать костылинаходить решение в условиях ограничений (например, платформы). Заодно, если он вспомнит про битовые операции, то несомненно плюс.Задача про вагоны из комментов вполне похожа на некоторые задачи биоинформатики с их кольцевыми ДНК.
Это далеко не самые оторванные от жизни в IT задачи, я вам скажу. Другое дело, что они банальные и задаются повсюду, отчего их ценность как каких-то индикаторов сходит на нет.
khim
brnovk
Иногда натыкаюсь в сети на тестовые задания или вопросы по алгоритмам на собеседованиях, обычно стараюсь сохранять ссылки и текст задачи (авось пригодится).
В основном встречаются скучные типовые задачи под конкретный стек технологий, но есть и достаточно необычные (по крайней мере, для меня):
2/ Ссылка
3/ Ссылка
4/ Ссылка
grossws
Из первого списка первая задача — zip+flatten, называть её merge не очень, если не предполагать имплицитно специальный компаратор, базирующийся на индексах в коллекциях.
Во втором SAX/StAX вполне должен укладываться в нужные характеристики. DOM и использование XSLT с большой вероятностью не взлетит.
3.1 — внешняя сортировка по вкусу. В 3.2 явная хрень в условии, тут либо использовать общепринятые термины (архивация/компрессия, ибо тот же tar — архиватор, но не компрессор), либо явно указывать что понимается под каждым термином…
4 — опять внешняя сортировка с парсингом, вполне нормальный вариант на поговорить. Хотя 4 часа выглядят сильно избыточно, если не нужно писать в блокноте.
sbnur
задача для собеседования
Стоит четырехэтажный дом, в каждом этаже по восьми окон, на крыше — два слуховых окна и две трубы, в каждом этаже по два квартиранта. А теперь скажите, господа, в каком году умерла у швейцара бабушка? (Из Гашека)
webfaker
Ну здесь как раз есть ответ: в 1894 году.
vesper-bot
А он выводится из исходных данных хоть как-то?
Arastas
Швейк рассказал свою задачу в 1914 году. Год кончины бабушки равен произведению общего числа окон этого дома на число труб и на возраст (в 1914 году) одного из квартирантов, лично присутствовавшего на похоронах. Итак, в каком же году умерла у швейцара бабушка?
На самом деле, это такой своеобразный фольклор про странные задачи.
vesper-bot
Про "на самом деле" — это было ещё прямо в книге. А вот приведенное вами решение требует дополнительных данных, которых в исходной постановке нет (про квартиранта — про него Швейк в книге не сказал ЕМНИП ничего). Значит, задача не является математической. (А вот примером странной задачи — является, ещё как.)
Спасибо, кстати, за решение, мне ещё не попадалось.
webfaker
На самом деле, всё просто: один мой хороший знакомый как раз потомок этого швейцара))) (кстати, он британский учёный и, по совместительству, русский хакер, — то есть источник, как вы понимаете, надёжный)
В остальном же прав Arastas: это классика идиотских задач и тут решения из исходных заведомо нет. Хотя можно собрать материальчик на историческое расследования, чтобы вычислить наиболее вероятный диапазон: как уже сказано, задача рассказана в 1914 году, вероятно несколькими днями позже 28-го июня, действие происходит в Праге и исходя из характера Швейка можно с большой долей вероятности утверждать, что дом этот — именно в Праге, а время — немногим ранее… и т.д… но зачем? если правильный ответ: 1894, и тут уж ничего не поделаешь!
khim
Проблема только в том, что правильный ответ там 1904. А 1894 на 28 не делится.
webfaker
asm0dey
А где в первой задаче сказано что доступны обе коллекции — исходная и перемешанная?
sand14
Про задачу с обменом чисел:
опять же, много допущений: в варианте со сложением вычитанием нужно исходить из того, что отключен креш при переполнении;
в варианте с XOR — исходим из того, что вычисление производятся на компьютере с бинарной логикой (а где вообще в задаче сказано, что вычисления будут производиться на компьютере, а не на листе бумаги или компьютере с троичной логикой?).
И самое главное — сбивает с толку то, что кажется, что задача поставлена из соображений оптимизации (скорость, экономия памяти), и начинаешь искать это "оптимальное" решение.
Получаем то, что называется "преждевременной оптимизацией":
При введении переменной-буфера мы всего лишь вводим одну переменную, и операция копирования значения — из одной ячейки памяти в другую — весьма быстрая (если речь о переменной 32/64 бита, а не BigInteger — а где это оговорено в условии?).
Давайте не забывать, что операции сложения/вычитания, битового маскирования явно помедленнее — нужно поместить значения из памяти в регистры процессора, выполнить собственно операции, считать это обратно в память.
И еще надо разобраться, не введет ли при этом компилятор промежуточные переменные на стеке (а тогда за что боролись)?
И что значит два числа? Где оговорено, что это int, не float? Для float результат сложения/вычитания будет вообще долгим и неточным, а XOR для float вообще будет неприменим (хотя, конечно, можно интерпретировать float как бинарные данные и привести с int, а потом обратно к float — это тоже куча лишний операций, в результате которых теряется смысл задачи).
Shifty_Fox
Ох…
Эти неверные постановки задачи. Первая задача — найдите число. Но не уточнили — нам нужна ссылка на удаленное число в первом списке\массиве или просто значение этого числа. Во втором случае конечно достаточно разницы сумм, но вот я к примеру подумал, что прежде всего по смыслу задачи нужно найти позицию индекс удаленного числа в первом списке, и в этом случае сортировка и линейная сверка один из оптимальных и быстрейших решений.
kruslan
Как? Как тут можно подумать об индексе удаленного числа? о_О
ser-mk
индекс в первоначальном массиве, хотя, най мой взгляд, четко сказано найти число(то бишь значение), а не индекс.
Shifty_Fox
Отвечу обоим. Сказано найти число, которое потерялось. Число, в памяти. Оно еще есть в какой-то ячейке — нужно найти ячейку с этим числом. А что не так с такой интерпретацией?
Скажем так, если бы формулировка была — вычислить, тогда вопросов бы вообще не возникло. Там написано — найти удаленное число. Для меня это двояко.
kruslan
С чего вы решили, что это число есть в памяти? Возможно — на листке бумаги записано.
Если-бы нужно было найти ячейку — формулировка задачи звучала-бы как у вас, но в задаче довольно точное описание — найти удаленное число.
P.S.: странно, что с такой логикой вы не дошли до «найти операционную систему, в которой удалено число» ;)
Shifty_Fox
Ну просто в моем языке программирования число — это объект, а объект ищут по ссылке.
kruslan
А как связана задача и конкретный язык программирования? о_О
Кроме того — вы действия «в своем языке программирования» совершаете над объектами или над значениями?
Shifty_Fox
Вот именно что обычно над ссылками на объекты
kruslan
Вы складываете ссылки вместо значений?))) Нууу, ок.
Shifty_Fox
Смотрите, действие — найдите удаленное число для меня звучит в отрыве от типов. Для меня это фраза — найдите потерянный объект в массиве, т. е. указатель на него\индекс в исходном массиве.
kruslan
Каких типов? Какой объект? Вы вообще о чём?!
Перестаньте думать в критериях языков программирования! Думайте логически и математически. Язык — это всего-лишь инструмент выражения знаний и опыта. Переводя каждую задачу в область одного ЯП вы лишаетесь гибкости рассуждений. Как так можно?!
Даже тут — откуда взялся объект и почему вдруг надо искать индекс, если речь о числе? Ну ок, предположим… Тогда почему массив 1..N не может лежать в памяти с адресацией от 1 до N? Так вам проще?
P.S.: вообще — это очень, очень плохая привычка — додумывать задачи. Вот честно, по работе сталкиваюсь с подобным и ни разу это не привело ни к чему хорошему. Из-за подобных привычек задачи выполняются дольше и сложнее, и как следствие, сложны в поддержке в будущем.
saboteur_kiev
Поддержу.
Программист, который не пытается понять бизнес-задачу клиента, будет решать свои программистские проблемы, а не проблему клиента.
В результате это ведет к множественным недопониманием друг друга, заваливание сроков и реализации некорректной логики.
Логические задачки для того и нужны, чтобы их решать логически.
Shifty_Fox
В чем вообще проблема? Я ничего не додумывал, и формулировка действительно двоякая. То, что для вас очевидно и однозначно, вполне может быть не очевидным и не однозначным для других. И навыки программирования тут совершенно не при чем. В контексте вычисления потерянного значения — берем суммы, в контексте _поиска_ потерянного числа — находим индекс. Проще уточнить задачу, и она будет уточнена, если это будет реальный разговор меня и собеседника.
kruslan
Уточнять желательно — тут полностью согласен. Но уточнять в данной задаче — это что-то новое. Если-бы было сказано «найдите то, что убрано» — да, появляется двоякость. В задаче-же четко сказано — найдите удаленное число. Удаленное число! Где тут «двоякая формулировка»? Не понимать (с)…
Shifty_Fox
найдите то, что убрано
найдите удаленное число
Вот читаю и вижу одно и то же.
То что по разному выглядит для вас, одинакого может выглядеть для других, и наоборот. Люди разные, ничего страшного.
kruslan
Хм… А если задача найти недостающее слово в тексте — тоже позицию искать будете?
Тут дело не в том, что люди разные, а в том, что вы додумываете задачу под свои критерии. Именно этому я и удивляюсь, если честно. Заметьте, кроме вас никто не прочел задачу подобным образом (либо я этого не увидел в комментариях).
Как-бы там ни было, давайте на этом и закончим.
Shifty_Fox
Эээ, я уточню что искать, позицию или слово. Я не очень понимаю, что клиенту даст слово, без места, где оно должно было стоять или было убрано.
Больше того, в таких задачах просят подчеркнуть слово, а не просто написать его, т. е. все таки найти позицию.
kruslan
Ха… Снова додумываете, хоть и не хотите себе в этом признаваться…
Вот в задаче сказано — найти недостающее слово. Для чего и что с ним будут делать потом — абсолютно не важно. Есть задача — найти слово. Что подразумеваете вы?
Откуда вдруг взялась позиция?)))) Ясно и четко написано — найти удаленное слово. Для чего вы пытаетесь придумать себе новую задачу, не решив поставленную?))))
Критерий всегда(!) один — решение поставленной задачи.
Значит! И еще как! С подобным подходом вы тормозите и усложняете работу своих коллег, т.к. чаще всего от поставленной вам задачи зависят другие задачи, которые решают другие люди. Если вам поставлена задача найти слово, но в результате вы возвращаете позицию — значит следующий за вами разработчик не сможет решить свою задача (например, занести это слово в словарь на анализ).
Я понимаю, что вам хочется проявлять инициативу, но чаще всего это путь к проблемам. Найдите в себе силы и избавьтесь от подобной привычки. Это мое искреннее пожелание.
Shifty_Fox
Пожалуй я сохраню привычку уточнять задание, прежде чем потенциально сделать то, что потом придется переделывать из за возможной двусмысленной трактовки задачи.
Заметьте, я не утверждал что условие именно найти позицию, я указал что есть такой вариант, и в этом варианте решение будет более общим, хоть и алгоритмически более медленным.
Привычка уточнять дух задачи, а не формулировку, обдумывание наперед того, какие задачи возникнут в будущем — хорошая привычка.
kruslan
Прочтите мои ответы выше. Я не предлагал избавиться от привычки уточнять, я предлагал избавиться от привычки додумывать. И, как я уже говорил выше, уточнять — это хорошая привычка.
Shifty_Fox
Можете указать, где я хоть раз что-то додумывал? Я лишь поставил вопрос — есть такая трактовка, и гипотетически рассуждал в этом направлении.
Если проблема в этом, то наконец пожимаем руки, я рад что мы поняли друг друга.
kruslan
Здесь, здесь, здесь и здесь…
Так вот тут и непонятка… Как(!) в текущем изложении(!!) можно трактовать иначе?! Вот блин — я честно не понимаю этого.
А проблемы в принципе нет. Просто была моя попытка понять как и о чем рассуждает человек, когда переворачивает исходную задачу. К сожалению, так и не понял, хотя очень-очень пытался ((((
Увольняйте такого менеджера. Поверьте — это добрый совет. Если поставлена задача, которая не обдумана — тратятся ресурсы не только менеджера, но и программиста, тестировщика и пр.
Shifty_Fox
Вас удивляет что у нас разные критерии, но я точно ничего не додумываю. Просто вы видите условия так, а я иначе. Ниже в комментариях есть ответ, что большинство видит задачу так как вы, я с этим не спорю, я в меньшинстве, но это не значит что меня нет или я в чем-то не прав.
balexa
У вас правда странный подход.
Я прямо вижу диалог.
— напиши программу которая находит недостающее слово.
— А надо слово или позицию?
— Слово
— А надо слово, или номер статьи в словаре Даля?
— Слово
— В общем я тут решил задачу, моя программа подчеркивает предложение где это слово пропущено, возвращает ссылку на викисловарь и печатает номер позиции в тексте.
-…
Shifty_Fox
Вы сами придумали этот диалог.
— Надо слово или позицию? Какие еще метаданные к этому слову нужны?
— Только слово
— Ок, но если понадобится что-то еще, придется полностью переписать алгоритм с нуля.
И тут вдруг менеджер начинает действительно думать, а не понадобится ли что-то еще.
Если не понадобится, то
— Нет, только слово
— Ок.
balexa
Нет, я взял его из диалога выше, где вы упорно доказываете что под «недостающим числом» может пониматься что угодно — от индекса до ссылок в вашем любимом языке программирования.
В целом у вас как-то все очень странно. Менеджер который начинает задумыватьтся о том может ли что-то понадобиться не в момент формулировки и планирования задачи, а после вникания программиста. Система которую надо переписывать с нуля каждый раз когда требуется внести какие-то изменения.
Shifty_Fox
Я не переворачиваю задачу. То, что вы считаете, что понятие числа — это его значение — единственно адекватная и верная трактовка — это заблуждение. Вы правы, что это адекватный контекст для большинства людей, но тем не менее это всего лишь контекст. Считать меньшинство людей, которые совершенно спокойно видят много контекстов, и не возвышают один над другим, вместо того уточняя какой имелся ввиду — странными — странно для меня.
А что касается задумываний менеджера и системы которую надо переписывать с нуля, это как раз относилось к задаче.
Если мы будем решать задачу через суммы, а в будущем окажется, что нам все таки где-то нужна не только сумма, но и сам объект, который ее содержал до этого, возникнет новая задача, в которой таки придется сортировкой и перебором искать искомый объект (с вашей точки зрения новая задача). Но это вполне очевидный и обыденный кейс для меня — сразу узнать будущие кейсы и уточнить с менеджером более удачную реализацию, подходящую для дальнейших хотелок. Такие ситуации у меня на работе штатные, и не поверите — бывают и такие формулировки как в этой задаче, и именно со смыслом находить объект, чтобы потом как-то работать с статистикой по нему.
kruslan
Можете назвать компанию, в которой работаете? Я для себя, чтобы занести на будущее в черный список. Честно.
Вы серьезно или начали троллить?)
Если первое… Да, число === значение, в контексте данной задачи. И это неоспоримый факт. Не понимаю, почему вы до сих пор пытаетесь себя и других убедить в обратном. Заметьте — никто, кроме вас, не прочел задачу в виде «найдите индекс». Думаю, хотя-бы это уже является поводом задуматься…
Я не считаю это странным. Я искренне считаю это вредным. В первую очередь — по отношению к своим сослуживцам. Одно дело, когда задача действительно не описана полностью, другое — искать причину подстроить задачу под себя. В данном случае — второй вариант. Задача описана максимально ясно и не допускает двойной трактовки.
Снова начались додумывания условий (((. Да, это новая задача, которая может содержать в себе совсем другие условия. И новые бизнес-требования.
Не поверю. Либо вы лукавите, либо ваши постановщики задач не компетентны.
Shifty_Fox
Вы странный (:
А с моей работой все в порядке.
kruslan
Я странный?! )))))))))))))))) Нууу, ок.
Shifty_Fox
Я аккуратно намекнул на вашу нетерпимость.
kruslan
А на хабре теперь запрещено свое мнение публиковать? о_О
И что не так с моими высказываниями? То, что я не хочу никогда работать в компании, в которой менеджеры меняют условия задачи в любой момент? Или то, что сотрудники, вместо решения конкретной задачи, начинают придумывать свои условия?
Если это так (а судя по вашим словам это именно так) — я не хочу работать в такой компании, не хочу видеть их вакансии и считаю менеджеров в данной компании не компетентными. Да, это мое мнение и считаю, что я обосновал свою точку зрения.
ZyXI
Действия согласно семантике программы совершаются над значениями, согласно семантике языка — над объектами, а реально оптимизатор может много чего повыкидывать и совершать действия над регистрами и памятью вплоть до того, что новый объект числа создастся только на строчке
return missing_number. «Найти число» в смысле «найти [ссылку на] число» — вполне допустимая интерпретация, «ссылку на» при разговоре часто опускают, хотя обычно это делают только когда идёт речь о более «сложных» объектах, что почти всегда передаются по ссылке.kruslan
Действия, в большинстве случаев, совершаются над значениями. Даже в семантике языка. Передача объекта по ссылке — это передача ссылки на объект и тут ссылка и является значением.
Но, даже если принять вашу точку зрения — в задаче сказано явно — найти число. Как это можно интерпретировать иначе — для меня загадка. Подобное, в своей практике, встречал не часто. Обычно — когда человек пытается не решить задачу, а придумать кучу проблем и героически их решать.
ZyXI
Интерпретировать вполне можно и так, как Shifty_Fox. Другое дело, что большинству программистов (включая меня) это действительно не придёт в голову: почти во всех языках программирования, даже если число является объектом, всё определено так, что разница между числом x в объекте по адресу A и разница между тем же числом x в объекте по адресу B настолько мала, что нормальный программист о ней вспомнит разве что после того, как у него начнутся проблемы с производительностью на большом количестве чисел.
Но именно такая интерпретация мне пришла бы в голову, если бы «число», к примеру, было «клиентом».
Shifty_Fox
del.
yarric
Я бы решил первую задачу вычитанием двух множеств: вычтем из первого множества со всеми числами 1..N второе множество без одного числа, получим это недостающее во втором множестве число.
lega
Мне понравилась такая задача:
* 4 человека, с разной скоростью передвижения (1, 2, 5, 10 мин)
* нужно перебраться всем по мосту
* по мосту могут идти только 2 одновременно
* по мосту можно идти только с фонариком, фонарик один
За какое минимальное время можно перебраться всем на другую сторону?
Shakhmin
А доказательство, что данное время минимально, без полного перебора вариантов существует?
wataru
Очевидно, вперед всегда идут двое, потом кто-то один возвращается с фонариком. Минимальное количество ходок — 5 (3 туда, 2 обратно). Покажем, что нет решения за 16 и меньше. Из трех ходок туда, хотя бы одна будет с 10, оставшиеся стоят не меньше 2 (ибо там 2 человека идут). Еще 2 ходки назад стоят не меньше 1 каждая. Т.е. теоретически минимальное время 16. Это только если оба раза назад идет 1. Но в этом случае туда всегда идет 1 с кем-то (и они все разные) и 3 ходки вперед стоят не 10+2+2, а 10+5+2 — уже больше 16.
x67
Совсем не понимаю, каким образом у вас получилось выкинуть оттуда 5. Как минимум один раз 5 должна пройти. Время пересечения не может быть меньше времени пересечения для самого медленного звена. Если перебрались все, значит каждый как минимум раз прошел. Если мы 5 спрячем в 10, назад все равно придется 5 возвращаться. Поэтому самым рациональным является сделать минутку гонцом.
10> +1< +5> +1< +2> = 19
wataru
5 действительно может быть спрятанно за 10. Но в этом случае, как уже сказано, нельзя оба раза вернуть назад 1. При этом не обязательно, что назад идет кто-то из пары, только что пришедших. В этом случае 5 не обязано идти назад. Выше я показал, что 16 вообще оценка снизу, к тому же не достижимая. Доказать, что ответ 17 можно только приведя и сам ответ:
> 1 2
< 1
> 10 5
< 2
> 1 2
fireSparrow
Что-то я не пойму, как получилось 17. Можете по пунктам объяснить?
У меня меньше 19 не получается.
В вашем решении учтено, что по крайней мере два раза кто-то с фонариком должен будет ещё и возвращаться к началу?
Carbonade
Instant return, видимо. Присоединяюсь к вопросу.
wataru
Хитрость в том, чтобы с 10-кой, которая обязательно посчитается, пустить максимальный из оставшихся — 5. Таким образом, мы исключаем 5 вообще из суммы. Чтоб ему назад не идти потом, 10 и 5 идут вперед не первыми. Тогда кто-то другой уже будет на другой стороне, чтоб вернуться назад.
gerod
а вариант когда идет человек 10 минут с фанариком, с ним начинает идти 1-минутный, после того как выходит 1-минутный идет сразу 2 и затем так же 5-ка… и того 10 минут… или я что то не так понял?
khim
Нужно всех перевести, однако, а не только бабушку и дедушку.
lega
oleg_gf
С компьютерной точки зрения это (да и никакое) решение неверно, так как у каждого из этих людей своя скорость передвижения и, следовательно, никакие из них не могут двигаться вместе. Ведь в задаче нигде не говорится, что кто-то из них может двигаться с более низкой скоростью. Мало того, в задаче сказано, что по мосту могут идти только 2 одновременно, что можно трактовать как запрет ходить по одиночке.
lega
Изложил задачку в кратком и понятном для человека виде, для «компьютерной точки зрения» могу расписать это на 10 листах, но на хабр оно точно не нужно, вам бы лишь поприкапываться.
gerod
не могу понять почему не верна логика когда стартует первый с 10-ка и с ней в паре еще любой другой, пока 10-ка идет, поочередно другие заходят на мост, после того как закончат идти другие пары… Ведь по сути ваш вариант 1-ца возвращается после достижения края моста… почему в это время не может начать движение другой человек с противоположного конца моста? что в правилах задачи ему это запрещает? На мосту есть человек с фонариком, одновременно там 2… Объясните не понимающему данную задачку
gerod
дошло почему не верная логика, простите.
BubaVV
Есть ли устоявшееся английское название у задачи с бутылками?
OldFisher
water and jug problem или просто jug problem
BubaVV
Общий способ решения.
Знал о нем давно, но нагуглить без названия не получилось. Основан на равенстве суммы высот для всех точек равностороннего треугольника
ALexhha
Вторая задача прям из фильма Крепкий орешек 3, сцена у фонтана со слоном.
Но я не так ее решал
1. Наполняем 3х литровую и переливаем в 5ти
2. Повторяем 1й шаг, в результате после 2й итерации у нас в 3х литровой останется 1 литр
3. Опустошаем 5ти литровую и переливаем туда 1литр с 3х литровой
4. Наполняем 3х литровую и переливаем в 5ти. Получаем 4 литра
Dreyk
У меня короче — 6 шагов
а блин, там выше уже такой алгоритм рассказали
japan007
и что вам даст это при собеседовании кандидата на позицию, скажем, Software Engineer?
khim
Можно будет отсеять примерно половину кандидатов за явной неадекватностью.
С оставшимися нужно будет говорить на другие темы, конечно.
ClausMark
Забавно, мне на собеседованиях попадались все перечисленные в посте задачи :) Первую решал через разницу сумм исходной и новой последовательности, вторую и третью предложенными вариантами.
PiCensored
Вот такая задача была на собеседовании
Встречаются два приятеля — математика:
— Ну как дела, как живешь?
— Все хорошо, растут два сына дошкольника.
— Сколько им лет?
— Произведение их возрастов равно количеству голубей возле этой скамейки.
— Этой информации мне недостаточно.
— Старший похож на мать.
— Теперь я знаю ответ на твой вопрос.
Сколько лет сыновьям? (Ответ логичный и однозначный)
BubaVV
1 и 4?
Arastas
Почему не 1 и 9 или 2 и 8? Или автор лукавит про однозначность.
Shifty_Fox
Чтобы решить задачу, нужно понять — математики знали количество голубей, а мы не знаем.
1) Дошкольники. Значит им от 1 до 7 лет.
2) Их произведение равно известному только математикам X
3) Старший похож на мать. Именно этот факт дал второму математику ответ, из чего мы знаем что, до вопроса — число голубей раскладывалось как на два одинаковых числа, так и на два разных, и тот факт то возрасты не равны — отсек вариант с одинаковыми числами, оставив два разных — 1 и 4
Задача решается перебором и проверкой каждого варианта на все эти условия.
Arastas
Согласен, я упустил, что дошкольники.
ozonar
Все равно осталась неоднозначность насчет того, почему им не может быть 1 и 3 или 2 и 5?
ozonar
Понял. Фраза
Это часть условия
Shifty_Fox
Скорее вот это условие не проходит:
«Этой информации мне недостаточно.»
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 и т. д., уже не дошкольники.
Arastas
Хотя не сказано, что им целое число лет. Например 6 лет и полтора года дадут те же 9 голубей, что и два по три года. Да и то, вдруг они возраст в днях считают.
BubaVV
И никто не сказал, что целое число голубей
saboteur_kiev
Делаем матрицу перемножений всех комбинаций чисел от 1 до 7.
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
icysnake
Что касается третьей задачи, то одно из значений переменных можно положить на стек или воспользоваться регистром. Когда нужно в ход идёт любой ассемблер.
zagayevskiy
И в чём будет отличие от использования переменной?
alexeykuzmin0
Можно подумать, вариант с xor'ами регистры процессора не использует
zagayevskiy
по факту, можно считать, что они уже там лежат
khim
Именно так. Три PXOR'а займут столько же времени, что и три MOVAPS, но вам не потребуется дополнительный регистр.
А ответы типа вот этого — это просто праздник какой-то: одной тривиальной задачки достаточно чтобы понять, что человек неадекватен. Это ли не счастье для интервьюера?
vesper-bot
Насчет ответа — такой ответ означает, что у вас на интервью не системный программист, а математик. Математики тоже нужны, но в других местах обычно. А ещё он прав изначально — очень много допущений возможно в задаче. Их надо разбирать прямо на интервью, причем интервьюер должен это уметь, иначе даже хороший программист не пройдет такое интервью.
khim
Кто-нибудь видел в XXI веке компьютеры с другой логикой?
Ну да — это такой способ экономии регистра при кодогенерации. Но так ли это важно? Того, что написано в условии — достаточно.
Обращение в память в современной архитектуре — выполняются медленнее, чем вычисления. Задержка даже пре обращении в L1 кеш — 4-5 циклов, вычисления же делаются за 0.25-0.5 цикла. И то и другое, конечно, накладывается на разные другие эффекты, так что всё не так однозначно — но сходу заявлять что эти алгоритмы «никуда не годятся» нельзя, они реально используются на практике даже сейчас.
Вот как раз для BigInteger этого делать не нужно, так как «удава можно перемещать по частям»
Вот это — просто шик-блеск. Да, это аргумент. Для компьютеров 70х-80х годов. Современные же архитектуры (SSE, NEON) позволяют смотреть на одни и те же регистры либо как на состоящие из целых чисел (сторого говоря PXOR/VEOR рассматривают регистры просто как последовательность битов, не вдаваясь в детали о том, что там такое внутри).
oleg_gf
А в чём проблема третью задачу решить в стиле:
function (a,b) {
return b,a;
}
Scf
Можно и так, но неспортивно же
oleg_gf
Почему неспортивно? Ограничение же на способы решения было только одно.
rzykov
Третью задачу можно решить на ассемблере через стек :-) Push a, pop b
gbg
А место, скушанное в стеке, у вас переменной не считается? А зря. И потом, значения нужно обменять, а вы B затерли значением из A. Нужно что-то вроде
push ax
push bx
pop ax
pop bx
alexeykuzmin0
Тогда уж проще через регистры
mov eax, a
mov edx, b
mov b, eax
mov a, edx
Причем если смотреть на быстродействие, то у нас самая затратная операция — это общение с памятью. Этих самых пересылок, если не оптимизировать, здесь 4, в классическом трехпеременном варианте — 6, а в двухпеременном — 9.
Ravager
задачки легкие, решаются быстро.
у меня вот недавно на собеседовании спросили задачку отсортировать inplace последовательность целых чисел(числа могут повторяться) быстрее чем nlogn.
короче за 1.5 часа я изобрел сортировку подсчетом, при том что принцип я не помнил практически. и мне абсолютно не помогали.
несмотря на правильное решение меня не взяли, но это уже другая история…
wataru
Сортировка подсчетом inplace? Это как?
Ravager
вначале точно также, высчитывается массив counters. затем делается проход и суммирование предыдущих элементов — по итогу в массиве counters позиции на которой должен оказаться i элемент в итоговом массиве. дальше цикл по исходному массиву: берется i элемент, в массиве counters берется его позиция m. i элемент меняется местами с элементом стоящим на позиции m. после этого элемент стоящий на i позиции стоит возможно не на своем месте. для него применяется такая-же история. если все ок, то i++
wataru
Дак как оно inplace когда целый массив counters создается? В таком виде вторую часть можно упростить — не надо никаких элементов менять местами — просто можно перезаписать массив нужными числами. Число i записывается на позиции counters[i-1]+1..counters[i],
Ravager
да, не совсем inplace. нужна память для диапазона значений, но считается что диапазон значений маленький по сравнению с входными данными. так что «почти inplace». вообщем неправильно так говорить, но на собесе кстати так и выдвинули мне «inplace». а потом оговорились что типа под такую структуру можно память выделить. крч бред)
по поводу перезаписывания — не пойдет. ибо там массив не просто чисел а структура, по полю которого нужно сортировать
Ravager
примерно так. там надо еще подшаманить для одинаковых чисел — сделать декремент counters
klirichek
"Сложная" задача про кувшин в чуть другой формулировке (ведро и банка там кажется были) была в советском учебнике по математике, кажется, за 5-й класс. Причём просто задача, не "со звёздочкой".
iig
Кстати, интересно, есть ли математический аппарат для решения подобного класса задач? Можно ли без интуиции и brutforce определить, что задача с N числами имеет 0 (1, X) решений?
TimeCoder
Хочу отметить (но не хочу обидеть автора статьи), что в современных программистских реалиях эти задачи — тривиальны. У меня ушло порядка 5 секунд на решение каждой, и если пойти на собеседование в компанию «любителей задач», таких как Яндекс и Мейл, то задачи оттуда — на порядок сложнее.
Мне очень понравилась задача (не из этих 2-х компаний), которая, на мой взгляд, тоже простая математически, но очень хорошо проверяет тип мышления. Если он «программистский» — человек решит задачу быстро. Вот задача: в ящик положили бактерию, через минуту их стало 2, через минуту 4 и так далее. Один раз в минуту каждая бактерия делится на 2. Чтобы заполнить ящик им нужен час. За сколько они заполнят ящик, если положить в него изначально 2, а не 1 бактерию?
Arastas
59 минут? В чём тут суть "программисткого" мышления?
TimeCoder
В том, что люди, далекие от программирования, пытаясь решить задачу в лоб, часто дают ответ «30 минут» (мол, ну а как, ведь в 2 раза больше бактерий изначально!). А если в голове сидит понимание, как работает цикл, то человек сразу же понимает, что условия задачи идентичны второй итерации цикла. Чисто мое imho.
alex4321
Ну как бы циклы тут не нужны. Оперируем степенями/логарифмами же :-)
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
Но это такое себе, да :-)
iig
Аналитичекое решение выглядит своеобразно ;)
Между состояниями "2 бактерии" и "1 бактерия" — 1 минута. 60-1 = 59.
alex4321
И то верно. Тем более, что уже присутствует оговорка о том, что через минуту их будет 2.
alexeykuzmin0
Поэтому лучше формулировать задачу иначе: "… Для решения проблемы перенаселения бактерии нашли еще три точно таких же ящика. На сколько им их хватит?"
iig
По той же схеме, через 60 мин их будет 1 ящик, +1 мин — 2 ящика, +2мин — 4 ящика.
demser
Можно изменить первую задачу так: дана последовательность степеней двойки -1,2,4,8,16,32,64,...,n (Последовательность ограничена сверху, т.е. существует число n, такое что все остальные члены последовательности меньше этого числа n). Из этой последовательности убрали одно число, а оставшиеся числа сложили. Зная сумму (например, 95), найти удалённое число.
zzmaster
В условиях второй задачи нет ограничений на силу тяжести. Предположим, что мы находимся в невесомости ))
Аккуратно выливаем содержимое 5-литрового кувшина в пространство. Зачерпываем из этой капли 3 литра, получам в остатке 2. Повторяем операцию. Объединяем остатки. Готово.
Pusk1
1 -я задача для школьника шестого класса.
2-я на состав числа — для начальной школы. Сыну давал в 6 лет. Справился.
3-я для тех, кто изучает арифметические операции и не раз мне попадалась в различных учебниках. За красивый вариант с XOR спасибо.
muradovm
Вторая задача скорее на знание математики. Решается теоремой Безу.
5*2 — 3*2 = 4