Задачка: Перестановки в массиве

Дан массив
[ a₁, a₂, ... a_n, b₁, b₂, ... b_n ]

Необходимо переставить элементы в массиве, так, чтобы получился

[ a₁, b₁, a₂, b₂, ... a_n, b_n ]

замечание: дополнительная память O(1), сложность < O(n²)

java: Adaptive throttling, Part 1

Типичная проблема, которая возникает при обработке большого потока сообщений:

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


При этом существуют некоторые ограничения на поток данных :

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

На диаграмме приведён пример разрешения проблемы: нагребатор™ работает на нитке T₁, а следовательно разгребатор™ на нитке T₂

• за время обработки события типа A успевают прийти новые события как типа B, так и A
• после обработки события типа B необходимо обработать наиболее актуальное событие типа A

Проблема осложняется ещё тем, что может быть несколько нагребаторов™, при этом каждый нагребатор™ может порождать только события одного типа; так и есть потребность в нескольких разгребаторах™ - при этом

Терминология. Stream есть поток данных, тогда как thread есть нитка или нить выполнения. И не стоит путать потоки с нитками.

Задачка: развернуть односвязанный список

Задан односвязанный список, например:

A -> B -> C -> ... -> X -> Y -> Z

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

Z -> Y -> X -> ... -> C -> B -> A

Сложность: O(N), доступная память: O(1).

замечание: можно модифицировать исходный список.

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

Задачки: Количество сообщений в минуту

Есть некоторый поток сообщений, идущий не равномерно.

Например, с 0 - 10 секунду может прийти 1 сообщение, в следующие 10 ещё 5, потом 10, потом 100 и т.д и опять наступит затишье.

В целях мониторинга хочется иметь представление о точном количестве полученных сообщений (скользящим окном) за крайнюю минуту.

Пояснение: если мы запрашиваем кол-во сообщений в 13:12:05, то должны получить кол-во сообщений с 13:11:05 по 13:12:05. Запрос в 13:12:57 отображает число сообщений с 13:11:57 по 13:12:57.

При этом не интересует сколько было получено две минуты назад, только реальные актуальные цифры. Допускается огрубление с точностью до секунды.

Ограничения: память O(1), сложность O(1), одна нитка выполнения.

p.s. я не знаю, существует ли какое-то классическое и/или единственно верное решение или нет, уже засыпая я смог придумать вполне приемлемое для меня решение, но которое расходует больше, чем 3-5 переменных.

Задачка: <L| и |R>

Заданы два оператора:
L : L(a,b) => ( 2 * a - b , b )
R : (a,b)R => ( a, 2 * b - a )
и начальная точка (a, b) = (0, 1).

Существует последовательность операторов L и R, такая, что в результате либо a = N, либо b = N.

Например:
Число 21 может быть получено кратчайшей последовательностью L L R L R:

  (a, b):   L(a, b) | (a, b)R
  (0, 1):   (-1, 1) | (0, 2)
 (-1, 1):   (-3, 1) | (-1, 3)
 (-3, 1):   (-7, 1) | (-3, 5)
 (-3, 5):  (-11, 5) | (-3, 13)
(-11, 5):  (-27, 5) | (-11, 21)


Какова минимальная длина последовательности с помощью которой можно получить N ?

Замечание №1: число N может лежать в диапозоне -2³¹ .. 2³¹-1.
Замечание №2: сложность O(log(N)).
Замечание №3: досупная память O(1).

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

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

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

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) и сохранение полного графа объектов.
Однако, идея сохранения графа имеет и положительный аспект.