https://leetcode.com/problems/concatenated-words/

Спасибо

Кстати, а почему бы не хранить в сете не саму строку, а ее хеш?

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

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

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

В общем, я решил поступить иначе. По аналогии, с этой задачей https://leetcode.com/problems/word-break/ — по сути, она является составной частью.

Не решал её. Почему-то.

Здесь дпшечка делает по суффиксу тоже, но ты просто хранишь индекс. То есть dp[i] значит суффикс, начиная с i-го символа можно разбить, а значит пересчитывать не надо.

Я так же хотел делать только зачем-то хранить сами суффиксы, а это копирование строк.

Фу-фу.

Здесь дпшечка делает по суффиксу тоже, но ты просто хранишь индекс. То есть dp[i] значит суффикс, начиная с i-го символа можно разбить, а значит пересчитывать не надо.

Т.е. ты идешь с конца налево, и для каждого индекса i проходишь направо до конца и ищешь до первого j, где bool=true и [i,j-1] — слово из словаря. И в этот i пишешь true, если нашёл. Так?

Т.е. ты идешь с конца налево, и для каждого индекса i проходишь направо до конца и ищешь до первого j, где bool=true и [i,j-1] — слово из словаря. И в этот i пишешь true, если нашёл. Так?

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

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

А зачем тут кеш? 🤔

Мне эта задача напомнила задачу про лягушку

А зачем тут кеш? 🤔

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

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

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

Да нормально. С сортировкой хорошо получилось.

Я тут решал вчера вот эту задачу: https://leetcode.com/problems/closest-dessert-cost Тоже пригодилась сортировка. Потратил много времени, тег Greedy только сбил с толку.

А зачем тут кеш? 🤔

кеш = дпшечка, я имею в виду.

Я тут решал вчера вот эту задачу: https://leetcode.com/problems/closest-dessert-cost Тоже пригодилась сортировка. Потратил много времени, тег Greedy только сбил с толку.

👍

кеш = дпшечка, я имею в виду.

Всё, понял.

Т.е. ты идешь с конца налево, и для каждого индекса i проходишь направо до конца и ищешь до первого j, где bool=true и [i,j-1] — слово из словаря. И в этот i пишешь true, если нашёл. Так?

Реализовал решение. Только проход не с конца, а с начала. public class Solution { public bool WordBreak(string s, IList<string> wordDict) { int len = s.Length; bool[] dp = new bool[len+1]; dp[0] = true; HashSet<string> hs = new HashSet<string>(wordDict); int j = 1; while (j <= len) { int i = j - 1; do { if (dp[i] == true && hs.Contains(s.Substring(i, j-i))) { dp[j] = true; break; } i--; } while (i >= 0); j++; } return dp[len] == true; } }

У тебя наверно такое же.

Пипец, решал сейчас задачку на дп (готовлю на завтра статью), есть стандартная проверка const dp = {}; // ... if (dp[suffix]) { return dp[suffix]; } И упал один тест, где dp["constructor"] сказал true в этом месте, хотя не должен был. Это урок про зачем нужен hasOwnProperty 🙂 Вкрутил Map, в итоге.

https://t.me/ctci_chat_ru/7168

И вы ниже написали как это обойти 🙃 Вроде еще hasOwnProperty поможет

https://t.me/ctci_chat_ru/7168

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

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

Виктор, не перестаю удивляться вашей позитивностью! 🤣 У вас стакан наполовину полон водой, а на другую половину полон воздухом

Виктор, не перестаю удивляться вашей позитивностью! 🤣 У вас стакан наполовину полон водой, а на другую половину полон воздухом

Именно! 🙂

Именно! 🙂

Мб статью как так думать?)

@vitkarpov Word Break II порекомендовала Concatenated Words. Не зря они показались похожими.

Мб статью как так думать?)

лол. мотивационный тренинг 😂

Виктор, не перестаю удивляться вашей позитивностью! 🤣 У вас стакан наполовину полон водой, а на другую половину полон воздухом

Наполовину полон водой, на другую половину воздухом, и ещё наполовину ромом 🤣

Наполовину полон водой, на другую половину воздухом, и ещё наполовину ромом 🤣

Бутылка рома наполовину полна, а на другую половину в надежном месте

А имплементация таких вещей как mutex и semaphore к алгоритмическим задачам относится или все же к систем дизайн?

А имплементация таких вещей как mutex и semaphore к алгоритмическим задачам относится или все же к систем дизайн?

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

зависит от позиции ещё, наверное, и от собеседующего. конкретный пример, когда я был на собесе в гугле, на плюсовика SRE-шника, то был обычный литкод (хард), параллельный код писать не нужно было.

но понятно, что по одному случаю общий вывод делать не стоит.

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

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

Там их очень мало(((

Там их очень мало(((

это правда, это минус.

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

А написать такие структуры данных, это уже из категории “что-то пошло не так”?)

На самом деле, не знаю даже как писать такую штуку на тру трэдах. На промисах пишется не шибко тяжело

На самом деле, не знаю даже как писать такую штуку на тру трэдах. На промисах пишется не шибко тяжело

А какую штуку?

mutex например

А, понял. Ну это тоже странно. Я думал ты про использование.

То есть тебе дают задачку и надо написать для неё структурку, которая будет поддерживать параллельное чтение/запись.

И ты расчехляешь мьютекс и пишешь.

Говоришь про живые и мертвые локи, и вот это всё.

Такой вариант мне кажется норм.

у меня вопрос, наверное, не в тему, но) сейчас делаю дз по CQRS Event Sourcing и вот задумываюсь: на диаграмме компонентов Event store что обычно используется разработчиками в качестве event store? А то по докладам этот момент для меня не очень раскрылся Стоит ли использовать здесь кафку/кролика? вопрос, наверное, про систем дизайн)

Говоришь про живые и мертвые локи, и вот это всё.

ну вот это больше похоже на сис. диз (не только же про дистрибутивные системы говорить)

у меня вопрос, наверное, не в тему, но) сейчас делаю дз по CQRS Event Sourcing и вот задумываюсь: на диаграмме компонентов Event store что обычно используется разработчиками в качестве event store? А то по докладам этот момент для меня не очень раскрылся Стоит ли использовать здесь кафку/кролика? вопрос, наверное, про систем дизайн)

DynamoDB с двумя табличками 😄

DynamoDB с двумя табличками 😄

сразу видно, что из Амазона!

у меня вопрос, наверное, не в тему, но) сейчас делаю дз по CQRS Event Sourcing и вот задумываюсь: на диаграмме компонентов Event store что обычно используется разработчиками в качестве event store? А то по докладам этот момент для меня не очень раскрылся Стоит ли использовать здесь кафку/кролика? вопрос, наверное, про систем дизайн)

А что за дз? Что проходишь?

А что за дз? Что проходишь?

system design предмет прошлые два дз были на реактивщину и акторы эта на ивент саурсинг преподает человек из Яндекса СПБ)

system design предмет прошлые два дз были на реактивщину и акторы эта на ивент саурсинг преподает человек из Яндекса СПБ)

я, наверное, пропустил где ты учишься 🙂

я, наверное, пропустил где ты учишься 🙂

ИТМО

ИТМО

Понял. Вот это я понимаю обучение!

ИТМО

Там случаем в acm-ной команде не состоишь? 🙂

Там случаем в acm-ной команде не состоишь? 🙂

я на этой кафедре учусь, но никогда не участвовал и даже не близок к этому(халявил на 1-2 курсе алгоритмы), хоть и друзья с потока финалисты)

DynamoDB с двумя табличками 😄

а разве тут правильный ответ не “it depends”?)

а разве тут правильный ответ не “it depends”?)

Это правильный ответ на всё, мне кажется 🙂

У меня есть еще один вопрос относительно подачи резюме. Кто-нибудь когда-нибудь писал Cover letter и если писали о чем оно должно быть? Подаюсь на 3 вакансии и везде cover letter хотят)

У меня есть еще один вопрос относительно подачи резюме. Кто-нибудь когда-нибудь писал Cover letter и если писали о чем оно должно быть? Подаюсь на 3 вакансии и везде cover letter хотят)

Я избегал этого всегда либо с помощью рефера от человека, либо потому что рекрутер сам доходил до меня на Линкедине.

У меня есть еще один вопрос относительно подачи резюме. Кто-нибудь когда-нибудь писал Cover letter и если писали о чем оно должно быть? Подаюсь на 3 вакансии и везде cover letter хотят)

Я раньше писал что-то типа «Знаю, что вы делаете клевый продукт и хочу стать частью вашей команды». Но более развернуто, конечно. Всегда прокатывало

Все больше и больше людей из этого чата встречаю в твиттере, айтишная туса и правда очень небольшая :))

Все больше и больше людей из этого чата встречаю в твиттере, айтишная туса и правда очень небольшая :))

Тоже увидел пост @Semper_viventem о переезде в Таллин?)

Тоже увидел пост @Semper_viventem о переезде в Таллин?)

Да )

Про животных особенно секцию тщательно прочитал ))

Когда все так массово уезжают, желание поучавствовать в данном процессе растет)

Про животных особенно секцию тщательно прочитал ))

Обязательно расскажу об этом еще подробнее по ходу дела! )) Там, судя по всему, еще будут приключения

Можно ссылку на пост, пожалуйста

Обязательно расскажу об этом еще подробнее по ходу дела! )) Там, судя по всему, еще будут приключения

Спасибо )

Можно ссылку на пост, пожалуйста

https://twitter.com/semper_viventem/status/1368602209089429507?s=21

https://twitter.com/semper_viventem/status/1368602209089429507?s=21

Спасибо)

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

Happy Monday! 👋 На этой неделе разбираемся с префиксными деревьями. Будем искать слова, которые могут быть составлены конкатенацией других слов. https://vitkarpov.me/posts/concatenated-words/

Капец, только сейчас решил Бивикли Хард 🤣 https://leetcode.com/problems/count-pairs-of-nodes/discuss/1099417/Python-Same-algorithms-as-DBabichev-but-shorter-code

Капец, только сейчас решил Бивикли Хард 🤣 https://leetcode.com/problems/count-pairs-of-nodes/discuss/1099417/Python-Same-algorithms-as-DBabichev-but-shorter-code

Выглядит и вправду коротко.

Выглядит и вправду коротко.

На самом деле там на строк 5-6 меньше чем у Бибича. Можно еще короче, там некоторые переменные всего 1 раз встречаются, но это уже хуже выглядить будет