Собеседование без теоретических вопросов, выглядит следующим образом: Дано 3 задачи. За отведенное время (1 час) в реал тайме необходимо их решить. Решение должно быть оптимизированным и подходить по требованию поставленного условия.
Решение задачи должно быть сопровождено рассуждениями, так как нанимателю важно видеть аналитические способности и склад ума собеседуемого.
Задача:
Дан отсортированный массив. Необходимо написать метод, который проверяет, есть ли указанный элемент в массиве. Массив может быть очень большим. Тип данных – int. Массив одномерный.
Решение:
Самое простое решение, это конечно же линейный перебор с помощью простого цикла
public boolean linearSearch(int[] array, int number) {
for(int i = 0; i < array.length; i++) {
if (array[i] == number) {
return true;
}
}
return false;
}, но данный метод очень плохо работает с большими массивами, так как в наихудшем случае (отсутствия элемента) придется перебрать все элементы массива. Сложность такого алгоритма составляет O(n) - т.е. для массива с 1_000_000 элементов потребуется 1_000_000 шагов.
Правильным подходом в этом случае является бинарный поиск, который как раз предназначен для отсортированных массивов.
public boolean binarySearch(int[] array, int number){
int low = 0;
int high = array.length - 1;
while(low <= high) {
int mid = (low + high) / 2;
if (array[mid] == number) return true;
if (array[mid] > number) high = mid - 1;
if (array[mid] < number) low = mid + 1;
}
return false;
}, где на каждой итерации происходит разделение массива на 2, вследствие чего ненужная половина (старшая или младшая) просто отбрасывается, что позволяет нам оптимизировать алгоритм до сложности O(log(n)) - т.е. для массива с 1_000_000 элементов - в наихудшем случае потребуется 20 шагов!
Задача:
Реализуйте класс “Циклический Буфер”. Это коллекция с ограничением по размеру. Если при добавлении нового элемента в буфер оказывается, что он уже содержит максимальное количество элементов, самый старый элемент перезаписывается новым. Должны поддерживаться следующие операции:
- добавить элемент,
- получить текущее количество элементов,
- получить элемент по индексу,
- удалить элемент по индексу.
Решение:
Прежде чем приступить к реализации класса цикло-буффера, хорошим тоном будет определить интерфейс для этого класса(как в коллекциях), контрактами которого будут наши 4 метода:
- void add(E e);
- int size();
- E get(int index);
- void remove(int index);
public interface Buffer<E> {
void add(E e);
int size();
E get(int index);
void remove(int index);
}Наша интерфейс и реализующий его класс обязаны быть обобщенными, чтобы удобно было работать с любыми типами классов.
Задача:
Написать класс TestClass. Создание объектов этого класса должно быть невозможно снаружи этого класса. Добавить статический метод getInstance(), создающий и возвращающий экземпляр класса TestClass. Если метод уже вызывался, он должен возвращать ранее созданный объект. Предусмотреть, что TestClass.getInstance() может быть вызван из нескольких потоков.
**Решение:**
Чтобы реализовать задачу на примитивном уровне, достаточно применить широко известный паттерн Singleton:
public class TestClass {
private static TestClass instance;
public static TestClass getInstance() {
if (instance == null) {
instance = new TestClass();
}
return instance;
}
private TestClass() {
throw new AssertionError();
}
}Где единственный экземпляр нашего класса хранится в статической внутренней переменной, и при вызове getInstance() проверяется, была ли эта переменная привязана к нашему классу. Конструктор же делаем приватным, чтобы обезопасить себя от вызова ненужных инстансов, более того для убедительности, что инстанс не будет вызван через рефлексию - пробрасываем AssertionError при попытке взлома.
Но, главная проблема в том, что при параллельном вызове из нескольких потоков - для каджого потока в одинаковый момент времени проверка instance == null будет возвращать TRUE, что соответственно позволит получать объект НЕ в единственном экземпляре, а значит наш Singleton не будет работать. Чтобы это исправить, мы вешаем блокировку на вызов getInstance(), накладывая на метод модификатор synchronized:
public synchronized static TestClass getInstance() {
if (instance == null) {
instance = new TestClass();
}
return instance;
} , этот подход гарантирует нам, что любой параллельный поток будет ожидать завершения (lock) метода getInstance()* в руках текущего потока и класс-одиночка не инстанцируется больше 1 раза.