Продолжение поиска работы

В понедельник был ещё одно собеседование. По сложности - примерно такое же, как в пятницу. Два часа к ряду мурыжили по техническим вопросам. Причём спрашивали не только по .Net, но и по C++, на котором я не писал уже года три, и по программированию под Винды. Как ни странно, знания, почерпнутые из ряда книжек по C++ и Виндам, прочитанных в глубоком детстве (лет десять назад), не выветрились полностью, и на вопросы удавалось более-менее осмысленно отвечать.

На этом интервью мне впервые в жизни давали решать головоломки! Я про такое конечно не раз слышал - что дают на собеседовании всякие отвлечённые задачки, не имеющие прямого отношения к программированию. В частности, славятся этим компании Microsoft и Google. Но на практике с таким подходом пришлось столкнуться впервые. Было три головоломки:

1) В стакан кладут амёбу. За одну секунду амёба делится на две точно такие же амёбы. Полностью стакан наполняется амёбами за один час. За какое время наполнится стакан если в него положить две амёбы?

2) Имеется лифт в десятиэтажном доме. Какова вероятность того, что когда человек заходит в дом, лифт оказывается на первом этаже?

3) Имеется стоэтажный небоскрёб. Также имеются два одинаковых стеклянных шара. Шар разбивается если его кидают с высоты, однако пороговое значение, с которой шар начинает разбиваться, не известно. Имея только два этих шара определить, начиная с какого этажа шары разбиваются. Найти самое быстрое решение.

Ответы - через два дня.

test


test

spolier: (press page down :) )


































1. 3599 c.
2. 0.5, наверное
3. начинать со второго, и идти вверх через один

1. Согласен
2. Зависит от времени суток :)
3. Такой ответ очевиден... Но самый ли это быстрый способ? Надо будет подумать.


P.S. Снова читал Виталика... Много думал...

Комментарий к 1. Пока нет комментариев.
Комментарий к 2. Считать, что от времени суток не зависит.
Комментарий к 3. Способ не самый быстрый. Есть ещё быстрее.

Виталик, ты же сказал, что не знаешь ответа на третий вопрос?
Мой вариант - достаточно 15 попыток (алгоритм не тот, который я предлагал вначале). Меньше пока не получается

14 попыток...
В общем на N этажное здание потребуется <= sqrt(2*N) попыток.

Основываясь на своём житейском опыте могу сказать, что вероятность того, что лифт окажется на первом этаже очень высокая, процентов 25-30.
Живя в Питере в девятиэтажном доме, частенько заставала лифт на первом этаже. А если наоборот нужно спуститься вниз, то вызваный лифт часто тащится наверх очень долго, не иначе как опять же с первого этажа.( Василий Иванович, сколько будет 0,5 + 0,5? Петька, нутром чувствую что литр, а доказать не могу.)

Виталик, гони ответы :) общественность волнуется. Товарищу AlexP — респект. Я, конечно, эти шарики нагуглил за 5 минут, но придумать такое самому — это круто.

Как было обещено - ответы.

1. 3559 секунд. Для проверки можно нарисовать модель не бумажке.

2. 50%. Все события, изменяющие положение лифта, делятся на те, которые перемещают его на первый этаж, и те, которые перемещают его не на первый этаж (так как люди либо выходят из дома, либо идут домой). Если откинуть суточные изменения характера перемещений лифта, то вероятность получается 50%.

3. Кидаем с 10 этажа. Если разбился кидаем с 1 до 9. Где разбился - там порог разбивания. Если на 10 не разбился, кидаем с 20. Если на 20 разбился кидаем с 11 до 19. Где разбился - там порог разбивания. Ну и так далее. В худшем случае получается 19 бросков. Про вариант с 14 бросками расскажет автор (если захочет).

1 и 2 — "так я и думал" :) 3 — и ты прав, и AlexP. Но у него алгоритм, очевидно, эффективнее. Хотя и похож — разница в том, что изначально бросается с 14-го этажа, потом с 27-го, потом с 39-го. В результате количество бросков никогда не превышает 14.

На счёт второго ответа не согласна. Люди часто ездят в лифте в гости к соседям, а у нас в доме почтовые ящики находятся на втором этаже, так многие жильцы или за почтой едут на второй этаж и обратно домой, или едут до второго, заберают почту и спускаются пешком до первого. В итоге лифт остаётся на 2-м этаже. К нашему дому эта задача не подходит.

Поправка - на первую задачу ответ 3599 секунд, а не 3559. Короче 59 минут 59 секунд. Очепятка.

Анюта, ты права, если учитывать поездки к почтовому ящику и друг к другу в гости, то ответ будет другим. Но в данном случае этим принебергаем. Собственно, этот момента, а также то, влияет ли время суток на ответ - это то, что можно и нужно уточнять у задающего. Если в условии задачи про это сказать, то ответ станет слишком очевидным.

На книжной полке рядом стоят два тома Пушкина: первый и второй. Страницы каждого тома имеют вместе толщину 2 см, а обложка - каждая - 2 мм. Червь прогрыз (перпендикулярно страницам) от первой страницы первого тома до последней страницы второго тома. Какой путь он прогрыз?

только без гугла, задачка для детей от 5 лет.

Я бы сказал, 4 мм. Correct?

yes )

Ну слава богу, хоть задачки для детей от пяти лет решаю. :)))

Ты в пустыне и не знаешь куда идти. Встречаешь старика и он тебе говорит, что в одну сторону оазис, в другую бесконечные пески. Он знает куда идти, но ты можешь задать ему всего один вопрос. При этом он в один день всегда говорит правду, а в другой всегда врёт. Какой вопрос ты ему задашь, чтобы узнать правильный путь?

В тёмной комнате стоит стол, на котором лежат монеты — 5 вверх решкой и 8 орлом. Нужно разделить их на 2 кучки таким образом, чтобы в каждой оказалось одинаковое количество монет решкой вверх. Монетки можно переворачивать. Напоминаю: всё происходит в полной темноте.

Правда, я сам #17 и #18 пока решать не пробовал и даже не знаю, осмысленные ли эти задачи и имеют ли они решение.