Java in NYC – нужен совет.

[nyekimov]

Ну в твоем решение ты используешь много доп памяти. Но получаешь хороший рантайм. У тебя O(N) памяти, но и O(N) рантайм что очень хорошо, вернее 2 * O(N) но это тоже самое что O(N)
В решение с сортировкой - доп память не используется, но ухудшается оченть сильно рантайм. O(n long n) на сортировку.
Собственно так. Оба решения правильные, но нужно это понимать какие плюсы и минусы каждого. Можно это как на духу и выдать на интервью. Могу и так и так решить, такие то плюсы и минусы.

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

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

У меня был коллега, у которого не было детей и он очень любил развлекаться на всяких соревнованиях на хакерранке или где они там проходят. Пару ребят тоже было, кого даже с родины фаанг возили на собеседование и гоняли по стандартному интервью все равно.
Мне тот коллега советовал даже здесь учавствовать в контекстах, чтобы позвали на интервью. Хотя вроде на линкедин пишут и без этого. Так что наврятли без интервью совсем получится обойтись, а вот получить доступ к интервью - может быть и будет необходимым шагом.

[Krys-Krys]

Ну в твоем решение ты используешь много доп памяти. Но получаешь хороший рантайм. У тебя O(N) памяти, но и O(N) рантайм что очень хорошо, вернее 2 * O(N) но это тоже самое что O(N)
В решение с сортировкой - доп память не используется, но ухудшается оченть сильно рантайм. O(n long n) на сортировку.
Собственно так. Оба решения правильные, но нужно это понимать какие плюсы и минусы каждого. Можно это как на духу и выдать на интервью. Могу и так и так решить, такие то плюсы и минусы.

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

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

Я немного общиблась, у тебя ни 2 * O(N) а просто сразу O(N) по памяти, при чем в самом плохом случае, а в хорошем памяти может по минимуму быть. Я бы на самом деле именно такое решение как ты и написала.
Да, именно так - нужно сделать 2 медиум задачи за 40 минут по сути, т е 20 мин на задачу, чтобы уложиться все должно быть отведено до автоматизма и нужно быть в самой хорошей форме по подготовке. Считай что ты бежишь марафон.
Идея хорошая с литкод счетом - но не реализуемая, по понятным причинам. Поэтому и проводятся такие интервью.

[valchkou]

Я немного общиблась, у тебя ни 2 * O(N) а просто сразу O(N) по памяти, при чем в самом плохом случае, а в хорошем памяти может по минимуму быть. Я бы на самом деле именно такое решение как ты и написала.

на код ревью я бы тоже предпочел мое решение. Рассмотрим 2 варианта

Code: Select all

        Set<Integer> set = new HashSet(nums.length);
        for (int num : nums) {
            if (set.contains(num)) return true;
            set.add(num);
        }
        return false;

VS

Code: Select all

        Set<Integer> set = new HashSet(nums.length);
        for (int num : nums) {
            set.add(num);
        }
        return set.size() != nums.length;

С точки зрения литкода вариант 2 более оптимальный.
С точки зрения меня, вариант 1.
Ведь под каждый элемент в мапе или сэте дополнительно создается объект врапер.
Короче проверки нужно делать как можно раньше , а создавать новые объекты как можно позже, а вдруг и не понадобятся.
Плюс литкод не учитывает красоту дизайна, к сожалению. Можно было бы хотябы сонаркуб прикрутить.

Но в целом думаю от литкода хуже не станет, нужно заставить себя решать хотябы 1 задачку в день на завтрак

[Мальчик-Одуванчик]

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

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

[Krys-Krys]

Конечно же 1й вариант лучше чем второй. Зачем все элементы кидать в хэш сет, может быть входной массив будет очень большим, а 1й и 2й элемент в нем одинаковые. Т е O(N) for memory and runtime в 1м решение варьирует from O(1) to O(N) (most optimal and least optimal case), а во 2м решение O(N) for memory and runtime always O(N). Not cool.
Думаю возможно придумать решение и лучше, вообще без доп памяти но с лучшим рантаймом, если копать в сторону разных алгоритмов сортировки, коих я и так не знала а тут еще и забыла. В какому-то из алгоритмов возможно получится как-то совместить сортировку и проверку на дупликаты и получить лучше рантайм чем O(n log n) но тут я не уверена. Bucket sort, radix, merging sort, insert sort? В общем слышен звон, да не знаю где он.

[roadman]

https://docs.oracle.com/javase/7/docs/a ... tml#add(E)
Обычно для контейнеров set, map, hash* - метод add работает подобно contains в случае дубликатов.

Code: Select all

        Set<Integer> set = new HashSet(nums.length);
        for (int num : nums) {
            if (!set.add(num)) return false;
        }
        return set.size() != 0;

[valchkou]

Конечно же 1й вариант лучше чем второй. Зачем все элементы кидать в хэш сет, может быть входной массив будет очень большим, а 1й и 2й элемент в нем одинаковые. Т е O(N) for memory and runtime в 1м решение варьирует from O(1) to O(N) (most optimal and least optimal case), а во 2м решение O(N) for memory and runtime always O(N). Not cool.
Думаю возможно придумать решение и лучше, вообще без доп памяти но с лучшим рантаймом, если копать в сторону разных алгоритмов сортировки, коих я и так не знала а тут еще и забыла. В какому-то из алгоритмов возможно получится как-то совместить сортировку и проверку на дупликаты и получить лучше рантайм чем O(n log n) но тут я не уверена. Bucket sort, radix, merging sort, insert sort? В общем слышен звон, да не знаю где он.

на самом литкоде предложено решение, которое по их мнению самое оптимальное, а по моему самое дурацкое

Code: Select all

    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 1; ++i) {
        if (nums[i] == nums[i + 1]) return true;
    }
    return false;

допустим массив это список ID каких то объектов.
Теперь у меня ID это не интежер а UUID или строка или вообще сложный объект, и все, сломался наш самый эффективный алгоритм, новый надо делать.
С hashset же наоборот. Решение масштабируемое, универсальное, дубликаты можно найти для любых типов данных и объектов.
Насчет сортировок, они все время менются, в 7ке был TimSort, в 11 вот гляжу уже какойто DualPivotQuicksort.
Наверное можно взять какой нибудь сорт добавить свой IF и вот уже это ValchkouSort, можно писать диссертацию и файлить патент

[valchkou]

https://docs.oracle.com/javase/7/docs/a ... tml#add(E)
Обычно для контейнеров set, map, hash* - метод add работает подобно contains в случае дубликатов.

Code: Select all

        Set<Integer> set = new HashSet(nums.length);
        for (int num : nums) {
            if (!set.add(num)) return false;
        }
        return set.size() != 0;

но есть 2 замечания
1) if (!set.add(num)) return true;
2) последнее сравнение лишние, просто return false;

[valchkou]

https://docs.oracle.com/javase/7/docs/a ... tml#add(E)
Обычно для контейнеров set, map, hash* - метод add работает подобно contains в случае дубликатов.

Code: Select all

        Set<Integer> set = new HashSet(nums.length);
        for (int num : nums) {
            if (!set.add(num)) return false;
        }
        return set.size() != 0;

но есть 2 замечания
1) if (!set.add(num)) return true;
2) последнее сравнение лишние, просто return false;

этот вариант еще круче:
Runtime: 3 ms, faster than 99.69% of Java online submissions for Contains Duplicate.
Memory Usage: 42.5 MB, less than 82.79% of Java online submissions for Contains Duplicate.

[roadman]

Код подразумевал, что проверяем массив на уникальность элементов, в случае пустого массива возвращаем "false", как ошибку ввода, но это уже несущественные детали.

[Vladimir Kr.]

3 ms Contains Duplicate на 42.5 MB данных это супер!

[Vоvan]

https://docs.oracle.com/javase/7/docs/a ... tml#add(E)
Обычно для контейнеров set, map, hash* - метод add работает подобно contains в случае дубликатов.

Code: Select all

        Set<Integer> set = new HashSet(nums.length);
        for (int num : nums) {
            if (!set.add(num)) return false;
        }
        return set.size() != 0;

но есть 2 замечания
1) if (!set.add(num)) return true;
2) последнее сравнение лишние, просто return false;

этот вариант еще круче:
Runtime: 3 ms, faster than 99.69% of Java online submissions for Contains Duplicate.
Memory Usage: 42.5 MB, less than 82.79% of Java online submissions for Contains Duplicate.

Wrong Answer
Details
Input
[0]
Output
true
Expected
false

--
V.

[valchkou]

https://docs.oracle.com/javase/7/docs/a ... tml#add(E)
Обычно для контейнеров set, map, hash* - метод add работает подобно contains в случае дубликатов.

Code: Select all

        Set<Integer> set = new HashSet(nums.length);
        for (int num : nums) {
            if (!set.add(num)) return false;
        }
        return set.size() != 0;

но есть 2 замечания
1) if (!set.add(num)) return true;
2) последнее сравнение лишние, просто return false;

этот вариант еще круче:
Runtime: 3 ms, faster than 99.69% of Java online submissions for Contains Duplicate.
Memory Usage: 42.5 MB, less than 82.79% of Java online submissions for Contains Duplicate.

Wrong Answer
Details
Input
[0]
Output
true
Expected
false

--
V.

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

Code: Select all

        Set<Integer> set = new HashSet(nums.length);
        for (int num : nums) {
            if (!set.add(num)) return true;
        }
        return false;

[Сабина]

я тут на литкод зашел и решил свою первую задачку, аж прям радость распирает

Ну вот, с почином
Я с удивлением заметила что на «литкодах» народ не очень Скалу жалует. Ковырялась в Coderbyte и мое решение на Скале было первым для в общем то популярной задачки . Note to myself - писать где можно лучше на Скале вместо Джавы (точно) и Питона (May be)

[Сабина]

for(;;ol--)
c.add(I.valueOf(nums[ol]));

Что это у вас такое этакое внутри for(). Это ж тихий ужас! Зачем так писать?
Вам потом скажут после интервью "Решить было мало. Код нужно было писать красивее"

hee hee, I was playing to see how leetcode changes memory allocation.

It is defintely not the worst I need to deal with

--
V.

Мне тоже понравилось , типа кто поймёт тот заценит