36

Есть 3 задачки для прохождения собеседования в Yandex на должность Android Developer. После выполнения этих 3 заданий мне сообщили, что я не выполнил ни одного задания верно, хотелось бы услышать от вас, где у меня ошибки.

  • Задача 1: Какие объекты доступны для сборщика мусора на момент вызова System.gc() и почему?

    public class GCTest {
        static class A {
            private String myName;
            public A(String myName) {
                this.myName = myName;
            }
        }
    
        public static void main(String[] args) {
            A a1 = new A("a1");
            A a2 = new A("a2");
            ArrayList list = new ArrayList();
            list.add(a1);
            A[] mas = new A[2];
            mas[0] = a2;
            a2 = a1;
            clear(mas);
            a1 = null;
            a2 = null;
            System.gc();
            // дальше идет какой-то код
            ...
        }
    
        private static void clear(A[] mas) {
            mas = null;
        }
    } 
    

    Мой ответ: Массив new A[2] из строки A[] mas = new A[2] будет очищен, так как мы выполняем функцию, которая зануляет этот массив (mas = null). Также будет очищен объект new A("a2"), так как мы теряем на него ссылку в строке a2 = a1, соответственно он ссылается уже на объект new A("a1"). А далее мы зануляем массив, как я писал выше, поэтому больше никто не ссылается на на объект new A[2].

  • Задача 2: Перечислите все проблемы, которые вы видите в данном коде:

    public class Generator {
        private static final Map<byte[], byte[]> cache = new HashMap<byte[], byte[]>();
    
        public static byte[] generate(byte[] src) {
            byte[] generated = cache.get(src);
            if (generated == null) {
                synchronized (cache) {
                    generated = cache.get(src);
                    if (generated == null) {
                        generated = doGenerate(src);
                        cache.put(src, generated);
                    }
                }
            }
            return generated;
        }
    
        private static byte[] doGenerate(byte[] src) {...}
            // ...
        }
    

    Мой ответ: Я написал, что использование byte[] в качестве ключа HashMap недопустимо, так как у byte[] метод Hashcode() реализован на алгоритме Park-Miller RNG. Hashcode() у byte[] реализован так же, как и у Object, точно так же метод equals() будет работать, как у Object и будет сравнивать ссылки на объект, а не само содержание объектов (как обычно людям кажется), соответственно на основании этого я написал, что данная коллекция будет работать некорректно.

    Далее я написал, что также все строки кода, в которых выполняется добавление данных в коллекцию или удаление не имеет смысла, так как мы используем в качестве ключа byte[].

    Далее я написал, что код:

    if (generated == null) {
        synchronized (cache) {
            generated = cache.get(src);
            if (generated == null) {
                generated = doGenerate(src);
                cache.put(src, generated);
            }
        }
    }
    

    слишком растянут и имеют лишние строки, которые повторяются далее.

  • Задача 3: Есть две задачи: Task 1 и Task 2. Стек Activity для Task 1: A,B,C,D. Стек Activity для Task 2: X,Y,Z.

    После выполнения указанного действия для всех пунктов в ответе необходимо указать:

    1. Как будет выглядеть стек Activity для задач. Например, Task 1: A,B,C,D; Task 2: X,Y,Z;

    2. Историю того, как будут изменяться стеки при нажатии кнопки BACK, пока не возвратимся в Home screen. Например: A,B,C,D - back -> A,B,C - back -> A,B - back -> A - back -> Home screen;

    а) У всех Activity установлен launchMode="standard". В текущий момент отображается Activity Z. Из Activity Z отправляется Intent на открытие Activity D.

    б) У всех Activity установлен launchMode="standard", но только у Activity D установлен launchMode="singleTop". В текущий момент отображается Activity Z. Из Activity Z отправляется Intent на открытие Activity D.

    в) У всех Activity установлен launchMode="standard", но только у Activity D установлен launchMode="singleTask". В текущий момент отображается Activity Z. Из Activity Z отправляется Intent на открытие Activity D.

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

    1. а) Task 1: A,B,C,D; Task 2: X,Y,Z,D;

      б) A,B,C,D - back -> A,B,C - back -> A,B - back -> A - back -> Home screen; X,Y,Z,D - back -> X,Y,Z - back -> X,Y - back -> X - back -> Home screen;

    2. а) Task 1: A,B,C,D; Task 2: X,Y,Z,D;

      б) A,B,C,D - back -> A,B,C - back -> A,B - back -> A - back -> Home screen; X,Y,Z,D - back -> X,Y,Z - back -> X,Y - back -> X - back -> Home screen;

    3. а) Task 1: A,B,C,D; Task 2: X,Y,Z;

      б) A,B,C,D - back -> A,B,C - back -> A,B - back -> A - back -> Home screen; X,Y,Z - back -> X,Y - back -> X - back -> Home screen;

Я также искал в просторах интернета ответы на эти задачи, кроме 3, и нашёл пару ссылок, на первую задачу отвечают, что сборщик мусора отчистит ноль объектов; а я ответил, что два: массив и объект. Я не совсем понял, почему это так? Почему зануление массива не влияет на сам массив, почему он всё равно существует?

По поводу второй задачи были споры, что коллекция не является потокобезопасной; никто не писал по поводу ключа в качестве byte[]. Но как из их задачи вообще можно понять, что они там хотят сделать? Там же нету дополнений, что всё выполняется в несколько потоков. Так-то я в курсе, что коллекция не потокобезопасна, и для этого есть специальные реализации синхронизированных коллекций.

Прошу от вас конструктивных ответов, так как у меня завязался спор с сотрудником из Yandex, и мы договорились, что пусть более компетентные люди с большим опытом попробуют дать ответ на эти задачи и растолкуют мне мои недочёты. Если я был прав хотя бы в одном из ответов, то по этому вопросу будет непосредственное разбирательство внутри их компании; а я на 99% уверен, что 3 задачу я решил верно, и там варианты ответа не такие размазанные, как во 2 задаче, где каждый может найти свою неточность или огрех.

Заранее благодарю за ответы, ибо для меня это дело принципа!

3
  • Я проходил данный этап у Яндекс, ещё зеленным. У вас в каждом ответе ошибки и неточности и не надо ругаться, просто просите ласково feedback. В первом вопросе вы разобрались, это явно и очень просто. Во втором вы раскручиваете идею которой может и не быть в коде, а там стандартные проблемы хеширования и всем известные проблемы hashMap в Java, и обратите как идет sync для него, частично вам ответили. Последняя задача у вас только 2-й вариант правильный в первом ошибка, а третий не верен, вы не до конца понимаете принцип, там будет тип того Home: X, Y, Z, A, B, C, D. Удачи,учатся на ошибках) 18 сен 2016 в 6:06
  • Пипец. Это Яндекс такие вопросы задаёт или так везде? Сложно вроде. И причём тут андроид девелоперская и сборка мусора?
    – user194625
    3 дек 2016 в 10:35
  • @СергейГрушин Потому что Android неизбежно сопряжён с Java, поверьте, с опытом эти вопросы становятся детскими
    – BORSHEVIK
    4 дек 2016 в 19:07

4 ответа 4

25

За 3-ю задачу говорить не буду, т.к. android не занимаюсь.

В первой задаче ответ действительно неверный. Изучайте Java. В том числе смотрите про передачу параметров в Java.

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

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

3
  • 3
    Давайте я ещё намекну, что параметры передаются по значению (надеюсь, это не слишком повредит Яндексу), и что имеет смысл посмотреть в отладчике, какой эффект имеет метод clear.
    – VladD
    17 сен 2015 в 11:30
  • 2
    Какой же я днище! Я реально в попыхах не обратил внимание на саму функцию, а тупо посмотрел на то, что происходит зануление и всё и мозгом не подумал, что зануление происходило не самого массива, а лишь её копии внутри функции, вот это я реально лоз
    – BORSHEVIK
    17 сен 2015 в 11:33
  • @BORSHEVIK: Это была достаточно подлая ловушка, функция называлась clear.
    – VladD
    18 сен 2015 в 14:28
8

Во второй задаче помимо использования byte[] в качестве ключей (в конкретном коде может это и не проблема, сравнивать ключи по ссылке иногда может быть нормально) серьёзная проблема — это ламерская реализация double-checked locking. Запись в HashMap охраняется локом, но первое чтение — нет. В результате поведение может быть неспецифицированным. Возможно что угодно — произвольное исключение, неверный результат или даже зацикливание с полным подвисанием потока. DCL можно применять с volatile-переменной, которую вы контролируете (и то осторожно, там есть тонкости с публикацией объекта), но со структурой данных, которую вы не контролируете — ни в коем случае.

В данном случае надо не мучать киску, а использовать ConcurrentHashMap. Если хочется вычислять значение не более одного раза для каждого ключа и Java-8 использовать нельзя, то можно сделать ConcurrentHashMap<KeyType, AtomicReference<ValueType>> и реализацию вроде:

private static final Map<KeyType, AtomicReference<ValueType>> cache = new ConcurrentHashMap<>();

public static ValueType generate(KeyType key) {
    AtomicReference<ValueType> ref = cache.get(key);
    if(ref == null) {
        ref = new AtomicReference<>();
        AtomicReference<ValueType> oldRef = cache.putIfAbsent(key, ref);
        if(oldRef != null) ref = oldRef;
    }
    ValueType value = ref.get();
    if(value == null) {
        synchronized(ref) {
            value = ref.get();
            if(value == null) {
                value = doGenerate(key);
                ref.set(value);
            }
        }
    }
    return value;
}

Примерно такая идея. Так у вас для каждого ключа вычисляется значение единожды, и при этом решается ещё одна проблема: при вычислении значения для одного ключа работа с остальными не блокируется.

В Java-8 то же самое гораздо проще:

public static ValueType generate(KeyType key) {
    return cache.computeIfAbsent(key, this::doGenerate);
}

Правда оно вроде как блокирует целый node, а не одну запись, но в node нечасто бывает больше одной записи.

Соответственно ваш ответ по второй задаче в корне неверен в том смысле, что вы даже понятие DCL не упомянули.

5
  • Да, есть такое дело, данный анти-паттерн не был мной упомянут, нужно было написать, что для такого паттерна необходимо было бы добавить модификатор volatile для переменной
    – BORSHEVIK
    22 сен 2015 в 10:14
  • @BORSHEVIK, вас бы на этом точно засыпали. Модификатор volatile на какой переменной вы имеете в виду? 22 сен 2015 в 10:15
  • На перменной chache
    – BORSHEVIK
    22 сен 2015 в 10:43
  • @BORSHEVIK, не возьмут вас в яндекс. 22 сен 2015 в 10:51
  • Не велика беда, а раз вы такой умный, то поясните свою точку зрения по поводу Volatile
    – BORSHEVIK
    23 сен 2015 в 7:25
7

По трейтьей задаче. Сначала надо понять как получили два таска, т.е. что это вообще такое (допускаю, что вы об это прекрасно знаете, но для ясности опишем).

Запускаем с home screen'а активити: A, из которого переходим в B, дальше в C, и D. Жмем home. Запускаем с home screen'а активити X, из него Y, и него Z.

Пример. Есть приложение sms и приложение dialer и в том и другом можно вызвать активти списка контактов. И вот в sms открыли список контактов и в dialer'е собираемся открыть тот же список контактов. Дальше варианты:

a) Мы находимся в task 2, у которого стек XYZ. Переходим в D и теперь задача узнать какие стеки будут у каждого из task'ов. task1 так и останется ABCD. task2 станет XYZD. В standard mode Активити D создастся и добавится в стек task2, не влияя никак на task1. В результате последовательного нажатия back:

Task1=ABCD, Task2=XYZD ->
Task1=ABCD, Task2=XYZ ->
Task1=ABCD, Task2=XY ->
Task1=ABCD, Task2=X ->
Task1=ABCD, Task2 завершится (стек пустой) перейдем в home screen.

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

b) singleTop для активити D в данном случае ничем не отличается от standard. Эти режимы относятся к одному task'у и отличия standard от singleTop лишь в том, что если бы мы потом запустили активити D в том же таске и она была бы на вершине стека, новый экземпляр не создавался бы, а сработало бы onNewIntent для существующей активти. Например, такой вариант запуска активти применяется при реализации поиска... Короче говоря результат будет таким же как и в первом пункте.

пример естественно будет тот же.

c) режим singleTask для D говорит о том, что активити D запускается только в одном таске. Следовательно, при запуске D из Z произойдет смена таска на первый, далее нажимаем back, как только мы выйдем из стека таска 1, вернемся в таск 2 и будем выходить из него. При этом возврат на главный экран произойдет только в конце, т.е. когда оба таска опустеют.

Task1=ABCD, Task2=XYZ (D уже запущена в таске 1) ->
Task1=ABC, Task2=XYZ ->
Task1=AB, Task2=XYZ ->
Task1=A, Task2=XYZ ->
Task1=<умер>, Task2=XYZ ->
Task1=<умер>, Task2=XY ->
Task1=<умер>, Task2=X ->
home screen.

по примеру. если бы список контактов был singleTask (хоть это и бред), то зайдя в sms добравшись до списка, вернулись на домашний экран, открыли dialer, опять открыли список контактов, нажали back и оказались в sms 8-() жмем back, окзаываемся в dialer'е 8-()

3

А я как раз таки попробую высказать небольшое предположение по поводу 3-его вопроса.

Если отталкиваться от того, что Ваш ответ не был принят, хотя как мне кажется все вроде правильно написано, попробуем немного по другому посмотреть вот на это задание:

Историю того, как будут изменяться стеки при нажатии кнопки BACK, пока не возвратимся в Home screen. Например: A,B,C,D - back -> A,B,C -back -> A,B - back -> A - back -> Home screen;

Как вариант, возможно здесь имелось ввиду привести изменение стеков до первого возврата на Home screen.

Тогда:

  1. X,Y,Z,D - back -> X,Y,Z -back -> X,Y - back -> X - back -> Home screen;
  2. X,Y,Z,D - back -> X,Y,Z -back -> X,Y - back -> X - back -> Home screen;
  3. A,B,C,D - back -> A,B,C -back -> A,B - back -> A - back -> X,Y,Z - back -> X,Y -back -> X - back -> Home screen;

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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.