Логические задачи. Два кувшина

Есть два пустых кувшина: на 3 и 5 литров. Необходимо в этих кувшинах принести ровно 7 литров. Никаких других способов измерения объема, кроме самих кувшинов использовать нельзя.

Ответ

1) Наполняем 3-литровый кувшин и переливаем в 5-литровый. Остаются незаполненными 2 литра
2) Снова наполняем 3-литровый кувшин и льем в 5-литровый, пока тот не станет полным. Теперь у нас в 3-литровом 1 литр.
3) Освобождаем 5-литровый и переливаем туда 1 литр из 3-хлитрового.
4) Наполняем 3-хлитровый и переливаем в 5-литровый. Теперь там 4 литра.
5) Наполняем 3-хлитровый. Итого у нас 7 литров.

Логические задачи. Русская рулетка

Я заряжаю барабан револьвера на 6 патронов. Ты успел подсмотреть, что патроны вставлены подряд. Я вращаю барабан, делаю выстрел - промах. Теперь твоя очередь. Ты бы хотел, что бы я вращал барабан или ты будешь делать следующий выстрел без вращения?

Ответ

Я бы не стал вращать.
Вероятность выстрела после вращения равна 2 из 6, т.е. 1/3
Если рассматривать вариант без вращения, то мы знаем, что на данный момент барабан находится в безопасной позиции. Так как патроны вставлены подряд, то после следующего нажатия курка может выпасть либо патрон, либо одна из 3-х пустых позиций. Таким образом один из 4-х вариантов должен выстрелить.
Итого, имеем вероятность выстрела: 1/3, если вращать и 1/4, если не вращать.

Логические задачи. Взвешиваем шары

Даны 8 бильярдных шаров. Все равного веса, кроме одного. Какие минимальное количество взвешиваний на двух чашах, понадобится, чтобы определить тяжелый?

Ответ

Можно определить за 2 взвешивания
1. Кладем на каждую чашу по 3 шара. Если чаши уравновешены, значит взвешиваем оставшиеся два

2. Если одна чаша перевешивает, берем из нее два шара, а третий убираем в сторону. Если чаши уравновешены, значит тяжелее третий, иначе, один из двух.

Логические задачи. Теннисный турнир

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

Задача взята из книги "Как сдвинуть гору Фудзи?" Уильяма Паундстоуна

Ответ

Чтобы появился победитель, он должен сыграть с каждым участником минимум одну игру. Т.е. требуется сыграть 127-1=126 матчей

Получаем список ключей в Map

Если в Map получить список ключей, а затем удалить ключ из этого списка, то данная запись пропадет из Map. Добавлять новые записи в этот список нельзя. Выдаст UnsupportedOperationException.

public class MapTest {
    public static void main(String[] args) {
        Map<String, Object> map = new HashMap<>();
        map.put("One", new Object());
        map.put("Two", new Object());
        map.put("Three", new Object());
        
        Set<String> mapKeys = map.keySet();
        mapKeys.remove("One");
        
        for (Entry entry : map.entrySet()) {
            System.out.printf("%s - %s%n", entry.getKey(), entry.getValue());
        }
        mapKeys.add("One");
    }
}

Программа выведет:
Three - java.lang.Object@19e421e
Two - java.lang.Object@106d4ea
Exception in thread "main" java.lang.UnsupportedOperationException

Как я пытался понять смысл метода finalize

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

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

Так вот, первое, что требовалось понять - назначение.

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

Не стоит полагаться на finalize для чистки данных. Во-первых, нет гарантии, что он будет вызван, т.к. где-то может остаться ссылка на объект. Во-вторых, нет гарантии на то, в какое время будет вызван метод. Это связано с тем, что после того, как объект становится доступным для сборки и, если в нем переопределен метод finalize, то он не вызывается сразу, а помещается в очередь, которая обрабатывается специально созданным для этого потоком. Стоит отметить, что в очередь на финализацию попадают только те объекты, в которых переопределен метод finalize.

Есть вероятность, что этот метод не будет вызван совсем. Это может произойти в момент, когда объект уже станет доступным для сборщика мусора и программа завершит свою работу.

Интересной особенностью метода является то, что он может снова сделать объект доступным, присвоив this какой-нибудь переменной, хотя так делать не рекомендуется, т.к. при восстановлении объекта, повторно finalize вызван не будет

Может случиться еще один редкий момент. У нас есть класс A, в котором реализован метод finalize. Мы создаем класс B extends A, в котором забываем про finalize. Объекты класса B содержат в себе много данных. Когда объекты классы B становятся ненужными, они попадут в очередь на финализацию и определенное время еще будут занимать память, вместо того, чтобы миновать этой очереди и сразу утилизироваться.

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

Исключения, брошенные в методе finalize, не обрабатываются потоком-финализатором, т.е. данный стектрейс скорее всего нельзя будет отследить.

Есть один способ быть уверенным, что finalize-методы были запущены для объектов, доступных для сборки: вызвать System.runFinalization() или Runtime.getRuntime().runFinalization(). Выход из метода осуществляется только тогда, когда все доступные методы объектов для финализации будут выполнены

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

Лучше вместо finalize писать методы типа close в java.io и вызывать их в блоке finally. Недостатком является то, что разработкик должен помнить, что ресурс после использования нужно закрыть. На помощь тут нам пришла Java SE 7 со своими try-with-resources

Но ведь этот метод для чего-то есть. Где и как его можно использовать? Есть ли примеры использования?

Finalize можно использовать как последний шанс закрыть ресурс, но никогда как первая или единственная попытка. Т.е. в дополнение к тому, что клиент может вызвать, например, метод close на объекте, представляющем ресурс. А может и забыть. Тогда можно попытаться ему помочь. Так сделано, например, в классе FileInputStream.java:

protected void finalize() throws IOException {
    if ((fd != null) &&  (fd != FileDescriptor.in)) {
        /*
         * Finalize should not release the FileDescriptor if another
         * stream is still using it. If the user directly invokes
         * close() then the FileDescriptor is also released.
         */
        runningFinalize.set(Boolean.TRUE);
        try {
            close();
        } finally {
            runningFinalize.set(Boolean.FALSE);
        }
    }
}

Данный подход часто используется в библиотеках Java.

PS. Прошу не принимать написанное за чистую правду. Я написал лишь то, как я понял прочитанный материал. Приму с радостью любые дополнения, критику и исправления.

Список использованной литературы:
How to Handle Java Finalization's Memory-Retention Issues
Java Finalize method call
java.lang. Class Object
10 points on finalize method in Java – Tutorial Example
Habrahabr. Finalize и Finalizer

Статическая и динамическая загрузка классов

Статическая загрузка классов - это всем привычная загрузка, которая производится автоматически. При запуске программы загрузчик классов рекурсивно загружает все классы, встречающиеся в программе, начиная с main-класса. Объекты таких классов создаются стандартным способом - через оператор new.

Динамическая загрузка классов производится через метод Class.forName(String className) или с использованием ClassLoader-а. Динамическая загрузка классов имеет смысл, когда требуется загрузить класс во время выполнения программы, когда нужно заменить класс, изменив, например, какую-то логику, не рестартуя приложения. Иногда может понадобиться загружать классы удаленно, например по http

Class animalClass = Class.forName("org.dmitrievs.Cat") ;
//Создается класс с конструктором по умолчанию
myAnimal = (Cat) animalClass.newInstance(); 

//загружаем класс через ClassLoader
ClassLoader classLoader = MainClass.class.getClassLoader();
Class aClass = classLoader.loadClass("com.jenkov.MyClass");
myClass = (MyClass) aClass.newInstance();

Один и тот же ClassLoader не может повторно загружать один и тот же класс, поэтому для повторной закрузки используется новый загрузчик. Подробнее можно почитать тут: http://tutorials.jenkov.com/java-reflection/dynamic-class-loading-reloading.html

Перегрузка методов

Всё ли в порядке с классом?

public class B {
    public int test(int i){return 1;};
    public int test(float i){return 2;};
    public int test(Integer i){return 3;};
    
    public static void main(String[] args) {
        B b = new B();
        System.out.printf("%d %d %d", b.test(1), b.test(1.0f), 
            b.test(Integer.valueOf(1)));
    }
}

Ответ

Output: 1 2 3 Класс скомпилируется и будет работать, т.к. значения считаются разными и попадут в нужные методы

Где начинаются проблемы?

Object[] o = new Integer[2];//1
o[0] = "fff"; //2
System.out.println(o[0]); //3

Ответ

Строка 1 отработает без проблем. 2 строка скомпилируется, массивы ковариантны. 3 строку компилятор тоже пропустит. А вот при запуске на 3-й строке выскочит ArrayStoreExceptions

Кто первый?

Что выведет программа?

class Tree {
    static int i[];
    public static void main(String... args)
    {
        int eye[] = new int[0];
        try {
            try {
                System.out.println(i.length);
            } finally{
                i = eye;
            }
        } catch (RuntimeException e) {
            e.printStackTrace();
            System.err.println(i.length);
        }
    }
}

Ответ

Output: 0
Cначала выполнится блок finally, затем программа попадет в блок с исключением.

Объявления массивов и коллекций

Можно ли выполнять следующие объявления?

Object[] array = new String[5]; //1
Object [] object = new String[5][5][5]; //2
List<Integer> list = new ArrayList<Number>(); //3
List<? extends Number> list = new ArrayList<Number>(); //4
List<Number> list2 = new ArrayList<Integer>(); //5
List<? super Integer> list3 = new ArrayList<Number>(); //6

Ответ

1. Можно. Массив String является подтипом массиват Object
2. Можно
3. Нельзя, т.к. колленция не является подтипом коллекции
4. Можно. Тут мы говорим, что коллекция может соржать любой тип, наследующий от Number. Считается, что Number наследует от Number
5. Нельзя, т.к. колленция не является подтипом коллекции
6. Можно. Коллекция может содержать объект любого типа, от которого наследует Integer

Определяем поведение для группы элементов в enum

Пример взят из книги Effective Java

// The strategy enum pattern
enum PayrollDay {
    MONDAY(PayType.WEEKDAY), 
    TUESDAY(PayType.WEEKDAY),
    WEDNESDAY(PayType.WEEKDAY), 
    THURSDAY(PayType.WEEKDAY),
    FRIDAY(PayType.WEEKDAY),
    SATURDAY(PayType.WEEKEND), 
    SUNDAY(PayType.WEEKEND);
    
    private final PayType payType;
    
    PayrollDay(PayType payType) { this.payType = payType; }
    
    double pay(double hoursWorked, double payRate) {
        return payType.pay(hoursWorked, payRate);
    }
    
    // The strategy enum type
    private enum PayType {
        WEEKDAY {
            double overtimePay(double hours, double payRate) {
                return hours <= HOURS_PER_SHIFT ? 0 :
                (hours - HOURS_PER_SHIFT) * payRate / 2;
            }
        },
        WEEKEND {
            double overtimePay(double hours, double payRate) {
                return hours * payRate / 2;
            }
        };
        
        private static final int HOURS_PER_SHIFT = 8;
        
        abstract double overtimePay(double hrs, double payRate);
        
        double pay(double hoursWorked, double payRate) {
            double basePay = hoursWorked * payRate;
            return basePay + overtimePay(hoursWorked, payRate);
        }
    }
}

Создание объектов с переменным числом параметров. Три способа.

1. Простой и понятный, но не самый изящный способ - использовать паттерн Телескоп

public class Menu {
    private final String salad; //optional
    private final String soup; //required
    private final String second; //required
    private final String tea; //optional
    private final String desert; //optional
    private final String fruits; //optional
    Menu(String soup, String second) {
        this(soup, second, null);
    }
    Menu(String soup, String second, String salad) {
        this(soup, second, salad, null);
    }
    Menu(String soup, String second, String salad, String tea) {
        this(soup, second, salad, tea, null);
    }
    Menu(String soup, String second, String salad, String tea, String desert) {
        this(soup, second, salad, tea, desert, null);
    }
    Menu(String soup, String second, String salad, String tea, String desert, String fruits) {
        this.soup = soup;
        this.second = second;
        this.salad = salad;
        this.tea = tea;
        this.desert = desert;
        this.fruits = fruits;
    }
}

2. Использовать класс с пустым конструктором и множеством сеттеров. Такой паттерн называется JavaBeans. Его недостатками являются возможность создать недоконструированный объект, а так же невозможность создавать Immutable-объекты

public class Menu {
    private String salad; //optional
    private final String soup; //required
    private final String second; //required
    private String tea; //optional
    private String desert; //optional
    private String fruits; //optional
    Menu(String soup, String second) {
        this.soup = soup;
        this.second = second;
    }

    public void setSalad(String salad) {
        this.salad = salad;
    }
    
    public void setTea(String tea) {
        this.tea = tea;
    }
    
    public void setDesert(String desert) {
        this.desert = desert;
    }
    
    public void setFruits(String fruits) {
        this.fruits = fruits;
    }
}

3. Использовать шаблон Строитель. Немного усложненная структура, но зато как красиво можно собирать объекты.

public class Menu {
    private final String soup; //required
    private final String second; //required
    
    private final String salad; //optional
    private final String tea; //optional
    private final String desert; //optional
    private final String fruits; //optional
    
    public static class MenuBuilder {
        private final String soup; //required
        private final String second; //required
        
        private String salad; //optional
        private String tea; //optional
        private String desert; //optional
        private String fruits; //optional
        
        MenuBuilder(String soup, String second) {
            this.soup = soup;
            this.second = second;
        }
        
        public MenuBuilder setSalad(String salad) {
            this.salad = salad;
            return this;
        }
        
        public MenuBuilder setTea(String tea) {
            this.tea = tea;
            return this;
        }
        
        public MenuBuilder setDesert(String desert) {
            this.desert = desert;
            return this;
        }
        
        public MenuBuilder setFruits(String fruits) {
            this.fruits = fruits;
            return this;
        }
        
        public Menu build() {
            return new Menu(this);
        }
    }
    
    private Menu(MenuBuilder builder) {
        soup = builder.soup;
        second = builder.second;
        salad = builder.salad;
        tea = builder.tea;
        desert = builder.desert;
        fruits = builder.fruits;
    }
    
    public static void main(String[] args) {
        Menu menu = new Menu.MenuBuilder("soup", "second")
            .setDesert("desert")
            .setFruits("fruits")
            .setSalad("salad")
            .setTea("tea")
            .build();
    }
}

Вставка данных в таблицу, если запись в ней отсутствует. Oracle

INSERT INTO table
SELECT trunc(sysdate), 0
FROM dual
WHERE NOT EXISTS (
  SELECT NULL 
  FROM table
  WHERE day=trunc(sysdate)
);

Чем отличается абстрактный класс от интерфейса?

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

В абстрактном классе может присутствовать реализация методов, конструкторов, переменных состояния, а так же объявление методов, которые должны быть реализованы наследниками. В интерфейсе не может быть реализации методов, он может содержать список методов, которые должны быть переопределены.

Один класс может напрямую наследовать только от одного абстрактного класса. Реализаций интерфейса может быть несколько для одного класса. Осносное назначеине - решение проблемы с множественным наследованием. Т.е. класс может быть одновременно нескольких типов. Так же интерфейс помогает избавиться от ромбовидного наследования

Абстрактный класс должен служить для определения общей функциональности объектов, а интерфейс должен описывать, через какие методы можно обращаться в объекту.

Как работает substring для объектов String в Java?

Как работает метод substring для объектов String в Java?

Ответ

Работа метода substring зависит от версии Java. Начиная с версии 7u6, после вызова метода substring создается новый объект String, через конструктор

public String(char value[], int offset, int count) {
    ...
    ...
    this.value = Arrays.copyOfRange(value, offset, offset+count);
}

где char value[] исходный массив символов строки, offset - смещение и count - количество символов. Из кода видно, что создается новый массив, хранящий символы. В версиях до Java 7u6 дела обстоят иначе: так же создается новый объект String, но используется старый массив char value[].

// Package private constructor which shares value array for speed.
String(int offset, int count, char value[]) {
    this.value = value;
    this.offset = offset;
    this.count = count;
}

Т.е. если исходная строка имеет очень большой размер, то создав короткий substring от нее, мы будем хранить в памяти большой массив из-за оставшейся на него ссылки. Это не позволяет сборщику мусора собрать оригинальную строку, из-за чего может возникнуть утечка памяти. Изначально это было сделано для ускорения создания подстрок, но было отмечено как баг и устранено в версии Java 7u6.

Чем отличается создание строки через new от создания через литерал?

String s1 = new String("test1");
String s2 = "test2";

Ответ

При создании строки через new, она не попадает в string pool. Что бы она туда попала, необходимо сделать s1.intern() или создать строку через литерал. String pool служит для того, что бы не создавались повторно существующие строки.

Что выведет программа?

int i = 0;
if (i == 1) if (i == 0) i = 10; else i = 20;
System.out.println(i);

Ответ

0
"Else" принадлежит к ближайшему "if" слева. В связи с возможностью неоднозначного понимания, рекомендуется расставлять скобки.

int i = 0;
if (i == 1) {
    if (i == 0) {
        i = 10;
    } else {
        i = 20;
    }
}
System.out.println(i);

Бинарный поиск

Одним из основных алгоритмов поиска является бинарный поиск. Он работает только с отсортированными данными, за счет этого достигается большая скорость поиска: O(logN). Принцип работы алгоритма прост: находим середину массива данных, проверяем, больше, меньше и равно искомое значение значению в середине. Если равно, значит нашли. Если искомое больше, значит дальше ищем только в правой половине, если меньше - в левой. Т.е. с каждой итерацией количество данных для поиска делится надвое.

public class Binary {
    public static void main(String[] args) {
        int[] arr = { 1,12,23,34,55,61,67,88,89,101 };
        System.out.println(rank(55, arr));
    }
    
    public static int rank(int val, int[] arr) {
        return rank(val, arr, 0, arr.length-1);
    }
    
    private static int rank(int val, int[] arr, int lo, int hi) {
        if (lo > hi) return -1;
        
        int mid = lo + (hi - lo) / 2;
        
        if (val < arr[mid]) {
            return rank(val, arr, lo, mid - 1);
        } else if (val > arr[mid]) {
            return rank(val, arr, mid + 1, hi);
        } else {
            return mid;
        }
    }
}

Как проверить, является ли число простым

Простые числа являются элементарными строительными блоками натуральных чисел. Простые числа применяются, например, в криптографии. За нахождение простых чисел из более чем 100 000 000 и 1 000 000 000 десятичных цифр назначена премия в 150 000 и 250 000 долларов США, говорится в Википедии.

/**
 * Является ли число простым?
 */
public static boolean isPrime(int N) {
    if (N < 2) return false;
    for (int i = 2; i*i <= N; i++)
        if (N % i == 0) return false;
    return true;
}