Статьи
YouTube-канал
Отзывы

Статьи с тэгом «головоломки»

Решето Эратосфена для поиска простых чисел

17 июня 2022

Тэги: Java, Collections, алгоритмы, головоломки, руководство, YouTube.

Ранее я уже приводил Алгоритм поиска простых чисел методом перебора делителей. Эта реализация хороша, если вам нужно ровно N первых простых чисел. Но если вы ищете простые числа в некотором диапазоне (скажем, не превосходящие 1 000 000), то лучше воспользоваться более быстрым алгоритмом, который называется «решето Эратосфена».

Читать полностью...

Алгоритм чисел Фибоначчи на Java и Kotlin

6 мая 2022

Тэги: алгоритмы, Java, головоломки, Kotlin.

Немного теории

На собеседованиях по алгоритмам любят давать такую задачку, как нахождение чисел из последовательности Фибоначчи. Эта числовая последовательность названа в честь Леонардо Пизанского - известного математика Средневековья.

Сама последовательность довольно проста. Она состоит из целых положительных чисел, где каждый следующий элемент равен сумме двух предыдущих. Например, 2 = 1 + 1, 3 = 2 + 1, 5 = 3 + 2.

Последовательность начинается с 0 и 1:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ...

Иногда в этой последовательности принято пропускать 0 и начинать её с двух единиц, однако официально она начинается именно с 0.

Читать полностью...

Проверка вложенности скобок

22 марта 2021

Тэги: Java, алгоритмы, головоломки, Java 8.

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

Зачем нужно проверять вложенность скобок

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

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

Читать полностью...

Как обменять значения двух переменных без буфера

1 мая 2018

Тэги: головоломки, Java, алгоритмы.

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

int buffer = a;
a = b;
b = buffer;

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

А что, если нам нужно обменять значения числовых переменных между собой, не создавая новых переменных?

Читать полностью...

Передача null в перегруженный метод

4 января 2018

Тэги: ООП, Java, головоломки.

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

interface MyInterface {
    void doWork();
}

class MyBaseObject implements MyInterface {
    @Override
    public void doWork() {
        System.out.println("Base");
    }
}

class MyChildObject extends MyBaseObject {
    @Override
    public void doWork() {
        System.out.println("Child");
    }
}
Читать полностью...

Произведение всех чисел в столбце таблицы одним SQL запросом

3 января 2018

Тэги: SQL, PostgreSQL, головоломки.

Я думаю, каждый знает такую функцию SQL, как SUM(). Она позволяет посчитать сумму всех значений по определённому столбцу. Но что, если нам вдруг понадобится посчитать не сумму, а произведение всех значений?

Как ни странно, функция SUM() нам тоже пригодится. Как нам от произведения перейти к сумме? Вспомним начала матанализа: логарифм произведения равен сумме логарифмов. Будем использовать натуральный логарифм LN() в паре с функцией возведения экспоненты в степень EXP()

Привожу пример для postgresql, но должно работать и в других СУБД:

select exp(sum(ln(field))) from tab
Читать полностью...