Статьи
YouTube-канал

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

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

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
Читать полностью...