Красота.

Вообще понятно? Надо по хорошему ребят спрашивать из чата, у которых нет 300+ нарешенных 😆, но они почему-то редко отписываются

почему в этом примере начинается с 8, а не с 1?

Вообще понятно? Надо по хорошему ребят спрашивать из чата, у которых нет 300+ нарешенных 😆, но они почему-то редко отписываются

Это сегодняшняя? Я ещё не решал, потом прочитаю

почему в этом примере начинается с 8, а не с 1?

видимо, потому что 1 находятся в разных списках. здесь хотят найти не одинаковое значение, а именно точку в которой списки «сливаются в один».

видимо, потому что 1 находятся в разных списках. здесь хотят найти не одинаковое значение, а именно точку в которой списки «сливаются в один».

intersectVal задаётся в условии явно.

понял, спасибо)

видимо, потому что 1 находятся в разных списках. здесь хотят найти не одинаковое значение, а именно точку в которой списки «сливаются в один».

+

я конечно понимаю, что просят O(1) по памяти, но очень лениво это писать когда просто можно сложить все в сет 😃

я конечно понимаю, что просят O(1) по памяти, но очень лениво это писать когда просто можно сложить все в сет 😃

А я это и не писал, нажал кнопочку "last submitted" 🤣

Правда код немножко улучшил, но это мелочи

Интересно, в чем сакральная суть Бесконечного отеля? То есть в чем суть вот этих всех перемещений постояльцев на номер+1? Не легче ли сделать вставку в конец списка (последний постоялец)+1?

Интересно, в чем сакральная суть Бесконечного отеля? То есть в чем суть вот этих всех перемещений постояльцев на номер+1? Не легче ли сделать вставку в конец списка (последний постоялец)+1?

это ж про парадокс бесконечных множеств?

там по-моему суть не в этих перемещениях, они просто нужны чтобы проиллюстрировать, что когда речь идёт о бесконечностях, то обычные сравнения к которым мы привыкли а-ля «количество комнат с нечетными номерами всегда меньше общего количества комнат» теряют смысл.

к чему этот вопрос вообще? ты какую книгу читаешь? 😃

Я сейчас читаю "Практика реактивного программирования в Spring 5". И почему-то в голове начал крутиться этот парадокс бесконечного отеля.

Я сейчас читаю "Практика реактивного программирования в Spring 5". И почему-то в голове начал крутиться этот парадокс бесконечного отеля.

ахаха. неожиданно 😃

там по-моему суть не в этих перемещениях, они просто нужны чтобы проиллюстрировать, что когда речь идёт о бесконечностях, то обычные сравнения к которым мы привыкли а-ля «количество комнат с нечетными номерами всегда меньше общего количества комнат» теряют смысл.

Т.е. суть была в том, что бы показать равенство нечетных чисел общему количеству чисел в бесконечности?

ахаха. неожиданно 😃

Да, такое у меня бывает)) позднее зажигание😂😂

Т.е. суть была в том, что бы показать равенство нечетных чисел общему количеству чисел в бесконечности?

Типа того, парадокс ж 😊

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

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

и привыкает к этому с детства.

... а потом ты поступаешь на мехмат и твой мир медленно рушится у тебя на глазах 😂

Да, в этом ракурсе, конечно, невероятный парадокс. Спасибо за разъяснения)))

Если есть желание прыгнуть в кроличью нору, рекомендую классику https://en.wikipedia.org/wiki/What_Is_Mathematics%3F

😁👍

В сегодняшней задаче неоптимальное решение лежит недалеко от оптимального) В неоптимальном можно бежать по одним и тем же листам K раз, пока не пересекуться, то есть cur1 = cur1 ? cur1.next : head1 cur2 = cur2 ? cur2.next : head2 А в оптимальном головы надо менять местами, когда дошли до конца)

Вот это я называю упоролся: https://github.com/mame/quine-relay

Кто не понял, этот код производит аутпутом код другого языка, который производит код еще другого языка и т.д., а в конце он возвращается в первый код

Свифта нет(

В сегодняшней задаче неоптимальное решение лежит недалеко от оптимального) В неоптимальном можно бежать по одним и тем же листам K раз, пока не пересекуться, то есть cur1 = cur1 ? cur1.next : head1 cur2 = cur2 ? cur2.next : head2 А в оптимальном головы надо менять местами, когда дошли до конца)

Ага. И потребуется всего два прохода

Ага. И потребуется всего два прохода

Да вроде за 1 можно

Да вроде за 1 можно

Как?

Как?

Ну это вроде не совсем один проход, но один while loop https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/1092935/Python-Short-but-difficult-solution-explained

Ну это вроде не совсем один проход, но один while loop https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/1092935/Python-Short-but-difficult-solution-explained

Полтора, можно сказать

Решил идти от обратного, делать не ИЗИ, а ХАРД решения для ПРО: https://leetcode.com/problems/average-of-levels-in-binary-tree/discuss/1094418/Python-short-tricky-solution-for-pros-explained

Решил идти от обратного, делать не ИЗИ, а ХАРД решения для ПРО: https://leetcode.com/problems/average-of-levels-in-binary-tree/discuss/1094418/Python-short-tricky-solution-for-pros-explained

да, нормальная тема через BFS, хотя DFS выглядит проще здесь, имхо. но для тренировки стоит и то и то написать.

да, нормальная тема через BFS, хотя DFS выглядит проще здесь, имхо. но для тренировки стоит и то и то написать.

Почему DFS проще? Наоборот же надо уровни посчитать...

Почему DFS проще? Наоборот же надо уровни посчитать...

ну как-то для понимания что ли проще: завёл мапу для уровней, прошёлся рекурсивно по дереву и разложил в мапу по уровням.

да, нормальная тема через BFS, хотя DFS выглядит проще здесь, имхо. но для тренировки стоит и то и то написать.

Так, не вижу апвоута. Намек понял, делаю иллюстрацию

то, как работает BFS, ещё знать надо.

но вообще поэтому для тренировки и полезно его написать.

ну как-то для понимания что ли проще: завёл мапу для уровней, прошёлся рекурсивно по дереву и разложил в мапу по уровням.

Да вроде я каждый уровень “складываю”, и иду дальше, все понятно вроде

Ладно, щас пример распишу

Да вроде я каждый уровень “складываю”, и иду дальше, все понятно вроде

не, всё понятно, я ж не про это. я просто говорю, что это чисто субъективное ощущение, что разложить по уровням рекурсивно проще, чем знать что BFS и так разложит тебе по уровням, потому что он так работает.

хотя на собесе мне было б интересно знает ли кандидат «как работает BFS».

не, всё понятно, я ж не про это. я просто говорю, что это чисто субъективное ощущение, что разложить по уровням рекурсивно проще, чем знать что BFS и так разложит тебе по уровням, потому что он так работает.

Наверное, я BFS решал на собесе в Яндекс 1.5 года назад, когда для меня деревья это в парке только были))00

Наверное, я BFS решал на собесе в Яндекс 1.5 года назад, когда для меня деревья это в парке только были))00

ну вот всё индивидуально. мне кажется, что рекурсивный обход дерева обычно люди раньше понимают чем BFS.

просто потому что с BFS сталкиваться где-то кроме литкода не приходится 😂

Хотя решение через BFS мне нравится. Написал оба 🙂

https://gist.github.com/vitkarpov/54c7f35cfce3b822cf57ad8500871d92

Решил идти от обратного, делать не ИЗИ, а ХАРД решения для ПРО: https://leetcode.com/problems/average-of-levels-in-binary-tree/discuss/1094418/Python-short-tricky-solution-for-pros-explained

Короче, кому интересно, в конце проитерировал одно дерево

Добби свободен, коллеги реально носок подарили

Добби свободен, коллеги реально носок подарили

😱

поздравляю 🙂

в добрый путь, как говорится.

https://www.instagram.com/p/BprbSnKFRW4/?igshid=1z2hthszzh0j

помню этот день у себя. такой день бывает только раз 😊

птенец выпархнул из уютного гнезда 😃

Как бы вы эту задачу решали? Как я это вижу: добавить в Trie, а потом где-то увидеть дп. https://leetcode.com/problems/concatenated-words/

Прорешал. Трай + бектрекинг. Дпшечку не использовал.

Задача классная, надо разбор делать.

var findAllConcatenatedWordsInADict = function(words) { const trie = new Trie(); function dfs(word, start, chainLen) { if (word.length == start) { // нужно убедиться, что нашли больше чем одно слово в цепочке return chainLen > 1; } let curr = trie.root; for (let i = start; i < word.length; i++) { curr = curr.get(word[i]); // если в дереве нет следующем буквы, // значит нет ни одного слова для продолжения if (!curr) { return false; } // если это лист, надо попборовать снова поискать все дерево // в поиске следующих слов, только отрезав уже найденный «префикс» if (curr.isLeaf && dfs(word, i + 1, chainLen + 1)) { return true; } } return false; } const result = []; // оптимизация, которая позволит // исключить TLE для кейса с общими префиксами: // a, aa, aaa, aaaa, aaaaa, ... // имеет смысл добавлять слова в трай постепенно, // т.к. в любом случае маленькие слова нельзя побить большими, // соответственно и в дереве они раньше времени не нужны words.sort((a, b) => a.length - b.length); words.forEach((word) => { if (dfs(word, 0, 0)) { result.push(word); } else { trie.add(word); } }); return result; }; class Trie { root = new Node("") add(word) { let curr = this.root; for (let i = 0; i < word.length; i++) { curr = curr.add(word[i]); } curr.isLeaf = true; } } class Node { isLeaf = false; children = new Array(26); constructor(val) { this.val = val; } add(val) { const idx = this.idx(val); if (!this.children[idx]) { this.children[idx] = new Node(val); } return this.children[idx]; } get(val) { return this.children[this.idx(val)]; } idx(val) { return val.charCodeAt(0) - 'a'.charCodeAt(0); } }

В принципе. если исключить сам трай отсюда, то даже компактная получилась.

Прорешал. Трай + бектрекинг. Дпшечку не использовал.

Ого. Благодарю, изучу решение.

По времени нормально?

По времени нормально?

вроде норм

👍

по крайней мере, проходит.

я там отметил оптимизацию без которой не проходит.

то есть все слова заранее в трай пихать нельзя.

то есть все слова заранее в трай пихать нельзя.

Почему? 🤔

А, нашел комментарий

Почему? 🤔

а там есть кейс с a, aa, aaa, aaaa... и тогда этот dfs начинает зря искать просто как не в себя.

ага.

я сперва делал просто, потом этот кейс свалился.

пришлось чутка оптимизировать.

https://www.instagram.com/p/BprbSnKFRW4/?igshid=1z2hthszzh0j

Ага, у меня такой фоточки уже не будет... Электронная трудовая

помню этот день у себя. такой день бывает только раз 😊

Пхахаа, у меня коллега уже 2ой раз из Я уходит))0)

Пхахаа, у меня коллега уже 2ой раз из Я уходит))0)

вернулся только за ачивкой терминатора? 😃