Мы отобрали для Вас несколько интересных вопросов и алгоритмических задач, задаваемых на собеседованиях в Luxoft.
При устройстве на работу в Luxoft, соискателям чаще задаются вопросы технического характера, например, для проверки уровня владения технологией. Но тем не менее, встречаются и вопросы, связанные с логикой, и алгоритмические задачи. Ниже приведены наиболее интересные из них, среди которых мы постарались выбрать вопросы различного уровня сложности.
Ответы будут даны в течение следующей недели — успейте решить. Удачи!
При устройстве на работу в Luxoft, соискателям чаще задаются вопросы технического характера, например, для проверки уровня владения технологией. Но тем не менее, встречаются и вопросы, связанные с логикой, и алгоритмические задачи. Ниже приведены наиболее интересные из них, среди которых мы постарались выбрать вопросы различного уровня сложности.
Вопросы
- 3 Travellers crossing the river
Three travellers need to cross a river. Each traveller has certain amount of gold coins kept in his bag.
Traveller A has 1000 gold coins
Traveller B has 700 gold coins
Traveller C has 300 gold coins
To cross the river there is a boat which can carry a maximum of two objects at a time that means either a maximum of two travellers can cross the river or a traveller with a bag can cross the river. The problem is that in this process of crossing the river if a traveller is left with an amount of coins more than his own then he will run away with that. The same rule applies for two travellers, if they are left with a total of more than their cumulative gold coins then they will run away with that money.
What strategy will ensure that they all cross the river properly ?ПереводТрём путешественникам нужно пересечь реку. У каждого из них определенное количество золотых монет в рюкзаке.
Путешественник А имеет 1000 монет
Путешественник B имеет 700 монет
Путешественник C имеет 300 монет
Для пересечения реки есть лодка, которая может вместить максимум 2 объекта — двух путешественников или путешественника с рюкзаком. Проблема заключается в том, что если оставить любого путешественника с количеством золота, превышающим его собственное — он сбежит, прихватив все деньги. То же касается и двух путешественников, если они останутся с золотом, превышающим их суммарные запасы — они убегут с золотом.
Какая стратегия позволит всем пересечь реку и остаться при деньгах?
- Heavy rock in the boat
You are in a rowing boat on a lake. A large heavy rock is also in the boat. You heave the rock overboard. It sinks to the bottom of the lake. What happens to the water level in the lake? Does it rise, fall or stay the same?
ПереводВы находитесь в гребной лодке посреди озера. В лодке также лежит тяжёлый камень. Вы с усилием поднимаете камень и выбрасываете за борт, в результате чего, камень уходит на дно озера. Что произойдёт с уровнем воды в озере? Он поднимется, опустится или останется таким же?
Задачи
- Multiple of 3
Write an efficient method to check if a number is multiple of 3.
ПереводНапишите эффективную программу для проверки, является ли число произведением тройки.
- Write a quine
A quine is a program which prints a copy of its own as the only output. A quine takes no input. You are not allowed to use, open and then print file of the program. Quines are named after the American mathematician and logician Willard Van Orman Quine (1908–2000).
ПереводНапишите куайн — программу, которая печатает на вывод свой исходный код. Куайн не принимает никаких входных данных. Вам не разрешено использовать файл, а потом выводить его содержимое. Куйан назван в честь американского математика и логика Уилларда Ван Ормана Куайна (1908-2000).
- Min/Max without branching
On some rare machines where branching is expensive, the below obvious approach to find minimum can be slow as it uses branching.
/* The obvious approach to find minimum (involves branching) */ int min(int x, int y) { return (x < y) ? x : y }
Write a program to find the minimum of two integers without branching.
ПереводНа некоторых машинах, где ветвление является дорогим, следующий подход для нахождения минимума будет медленным:
/* The obvious approach to find minimum (involves branching) */ int min(int x, int y) { return (x < y) ? x : y }
Напишите программу для нахождения минимума из двух чисел, не используя ветвление.
Ответы будут даны в течение следующей недели — успейте решить. Удачи!
Andy_U
Вопрос N2:
Ответ: Уровень воды уменьшится.
1) Как легко понять, неважно, где камень, в лодке на дне или привязан за веревку и находится полностью в воде. Ну, заменим камень песком или тяжелой жидкостью...
2) Т.е. если утопить камень (или перерезать веревку) сумма объема воды в озере плюс объем камня не изменится.
3) Но лодка всплывет.
4) Значит уровень воды упадет.
Segrio
Я бы сказал ваше объяснение для меня не совсем ясное. Я понимаю это так:
— камень в лодке на плаву, значит вытеснен объем воды по массе равный массе камня;
— камень на дне, значит вытеснен объем самого камня.
Из того, что плотность камня больше плотности воды (камень тонет), следует, что при одинаковой массе вода имеет больший объем чем камень.
Те. V_озера+V_воды_массой_камня > V_озера+V_камня.
Andy_U
Ну, конечная формула, очевидно, та же самая, что у меня. Только я совсем без формул и упоминания закона Архимеда в объяснении обошелся.
P.S. У меня может быть не совсем понятен только первый пункт. Ну, могу подробнее. Считаем лодку плоскодонкой. Далее давайте условно расплавим камень, потом, сделаем поверх новое дно лодки а низ отрежем — пусть тонет. Понятно, что мы имеем право считать дно лодки невесомым — неважно, где вес сосредоточен.
yellow79
Задача 1
Путешественник А перевозит все деньги на другой берег. Далее перевозит путешественника Б, но на обратном пути забирает свою тысячу. Забирает путешественника C, оставив свою тысячу на изначальном берегу, после возвращается за ними.
Andy_U
И сбегает с ними…
yellow79
с какого перепуга? согласно условий он сбегает если сумма чужих денег выше чем у него, а в данном случае получится сумма равна
Andy_U
Все деньги, это 1000+700+300? Или таки только свои?
yellow79
да, все две тысячи постепенно перевезти на другую сторону, согласно условия задачи
он не сбежит, так как количество чужого золота не превышает его собственное
Andy_U
Про «постепенно»… Я спрашивал про первый ход.
Dimenko
согласно условиЮ
Andy_U
Нет. См. условие задачи. Он сбегает, как только он остается наедине с суммой, большей, чем у него было изначально:
ITMatika
Multiple of 3
Не совсем понятно условие.
Если число представлено в десятичной записи, то достаточно проверить сумму его цифр на делимость на 3.
reci Автор
Да, число вводится в десятичной записи.
Andy_U
Как строка?
reci Автор
Думаю, как int
Andy_U
Тогда оно окажется в системе счисления компьютера, и школьное правило окажется неэффективным, поскольку потребует предварительного перевода N-ричного числа в десятичную систему счисления.
ITMatika
да, как строка, и тогда можно работать с ооооооооооооооооооочень длинной арифметикой )
Andy_U
Задача N3:
Если число десятичное, то школьное правило, если троичное, то ноль в конце, если шестнадцатеричное, то поскольку 16^N mod 3 == 1, то тоже самое школьное правило, для прочих систем счисления тоже можно найти подобные правила (типа как для двоичной — см. google):
На самом деле последовательность вида M^k mod 3, k=1,2,3… где M — основание системы счисления бывает, вроде бы, всего лишь трех типов:
0, 0, 0, 0,…
1, 1, 1, 1…
1, 2, 1, 2,… (или с двойки начинается).
Если первый вариант, то систем «троичная» и надо, чтобы был ноль в конце. Если второй — то «школьное» правило, а вот если третий вариант, то тот же способ, что и для двоичной системы — надо, что бы сумма цифр, стоящих на четных местах, минус сумма, стоящих на нечетных, делилась на три.
A вот если N число задано, например, последовательностью из N единиц, а потом нулем, и неизвестно, на какой системе счисления основан компьютер (или даже просто неизвестно про систему счисления — ну, типа в римских числах), то все становится интереснее.
smer44
первая задача:
Обозначение: берег — {лодка} --> берег
B,C, 1000 — {A,1000} --->> 0
B,C, 1000 << — {A} — 1000
A, 1000 — { B,C} --->> 1000
A, 1000 << — {C, 300} — B, 700
C, 300 — {A,1000} -->> B, 700
C, 300 << — {B, 700} — A, 1000
1000 — {B,C} --->> A, 1000
1000 << — {A} — B,C, 1000
0 — {A, 1000} -->> B,C, 1000
Минимум без условий:
min = (a + b – (a – b) & 0x7FFFFFFF) / 2
Задача про деление на три: если разница между суммой четных и нечетных битов делится на три. Сумму считаем примерно как в классическом примере о подсчёте битов.
Разница может быть только меньше 16 для x32 числа и меньше 32 для x64 числа, поэтому для неё можно сделать лукап- таблицу.
попозже может мину исходники: дерево решений для первой и код для других задач.
smer44
vesper-bot
В этом случае А едет с двумя мешками на первом или на последнем ходу. То есть в лодку не влезет.
Rsa97
2. Туда: B + C, обратно B + 700
3. Туда: A + 1000, обратно C + 300
4. Туда: B + C, обратно A
5. Туда: A + 1000
ITMatika
Multiple of 3 решена неверно )
Rsa97
Да, пока модерация шла, я уже сам понял.
}
ITMatika
Подумайте ещё )
ITMatika
Пардон, не разглядел приведение модуля, вот теперь похоже не правду )
IIvana
r = (a+b-abs(a-b))/2;надеюсь взятие модуля числа и деление на 2 сдвигом недороги на неуказанной абстрактной платформе, где будет исполняться кот
smer44
в предполагаемой платтформе, взятие модуля числа будет либо операцией с условием либо каким то числовым трюком как в моём ответе
IIvana
зависит от представления отрицательных чисел — в обратном, дополнительном до 1 или дополнительном до 2 коде. где-то достаточно просто занулить знаковый бит по И по маске, где-то просто прибавить максимальное число разрядной сетки умноженное на знаковый бит, сдвинутый вправо на ту же величину разрядной сетки — получается мы прибавляем макс_сигнед_инт умноженный на 1 если число отрицательное и на 0 если положительное — и получаем модуль числа.
но это уже детали реализации. стравлю 200 денег, что составители задачи хотели увидеть именно такое решение, как написано выше
71rmn
примерно так:
int[3] a={y,y,x};
int i=sign(x-y);
return a[i+1];
IIvana
Отлично. Сигн по знаковому биту, выделенному маской и сдвинутому в 0 позицию даже проще чем модуль.
IIvana
del
IIvana
Вопрос 2 — на физфаке нас учили проверять формулы и модели устремляя какие-либо величины к крайним значениям. Допустим, у нас камень из страшного вещества с огромной плотностью, диаметром сантиметр и массой тонну. Пока он лежит в лодке — лодка сильно погружена в воду и вытесняет существенный объем. Когда мы выкинем камень, его объем почти не скажется на результате, за то лодка существенно поднимается и уровень воды опустится. Варианты когда плотность камня меньше плотности воды или воздуха рассматривать лень — думаю ответа выше вполне достаточно.
ViViVi
Камень плотность которого меньше воздуха — взлетит), камень плотность которого меньше воды — всплывет)). За условием задачи камень упал на дно — значит его плотность больше плотности воды.
IIvana
Его можно силой затащить на дно, привязав веревкой к коряге )) И тогда уровень воды поднимется — по той же логике крайних значений — представьте что вы везли в лодке огромный воздушный шар )) И это стройно укладывается в модель — при плотности камня больше плотности воды уровень опустится, при меньше — поднимется. А если камень деревянный, и не затаскивать его на дно, а позволить плавать свободно после выкидывания за борт — то вангую что уровень не изменится — но надо аккуратнее разобрать этот вариант для уверенности )
andyudol
В исходной ситуации суммарный вес камня и лодки скомпенсирован весом вытесненной ими воды. После потопления камня — нет. То есть вес вытесненной воды стал меньше суммарного веса лодки и камня. Так как трудно себе представить, что при потоплении камня удельный вес воды изменяется, то уменьшение веса вытесненной воды может произойти только за счёт уменьшения её объёма. Следовательно, уровень упадёт.
А если камень плавучий, то действительно не изменится.
IIvana
Квайн:
1проверяется в любом РЕПЛе
я не думаю, что составители задачи будут в восторге от такого ответа, но квайнопись сильно зависит от языка — а он не был озвучен. Или это интервью в ту компанию, где кроме С языков не знают? ))
qw1
Для интерпретируемых языков самый простой квайн — пустой файл.
andyudol
#! /bin/more
Дальше что угодно.
Nick_mentat
-2 уезжает со своими 700 и оставляет там, возвращаясь
-3 берёт 300 и отвозит на тот берег, возвращается (ведь у него и своих столько же)
-отбывают 1 и 2, кто-то из них возвращается со своим, чтобы его место на том берегу занял 3 (со своим)
-отбывает второй со своим, теперь оба переезжают без мешков, все три путника на другом берегу
-3 плывёт назад за 700 и возвращается
-1 плывёт назад за 300 и возвращается