I used translation 😶

Зато бивикли первые три простые, четвёртая хард. Не сбалансированные контесты.

Бабичев небось все решил? Или дп на графе подзавалил?

Вот сегодншняя задачка вообще плохая. Ну какой int to int hashmap… Детский сад какой-то. Я сначала обрадовался что нормальная мапа будет из строки в значение

ну а че, по сути будет разница в функции хеширования, очевидно с числами она намного проще, но саму мапу написать придётся.

капасити у хеш-таблицы 10^6? ну-ну.

Как в условиях

а если попросят рехеширование написать, так это вообще весело.

Я вот на это и надеялся. Через trie знаю как, а вот с честным хэшированием...

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

это я все к тому, что задачка не такая простая. хорошая задача для собеседований.

Посмотрел на другие решения на JavaScript, и кажется люди реально не понимаю, что такое хеш-таблица. var MyHashMap = function() { this.data = []; }; MyHashMap.prototype.put = function(key, value) { this.data[key] = value; }; MyHashMap.prototype.get = function(key) { return this.data[key] !== undefined ? this.data[key] : -1; }; MyHashMap.prototype.remove = function(key) { this.data[key] = -1; }; Говорят в условии — не используйте встроенную хеш-таблицу в языке. Интересно, а вот когда ты пользуешься массивом нефиксированной длины, это ты чем пользуешься под капотом? 😄

Ээ, а чем пользоваться? Массивом? (Задачу не читал)

@Glazomer47 вот тебе непаханное поле для написание статей в дискасе 🙂

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

Ну в V8 вроде массивы это непрерывные куски, но задача понятна. Я перестал открывать литкод :)

Ну в V8 вроде массивы это непрерывные куски, но задача понятна. Я перестал открывать литкод :)

Если бы они условие задачи поменяли с интов на строки, это заставило бы людей подумать как написать нормальную хэшмапу)

https://pastebin.com/yhWA1q25 С рехешированием, но по легкому пути — через бакеты 😀

капасити у хеш-таблицы 10^6? ну-ну.

ну да, на самом деле, можно написать как угодно, оно пройдёт.

удобно.

А вообще, я когда увидел эту задачу, быстро в голове прокрутил 3 реализации (Buckets=LinkedList, Linear probing и Buckets=RBTree) понял, что все помню и сделал capacity = 10^6. ;D

😁 прально, зачем нам эти все эти линкед листы...

ну, кстати, да.

Бабичев нормальное объяснение сделал https://leetcode.com/problems/design-hashset/discuss/768659/Python-Easy-Multiplicative-Hash-explained

Хто старое, он уже новое сделал

Да там у него вроде одинаковое

Кстати, я вот никогда не мог без подглядки написать RBTree. Я все время забываю правила, которые надо соблюдать, чтобы дерево было по определению красно-черное. И еще левая и правая ротации пишу с ошибками с первого раза)

Кстати, я вот никогда не мог без подглядки написать RBTree. Я все время забываю правила, которые надо соблюдать, чтобы дерево было по определению красно-черное. И еще левая и правая ротации пишу с ошибками с первого раза)

Red-Black Tree

Не-а, только в академических целях) Когда участвовал в олимпиаде, наблюдал картину, как парень накинул все дерево за 2-3 минуты)

Не-а, только в академических целях) Когда участвовал в олимпиаде, наблюдал картину, как парень накинул все дерево за 2-3 минуты)

@KlenZeleny кстати, это та задача про concatenated words. я решил вкрутить туда дпшечку для порядка, а то вариант с сортировкой выглядит как хак больше.

И как вкрутил? [i][j] — есть ли в этом префиксе от i до j конкатенация слов? bool

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

А напомните плз ссылку на эту задачу