Логические вопросы на собесах

8 монет. Одна фальшивая (она легче)…

В классике там 9 монеток. Но гораздо веселее - 1 из 12ти, и неизвестно фальшивая легче или тяжелее.

В классике там 9 монеток

С 9ю же фокус с двумя взвешиваниями не пройдет.

Тут весь кайф в двоичной vs троичной логике же. Биты vs триты.

С 9ю же фокус с двумя взвешиваниями не пройдет.

?? Шутите?

Вообще-то нет.

Ладно, подумаю. Может и вру. Вот так с разбегу - не находится схема на два взвешивания.

Всё, дошло.

Да ладно: 9 == 3 ^ 2, и это предел для 2х взвешиваний. Вы наверное решили что там 2 ^ 3.

Но Вы подумайте про вариант с 12ю - там реально есть над чем пошевелить мозгами…

ПыСы. А по поводу часов - мне очень нравится задачка которая на самом деле породила целый класс себе подобных. Нравится простотой формулировки, но честное аналитическое решение там совсем зубодробительное. Итак: какова вероятность посмотрев на наручные часы с плавным ходом 3х стрелок (часовая, минутная, секундная) обнаружить секундную ближе к часовой чем к минутной. Это не для интервью, очевидно - в лучшем случае можно поинтересоваться в какую сторону будет отклонение от «ожидаемого».

Идиотизм, практиковавшийся гуглом 10 лет назад, дошел до считающих себя офигенно продвинутыми хрюнделей заборостроительных контор.

Жалкое зрелище, на самом деле.

Насчитал 11 раз за круг.

12 раз за первый круг, 11 за второй (начальная встреча в 0:00 считается, финальная встреча в 0:00 нет — она принадлежит следующему дню).

12 раз за первый круг, 11 за второй

Продолбался, но где? %)

Вот поэтому я и не люблю переборы по индексу — вечно то потеряешь один, то лишний приплетёшь.

Очевидно, никаких встреч между 0:00 и 1:01

Почему-то встречается еще вариант 37 (sic!)

Шутят так. 37 на все вопросы — это мем.

https://www.youtube.com/watch?v=d6iQrh2TK98

Но гораздо веселее - 1 из 12ти, и неизвестно фальшивая легче или тяжелее.

За сколько взвешиваний?

Вообще у меня так же получается 12 за первый, 11 за второй.

Первый круг:

1. 00:00
2. час с чем-то
3. два с чем-то
4. три с чем-то
5. четыре с чем-то
6. около пол-шестого
7. шесть с чем-то
8. семь с чем-то
9. восемь с чем-то
10. без чего-то десять
11. без чего-то одиннадцать
12. без секунды двенадцать

За второй круг 00:00 в начале не считаем, потому что после 12-го раза последнюю секунду стрелки не расходятся, а движутся вместе, поэтому получается 11, а не 12.

Получается 11+12 = 23 раза всего за сутки.

Насчитал 11 раз за круг. Следовательно - 22 раза за два круга.

За первый круг 12 раз, потому что мы ещё и 00:00 по идее считаем. Или это не считается «встретятся», когда они начинают с одной точки?

Короче, тут зависит то двух неопределённых вещей:

1. Что считается за «встретятся»
2. От какого момента мы считаем сутки.

Если «начать в одной и той же точке» ∈ «встретиться», а сутки начинаются с 00:00:00.000, то 23 раза.

Если не считается, то 22.

Если с любого другого времени, которое не является точкой встречи двух стрелок, отсчитываем сутки, то тоже 22.

Если «начать в одной и той же точке» ∈ «встретиться», а сутки начинаются с 00:00:00.000, то 23 раза.

Очевидно, сутки должны считаться полуоткрытым интервалом, иначе существует момент времени, для которого дата не определена.

Когда у меня были попытки войти в ойти ни разу не было. Но если бы были я бы завалил все гарантированно

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

Это не логическая задачка наверное, а просто прикладная штука. Но один фиг, обладая свойством тугодумия у меня ушло минут 20 из которых 10 минут я не понимал что не так задавая int j = 0, а не int j = i

#include <stdio.h>

int main(int argc, char *argv[])
{
    signed char input[] = {1,-5,2,-4,3,-2,4,5,6,-64,7,8,9,-12};
    int doits = 1;
    while(doits)
    {
        int found = 0;
        for (int i = 0; i != sizeof(input); ++i)
        {
            for (int j = i; j != sizeof(input); ++j)
            {
                if(input[i] < input[j] && input[i] < 0 && input[j] < 0)
                {
                    int buff = input[i];
                    input[i] = input[j];
                    input[j] = buff;
                    found = 1;
                }
            }
        }
        if(found == 0)
        {
            doits = 0;
        }
    }
    for (int i = 0; i < sizeof(input); ++i)
    {
        printf("%d ",input[i]);
    }
    puts("");
    return 0;
}

dron@gnu:~/Рабочий-стол$ ./a.out 
1 -2 2 -4 3 -5 4 5 6 -12 7 8 9 -64 
dron@gnu:~/Рабочий-стол$ 

Вот поэтому я и говорю всегда, уметь кое как кодить != быть программистом, как построивший сарай не является строителем, но нет ничего зазорного в том чтобы просто кодить, это своя стезя и в ней свои правила, а нее те что хотят головоохотники. Вот мне не суждено. Может и тебе =) Ищи места где не нужно программировать, но можно кодить. Где нет ААААААААА КРИТИЧЕСКАЯ БАГА В АЛГОРИТМЕ ШИФРОВАНИЯ, а типа, там подправить, тут добавить, здесь прикрутить и так далее. Или качайся дабы про вот такие задачи ты тупо знал заранее. Хотя где такое искать понятия не имею.

Это понятно, но я не об этом. Я о том, что если сутки начинаются в 00:00:00, то 23 раза, а если в случайное время (например в 13:30:54), то 22 раза.

В условии сказано «сколько раз за сутки», а «за сутки» — это интервал времени в 24 часа ровно. Не сказано, что это конкретно за календарные сутки, начинающиеся в полночь.

Но гораздо веселее - 1 из 12ти, и неизвестно фальшивая легче или тяжелее.

За сколько взвешиваний?

Если всё сделать по уму то можно вывернуться за 3 :)

Ужас, я вывернулся. Это тоже на собеседование задачка? Мне полчаса потребовалось.

Кстати, какая область математики занимается такими задачами в общем виде?

Если сутки начинаются в 00:00:00, то когда в следующий раз будет 00:00:00 — это будут другие сутки уже.

Во избежание недоразумений можно вычислить предел отношения f(n)/n, где f(n) — количество встреч за n суток, при n, стремящемся к бесконечности.

Если сутки начинаются в 00:00:00, то когда в следующий раз будет 00:00:00 — это будут другие сутки уже.

Только стрелки встретятся за несколько мгновений до этого — ещё в предыдущие сутки, а затем вместе сдвинутся в положение на 00:00:00, а соответственно, «встреча» будет ещё в предыдущие сутки. Время, когда стрелки «вместе» — не нулевое.

Во избежание недоразумений можно вычислить предел отношения f(n)/n, где f(n) — количество встреч за n суток, при n, стремящемся к бесконечности.

Ну тут очевидно, что 22.

Ужас, я вывернулся. Это тоже на собеседование задачка? Мне полчаса потребовалось.

Поздравляю :) Из того что я слышал - довольно умные люди решают её за 45 минут, «гении» - за 15. Так что Ваш результат очень достоен :)

Кстати, какая область математики занимается такими задачами в общем виде?

Врать не буду - я не математик. И область моих интересов лежит в сугубо прикладной плоскости. Мне просто нравятся подобного рода задачки, и я их коллекционирую (надо же мозги разминать, а то заржавеют) ;-)

Мне просто нравятся подобного рода задачки

Ну, раз такое дело.. на тебе:

«Дана окружность с центром. С помощью циркуля построить вершины вписанного в окружность квадрата.»

Если собеседующий адекватен, то важен не результат, а процесс.

(Ну и в оригинале спрашивается за какое минимальное количество взвешиваний это можно сделать, а не предлагается найти как сделать за N.)

Только стрелки встретятся за несколько мгновений до этого — ещё в предыдущие сутки, а затем вместе сдвинутся в положение на 00:00:00

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

В любом случае, задача для детей. Про монетки мне больше нравится :)

Из того что я слышал - довольно умные люди решают её за 45 минут, «гении» - за 15.

Это скорее всего байки из разряда «только 2% могут решить головоломку Эйнштейна».

Ну и в оригинале спрашивается за какое минимальное количество взвешиваний это можно сделать, а не предлагается найти как сделать за N.

Это же вообще жуть. Я бы остановился на четырёх, если бы дело было на собеседовании.

Я бы остановился на четырёх

если бы интервьюировал я, то прикинулся бы Рэймондом нашим Смаллианом и сказал: «предположим, что вам стало известно, что эту задачу можно решить за меньшее количество взвешиваний…» :)

Это, по идее, зависит от устройства механизма часов, разве нет?

Да, зависит. Но насколько я понимаю, у любых часов движение стрелок всё же дискретное, хоть это и незаметно глазу (хотя в некоторых заметно, причём даже на минутной, а не только секундной, но редко). Каков именно шаг, зависит от устройства всех этих шестерёнок внутри и т.д. Ну и в кварцевых совершенно очевидно, что точнее, чем 1/32768 секунды не измерить никак, хотя на деле, конечно, даже до такого далеко.

А как в общем виде такие задачи решать? Должно же быть что-то такое.

у любых часов движение стрелок всё же дискретное

«Как отличить оригинальные часы Ролекс от подделки» (с)

Странное задание, очень простое. В голове задача решилась за секунду.

Возможно самое подходящее к «должно же быть что-то такое» чего попадалось – Дж. Пойа «Как решать задачу».

Это клоунада или действительно помогает кого-то выбрать адыкватного?

И то, и другое. Интеллект положительно кореллирует как с умением кодить, так и с умением отвечать на такие вопросы. Точно так же можно партию в шашки с соискателем сыграть. Главное, чтобы никто не прознал про такие ваши особенности, нето наберёте одних шашечников-головоломщиков, бесполезных в реальной жизни.

24 раза

Это уж слишком общее. Я имел в виду задачки на взвешивание. Там ведь всё довольно легко формализовать — есть конечное множество переменных, принимающих дискретные значения (настоящая монета, облегчённая и утяжелённая) и есть операции, которые позволяют часть неизвестных сделать известными. Требуется найти оптимальный алгоритм (последовательность операций в зависимости от результата предыдущей операции), который найдёт все неизвестные.

Есть же какая-то наука, которая таким занимается. Вот есть же доказательство неразрешимости уравнений выше четвёртой степени в радикалах. Тут что-то такое же должно быть.

«Как и вся наука, – сказал горбоносый. – Счастьем человеческим»

Какая наука занимается алгоритмами понятно.

Непонятно какой смысл углубляться в разработку алгоритма решения для совершенно непрактической задачи.

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

Иногда просто трудно остановиться.

module DoubleSort =

    let doubleSort xs =
        let sortedNegs =
            List.filter (fun x -> x < 0) xs |> List.sortWith (fun a b -> compare b a)

        let rec step xs negs sorted =
            match xs with
            | head :: tail ->
                if head < 0 then
                    step tail (List.tail negs) ((List.head negs) :: sorted)
                else
                    step tail negs (head :: sorted)
            | [] -> sorted

        List.rev (step xs sortedNegs [])

    let xs = [ 1; 10; 20; -1; -4; 5; -2; 8 ]
    printfn "xs:\n %A" xs
    printfn "doublesorted xs:\n %A" (doubleSort xs)

xs:
 [1; 10; 20; -1; -4; 5; -2; 8]
doublesorted xs:
 [1; 10; 20; -1; -2; 5; -4; 8]

Сколько раз в течение суток встречаются минутная и часовая стрелки

0 раз т.к. их нет на часах, там только цыфры

И что? Реализовать Selection sort пропуская цифры больше 0 :)

Сколько раз в течение суток встречаются минутная и часовая стрелки.

Блин, не прошел я тест в гугл, сразу бы ответил 23 и только после наводящего подумал о 22.

Как вы относитесь к подобного типа заданиям?

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

Если меня собеседуют - отношусь нейтрально. У меня подобные задачи (разумного уровня сложности) проблем обычно не вызывают.

Это клоунада или действительно помогает кого-то выбрать адыкватного?

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

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

Интересная задача. Сейчас лень думать, но в целом я бы завёл второй массив индексов и сортировал бы его.

Вообще я считаю около-идеальным собеседованием такое:

1. Берём какой-нибудь интересный кусок кода из нашего проекта. Интересный в том плане, чтобы там было побольше синтаксических конструкций, циклы, условия и тд.

2. Вносим туда ряд ухудшений. Каждое ухудшение должно характеризовать уровень программиста.

3. Просим товарища провести code review указанного куска кода, выделить проблемы, предложить пути решения.

Примеры ухудшений:

1. Явно кривое форматирование кода.

2. Плохие названия переменных и функций. Тут можно несколько уровней ввести - явно плохие названия вроде a1, a2, a3; какой-нибудь транслит, опечатка и др.

3. Баги, очевидные без погружения в предметную область.

4. Архитектурные проблемы.

5. Неправильное использование общеизвестного API.

В общем главное не уйти в субъективщину.

По тем проблемам, которые товарищ сможет обнаружить и по тем решениям, которые он сможет предложить - уже будет неплохо понятен его уровень.

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

8 монет. Одна фальшивая (она легче). Есть только простые весы с чашками. За ДВА взвешивания найти фальшивую.

Ну это просто, делим на две кучи по четыре монеты, ту что легче, тоже делим на две кучи по две монетки…. и тогда мне нужно ТРИ взвешивания чтоб понять какая монетка легче… я опять не прошел.

А причем тут дискретность, при непрерывном линейном движение стрелок идеальных сферических часов в вакууме стрелки идеально сойдутся 22 раза в сутки.

Update: посмотрел на часы и теперь думаю таки 23 :)

Весы это троичная машина. Они выдают три результата: -1, 0, +1. Соответственно ты за одно измерение получаешь l2(3) = 1.6 бита информации. За два взвешивания ты получишь 3.2 бита информации. В 3.2 бита можно закодировать 8 дискретных значений (точней 9, но у нас в задаче 8).

В общем исходи из этой постановки. Когда ты делишь кучу на 2 части, ты теряешь один результат. У тебя всегда будет -1 или +1, а 0 ты не используешь.

Мой надмозг сломался, но не объясняй, буду над этим думать следующие несколько лет :)

Вариант с восемью монетами «психологически» сложнее. Попробуй с девятью.

Это как-то совсем уже детская задачка, имхо.

Озвучь решение.

Решение рождается максимум за минуту если понимать что ножку циркуля с иглой тоже можно двигать. Вы с квадратурой круга не перепутали случаем?