*** ВНИМАНИЕ: Блог переехал на другой адрес - demin.ws ***

суббота, 26 июня 2010 г.

Bloomberg: Вакансии

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

Например, можно зайти в наш раздел вакансий, указать в «Job Function» категорию «Research and Development» (R&D) и получить список открытых позиций для программистов во всех наших офисах.

Я работаю в Лондонском офисе, и поэтому многое из этого поста относится к лондонскому R&D, но в целом, все верно и для остальных офисов.

Например, конкретные вакансии в подразделение «Trading Systems», где работаю я: раз, два и три.

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

Подавляющее количество позиций – это С++ и UNIX, но, например, в мобильную команду (iPhone/iPad/Android/Blackberry) также приглашают специалистов по Objective-C и Java.

Я координирую процесс найма в нашу группу, поэтому знаю процесс чуть более глубоко, и могу подсказать детали интересующимся.

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

Какие шансы пройти? Ничего гарантировать нельзя, но если у вас 4.0 и более баллов на Brainbench на тесте по С++ (не забудьте дать ссылку на профайл в резюме) и более чем пятилетний постоянный опыт больших проектов на С++ , то шанс добраться до телефонного интервью весьма велик. А если вдобавок у вас есть рейтинг на TopCoder’e, CodeForces или что-то в этом роде (также не забудьте дать ссылку), то шансы и на личном интервью очень даже неплохие.

Теперь самая интересная часть марлезонского балета – а как это все работает для граждан России и бывших соцреспублик, у которых нет европаспорта? Могу сказать, что Блумберг может предоставить визовое спонсорство для понравившегося кандидата.

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

Зарплаты? Блумберг всегда адекватен к текущему уровне зарплат на рынке. Насколько я знаю, сейчас зарплаты программистов в Лондоне могут колебаться от 35K до 75K фунтов в год (50K-100K USD) минус 20% налогов Великобритании. Вообще, для ориентации по заплатам и вакансиям можно посетить jobserve.co.uk или monster.co.uk.

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

Ну и под занавес, как говорится, чтобы два раза не вставать – у нас в Лондонском офисе 22-го июля будет Bloomberg Technology Open Evening – день открытых дверей для разработчиков. Однозначно понимаю, что не все россияне могут так чисто взять и на денек ради этого сюда приехать, на всякий случай – вдруг кому будет-таки полезно, и кто захочет прийти – могу сделать инвайт (пишите на alexander@demin.ws).

Макросы для определения компилятора, библиотеки, операционной системы или архитектуры

Очень полезный проект - http://predef.sourceforge.net/.

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

понедельник, 21 июня 2010 г.

Отладчик в Visual Studio 2010

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

Лондонское метро - live map

Не уверен, что это будет кому-либо полезно за пределами Лондона, но тут меня поразил сам факт существования подобного сервиса.

Живая карта Лондонского метро - http://traintimes.org.uk/map/tube/

Тут видно движение отдельных поездов.

И опять-таки, идея нереволюционная. Но! Самое важное, что такой сервис есть благодаря public API, официально поддерживаемый Лондонским Метро, которая является полугосударственной структурой. Теперь ясно, откуда такое изобилие приложений для айфона и андроида, предоставляющих разнообразную on-line информацию о метро. Я то думал, они просто парсят страницы официального сайт, а тут, оказывает, все дается на тарелочке.

воскресенье, 20 июня 2010 г.

Блог на английском для носителя русского языка?

Вы пробовали вести блог на английском?

Я уже долгое время тщетно пытаюсь это делать. Но дело как-то не идет. Каждый пост занимает в разы больше времени, посты приходится укорачивать, упрощать язык ("эдак" уже не завернешь). А самое, что внутренне неприятно - я четко вижу разницу в качестве языка. Вместо более-менее живого и, надеюсь, интересного, способа выражения мыслей, что я себе могу позволить на русском (хех, все-таки 30 лет практики), на английском получается какое-то сухое школькое сочинение, часто с неочевидными ошибками. И уж точно выглядещее, как НЕклево..

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

fill_n vs memset

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

А вот к чему. Если разобраться, что я могу писать код вообще без С-шных штучек типа массивов, malloc/free, старого способа приведения типов, строчек с нулем на конце и т.д. Получается, что мой диалект С++ можно урезать на тему всего, что я перечислил. Просто убрать, и все.

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

Например, как мне кажется, функция memset() в мире С++ в целом годится разве что для обнуления. Использование какой-либо иной константы-заполнителя принципиально приближает нас к проблемам с памятью. Хотите, например, "эффективно" заполнить строку пробелами, и зарядите для этого memset(), а потом вам неожиданно придется работать с многобайтовыми кодировками, и этот пробел, записанный через memset(), может стать источником проблем.

Так что используйте алгоритм "fill_n()" вместо "memset()". Может быть неэффективен? Может, а может и нет. Зато уж точно безопасен с точки зрения типизации.

пятница, 18 июня 2010 г.

Google I/O: all videos

Тут собраны все видео с Google I/O 2010, по категориям.

http://code.google.com/events/io/2010/sessions.html

Мне, например, очень понравилась презентация про новую Java машину с JIT в Android 2.2:



И про язык программирования Go:

Сумма цифр числа в Excel'е

Разбираясь с задачей из последней SRM'ки, решил я посмотреть, как будет выглядеть график у функции Y=D(X), где X - натуральное число, а D(X) - сумма цифр его десятичной записи. Оказывается, вот такой хитрой формулой:

=SUMPRODUCT(--MID(A1,ROW(INDIRECT("1:" & LEN(A1))),1))

можно в Экселе посчитать этот самый D(X). Ума не приложу, что это формула значит, но точно работает.

А вот и сам график, кому интересно:

TopCoder SRM 473. Уроки

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

Итак, по порядку. Дивизион 2, 75 минут, 3 задачи + 10 минут после на взлом (challenge) чужих решений.

Задача номер 1.

Есть набор куриц и коров. У каждой курицы две ноги и одна голова. У коровы четыре ноги и одна голова. Даны два числа: количество ног и количество голов (каждое число от 1 до 10^6). Надо ответить на вопрос: возможно ли существования некоторого количества куриц и коров при заданном количестве ног и голов.

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

Все просто. Но! В два часа ночи я родил иной подход: перебор! (для системы-то из двух линейных уравнений). Я даже помню ход свох мыслей: так как количество только 10^6, значит можно перебрать все возможные значение количество куриц. Для каждого значения вычислить количество коров, исходя их количество ног и из количество голов. Полученные значения сравнить, и если совпадают, значит найдено возможное решение.

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

Кстати, решение в итоге не прошло системных тестов. И к лучшему.

Задача номер 2.

Дано неограниченное поле, в некоторой точке которого стоит робот. Дана программа для робота – строка, каждый символ которой – команда: «S» - шаг вперед на какую-то константную величину, «L» - поворот налево, «R» - поворот направо. Требуется сказать, будет ли траектория робота, двигающего по этой программе, ограничена конечной окружностью, или робот будет постоянно удалятся от исходной точки. Длина программы для робота до 250 символов.

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

Решение есть. Теперь его надо запрограммировать. Надо было сделать имитацию выполнения программы, то есть команды робота «вперед», «влево» и «вправо».

Приведу фрагмент программы, которую родил мой воспаленный мозг ночью:

...
      if (cmd == 'S') { 
        x += dx; 
        y += dy; 
      } else { 
        if (cmd == 'L' && dx ==  0 && dy ==  1) dx = -1, dy =  0; 
        else if (cmd == 'R' && dx ==  0 && dy ==  1) dx = +1, dy =  0; 
        else if (cmd == 'L' && dx ==  1 && dy ==  0) dx =  0, dy =  1; 
        else if (cmd == 'R' && dx ==  1 && dy ==  0) dx =  0, dy = -1; 
        else if (cmd == 'L' && dx ==  0 && dy == -1) dx =  1, dy =  0; 
        else if (cmd == 'R' && dx ==  0 && dy == -1) dx = -1, dy =  0; 
        else if (cmd == 'L' && dx == -1 && dy ==  0) dx =  0, dy = -1; 
        else if (cmd == 'R' && dx == -1 && dy ==  0) dx =  0, dy =  1; 
...

Даже сейчас я не могу смотреть на это без содрогания. Надо то было всего:

...
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };
int d = 0;
...
if (cmd == ‘S’) {
  x += dx[d];
  y += dy[d];
} if (cmd == ‘L’)
  d = (d + 4 - 1) % 4;
else if (cmd == ‘R’)
  d = (d + 1) % 4;
...

И все!

Но увы. Когда время ограничено, на ум приходят странные решения.

Хотя мое решение прошло системные тесты, от его вида как-то грустно.

Задача 3.

Дано определение числа Y: Y = X/D(X). X – натуральное число, D(X) – сумма цифр в десятичной записи числа Х. Если Y получается целым, то читается, то Y есть «предок» числа X. Дан интевал чисел от «а» до «b» (каждое от 0 до 10^9), но «a-b» всегда не более 10000.

Спрашивается, сколько есть на данном интервале есть числе Y, у которых нет предка (то есть нет такого Х, чтобы Y был целым).

Итак, для решение перебираем все значения Y от «а» до «b» (их не более 10000). Для каждого Y числа надо проверить, если ли у него «предок». Ясно, что заменатель D(X) принимает только значения от 1 до 81 (число с максимальной суммой цифр – это 999999999, а их сумма 81). Итак, делаем внутренний цикл от 1 до 81, и вычисляем X как X=Y*i (i от 1 до 81). Далее по факту равенста i и D(X) (надо вычислить сумму цифр, составляющих текущее X) можно понять, если ли у текущего Y предок или нет.

Всего итераций будет максимум 10^4 * 81 * 9 ~= 10^6 = 1000000, что вполне реально.

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

Итак, выводы.

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

Заснуть под утро я так уже не смог. Все думал.

воскресенье, 13 июня 2010 г.

Перебор всех разбиений множества на два подмножества

Допустим, есть массив (вектор) v, и надо перебрать все возможные варианты разделения его компонент на два непересекающихся подмножества.

Если элементов множества немного, а именно - их количество умещается в разрядную сетку вашего компьютера, например, не более 32-х или 64-х, то есть элегантный способ организовать перебор следующим образом:

vector<int> v(20); // Исходное множество

// Всего вариантов будет: 2^(v.size())-1.
for (int i = 1; i < (1 << v.size()); ++i) {
  vector<int> left, right;
  for (int j = 0; j < v.size(); ++j) {
    if ((i >> j) & 1)
      left.push_back(v[j]);
    else
      right.push_back(v[j]);
  }

  // Текущий вариант множеств left и right готов для обработки.
  ...
}

суббота, 12 июня 2010 г.

return со значением для void-функции

Я как-то думал, что для void-функций оператор return не может иметь ничего, кроме пробелов, перед завершающей его точкой с запятой. Оказывается, что нет. Visual Studio съела без каких-либо жалоб вот такой код:

void v() {}
void f(){ 
  return v();
}

int main() {
  f();
}

Разностная машина из Лего, или динамическое программирование в жизни

Динамическое программирование - это очень интересный и очень эффективный прием. Недаром, огромный пласт олимпиадных задач по программированию посвящен этой теме.

А что в жизни? В жизни-то оно применимо? Конечно!

Итак, разностная машина, построенная из Лего!



Как сказано в описании: "Computing the next entry in a table can be significantly easier than computing an arbitrary entry of the table." - классика динамического программирования.

Вот оно - настоящее Железо!

Ссылки по теме:

пятница, 11 июня 2010 г.

Анализатор последовательностей

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

Формула может быть в замкнутом виде, когда ты просто подставляешь аргументы и разом получаешь результат за время O(1), или в динамической, рекуррентной форме, когда для вычисления i-го члена надо вычислить предыдующие.

Классический пример замкнутой формы - это сумма ряда n положительных чисел:

S(n)=n*(n-1)/2.

А для динамической, или рекуррентной формы - это, например, формула для i-го члена последовательности чисел Фибонначи:

F(i)=F(i-1)+F(i-2).

Например, вот такая задача (для школьников!).

Есть N чисел от 1 до N. Требуется разместить эти числа в ряд слева направо. Первым числом всегда идет 1. Каждое последующее может отличаться от предыдущего не больше, чем на 2. Например:

1 2 3 4 5 ...
1 3 2 4 5 ...
1 3 5 4 2 ...

и т.д. (эта задача есть на Тимусе).

Требудется найти количество возможных размещений по этому правилу для N чисел. N от 1 до 55.

Просто перебором в лоб не получится, так как вариантов будет 55! ~ 10^73, а времени дается всего одна секунда.

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

А вот теперь подходим к сути поста. Недавно я наткнулся на волшебный сайт - Онлайн-энциклопедия целочисленных последовательностей. Там ты просто вводишь несколько известных тебе членов последовательности, а сайт по большой базе данных ищет совпадения с какими-либо известными последовательностями, и в случае наличия такого совпадения, дает исчерпывающую информацию - формулы, статистический анализ и т.д.

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

В итоге, магия произошла. Когда я ввел вычисленные первые элементы последовательности в этот анализатор, мне просто сказали, что формула для i-го члена этой последовательсти: a(n)=a(n-1)+a(n-3)+1. И все! И по данной формуле задача решается пулей одним циклом за O(N).

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

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

среда, 9 июня 2010 г.

Проблемы с delete[]

Имеем следующий код:

#define T 2

class A {
  public:
    virtual ~A() { 
      p = 0;
    }
    int p;
};

class B: public A {
  int a;
};

int main() {
  A* a = new B[T];
  delete[] a;
  return 0;
}

У меня эта программа однозначно падает с "Segmentation fault" на строке "delete[] a". Проверено на Sun C++ на Солярисе, GCC на Линуксе и на FreeBSD. Вот, например, что происходит на BSD:

Program received signal SIGSEGV, Segmentation fault.
0x08048743 in main () at new_array.cpp:17
17        delete[] a;

Забавно, что под Windows в VS2008 ничего особенного не происходит.

Как я понимаю, что в этой программе принципиально важно, чтобы она падала: деструктор класса "A" должен быть виртуальным, дочерний класс "B" должен быть больше по размеру (тут есть член "a"), константа "Т" должна быть 2 или более (то есть мы должны создавать несколько экземпляров класса "B"), и деструктор класса "A" должен что-нибудь писать в свои члены (тут есть "p = 0;").

Что же тут происходит?

new[] создает массив экземплятор класса "B". Оператор же delete[] получает на вход указатель типа "A*" и начинает вызывать деструкторы элементов. Так как деструктор класса "А" виртуальный, то в ход пускается таблица виртуальных функций. Итак, отработал деструктор для первого элемента a[0]. Далее delete[] хочет получить адрес следующего элемента массиве "a". И для этого (внимание!) адрес следующего он вычисляется так: "a + sizeof(A)" (ему же на вход дали указатель типа "A*"). Но проблема в том, что sizeof(A) < sizeof(B) (это дает член класса B::a), и "a + sizeof(A)" будет указывать не на второй элемент в массиве "a", а куда-то между первым и вторым элементом, так как реальный адрес второго элемента - "a + sizeof(B)". И все бы ничего, но деструктор класс "A" пишет в член "p", тем самым меняя содержимое памяти, а так как для второго элемента адрес вычислен неправильно (его this указывает непонятно куда), то куда реально попадет 0 в присваивании "p = 0;" уже никто не знает, но явно не туда, куда надо. Вот и "Segmentation fault".

Другого объяснения у меня нет.

Если кто знает лучше, поправьте.

P.S. Забавно, что под виндами ничего страшного не происходит.

Update: В комментариях дали точное объяснение из стандарта: C++ 2003 5.3.5:
...In the second alternative (delete array), the value of the operand of delete shall be the pointer value which resulted from a previous array new-expression. If not, the behavior is undefined. [Note: this means that the syntax of the delete-expression must match the type of the object allocated by new, not the syntax of the new-expression.]

Update 2: Объяснение, почему не глючит в Visual Studio.

воскресенье, 6 июня 2010 г.

Опрос: как мы называем свою профессию

Создал небольшой опрос: "Как вы говорите про себя, когда вас спрашивают о профессии?".

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

Немного об алгоритмах

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

Scheduling для двоих детей, особенно с небольшой разницей в возрасте, конкретно отличается от одного, и является гораздо более сложной оптимизационной задачей, ибо количество переменных увеличивается на порядок. Но в целом - переходный процесс уже начал стабилизироваться, и снова появляется время позависать на всяких сайтах с алгоритмическими задачками (успел даже поучавствовать в двух SRM'ах на TopCoder'е).

Например, сайт Красноярского Дворца пионеров и школьников. Он позиционируется как место для самоподготовки школьников, интересующихся программированием, для олимпиад. Но хвала тем школьникам, которые могут сходу решать задачи сложности 50% и выше с этого сайта. Не всякий, как пишут в резюме, "профессиональный программист с многолетним стажем" сможет "взять" некоторые из них.

Обнаружил просто мега-сайт - e-maxx.ru/algo. Справочник по алгоритмам и их реализациями на С++. Все на русском языке. Как мне тут сказали, что, в принципе, освоив большинство из них, можно показывать неплохие результаты на программистских соревнованиях.

В разделе книг там также отличная подборка.

Из категории, опять-таки, олимпиадного программирования, могу посоветовать:



и



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

Кстати, заметил интересный факт. Лично я не люблю язык Паскаль. Мое субъективное мнение. Многословный и эстетически некрасивый синтаксис. Но Российская школа программирования уважает Паскаль и Дельфи (спасибо вечному Турбо Паскалю 7.0), и поэтому программы в этих книгах написаны на Паскале, а не на С++. И заставляя себя вчитываться в паскалевские куски кода, еще и изуродованные форматированием для печати в книге, получаешь более полное понимание алгоритма. Как говорят: умение читать код может быть даже важнее для программиста, чем писать его.

Далее. Нашел интересную страничну какого-то профессора из MIT, на которой лежат его мини видео лекции с разборами некоторых классических задач динамического программирования. Манера подачи материала очень интересна - видео представляет собой постепенную запись объяснения задачи от руки, сопровожаемую голосом. Например, задача о сдаче, или оба вида задачи о ранце - с повторами и без (0-1).

Алгоритмы - это очень интересно.

Посты по теме: