Несколько раз мне попадалась задача из разряда «собеседование в Google»:
нужно реализовать стек, хранящий целые числа, в котором дополнительно должна существовать операция max(), возвращающая максимальный элемент за O(1) времени и с использованием O(1) дополнительной памяти (в сравнении со стеком без этой операции).

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

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

Один из вариантов эффективного решения — умножать по модулю, вообще при этом не используя операции деления, с помощью алгоритма Монтгомери.

Про него я и хотел бы поговорить.

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

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

На сайте hackerrank.com есть отличная задача. По заданному массиву short[] A; найти максимальное количество его подмассивов, xor элементов которых будет одинаковым. Сам этот xor тоже нужно найти.

Максимальная длина массива равна 10⁵, так что квадратичный алгоритм не укладывается в лимит по времени исполнения. Я в своё время с этой задачей не справился и сдался, решив подсмотреть авторское решение. И в этот момент я понял почему не справился — автор предлагал решать задачу через дискретное преобразование Фурье.

Когда-то давно, году в 2013-м, на глаза мне попался следующий код:

>>>+[[-]>>[-]++>+>+++++++[<++++>>++<-]++>>+>+>+++++[>++>++++
++<<-]+>>>,<++[[>[->>]<[>>]<<-]<[<]<+>>[>]>[<+>-[[<+>-]>]<[[
[-]<]++<-[<+++++++++>[<->-]>>]>>]]<<]<]<[[<]>[[>]>>[>>]+[<<]
<[<]<+>>-]>[>]+[->>]<<<<[[<<]<[<]+<<[+>+<<-[>-->+<<-[>+<[>>+
<<-]]]>[<+>-]<]++>>-->[>]>>[>>]]<<[>>+<[[<]<]>[[<<]<[<]+[-<+
>>-[<<+>++>-[<->[<<+>>-]]]<[>+<-]>]>[>]>]>[>>]>>]<<[>>+>>+>>
]<<[->>>>>>>>]<<[>.>>>>>>>]<<[>->>>>>]<<[>,>>>]<<[>+>]<<[+<<
]<]

Это интерпретатор языка Brainfuck, написанный на самом Brainfuck. Ссылки на оригинал у меня не осталось, только код, так что автора я назвать не смогу.

Мне всегда было безумно интересно узнать, как он работает. И теперь я решил наконец-то это сделать!

java.util.concurrent.CompletableFuture - класс не новый. Он предстал перед нами во всём своём величии в 2014-м году вместе с выпуском Java 8. Много лет с тех пор прошло, а проще он не стал.

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

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

Я решил всерьёз выяснить, чему равна эта вероятность в зависимости от длины случайной строки? Можно ли получить явную математическую формулу для ответа? Что, если взять другое слово? Что, если взять другой алфавит?

Обо всём по порядку.

Уверен, многие из читающих иногда занимались на уроках бесполезной ерундой вместо того, чтобы слушать учителя. Я точно так делал, и одним из способов убить время были игры на бумаге. Особенно интересной мне казалась игра на превью (название которой мне до сих пор неизвестно), а причин тут две: она не требует второго человека и её можно завершить! Правда сделать это удавалось крайне редко. Долгое время мне было интересно, насколько простым может оказаться решение, и сейчас, спустя много лет, не составит труда найти его программным путём.

Существует классическая задача для собеседований, часто формулируемая следующим образом:

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

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

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

Конструктор java.lang.Class является одной из самых охраняемых сущностей в языке Java. В спецификации чётко сказано, что объекты типа Class может создавать только сама JVM и что нам тут делать нечего, но так ли это на самом деле?

Предлагаю погрузиться в глубины Reflection API (и не только) и выяснить, как там всё устроено и насколько трудно будет обойти имеющиеся ограничения.

Периодически на хабре можно встретить статьи о том, какие невероятные вещи можно сделать на шаблонах C++: конечные автоматы, лямбда-исчисление, машина Тьюринга и многое другое.

Параметризованные типы в Java традиционно считаются лишь пародией на шаблоны C++ (несмотря на то, что их даже сравнивать как-то некорректно), и причины этого несложно понять. Тем не менее не всё так плохо, и компилятор Java можно заставить производить во время проверки типов любые вычисления, лишь бы хватило оперативной памяти. Конкретный способ это сделать был описан в ноябре 2016-го года в этой прекрасной публикации. Его я и хотел бы объяснить.

Для затравки приведу следующий код. Корректен ли он? Предлагаю скомпилировать и проверить, угадали ли вы результат.

class Sample {

    interface BadList<T> extends List<List<? super BadList<? super T>>> {}

    public static void main(String[] args) {
        BadList<? super String> badList = null;
        List<? super BadList<? super String>> list = badList;
    }
}

Разберёмся, почему компилятор ведёт себя именно так (я бы не назвал это багом), как понимание данных причин может быть полезно и причём тут машина Тьюринга.

Я множество раз слышал о том, что дизайн Generic типов в Java является неудачным. По большей части претензии сводятся к отсутствию поддержки примитивных типов (которую планируют добавить) и к стиранию типов, а конкретнее — невозможности получить фактический тип параметра в рантайме. Лично я не считаю стирание типов проблемой, как и дизайн Generic-ов плохим. Но есть моменты, которые меня порядком раздражают, но при этом не так часто упоминаются.

1

Например, мы знаем, что метод Class#getAnnotation параметризован и имеет следующую сигнатуру: public <A extends Annotation> A getAnnotation(Class<A> annotationClass). Значит, можно писать вот такой код:

Deprecated d = Object.class.getAnnotation(Deprecated.class);

Тут я решаю вынести Object.class в отдельную переменную и код перестаёт компилироваться:

Class clazz = Object.class;
// incompatible types:
// java.lang.annotation.Annotation cannot be converted to java.lang.Deprecated
Deprecated d = clazz.getAnnotation(Deprecated.class);

Где я ошибся?

id = x => x
double = f => x => f (f (x))

Многие из вас наверняка знакомы с такой головоломкой, как судоку. Возможно, даже реализовывали программу для автоматического решения. На хабре тема судоку обсуждалась уже множество раз, и, как показывает практика, практически любой способ автоматического нахождения ответа в итоге сводится к направленному перебору. И это вполне естественно, ведь даже ручные решения придерживаются тех же принципов. Но что, если поступить иначе?
В данной статье я рассмотрю один очень занятный метод, предложенный в 2012 году, основанный на строго математическом подходе. Программная реализация прилагается.

Представьте, что есть у нас объект Function<A, B> foo = SomeClass::someMethod; Это лямбда, которая гарантированно является ссылкой на не статический метод. Как можно из объекта foo достать экземпляр класса Method, соответствующий написанному методу?

Если в кратце, то никак, информация о конкретном методе хранится исключительно в байткоде (всякие там инструментации я не учитываю). Но это не мешает нам в определённых случаях получить желаемое в обход.