вторник, декабря 14, 2010

Google?

Этим летом меня удивило письмо с темой «Hello from Google Zurich», оказывается меня через GitHub нашел гугл, точнее один из сотрудников по поиску кадров. Был небольшой телефонный разговор, сошлись на том, что до конца 4-го курса я точно учусь и никуда не поеду, а потом со мной может когда-нибудь и свяжутся (я так до конца и не понял, но возможно по окончании 4-го курса), чтобы позвать на стажировку.
И вот несколько недель назад мне пришло «from Google Russia», в Московском и Питерском офисе открыты вакансии на инженеров-стажеров. Я опять сказал, что никуда пока не хочу, хочу учиться. Предложили прособеседоваться, так, на будущее.. Я был не против, и вот, на 13 декабря договорились провести со мной телефонное собеседование.
(история гораздо длиннее и интереснее, но я хочу рассказать именно о собеседовании)

Ровно в два часа дня, как и договаривались, позвонил Костя, программист из московского офиса. Собеседование состояло из трех частей: введение (по-русски, объяснили что щас будет происходить), собственно собеседование (по-английски, я должен был отвечать на вопросы) и свободный разговор (по-русски, я мог задавать вопросы). Предварительно для меня расшарили текстовичок в Google Docs, в котором происходил весь обмен письменной информацией, вполне удобно.

So let's start. Дан массив X[n] и число Y, найти такие i ≠ j, что X[i] + X[j] = Y. Гавно вопрос! За O(n²) полным перебором. Костя захотел чего-нибудь более.. Быстрого. Я решил, что O(n) все равно недостижимо (я был так наивен), и тогда не грех и отсортировать массив за O(n log(n)). Отсортированный массив это хорошо, напрашиваются два индекса, идущие с разных сторон, пусть i слева, j справа. Тут я немного затупил, но Костя попросил медленно вслух повторить мысль и затуп разрешился. Смотрим текущую сумму X[i] + X[j], если она равна Y, то разговор окончен, если она меньше Y, то двигаем i вправо, ибо j двигать влево бесполезно, если она больше Y, то двигаем j влево. Повторяем сие действо, пока i < j. Иначе решения нет. Костя согласился с алгоритмом, попросил определить скорость — O(n), попросил доказать — доказал. (Уже после собеседования я смог строго доказать корректность алгоритма, Костя не прикапывался). Получаем в итоге O(n log(n)), я решил что неплохо, но меня так между делом спросили: "А за O(n) слабо?!" Задумался минут на 5... Предложили подсказку: какие контейнеры в Java я знаю. List, vector, hash map, .. Меня остановили, спросили, что я знаю про hash map. Я начал лечить что у него время доступа линейное, точнее почти линейное.. Понял что несу чушь, поправился, время доступа константное. "So could you use hash map here?" YES — крикнул я, не скрывая ощущения полного офигевания от простоты алгоритма, который уже понял. Идем по массиву, и добавляем каждый элемент X[i] в хэш таблицу следующим образом {ключ: x[i], значение: i}, и также проверяем в таблице наличие элемента с ключом (Y-X[i]), если он есть, то берем соответствующее ему значение j и пара i,j является искомой. Линейное время, память конечно покушается в некотором количестве, но как я понял тут было важно время.
So another task. Есть функция int foo(int x) { return x*100; }, реализовать эквивалентную ей, не используя операцию умножения. Гавно вопрос! x << 6 + x << 5 + x << 2. Костя согласился и предложил обобщить: написать алгоритм, которой для произвольного N будет генерировать выражение равное x*N. Написал алгоритм нахождения максимальной степени двойки, непревосходящей N (двигаем вправо, пока число положительно; считаем сдвиги). Дальше повторяя этот алгоритм получаем конечное разложение N на сумму степеней двойки: x << k₀ + x << k₁ + ... . Костя хитрым голосом предложил продемонстрировать работу алгоритма при N = 15. Вышло стремно: 8 + 4 + 2 + 1, можно ли как-нибудь по-лучше? Да, (x << 4) - x. Написал алгоритм для нахождения и этой степени, в итоге вышло  x << k₀ - x << k₁ + x << k₂ - x << k₃ + ... . Этот алгоритм вроде не является лучше, ибо очень много зависит от начального числа, но Костя сказал ОК и сообщил, что 40 минут отведенные на собеседование кончились.

Фуух, я очень волновался, и эти 40 минут пролетели нереально быстро. Костя оказался выпускником МехМата МГУ, уже более трех лет работает в гугл, как я понял ему очень нравится. Оказалось, что они не gmail на русский переводят, а деляет вполне секретные и интересные проекты вместе с зарубежными коллегами. Поинтересовался, действительно ли их офисы такие клевые.. Да, клевые, но вот он уже привык и гораздо больше акцентировал внимание на том, что работа интересная. Пожелали друг другу удачи и все.

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

p.s. К собеседованию никак не готовился, проходил по большей части для себя.

суббота, августа 21, 2010

Контрольная по математике в ЛШ-2010

У меня окончилась работа в Летней Школе. В этот раз у меня было много нового, меня приглашали проверять олимпиаду вступительную и принимать собеседования, но сейчас о другом.

Вел математику опять у класса 9-4, 29 человек в двух группах. Были умные, были неочень :)

Теперь конкретно по контрольной: пять задач (метод мат.индукции, делимость, планиметрия, комбинаторика, построения циркулем и линейкой), на все 4 часа. Мне потребовалась 21 минута, чтобы решить оба варианта, так что воздержусь от субъективной оценки уровня задача, но судя по общим результатам контрольная сложная.

Средний бал по классу 9.8, что соответстует двум задачам при оценке из пяти баллов. За такой результат ставили три. Разбаловка вообще простая: больше одной задачи — три, больше двух — четыре, больше трех — пять. В классе же 4 пятерки, 7 четверок, 10 троек, 8 двоек.

А теперь интересная статистика..
  • задачку на делимость решали 27 человек, причем 19 решили верно! Это говорит о том, что все-таки толк от меня есть, и работе с остатками я их научил
  • задачку на мат.индукции решали 24 человека, а решили опять же 19. Это опять говорит о том, что я молодец, но все-таки боязнь перед "страшной индукцией" присутвует, и далеко не все понимают теор.основу мат.индукции
  • задача на комбинаторику была жесткая, пытались решать и решили ее только 2 человека. В задаче нужно было использовать прием, который я на семинарах не давал, бывает
  • планиметрию решали 9 человек, решили 2. Она даже не была сложной. Просто почему-то второй год подряд ЛШата вообще не шарят в планиметрии (или это традиция такая?)
  • задачу на построения решали 14 человек, решили 6. А вот это я объяснить не могу, на семинарах основы разбирали, вроде все было понятно, единственное при проверке очень прикапывались к оформлению, может в этом дело
Теперь о рекомендациях. В ЛШ преподаватели должны по результатам семинаров выставить каждому ученику рекомендацию по шкале от "настоятельно не рекомендую" до "настоятельно рекомендую". В этом году все дети были вроде адекватные, поэтому "не рекомендую" я не ставил.
Можно попробовать выявить закономерность между рекомендацией (зеленые линии на графике) и оценкой за контрольную (синяя) — я не смог. Это отчасти связано с тем, что многие дети не хотят поступать и сливают контрольную не особо стараясь, а всякие упрямые и целеустремленные девочки делают все, чтобы написать хорошо.

В общем я доволен, на следующий год обязательно пойду преподом и опять буду думать о должности воспета.

четверг, июля 29, 2010

Стиль "прямоугольник"

Нашел в одном style-guid'е, очень красивый пример:

Форматирование исходного текста в стиле "прямоугольник", например
crlf    = (String) java.security.AccessController 
          .doPrivileged(new sun.security.action   
          .GetPropertyAction("line.separator"));  
есть неуважение к людям, которые вынуждены будут этот текст читать.

понедельник, мая 10, 2010

Ruby продолжает удивлять

Уже не в первый раз в жизни я столкнулся с задачей написания парсера какого-либо кода, на этот раз на Ruby.

Чтобы не забыть, вот так вот можно делать простенький разбор на токены:
"abc:def".split /:/   #=> ["abc", "def"]
"abc:def".split /(:)/ #=> ["abc", ":", "def"]

суббота, марта 13, 2010

The Time Tracking

Уже давно мы разрабатываем сервис TTT (The Time Tracker) - система учета времени. Реализована в виде веб-приложения, консольного клиента и кроссплатформенного GUI-клиента.. Но сейчас не об этом.
А о том, что же дает нам подобная система? Вот что она дает!

Это моя активность по разным проектам за последние полгода, с комментариями. :)

четверг, января 14, 2010

Писанина vs Лень

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

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

Перед экзаменом

Два часа ночи, а я недавно проснулся...

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

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

Как учу?
Всегда должен быть какой-то план: список вопросов или программа курса, иначе очень сложно оценивать свои силы и можно что-то не успеть. Так же успехи в изучении каких-то тем я отмечаю закрашиванием квадратика напротив этой темы, каждый квадратик, на самом деле, очень поднимает настроение! Собственно процесс изучения у меня однопроходный: прочитал тему, полностью разобрался во всех выкладках (я никогда не пропускаю что-либо в вопросе, всегда сразу во всем разбираюсь, если пропуск и происходит - то сразу всей темы, дальше в нее не вчитываюсь), представил, что говорить про этот билет - пошел дальше. Если в вопросе была крайне тяжелая выкладка - помечаю, через несколько часов я попробую ее восстановить и, если не получится, прочитаю еще раз.

Что я в итоге знаю?
После такой работы я ориентируюсь во всем материале, имею хорошо упорядоченные знания по предмету. Обычно я довольно хорошо знаю основы (постулаты или какие-либо аксиомы), а дальше все мои знания связаны переходами, какими-то рассуждениями (например кванты: я не помню вид операторов рождения и уничтожения, но я помню, как их вывести за весьма конечное время) - то есть если меня начнут "гонять" по всему курсу, требуя быстрых ответов по памяти, я заведомо слаб в этом деле, но этот подход используется по отношению к людям "плавающим" в материале, к коим я себя не отношу. Шпаргалки: обычно, не более одного листочка для записей с чем-то из следующего раздела или, крайне редко, целые книжки в уменьшенном варианте (лень выбирать оттуда что надо, а что не надо).

А что может пойти не так?
Если мы видим выкладку в которой в уме берутся БОЛЬШИЕ интегралы (и я не могу этого повторить), мы их шпорим. Если присутствует выкладка, в которой слабо прослеживается логика, мы ее (логику, основную суть) шпорим. Если присутствует целый билет, в котором суть спрятана так глубоко, что никто из группы с этим не разобрался, весь вопрос шпорим. Если весь предмет представляет из себя несвязанный набор формул и утверждений, значит я идиот и не должен здесь учиться (на других это не распространяется), так как именно я виноват, в том, что не могу разобраться, а не предмет (последнего еще ни разу не было).
Насчет "прогона" по всему курсу, тут было исключение. На функане Тресков Сергей Андреевич после ответа на билет начал спрашивать у меня одна за другой формулировки нескольких теорем (т.к. я не правильно сформулировал что-то там).. В итоге он сделал вывод, что думать я могу, думаю я правильно, но память плохая - я с ним согласился, но ведь он и не хотел от нас заучивания, поэтому, наверное, и поставил пять.

Когда заканчиваю?
Начиная за три дня подготовку к заведомо разным экзаменам (некоторые очень простые, другие очень сложные), реально учусь я совсем не три дня, иногда больше, иногда меньше.
Простой экзамен. Встал с утра, поел, как-нибудь отдохнул за ноутом, поучил, параллельно читая habra, опять поел. Вообщем за день, часа 3-4 чистой учебы набирается.
Сложный экзамен. Встал, поел, поучил, поел, лег спать. Порядка 10 часов чистой учебы. Но и этого обычно не хватает, в последний день за 12 часов до экзамена у меня (на примере функана и квантов) остается еще около 30-40% процентов материала, что придает мне безумное количество сил для того, чтобы к семи утра все дочитать.
Возможно, это не правильно, следовало бы сосредоточенно выучивать простые за день, а сложные за пять дней, но... Я так не могу, не хватает силы воли, да и я так уже привык, за последние три сессии я ни разу не спал в ночь перед экзаменом более одного часа. И каждый раз (кроме квантов, о них отдельно) приходя на экзамен, я произносил слова Нео "Я знаю кунг-фу" и хотел только пять, потому что в моем мировозрении именно ее я и заслужил.

Кванты
Начал за три дня. За первый день я прошел 6 вопросов из 30, и призадумался, что ситуация весьма неутешительная. К концу второго дня я даже не дошел до половины. В третий день, за 12 часов до экзамена оставалось еще 12 вопросов, ИМХО, самых сложных вопросов в курсе. В итоге у меня в голове осталось приблизительно 70% вопросов, которые я могу рассказать, а остальные 30% - только шпоры, которые я даже не успевал сделать. Подходя к аудитории, я осозновал, что скорее похож на Панду из "Кунг-фу Панда", чем на Нео. Я хотел пять, но остальные варианты не отбрасывались. В итоге зашел первым, долго выбирая билет я выбрал счастливый. С вопросом и задачей среднего уровня. Сдал. 5