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

Недавно мне довелось посетить собеседование на позицию стажёра в одной из крупных 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 объект с не переопределёнными equals и hashcode?
Нет, нельзя.

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

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


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



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

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

На этом у меня всё, надеюсь, кому-то эта статья поможет углубить или расставить по полочкам свои знания. Всем приятного обучения!

35 комментариев

Totem
Довольно интересно построено повествование с комментариями, прочитал на одном дыхании. Пишите ещё.
alex8894
Может быть когда-то, на заре Java, подобное сравнение LinkedList и ArrayList было правильным. Но сейчас причин для использования LinkedList, на мой взгляд, почти не осталось. ArrayList использует System.arraycopy(), который выполняется на низком уровне и работает очень быстро. Тесты подтверждают, что накладные расходы на обслуживание LinkedList в подавляющем большинстве случаев нивелируют весь (небольшой) выигрыш во времени, но LinkedList при этом потребляет примерно в 4 раза больше памяти. На подобный вопрос на собеседовании я бы ответил так — я буду во всех случаях использовать ArrayList.

Мне пока приходит в голову только одна ситуация, при которой можно было бы рассмотреть использование LinkedList — это вставка в середину с использованием итератора. Вставку в начало надо превратить во вставку в конец, «развернув» список наоборот. Вставку в начало и в конец — во вставку в конец в два списка, один из которых развернут наоборот.
alexeyfrei
  • alexeyfrei
  • +1
  • Комментарий отредактирован 2017-03-14 12:57:58 пользователем alexeyfrei
Были похожие мысли. Единственное про вставку в начало и конец не понятно. Можно подробнее как вы хотите такое провернуть? Содержать два ArrayList'a? Как их обновлять тогда, чтобы они имели актуальные значения после каждой вставки? Не будет ли это обновление, все тем же использованием System.arraycopy что могло бы быть при вставке в начало ArrayList'a?

P.S. Еще возник вопрос по мапе. В моих исходниках 8 джавы метод indexFor() отствует. Исследование показали, что его просто засунули прямо в метод putVal().
Тут кстати даже возникли сомнения, что данное собеседование имело место быть ближайшие месяцы, т.к. данные не совсем актуальны. Но все равно спс, порылся в исходниках, узнал, что-то новое.
GuitarFactor
Спасибо за уточнение, действительно метода indexFor уже нету. Если честно, написал про этот метод взяв инфу с Хабры — habrahabr.ru/post/128017/
А по двойному клику Shift в идее нашёл этот метод, но он оказался в классе WeakHashMap. Спасибо за уточнение!
NemchinovSergey
Благодарю автора за статью! Мне это ещё предстоит )
ArrayList действительно делает вставку через сдвиг массива в памяти, по сути вставка элемента происходит за константное время.
Вот код его метода:
/**
     * Inserts the specified element at the specified position in this
     * list. Shifts the element currently at that position (if any) and
     * any subsequent elements to the right (adds one to their indices).
     *
     * @param index index at which the specified element is to be inserted
     * @param element element to be inserted
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

Тут подробности Структуры данных в картинках. ArrayList
Shtramak
  • Shtramak
  • +1
  • Комментарий отредактирован 2017-03-14 20:41:11 пользователем Shtramak
За статью в карму плюсанул. Полезно хотя бы относительно представлять формат интервью… Кстати насчет вопроса про вычисления индекса в бакете — обратите внимание, что метода indexFor() уже нет в текущей реализации Мар — его логика перенесена в метод putVal(), кроме того непосредственно сам hashcode() не принимает участия в формировании индекса, там используется другое число полученное путем модификации хэшкода (так называемое рехэширование). Таким образом, ИМХО, правильным ответом будет — «Индекс „бакета“ вычисляется исходя из длинны массива бакетов и хэшкода добавляемого элемента»… Хотя, хз, что хотел услышать собеседующий :)

З.Ы. Не сразу заметил, что немного повторился с alexeyfrei
vsineln
Почему же не верить JR? :-) У нас же были задачи на скорость работы array & linked листов, из них все понятно. Мне единственно пришлось позже уже по работе разбираться с вставкой в середину листа — и там не все однозначно — зависит от размера списка habrahabr.ru/post/262943/
jekanik2012
Мне кажется, что утверждение «hashCode == адрес ячейки в памяти» неверно. Если смотреть на модель управления памяти в JVM, то можно увидеть, что объекты могут быть копированы с одной области памяти в другую (например, при переносе из new generation в old generation).
alexeyfrei
Поствил вам плюсик и все же заглянул в исходники. Вот что там написано в описании метода:

* As much as is reasonably practical, the hashCode method defined by
* class {@code Object} does return distinct integers for distinct
* objects. (This is typically implemented by converting the internal
* address of the object into an integer, but this implementation
* technique is not required by the
* Java™ programming language.)
Так что, похоже все верно — хэш определенный в классе Object зависит от адреса. Вероятно то, что в ходе работы программы адрес (а с ним и хэш) меняется, ни на что не влияет. Так как у одинаковых объектов, все равно одинаковый адрес. Либо мы переопредлили метод хэшкод в классе объекта и он теперь не зависит от адреса.
Exidnus
Смотрите. Вы положили объект, скажем, в HashSet. Потом сборщик мусора переместил объект в памяти. Если хэшкод у объекта изменится — то из HashSet'a вы, скорее всего, его не получите.
jekanik2012
  • jekanik2012
  • 0
  • Комментарий отредактирован 2017-03-15 12:32:31 пользователем jekanik2012
Мы говорим про нативную реализацию. Для коллекций в 100% случаев лучше переопределять hashcode и equals.
Exidnus
Я не понимаю, о чем вы говорите: то ли о рекомендациях по переопределению hashcode и equals (какой в этом смысл для 100% случаев коллекций?), то ли о том, как работает Object#hashcode.
jekanik2012
  • jekanik2012
  • 0
  • Комментарий отредактирован 2017-03-15 12:31:38 пользователем jekanik2012
Видел недавно статью, что в большинстве JVM хэшкод — случайное число.

UPD: https://habrahabr.ru/post/168195/.
Почти в самом конце статьи пример.
danilishe
Спасибо JavaRush, я по крайней мере теперь понимаю о чём вообще речь!
Дойду до 30го, уже буду думать о собеседованиях
imp
  • imp
  • 0
читается на одном дыхании, обязательно пишите еще :)

p.s. вопросы по технологиям были или только по Core гоняли?
GuitarFactor
Было много чего) Началось с вопросов на базовое понимание вещей: что такое JDK, JRE, что делает компилятор, что делает JVM, как запустить код без IDE. Потом пошли вопросы по Java Core. Я на 30 уровне остановился, в принципе курс JavaRush за эти уровни покрыл все спрашиваемые темы по core. Потом были вопросы на совсем базовом уровне (буквально на понимание самых азов) по sql, реляционным БД, xml, html, http. Ну и т.к. я заикнулся что имел маленький опыт с EE (делал вступительное задание на стажировку JavaRush) ещё попросили рассказать зачем нужен hibernate и зачем нужен spring IoC. Примерно такой план собеседования был, вышел я оттуда с квадратной головой))
svartberg
А не подскажите, что за компания? Я сейчас сам пытаюсь найти, куда можно податься, но пока даже на собеседования не приглашают.
GuitarFactor
Это T-Systems.
Если не приглашают, может быть Вы не достаточно рассылаете своё резюме? Попробуйте активно рассылать его по компаниям, которые ищут джунов или миддлов. В 10-15 компаний в день. Рано или поздно куда-нибудь да пригласят, не расстраивайтесь. На JavaRush 2.0 на тему поиска работы есть отличные статьи в разделе «Стажировка»)
svartberg
В t-systems 2 раза присылал резюме — ноль реакции. Мне кажется, что по возрасту не подошёл, хотя ограничений формальных нет.
GuitarFactor
Если Вы просто подавали заявку на junior разработчика, разумеется будет ноль реакции. Компания не набирает джуниоров, для этого при компании существует JavaSchool. Там джунов обучают сотрудники, и только потом могут взять на работу.
Если Вы всё же говорили о заявке в JavaSchool, то Вы в срок подали заявку?
svartberg
Да, я подавал на java school. И подавал в срок, где-то в середине февраля ещё через их форму. Потом ближе к концу февраля они ещё на HH выкладывали объявление, и я через НН им подавал.
Общался ещё с Deutche Bank, у них тоже была школа в том году, но они от неё отказались и берут теперь только выпускников и студентов, на стажировку, мотивировав это тем, что им нужны лучшие. И как. Понял, такие как я, кто окончил ВУЗ не в этом году, а пару лет назад — особо не нужны на стажировках.
GuitarFactor
Гм, вообще говоря странно… Сейчас со мной в группе обучаются люди разного возраста. Самый младший участник — студент 4 курса, самому старшему, думаю, уже за 40.
imp
такой вопрос, а английский они как проверяли?
GuitarFactor
В самом конце собеседования спросили уровень английского и попросили сказать пару слов о своей прошлой работе. Запредельных требований к уровню английского не было (может потому что домашние задания и тест на компьютере в классе были полностью на английском)
Str3psils
Интересная статья вышла, у меня тестовые задания и вопросы были куда хуже.
GuitarFactor
Хуже, это в каком смысле? Сложнее или из серии «спрошу-ка я какую-нибудь ерунду, которая редко используется, но зато я о ней знаю»?
Str3psils
  • Str3psils
  • 0
  • Комментарий отредактирован 2017-03-20 14:05:34 пользователем Str3psils
Тестовые задания сводились к работе с бд, а из вопросов — основы ООП. Остальное посчитали в то время не нужным, в итоге когда приступает человек к работе, он начинает менять цвет волос от объема информации, которую ему предстоит познать покинув стены университета.
GuitarFactor
А, ясно) Вообще у меня сейчас похожая ситуация. После того как прошёл 30 уровней JR, делал тестовое задние на стажировку (простое вэб-приложение с функциями CRUD), чуть с ума не сошёл сколько пришлось всего прочитать.
Теперь вот попал на обучение в T-sys, а там за 2 месяца надо сделать полноценный проект с кучей функционала (упрощённую кальку с реального проекта, выполнявшегося в компании), авторизацией, аутентификацией, разграничением ролей… Всё разрабатываешь сам: фронт энд, бэкэнд, тесты, документацию. Короч голова кругом, на измене сижу(( А требования к кандидатам были — всего лишь хорошее знание Java SE!
imp
вопрос про обучение — вам читают лекции или есть наставники с которым нужно общаться?
GuitarFactor
Есть и лекции и наставники) Но от лекций обычно не легче. Если прийти без базовых знаний о чём будут говорить на лекции, вряд ли что-то можно понять. А вот наставники это да, очень ценный ресурс.
imp
как пройдете стажировку напишите потом об этом :)
Torin
Очень интересный отчет, автор. Плюс в карму, пиши еще!
Vorlock
ТС, спасибо, интересно было, хотя и очень необычно
с одной стороны вроде базовые вещи спрашивают, с другой — местами необычные (сравниваю со своими собеседованиями).
Inspiron
честно говоря это собеседование на стажёра не отличается от собеседования на джуна, которые проходил я ))
Archie369
Спасибо за статью, надеюсь у тебя все получится
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.