18 дек. 2011 г.

Задачка: Сортировка по частоте

Дан (очень) большой массив целых чисел, необходимо отсортировать по частоте появления элемента в массиве.
Ограничения: постоянная память, сложность O(N log(N)).

Пример:
[ 1 3 1 ] -> [ 3 1 1 ] т.к. частота(3) = 1; частота(1) = 2
[ 7 1 1 0 ] -> [ 7 0 1 1 ]
[ 9 1 0 1 3 1 3 3 ] -> [ 9 0 1 1 3 3 3 ]

20 нояб. 2011 г.

garbage free logger

We do usually log lots of messages, for instance - for further investigation in case of outage. There are lots of pros and cons - for many reasons log files are usually in more or less human readable format. For low latency applications it's a sort of waste of time as it put a load onto the system via garbage collector and app suffers from stop-the-world pauses.

19 нояб. 2011 г.

java: autoboxing и ==

С появлением java 5 появилась и такая вещь как auto boxing, на мой взгляд штука скорее вредная, чем полезная, но не суть.

Наверняка многие java программисты сходу могут ответить на вопрос «какой будет результат ?»
        Integer a = 100;
        Integer b = 100;
        Integer c = 300;
        Integer d = 300;
        
        System.out.println(a == b);
        System.out.println(c == d);

Тем более, что многие книги, как то Java Puzzlers, упоминают об этом.

28 окт. 2011 г.

Spring Boostrap

We uses spring framework within each our project. I would like to share some small and useful tricks we use in our Bootstrap class.

To load any xml spring context you have to run smth like

try {
    final ClassPathXmlApplicationContext ctx = 
        new ClassPathXmlApplicationContext(
            new String[] {"application-context.xml"});
} catch ( final Throwable th) {
    log.error("Unable to start the context : " + th.getMessage(), th);
}

It's enough in the most cases.

15 авг. 2011 г.

Два презерватива на необитаемом острове

Волею судьбы на необитаемом острове оказалось четверо: двое мужчин и еще две прелестные дамы.

Через какое-то время природа взяла свое и было решено «заняться любовью», однако выяснилось, что все четверо болеют венерическими заболеваниями, причем все - разными.

Поскольку никто не желал добавлять себе еще одно, то после некоторых поисков было найдено два презерватива.

Как провести все четыре возможные встречи между разнополыми партнерами?

внимание! комментарии содержат ответ.

13 июл. 2011 г.

Задачка: 12 монет и 3 взвешивания

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

Известно, что одна из монет фальшивая - отличается только по весу, причём не известно - тяжелее ли она настоящей или легче.

Как при помощи только трёх взвешиваний определить какая монета фальшивая и тяжелее ли она или легче настоящей ?

8 июн. 2011 г.

Android: HTC MyTouch 4G

Вот уже почти месяц как я счастливый обладатель g-phone от HTC - MyTouch 4G, он же HTC Glacier. Изначально бюджет был определён как 10т.руб за новый Android с cpu класса 1GHz и ram не менее 512Mb - в итоге поторговавшись на ebay был получен данный аппарат. В бюджет самого телефона уложился и ещё ~$40 пришлось отдать за пересылку из Америки в Россию. После моего старого кирпича от SonyEricsson 6летней давности радовало всё: cpu ARMv7 1Ghz, 768Mb ram; как выяснилось уже после покупки - это и gpu на чипе Adreno 205, что делает работу с видео и графикой очень плавной и приятной; яркий и чёткий wvga (480 x 800) экран; две камеры - передняя и задняя (5Mpix); зарядка micro usb - он же и просто канал подключения к компу; wifi; gps; синхронизация с google account (адресная книга, почта, google reader, picasa); стандарный minijack; акселлерометр - он же g-sensor; pattern lock screen и куча софта на android market. Словом, value for money - я считаю, что платить 20круб за телефон подобного класса, но у которого чуть лучше экран - это перебор.

25 мая 2011 г.

java: деградация пула строк

Наверняка многие java программисты знают о существовании пула строк, который хранится в PermGen.

Кроме всего прочего каждая строка, которая была получена через
new String(data);
можно привести к каноническому представлению посредством вызова метода intern().

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

В своей статье вы уверены, что знаете про строки все? автор упоминает, что сложность intern() есть O(N), где N - размер пула строк.

Надо сказать меня сильно удивило - т.к. ещё в стародавние времена, когда стали доступны исходники sun hotspot jvm 1.4 (кстати, именно из них собирался blackdown-jdk) помню, что на уровне c++ пул строк сделан как Hashtable, у которого, как известно, сложность поиска O(1) - т.е константа.

8 мар. 2011 г.

Задачка: Честный стражник и лжец

Перед вами две двери:
одна из них ведет на волю, другая - прямая дорога к смерти.

Перед каждой из дверей сидит стражник, причем один из них - лжец, а второй говорит правду и только правду; однако вы не знаете, кто из них кто.

Задав только один вопрос только одному из стражников, определить дорогу на свободу.

Каков вопрос стоит задать ?
внимание! комментарии содержат ответ.

Serialization graph

Стандартная сериализация в java обладает рядом недостатков (см. Effective Java 2nd edition, автор Josh Bloch стр. 289), среди которых: медленная сериалазиция (см. jvm-serializers benchmarks) и сохранение полного графа объектов.
Однако, идея сохранения графа имеет и положительный аспект.

16 янв. 2011 г.

log2(1M)

Многие задачки, которые задают на собеседованиях появляются рано или поздно на ресурсах типа braingames.ru, что в общем-то и не удивительно.

Так например, fp-сообществу понравилась эта задачка, придуманная в нашем отделе.

По мотивам Top 25 Oddball Interview Questions Of 2010 и особенно вопроса, задаваемого в UBS
sqrt(2000) = ?
вспомнилась классическая задача, задаваемая у нас:
log2(1000000) = ?


Не предполагается, что ответ будет с точностью до какого знака после запятой (точки) - достаточно оценить с точностью до единицы.

1 янв. 2011 г.

Lock Coarsening, Biased Locking, Escape Analysis and others

Оптимизационные трюки, используемые при динамической компиляции jit'ом в java 6. В java 6 была существенно изменена (по сравнению с java 5) работа блокировок, существенно облегчив их, в java6u14 появился escape-анализ, который работает по-умолчанию, а так же много других интересных подходов.