juan_gandhi | с интервью

с интервью

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

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

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

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

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

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

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

Flat | Top-Level Comments Only | Expand All

Задачка

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

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

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

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

Edited 2010-02-08 23:28 (UTC)

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

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

Да. It's a small world.

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

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

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

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

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

(no subject)

ygam.livejournal.com - 2010-02-09 00:19 (UTC) - Expand

(no subject)

duchifat.livejournal.com - 2010-02-09 08:19 (UTC) - Expand

(no subject)

ygam.livejournal.com - 2010-02-09 16:43 (UTC) - Expand

Эта та Белла, что у вас во френдах в ЛинкдИне? Тогда как она оказалась в Кёркланде?

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

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

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

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

У меня UC по компьютерной науке (и вечерняя школа UW).

(no subject)

ivan-gandhi.livejournal.com - 2010-02-09 18:00 (UTC) - Expand

допустим.
А сколько времени Вы бы дали интервьюируемому на решение задачи про нули в факториале и на задачу про сумму делителей?

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

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

Это вы какую-то чепуху пишете. Все "числа делящиеся на 4 с остатком 2" будут, разумеется, четными, (как и "все делящиеся на 8 с остатком 4") в результате чего искомой суммы вы никак не получите.

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

все делящиеся на 4 с остатком 2, деля их на 2

:) Если вы возьмете последовательность чисел "делящиеся на 4 с остатком 2" и разделите их на 2, то вы получите последовательность чисел делящихся на 2 с остатком 1, т.е. просто напросто последовательность нечетных чисел: 1, 3, 5, 7... :) Объяснять это через нагромождение "все делящиеся на 4 с остатком 2, деля их на 2" - это все равно что ехать из Москвы с Санкт-Петербург через Владивосток.

На самом деле если выписать последовательность наших слагаемых на бумажке, то видно, что это просто напросто набор последовательностей 1, 3, 5, 7... вложенных друг в друга совершенно очевидным образом. Если вычеркнуть "самую верхнею" подпоследовательность 1, 3, 5, 7... (т.е. через одну), то оставшаяся подпоследовательность будет иметь тот же самый вид. Фрактал, понимаш :)

А решение из этого - очевидно. Берем сумму 1, 3, 5, 7... до N (арифметическая прогрессия), прибавляем сумму 1, 3, 5, 7... до N/2, затем до N/4 и т.д. до победного конца.

А ведь не так и трудно просуммировать 1+3+5+7...!:)

А явно суммировать ничего и не надо. Формулу суммы N первых членов арифметической прогрессии проходят в школе.

Flat | Top-Level Comments Only | Expand All