Задачи на собеседовании в одну небезызвестную контору

[CDR]

Задачки, которые были предложены одному моему знакомому, работающему за бугром, на собеседовании в Google .

Чувак в автобусе.
На остановке в ожидании 71-местного автобуса стоит 71 пассажир. У каждого из пассажиров есть билетик с номером места, которое ему необходимо занять при посадке в автобус. Для простоты пусть номер пассажира в очереди равен номеру его места в автобусе (1-ый чел должен занять место №1, 2-ой - №2, ... 71-ый - место №71 ). Однако первый стоящий в очереди пассажир - чувак, и при посадке в автобус он плюхается в кресло, которое ему понравилось больше всего (случайным образом от 1 до 71). Какова вероятность того, что последний (71-ый) пассажир займет свое (71-ое) место?
UPDATED: Упустил предложение, что каждый последующий пассажир, после первого, садится на свое место, если оно не занято, в противном случае ему достается случайное место из свободных.

100 лампочек.
На длинном щитке сигнализации в ряд вкручены 100 изначально выключенных лампочек. Охранник делает 100 обходов мимо этого щитка каждый раз в одном и том же направлении. В процессе каждого обхода охранник переключает (включает, если лампочка выключена; и выключает, если включена) определенные лампочки. При первом обходе переключаются все лампочки, при втором - каждая вторая (2, 4, 6, 8 ... 98, 100), при третьем - каждая третья (3, 6, 9 ... 96, 99) и т.д. Какие лампочки будут включены после того, как охранник завершит все обходы?

Краско.
Есть две бочки с одинаковым объемом краски в каждой из них. В первой находится синяя краска, во второй - красная. Из первой бочки во вторую перелили какое-то количество синей краски, перемешали ее с красной, а за тем это же количество полученной смеси перелили обратно в первую бочку. Чего оказалось больше: в первой бочке красной краски или во второй бочке синей?

Четыре беглеца.
Под покровом ночи 4 беглеца, спасаясь от погони, оказались на краю пропасти. Для окончательного спасения им осталось по натянутому веревочному мостику перебраться на противоположный край пропасти. Для этого у них есть всего 17 минут и один фонарик, который обязательно нужно иметь при себе при переходе по мостику, чтобы не оступиться и не упасть. Первый беглец может перебраться по мостику на противоположный край за 1 минуту, 2-ой - за 2 мин, 3-ий за 5, 4-ый - за 10. Одновременно мостик может выдержать не более двух беглецов. При этом если по мостику начнут перебираться два человека, они смогут двигаться лишь со скоростью самого медленного из них двоих. Как бедолагам уложиться в 17 минут?

Зеркало.
Почему у отражения в зеркале меняется местами только левая и правая сторона, а верх и низ остаются на своих местах?

Написать программулину.
Есть массив из n различных элементов. Необходимо вывести все перестановки этих элементов. Допускается использование не более одного вложенного цикла.
Например, n = 3. Соответственно, массив может иметь вид [a, b, c]. Необходимо вывести следующие варианты:

[a, b, c]
[a, c, b]
[b, a, c]
[b, c, a]
[c, a, b]
[c, b, a]

ПС: вложенный цикл - цикл, выполняющийся внутри другого цикла.

Предложенные задачки предлагают решить в течение полутора часов...
Я вот только на написание программки потратил почти полдня

[ice]

это на какую вакансию? программиста? если да, то вполне логичные задачки на знание математики

[e@gle]

Краско. Во во второй бочке синей краски больше. Т.к. синию добавляли концентрат, а красную - уже смесь.
Четыре беглеца. 1 и 2 вперед, 2 назад, 3 и 4 вперед, 1 назад, 1 и 2 вперед.
Зеркало. Потому, что право и лево меряются относительно человека. А верх и низ - относительно земли. Так например, если в зеркале смотреть не левую-правую стороны, а восточную-западную, то ничего не меняется.

[Milk]

Цитата:

Сообщение от CDR

Например n = 3. Соответственно массив может иметь вид [a, b, c]. Необходимо вывести следующие сочетания
[a, b, c]
[a, c, b]
[b, a, c]
[b, c, a]
[c, a, b]
[c, b, a]

Строго говоря, это ни разу не сочетания. Это перестановки. Хорошо, что привели пример С сочетаниями это, кажется, невозможно

[CDR]

Цитата:

Сообщение от ice

это на какую вакансию? программиста? если да, то вполне логичные задачки на знание математики

Вакансия senior developer или че-то вроде того. А задачки не на знание математики, для их решения вполне хватит уровня пятого класса.

Скорее на логику... или даже больше на сообразительность, что-ли ...

[CDR]

Цитата:

Сообщение от Milk

Строго говоря, это ни разу не сочетания. Это перестановки. Хорошо, что привели пример С сочетаниями это, кажется, невозможно

Трудности перевода .
Спасибо за замечание, уже исправил в первом посте.

[oip]

Цитата:

Сообщение от e@gle

Краско. Во во второй бочке синей краски больше. Т.к. синию добавляли концентрат, а красную - уже смесь.

Уверены?

[kashperuk]

Цитата:

Сообщение от e@gle

Краско. Во во второй бочке синей краски больше. Т.к. синию добавляли концентрат, а красную - уже смесь.

Я что-то тут высчитывал, и у меня получилось, что получится одинаково, в пропорции 2:5 в каждой бочке (разной краски, разумеется).

[kashperuk]

А для программы рекурсию использовать можно?

[belugin]

Цитата:

Сообщение от kashperuk

Я что-то тут высчитывал, и у меня получилось, что получится одинаково, в пропорции 2:5 в каждой бочке (разной краски, разумеется).

соотношение непонятно откуда взялось (понятно, что если вторую бочку перелисть в перыую целиком то будет смесь 1:1 в обеих). У меня получается

объемВзятого - (объемВзятого / объем1бочки) = объемВзятого * (1 - 1 / объем1бочки)

[CDR]

Цитата:

Сообщение от kashperuk

Я что-то тут высчитывал, и у меня получилось, что получится одинаково, в пропорции 2:5 в каждой бочке (разной краски, разумеется).

Цитата:

Сообщение от belugin

соотношение непонятно откуда взялось (понятно, что если вторую бочку перелисть в перыую целиком то будет смесь 1:1 в обеих). У меня получается

объемВзятого - (объемВзятого / объем1бочки) = объемВзятого * (1 - 1 / объем1бочки)

С краской все довольно просто получается.
Допустим из первой бочки взяли X синей краски и вылили ее во вторую. Из второй бочки взяли тот же объем X, но уже смеси синей и красной краски. Предположим, что в этом объеме X находится Y красной краски, тогда синей краски в этом объеме смеси будет (X-Y). Этот объем синей краски попадет обратно в первую бочку. Тогда во второй бочке синей краски из начального объема X останется X - (X - Y) = Y.
Таким вот не хитрым образом получаем, что во второй бочке синей краски находится столько же, сколько в первой красной краски.

[CDR]

Цитата:

Сообщение от kashperuk

А для программы рекурсию использовать можно?

Рекурсию использовать можно. Главное следить за тем, что бы рекурсия не привела к образованию вложенных циклов .

Для всех задачек найдены решения... Как я и писал, решения всех задач не требуют глубоких знаний математики, достаточно знаний на уровне пятого класса.
Пожалуй, программка оказалась самым сложным заданием

[Михаил Андреев]

Про краску задачка понравилась. Сначала я тоже подумал сделать вычисления. Потом сообразил, что считать вообще ничего не надо. Как ни перемешивай, ответ один

[belugin]

Цитата:

Сообщение от CDR

Рекурсию использовать можно. Главное следить за тем, что бы рекурсия не привела к образованию вложенных циклов .

Любой цикл можно переписать как рекурсию. Есть языки вообще без циклов

[CDR]

Цитата:

Сообщение от belugin

Любой цикл можно переписать как рекурсию. Есть языки вообще без циклов

В таком случае, предлагаю Вам "порвать гугл" и решить эту задачу не используя циклы вообще .

[MikeR]

Цитата:

Сообщение от belugin

соотношение непонятно откуда взялось (понятно, что если вторую бочку перелисть в перыую целиком то будет смесь 1:1 в обеих). У меня получается

объемВзятого - (объемВзятого / объем1бочки) = объемВзятого * (1 - 1 / объем1бочки)

Хм, а мне подумалось, что недаром же написано про краску. Вязкость и так все дела...
С точки зрения физики прав e@gle.
А вот если бы написали про жидкость, тогда имело бы смысл и формулы брать.

Цитата:

Сообщение от e@gle

Зеркало. Потому, что право и лево меряются относительно человека. А верх и низ - относительно земли. Так например, если в зеркале смотреть не левую-правую стороны, а восточную-западную, то ничего не меняется.

Много раз об этой задаче слышу. Здесь все ж таки специфика обработки информаций мозгом. Расположение глаз идет по горизонтали, а не как по вертикали. Чего то сразу представил человека с глазами по вертикали. ЖУТЬ!

[Михаил Андреев]

Цитата:

Сообщение от MikeR

Хм, а мне подумалось, что недаром же написано про краску. Вязкость и так все дела...

Цитата:

Краско. Во во второй бочке синей краски больше. Т.к. синию добавляли концентрат, а красную - уже смесь.

С точки зрения физики прав e@gle.
А вот если бы написали про жидкость, тогда имело бы смысл и формулы брать.

"Ну, вы, блин, даёте" (С) "Особенности национальной охоты"

И что, от переливания и смешивания стало больше краски суммарно? Ну-ну. Ломоносов бы в гробу перевернулся

[Vals]

Цитата:

Расположение глаз идет по горизонтали, а не как по вертикали. Чего то сразу представил человека с глазами по вертикали. ЖУТЬ!

Есть описанный физиологический опыт, в котором испытуемому на глаза надевают очки, переворачивающие картинку. В итоге, человек действительно видит всё "вверх ногами", но через некоторое время, происходит адаптация и все объекты снова видны в их настоящем положении.

[CDR]

Цитата:

Сообщение от MikeR

Много раз об этой задаче слышу. Здесь все ж таки специфика обработки информаций мозгом. Расположение глаз идет по горизонтали, а не как по вертикали. Чего то сразу представил человека с глазами по вертикали. ЖУТЬ!

Исходя из вашей логики, если закрыть один глаз, то в зеркале вместо левой и правой стороны поменяются верх и низ?

[Михаил Андреев]

Цитата:

Сообщение от CDR

Исходя из вашей логики, если закрыть один глаз, то в зеркале вместо левой и правой стороны поменяются верх и низ?

М-да. Я тоже посмеялся
Ну, кто же виноват в том, что человек симметричен относительно вертикальной плоскости?