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

Дан (очень) большой массив целых чисел, необходимо отсортировать по частоте появления элемента в массиве.
Ограничения: постоянная память, сложность 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 ]

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.

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, упоминают об этом.

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.

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

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

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

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

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

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

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

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

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

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

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круб за телефон подобного класса, но у которого чуть лучше экран - это перебор.

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

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

Кроме всего прочего каждая строка, которая была получена через

new String(data);

можно привести к каноническому представлению посредством вызова метода intern().

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

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

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

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

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

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

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

Каков вопрос стоит задать ?

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

Serialization graph

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

log2(1M)

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

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

По мотивам Top 25 Oddball Interview Questions Of 2010 и особенно вопроса, задаваемого в UBS

sqrt(2000) = ?

вспомнилась классическая задача, задаваемая у нас:

log₂(1000000) = ?

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

Lock Coarsening, Biased Locking, Escape Analysis and others

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