Кофе-брейк #205. 100 наиболее распространенных вопросов на собеседовании по Java для разработчиков с опытом работы от 1 до 3 лет. Бинарный поиск в Java — как он работает?

100 наиболее распространенных вопросов на собеседовании по Java для разработчиков с опытом работы от 1 до 3 лет

Источник: Medium Вашему вниманию предлагается подборка наиболее распространенных вопросов на собеседовании, которые могут встретиться Java-разработчику с опытом работы от 1 до 3 лет. Вы Java-программист с опытом работы от 1 до 3 лет? Поздравляем, вы прошли начальный уровень и теперь пришло время продемонстрировать свои навыки на новых собеседованиях. Чтобы помочь вам подготовиться к интервью, мы составили список из 100 самых популярных вопросов для собеседования по Java, с которыми вы можете столкнуться. Вопросы охватывают Java Foundation, контейнеры, многопоточность, отражение, копирование объектов, Java Web, исключения, Интернет и Spring MVC.

Вопросы по Java Foundation

• В чем разница между JDK и JRE?
• В чем разница между == и equals?
• Верно ли то, что equals() должно быть true, если два объекта имеют одинаковый hashCode()?
• В чем суть функции final в Java?
• Что означает Math.round(-1.5) в Java?
• Является ли String фундаментальным типом данных?
• Какие есть классы для работы со строками в Java? В чем разница между ними?
• Является ли строка str=”i” синонимом строки str=new String(“i”)?
• Каков наилучший способ инвертировать строку?
• Каковы общие методы класса String?
• Нужно ли иметь абстрактные методы в абстрактных классах?
• В чем разница между обычным классом и абстрактным классом?
• Можно ли использовать final для модификации абстрактных классов?

Вопросы о контейнерах

• Что такое Java-контейнеры?
• В чем разница между Collection и Collections?
• В чем разница между List, Set и Map?
• В чем разница между HashMap и Hashtable?
• Что лучше выбрать: HashMap или TreeMap?
• Каков принцип реализации HashMap?
• Каков принцип реализации HashSet?
• В чем разница между ArrayList и LinkedList?
• Как преобразовать массив в List?
• В чем разница между ArrayList и Vector?
• В чем разница между массивом (array) и Arraylist?
• В Queue, в чем разница между poll() и remove()?
• Что такое потокобезопасные классы коллекций?
• Что такое итератор?
• Каково назначение итератора? Каковы характеристики?
• В чем разница между Iterator и ListIterator?

Вопросы о многопоточности

• В чем состоит разница между параллелизмом и параллелизмом в значении Concurrency?
• В чем состоит разница между потоком и процессом?
• Что такое поток демона (daemon thread)?
• Сколько существует различных способов создания threads?
• В чем разница между runnable и callable?
• Какими могут быть состояния потока (thread)?
• В чем разница между sleep() и wait()?
• В чем состоит разница между notify() и notifyAll()?
• В чем состоит разница между thread run() и thread start()?
• Сколькими способами можно создать пул потоков?
• Каковы различные состояния пула потоков?
• В чем разница между методами submit() и execute() в пуле потоков?
• Как можно обеспечить безопасность многопоточных операций в Java-программе?

Вопросы об отражении

• Что такое отражение (reflection)?
• Что такое сериализация Java? Когда необходима сериализация?
• Что такое динамические прокси? В каких приложениях их можно использовать?
• Как вы используете динамические прокси?

Вопросы о копировании объектов

• Зачем нужно клонирование?
• Как работает клонирование объектов?
• В чем разница между глубоким и поверхностным копированием?

Вопросы по Java Web

• В чем разница между jsp и сервлетом?
• Что такое встроенные объекты jsp? Каковы их обязанности?
• Что такое четыре области jsp?
• В чем разница между сеансом и файлом cookie?
• Какова процедура сеанса?
• Можно ли использовать сеанс, если файлы cookie клиента отключены?
• В чем разница между spring mvc и struts?
• Как избежать SQL-инъекций?
• Что такое XSS-атака и как ее избежать?
• Что такое CSRF-атака и как ее избежать?

Вопросы на собеседовании об исключениях

• В чем разница между throw и throws?
• В чем разница между терминами final, finally и finalise?
• Какую часть последовательности try-catch-finally можно опустить?
• Если в try-catch-finally возвращается catch, будет ли final по-прежнему выполняться?
• Каковы некоторые примеры общих классов исключений?

Вопросы об Интернете

• Что означают коды ответа HTTP 301 и 302? В чем разница?
• В чем разница между forward и redirect?
• В чем разница между tcp и udp?
• Почему для tcp требуется три рукопожатия (handshakes), а не два? Почему?
• Как генерируются липкие пакеты tcp (sticky packets)?
• Каковы семь уровней модели OSI?
• В чем разница между запросами get и post?
• Как работает междоменная реализация?
• Каков принцип реализации JSONP?

Вопросы о шаблонах проектирования

• Какие шаблоны проектирования вам известны?
• В чем разница между простой и абстрактной фабрикой?

Вопросы по Spring

• Каковы преимущества использования Spring?
• Что такое aop?
• Что такое ioc?
• Каковы основные модули Spring?
• Каковы наиболее часто используемые методы injection в Spring?
• Является ли Spring bean потокобезопасным?
• Как много областей действия bean-компонентов может поддерживать Spring?
• Какими способами Spring автоматически собирает bean-компоненты?
• Каковы различные методы реализации транзакций Spring?
• Что такое spring-изоляция транзакций?
• Каков поток выполнения Spring MVC?
• Какие компоненты Spring MVC вы знаете?
• Что делает @RequestMapping?
• Какова функция @Autowired?

Бинарный поиск в Java — как он работает?

Источник: Medium Изучив это руководство, вы узнаете о том, как работает бинарный поиск в Java и в каких ситуациях его нужно использовать.

Что такое бинарный поиск?

Бинарный (двоичный) поиск — это алгоритм поиска, который делит пополам заранее отсортированный массив данных, чтобы обнаружить в нем нужный элемент. Бинарный поиск быстрее, чем линейный поиск, и работает только в отсортированном наборе элементов.

Как работает бинарный поиск?

Основная идея бинарного поиска состоит в том, чтобы разделить массив пополам и получить целевой элемент из первой части массива. Если он найден, вторая половина будет исключена. Это делает поиск намного быстрее, чем при любой другой модели поиска. Представьте, что у нас есть массив из 8 элементов, как показано на следующем рисунке: Мы хотим проверить, есть ли в массиве число 16, и определить его позицию в массиве. В данном примере он у нас в виде элемента, присутствующего на позиции 5. Что делает бинарный поиск, так это разбивает массив на две части и проверяет, присутствует ли искомое число в первой разделенной части: Алгоритм сравнивает искомый элемент со средним значением массива. Если они неравны, то эта половина исключается и поиск переходит на вторую половину. Давайте применим бинарный поиск на практике, создав пример на Java, который делает именно то, что было описано выше:

public int binarySearch(int[]array, int target, int low, int high) {
        int middlePosition = (low + high) / 2;
        int currentNumber = array[middlePosition];

        if (low > high) {
            return -1;
        }

        if (target == currentNumber) {
            return middlePosition;
        }

        if (target < currentNumber) {
            return binarySearch(array, target, low, middlePosition - 1);
        } else {
            return binarySearch(array, target, middlePosition + 1, high);
        }
    }

Если вы заметили, мы используем технику рекурсии вместо обычного while. А теперь давайте разбираться, что дальше. Сначала мы создаем метод binarySearch, который получает массив, искомую цель и два аргумента: low и high.

binarySearch(int[]array, int target, int low, int high) {
}

Параметр low будет первым индексом нашего массива, в первый раз он всегда будет равен 0, а high размера массива равен -1. Затем мы создаем переменные middlePosition и currentPosition, в которых будет храниться значение вычисления, что означает (low(0) + high(7))/2.

int middlePosition = (low + high) / 2;
int currentNumber = array[middlePosition];

Значение будет эквивалентно 3, оно находится в середине массива. Обратите внимание, что здесь речь идет о позиции массива 3, которая эквивалентна числу 8. В последовательности у нас есть первая проверка, которая означает, что мы не нашли нашу цель в массиве, и теперь мы возвращаем -1, что указывает, что цель не была найдена.

if (low > high) {
   return -1;
}

Далее мы должны проверить, точно ли цель совпадает со средней позицией массива. Если да, то мы нашли наш элемент и завершаем поиск.

if (target == currentNumber) {
   return middlePosition;
}

После этих двух проверок мы начинаем бинарный поиск с рекурсией.

if (target < currentNumber) {
    return binarySearch(array, target, low, middlePosition - 1);
} else {
   return binarySearch(array, target, middlePosition + 1, high);
}

Обратите внимание, что в первой итерации наша цель target(16) не меньше, чем currentNumber(8) (позиция 3 в массиве). Поэтому наш код переходит к вызову else, снова вызывая функцию и устанавливая младшую переменную со значением 4 — middlePosition(3) + 1 = 4, в результате чего наш поиск идет вправо и достигает позиции 4. Далее наш код переходит к значению 16 и, таким образом, возвращает этот индекс. Теперь давайте проверим нашу функцию:

@Test
    public void should_return_position_5_when_target_is_16() {
        int[] array = {3, 5, 7, 8, 13, 16, 17, 20};
        int target = 16;

        BinarySearch b = new BinarySearch();

        int position = b.binarySearch(array, target, 0, array.length - 1);
        Assertions.assertEquals(position, 5);
    }

    @Test
    public void should_return_minus1_when_target_is_notFound() {
        int[] array = {3, 5, 7, 8, 13, 16, 17, 20};
        int target = 33;

        BinarySearch b = new BinarySearch();

        int position = b.binarySearch(array, target, 0, array.length - 1);
        Assertions.assertEquals(position, -1);
    }

Заметьте, что мы создали два теста. Сначала мы проверяем, находится ли цель 16 в нашем массиве. А второй тест предназначен для проверки, отправляем ли мы элемент, которого нет в массиве, здесь тест возвращает -1.

Что более эффективно: простой цикл или бинарный поиск?

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

Простой цикл:

public class SimpleLoopSearch {
    public int searchNumberPosition(int[] array, int target) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] == target) {
                return i;
            }
        }
        return -1;
    }

}

Main:

public static void main(String[] args) {

        int[] array = new int[700000000];
        int target = 680000000;

        for (int i=0; i<array.length; i++) {
            array[i] = i + 1;
        }

        BinarySearch b = new BinarySearch();

        System.out.println(" Binary Search: ");

        System.out.println(LocalDateTime.now());
        b.binarySearch(array, target, 0, array.length - 1);
        System.out.println(LocalDateTime.now());

        System.out.println(" Simple Loop Search: ");

        SimpleLoopSearch s = new SimpleLoopSearch();
        System.out.println(LocalDateTime.now());
        s.searchNumberPosition(array, target);
        System.out.println(LocalDateTime.now());

    }

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

Заключение

Бинарный поиск — важный инструмент для работы с большими объемами данных. Он эффективный, надежный и незаменимый способ работы в программировании.