с интервью

[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?

[itman.livejournal.com]

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

[ygam.livejournal.com]

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

[itman.livejournal.com]

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

[ygam.livejournal.com]

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

[ivan-gandhi.livejournal.com]

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

[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...").

[duchifat.livejournal.com]

У меня тоже был знакомый, который любил аба-цаба-даба-цаба. Может, тот же самый?

[ygam.livejournal.com]

Скорее всего, тот же самый. Тесен мир, блин.

(я никогда не был в Питере, хотя у мой дедушка участвовал в прорыве его блокады)

[ygam.livejournal.com]

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

[itman.livejournal.com]

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

[ygam.livejournal.com]

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

[itman.livejournal.com]

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

[ivan-gandhi.livejournal.com]

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

[ygam.livejournal.com]

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

[ivan-gandhi.livejournal.com]

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

[hill-report.livejournal.com]

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

[itman.livejournal.com]

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

[ivan-gandhi.livejournal.com]

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

[lanceupper.livejournal.com]

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

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

[ygam.livejournal.com]

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

[lanceupper.livejournal.com]

:) Если вы возьмете последовательность чисел "делящиеся на 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 и т.д. до победного конца.

[buddha239.livejournal.com]

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

[lanceupper.livejournal.com]

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

[kashnikov.livejournal.com]

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

[ivan-gandhi.livejournal.com]

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

[kashnikov.livejournal.com]

В EP курс Java, вроде как, не так давно появился. Я в INRIA сидел вместе с преподавателем сего курса, собственно он мне и поведал. Ну и диаспора наша в EP, среди русскоговорящих самая большая :)

А можно спросить про Sophia Antipolis?

[dememax]

Собственно, стоит ли искать поводов туда ехать?

Re: А можно спросить про Sophia Antipolis?

[kashnikov.livejournal.com]

Можно. Что ответить не знаю. ИМХО, каждый для себя решает сам. А советовать не люблю, хоть и делаю это часто :( Если что конкретное спросить хотите, спрашивайте. ;-)

Re: А можно спросить про Sophia Antipolis?

[dememax]

Скажем, я решу поехать туда работать, зная французский, английский и являясь разработчиком ПО со стажем, чтобы получить опыт работы с иностранцами, чтобы лучше изучить язык, детям мир показать (Европа фактически единая), ...

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

Мне говорили, что в Sophia Antipolis можно найти работу такому, как я (у меня нет разрешения на работу в ЕС).
Что снять квартиру в Sophia Antipolis - от 500 евро в месяц для однушки.
С учётом налога на проживание (600 в год), налог на доход (примерно 1 зарплата), бензин (500 в месяц на 1 машину), еду (500 в месяц), электричество-вода-телефон (300 в мес), мобильный (100 в месяц), страховки (около 100 в мес) - получится, что мне нужно искать работу с не менее 3000 евро в месяц, если уж я решусь.
Я всё правильно понимаю?

Re: А можно спросить про Sophia Antipolis?

[kashnikov.livejournal.com]

Вобщем, правильно. Цифры, конечно, могут быть как уменьшены, так и увеличены, но в целом правильно. ;-)

Re: А можно спросить про Sophia Antipolis?

[dememax]

Спасибо!

[kashnikov.livejournal.com]

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

[ivan-gandhi.livejournal.com]

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

[kashnikov.livejournal.com]

Собственно, неважно. Механика у Вас была, а в ней данный подход нередко встречается. В МСС, помнится, есть определенные приемы решения задач с этим связанные. В EP очень хорошая механика.

[orleanz.livejournal.com]

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

[ivan-gandhi.livejournal.com]

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

[kashnikov.livejournal.com]

Да ну? Нам собственно когда давали интеграл Лебега в курсе Математического Анализа, приводили как раз такие примеры. Так что я согласен с orleans, но добавлю, что примеры вычислительного характера тоже были.

Так, что ли?

[spamsink.livejournal.com]

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

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

[ivan-gandhi.livejournal.com]

Оно. :)

[vit-r.livejournal.com]

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

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

[hill-report.livejournal.com]

хороший мальчик (с)
не то что предыдущие кандидаты про которых ужос-ужос рассказывали

[ivan-gandhi.livejournal.com]

Что, собственно, и доказывает тезис, что не зря придирался.

[mehas.livejournal.com]

буквальная иллюстрация к фразе "посмотреть на задачу под другим углом" )

[huzhepidarasa.livejournal.com]

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

[buldozr.livejournal.com]

Это что, к нам тоже один хочет из-под Парижу. Как эти люди думают жить в Хельсинки, не знаю.

[kashnikov.livejournal.com]

Да нормально, последние года снег идет. В данную минуту идет. Ну похолоднее у Вас, в Хельсинки немного. :)

[mr-aleph.livejournal.com]

француза этого случайно не Анри звали? ;-)

о вижу не у одно меня такие ассоциации...

Кстати, Годунов --- это Сергей Константинович? Если да, то клёвый дед. Жутко строгий, но клёвый.

[ivan-gandhi.livejournal.com]

Пьер-Эмманюэль.

Да, конечно, С.К.Годунов.

[blue-slonopotam.livejournal.com]

Есть большой массив чисел, разбитый на 3 области, следующих одна за другой с длинами A B C. Требуется переместить область B в начало, непосредственно за ней должна следовать область A. Что случится с С - не важно. Порядок следования чисел внутри области должен быть сохранён.

Количество пар операций чтения и записи в массив не должно превышать A+B+C.

[blue-slonopotam.livejournal.com]

C в начало, наврал. За ней A.

[huzhepidarasa.livejournal.com]

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

[huzhepidarasa.livejournal.com]

нет-нет, затуманивать известную задачу путем внесения в нее ненужных данных — не наш путь.

[blue-slonopotam.livejournal.com]

Мусорщик, ты что ли ?

[huzhepidarasa.livejournal.com]

Я не знаю, вряд ли, не замечал за собой.

Обе задачки сводятся к известной теме инверсии порядка слов в предложении. Здесь слова — A и B, в варианте выше — A и BC.

[huzhepidarasa.livejournal.com]

Виноват, не A и BC, а AB и C. Ну понятно, в общем. Любая перестановка из трех сводится.

[retiredwizard.livejournal.com]

признайтесь честно: только русские настолько ебанутые, чтобы задавать такие вопросы на собеседовании? верно?

[ivan-gandhi.livejournal.com]

Вы, уважаемый пенсионер, хотите спросить, перестал ли я пить коньяк по утрам?

Не волнуйтесь. Я уже работаю в конторе, где такие вопросы в порядке вещей. Я, конечно, не думаю, что Вы, с Вашим интеллектом, поверите профессионалу, что такие вопросы и надо задавать. Ну, скажем, если Вас просто попросить успокоиться, Вам поможет? Ведь учиться чему-нибудь Вам уже поздно, верно?

[retiredwizard.livejournal.com]

причем тут мой интеллект? ты, как и положено рашкинскому кодерку, первым делом переходишь на личности.

успокойся, дядя!

----------------------------------------------
вопрос вежлив и прост: у меня сложилось ощущение что только рашкинские кодерки с короткими письками задают такие вопросы. НО! может я не прав? я 8 лет как не работаю в америке, может все изменилось за это время?

вот и прошу ответить на этот простой вопрос: американцы на собеседованиях - какие ОБЫЧНО задают вопросы? в среднем по индустрии?

[ivan-gandhi.livejournal.com]

Никакого желания разговаривать в таком стиле; вообще Ваши комментарии мне надоели, так что забаню. На всякого психа не наздоровкаешься.