История одного собеседования: интересные вопросы

Недавно мне довелось посетить собеседование на позицию стажёра в одной из крупных IT-компаний. Это было моё первое IT-собеседование и, на мой взгляд, оно выдалось интересным. В общей сложности меня “допрашивали” больше 3 часов (этому предшествовали ещё домашние задания и тест в офисе на компьютере). Хочу отдать должное собеседующему, который не ставил крест, когда я отвечал на вопрос неверно, а с помощью своих наводящих вопросов заставлял меня вдумываться и приходить к верному ответу. Ниже я представлю несколько “зарисовок” – на мой взгляд, достаточно интересных вопросов, некоторые из которых дали мне более глубокое понимание отдельных аспектов в Java. Возможно, кому-то эти вещи покажутся очевидными, но думаю, найдётся те, для кого это будет полезно. Ниже фразы выделены следующими шрифтами: Собеседующий — жирным шрифтом Закадровые пояснения и мои мысли — курсивом Мои ответы — обычным шрифтом С предысторией закончили, перейдём к делу)

Зарисовка 1. “Казалось бы простой метод”

Напишите, как бы вы реализовали метод, возвращающий результат деления числа а на число b Собеседующий пишет на листочке

int divide(int a, int b) {
}

*Я недоверчиво покосился на листок с сигнатурой метода. В чём подвох?* Пишу:

int divide(int a, int b) {
    return a/b;
}

А какие-нибудь проблемы могут быть с этим методом? *Ловлю дииииикий тупняк* Вроде нет.. Далее следует законный вопрос: А если b=0? *Воу, меня сейчас выгонят из этого кабинета, если продолжу в том же духе!* Ах да, разумеется. Здесь у нас аргументы типа int, поэтому будет выброшен Arithmetic Exception. В случае, если бы аргументы были типа float или double, получилась бы Infinity. А что с этим будем делать? Начинаю писать try/catch

int divide(int a, int b) {
    try {
        return a/b;
    } catch (Exception e) {
        e.printStackTrace();
        return ... // ??? what the hack?
    }
}

*Дохожу до return и подвисаю: что-то ведь надо вернуть в случае ошибки. Но как это “что-то” отличить от результата вычисления?* А что будем возвращать? Гм… Я бы поменял тип возвращаемой переменной на Integer и в случае эксэпшна возвращал бы null. Давайте представим, что не можем менять тип. Можем как-то выкрутиться? Может, можем ещё что-то сделать с эксэпшном? *Тут дошло* Можем ещё пробросить в вызывающий метод! Верно. Как он будет выглядеть?

int divide(int a, int b) throws ArithmeticException{
    return a/b;
}

void callDivide(int a, int b) {
    try {
        divide(a, b);
    } catch (ArithmeticException e) {
        e.printStackTrace();
    }
}

А обрабатывать исключение обязательно? Да, ведь мы явно пробрасываем его из метода divide. (*Тут я ошибся! Далее следуют наводящие вопросы собеседующего, чтобы прийти к верному ответу*) А Arithmetic Exception - это какое исключение – checked или unchecked? Это Runtime exception, значит unchecked. *Тут следует убийственный вопрос* То есть получается, с Ваших слов, если мы в сигнатуре метода указали throws Arithmetic Exception, то оно стало checked исключением? *Ух ё!* Наверное… нет. Да, не стало. Если мы указали в сигнатуре throws /unchecked exception/ мы всего лишь предупреждаем, что метод может выбрасывать исключение, но обрабатывать его в вызывающем методе не обязательно. С этим разобрались. А ещё что-то можем сделать, чтобы избежать ошибки? *После некоторых раздумий* Да, можем ещё проверять, if (b==0). И выполнять какую-то логику. Верно. Таким образом, мы можем пойти 3 путями:

• try/catch
• throws – проброс в вызывающий метод
• проверка аргументов

В этом случае с divide какой из методов Вам кажется предпочтительнее? Я бы выбрал проброс исключения в вызывающий метод, т.к. в методе divide не ясно, как этот эксэпшн обработать и какой результат типа int вернуть в случае ошибки. А в вызывающем методе использовал бы проверку аргумента b на равенство нулю. Вроде бы такой ответ удовлетворил собеседующего, но если честно, не уверен, что этот ответ однозначный))

Зарисовка 2. “Кто быстрей?”

После стандартного вопроса, чем ArrayList отличается от LinkedList, последовал такой: Что произойдёт быстрее — вставка элемента в середину ArrayList или в середину LinkedList? *Тут меня перемкнуло, я вспомнил, что везде читал что-то вроде “используйте LinkedList для вставки или удаления элементов в середину списка”. Дома даже перепроверил по лекциям JavaRush, там фраза: “если ты собираешься вставлять (или удалять) в середину коллекции много элементов, то тебе лучше использовать LinkedList. Во всех остальных случаях – ArrayList.” Ответил на автомате* Быстрее будет с LinkedList. Поясните, пожалуйста

1. Для того чтобы вставить элемент в середину ArrayList, мы за константное время находим элемент в списке, а потом пересчитываем индексы элементов справа от вставляемого, за линейное время.
2. Для LinkedList.. Мы сначала за линейное время доходим до середины и затем за константное время вставляем элемент, меняя для соседних элементов ссылки.

Так получается, что быстрее? Гм… Получается одинаково. А когда LinkedList всё же быстрее? Получается, что когда вставляем в первую половину списка. Например, если вставлять в самое начало, в ArrayList придётся пересчитать все индексы до самого хвоста, а в LinkedList всего лишь поменять ссылку у первого элемента. Мораль: не верьте дословно всему что написано, даже на JavaRush!)

Зарисовка 3. “Куда же без equals и hashcode!”

Разговор об equals и hashcode был очень долгий – как переопределяем, какая реализация в Object, что происходит под капотом, когда вставляется элемент в HashMap и т.д. Приведу только ряд интересных на мой взгляд моментов* Представьте, что мы создали класс

public class A {
    int id;

    public A(int id) {
        this.id = id;
    }
}

И не переопределили equals и hashcode. Опишите, что произойдёт при выполнении кода

A a1 = new A(1);
A a2 = new A(1);
Map<A, String> hash = new HashMap<>();
hash.put(a1, "1");
hash.get(a2);

*Хорошо что перед собеседованием специально уделил пару дней на понимание основных алгоритмов, их сложности и структур данных – очень помогло, спасибо CS50!*

1. Создаём два экземпляра класса A

2. Создаём пустую мапу, по умолчанию имеющую 16 корзин. В качестве ключа выступает объект класса A, в котором не переопределены методы equals и hashcode.

3. Кладём a1 в мапу. Для этого сначала вычисляем хэш a1.

   Чему будет равен хэш?

   Адресу ячейки в памяти – это реализация метода из класса Object

4. Исходя из хэша, вычисляем индекс корзины.

   А как мы можем его вычислить?

   *Тут к сожалению я не дал вразумительный ответ. У вас есть длинное число – хэш, и есть 16 корзин – как определить индекс, чтобы объекты с разным хэшем равномерно распределялись по корзинам? Я мог бы предположить, что индекс вычисляется так:

   int index = hash % buckets.length

   Уже дома посмотрел, что оригинальная реализация в исходниках несколько отличается:

   static int indexFor(int h, int length)
   {
       return h & (length - 1);
   }

5. Проверяем, что не произошло коллизий и вставляем a1.

6. Переходим к методу get. Экземпляры a1 и a2 гарантированно имеют разный hash (разный адрес в памяти), поэтому мы ничего не найдём по этому ключу

   А если переопределим только hashcode в классе A и попытаемся вставить в хэшмап сначала пару с ключом a1, а потом с a2?

   Тогда сначала найдём нужную корзину по hashcode – эта операция будет выполнена корректно. Далее начнём идти по объектам Entry в прикреплённом к корзине ЛинкедЛисту и сравнивать ключи по equals. Т.к. equals не переопределён, то берётся базовая реализация из класса Object – сравнение по ссылке. a1 и a2 гарантированно имеют разные ссылки, поэтому мы “промахнёмся” мимо вставленного элемента a1, и a2 будет помещён в ЛинкедЛист в качестве нового узла.

   Какой же вывод? Можно ли использовать в качестве ключа в HashMap объект с не переопределёнными equalshashcode?

   Нет, нельзя.

Зарисовка 4. “Давайте нарочно сломаем!”

После вопросов об Error и Exception последовал такой вопрос: Напишите простой пример, когда функция выкинет StackOverflow. *Тут я вспомнил, как меня кумарил этот эррор, когда я пытался написать какую-нибудь рекурсивную функцию* Наверное, это случится в случае рекурсивного вызова, если неверно указано условие выхода из рекурсии. *Дальше я стал что-то мудрить, в итоге собеседующий помог, всё оказалось просто*

void sof() {
    sof();
}

А чем этот эррор отличается от OutOfMemory? *Тут я не ответил, уже потом понял, что это был вопрос на знание Stack и Heap памяти Java (в Stack хранятся вызовы и ссылки на объекты, а в Heap памяти – сами объекты). Соответственно, StackOverflow выкидывается, когда больше нет места в Stack памяти для очередного вызова метода, а OutOfMemory – место под объекты закончилось в Heap памяти*

---

Вот такие моменты из собеседования мне запомнились. На стажировку в итоге меня взяли, так что впереди у меня 2,5 месяца обучения и, если всё сложится хорошо, работа в компании) Если будет интересно, могу написать ещё одну статейку, уже поменьше, с разбором простой, но показательной задачки, которую мне дали на собеседовании в другую компанию. На этом у меня всё, надеюсь, кому-то эта статья поможет углубить или расставить по полочкам свои знания. Всем приятного обучения!