с интервью

[juan_gandhi]

Интервьюировал тут интересного француза, из-под Гренобля - Еколь Политекник, потом Бёркли. Мой первый вопрос - хрен ли тут у нас на посёлке делать после прекрасных предгорий? А тут типа у нас жизнь (а там типа нету). Молодёжь!

Короче, задал ему недавно тут пролетавшую задачу - сумму максимальных нечётных делителей для чисел от 1 до N. Сначала написал джавный код, который, будь у нас tail recursion (у него второй язык CAML), был бы ничо бы.

Я его попросил пооптимизировать. Нарисовал алгоритм, пропорциональный N. Я предложил поискать алгоритм, пропорциональный логарифму N. И тут он нарисовал чудесную вещь.

Он нарисовал график, где по горизонтальной оси N, а по вертикальной - значения, которые он складывает (ну понятное дело, логарифмы складывает). По горизонтали N столбиков. Или, по вертикали, log2(N) полосок. После чего решил взять, да интегрировать не по x, а по y. Так что сумм у нас будет всего log2(N), а значения, что суммируются - ну не биг дил посчитать.

Ребята, я такой фокус первый раз вижу! Наглядно донельзя: на графике.

Остаток интервью допрашивал его про метод Годунова - так, чтоб языком почесать.

Ну дай бог он к нам согласится.

Comments

[andy-scott.livejournal.com]

Шикарно. Просто шикарно. Очень заинтересовало, потому что со слов ничего толком не понял, но интересно же! :)

[ygam.livejournal.com]

Задачка

Для N=20 это 1+1+3+1+5+3+7+1+9+5+11+3+13+7+15+1+17+9+19+5 = 136?

[kashnikov.livejournal.com]

EP, это вам не хухры мухры. Java в EP теперь тоже есть :)

[itman.livejournal.com]

Похоже на правду.

[ygam.livejournal.com]

Ну тогда нужно суммировать все нечетные числа от 1 до N, все делящиеся на 4 с остатком 2, все делящиеся на 8 с остатком 4, и т. д.

[kashnikov.livejournal.com]

А Вы, кстати, вроде МехМат заканчивали?

[itman.livejournal.com]

Ну да, получается нужно просуммировать log N таких сумм.

[ygam.livejournal.com]

Мне 3 года назад на интервью в Гугеле задали вопрос: сколько нулей будет в десятичной записи n! ? Я посчитал так же.

[ivan-gandhi.livejournal.com]

Тебя Белла интервьюировала, что ли? :)

[ivan-gandhi.livejournal.com]

Он начинал с Камла. Джаву, наверное, уже в Бёркли подхватил.

[ivan-gandhi.livejournal.com]

Нет; матмех. Но фокуса такого не знал.

[orleanz.livejournal.com]

Послушайте, но идея интегрировать не по Х, а по У - это ведь фундаментальная математическая идея, которую всем на первом курсе мехмата обьясняют, в связи с интегралом Лебега. Есть интеграл Римана, это "когда по Х", и Лебега, "когда по У". По игреку в некоторых случаях проще, потому что (хотя это уже не применимо к программироованию) - множество точек, где функция принимает некое определенное значение может быть "неизмеримыми", но это не имеет значения, если значение=0, так что его просто отбрасывают, и берут оставшуюся (уже измеримую) часть, где знечение не равно нулю.

[ygam.livejournal.com]

Да. It's a small world.

[ygam.livejournal.com]

Я свою коронную задачку "abacaba" в ЖЖ рассказывал?

[spamsink.livejournal.com]

Я такой не помню.

[ygam.livejournal.com]

s₀ = ""
s₁ = s₀ + "a" + s₀ = "a"
s₂ = s₁ + "b" + s₁ = "aba"
s₃ = s₂ + "c" + s₂ = "abacaba"
...
s₂₆ = "...z..."

Написать функцию, которая будет возвращать символ в данной позиции s₂₆ .

[spamsink.livejournal.com]

Да, извратить простую задачку до неузнаваемости надо уметь.

[ygam.livejournal.com]

Я эту задачку придумал сам (точнее, adagio_burner мне рассказывал про своего одноклассника, который любил петь: "abacabadabacabaeabacabadabacaba...").

Так, что ли?

[spamsink.livejournal.com]

unsigned f(unsigned x) {
    return x <= 1 ? x : ((x+1)/2)*((x+1)/2) + f(x/2);
}

[vit-r.livejournal.com]

Эх! Это ж сколько лет назад мне для чего-то был надобен интеграл...

А единственный тут, кто как-то подошёл со словами "У меня один очень глупый вопрос...", был французом...

[ivan-gandhi.livejournal.com]

Но не с целью сократить вычисления с O(N) до O(ln(N)).

Re: Так, что ли?

[ivan-gandhi.livejournal.com]

Оно. :)

[itman.livejournal.com]

Нулей справа, или всего? :-)

[ygam.livejournal.com]

Справа, конечно.

[itman.livejournal.com]

Я уж испугался :-)