Мне интересно, как вы оцениваете свой уровень? Я не наезжаю, просто интересуюсь) просто я был на собесах даже больше, чем на 180к и там дают задачи не сильно сложнее этой. Обычно вообще собес на Джуна и Мидла отличается вопросами более глубокого понимания работы стека и в целом технологий, а задачки +- одни и те же
Ну да, всем известно же что на работе за 180к кодеры только и пишут код который буквы подсчитвает. Я проходил такие собесы, а потом смотришь на их реальные задачи, а они даже не близко к этому. Там на самом деле просто объёмные, но простые вещи. И эти задачи на собесе по итогу нафиг не упали. Я потом когда работу менял, то сразу извинялся, прощался и покидал зум когда они просилитна собесе вот такие вот тупые задачи решать, хотя портфолио моё видели заранее. В итоге остался в компании которая притащила на собес свою реальную задачу из своей такс-доски, я на словах рассказал чтобы и как решал и мы ударили по рукам. А зп там куда больше 180к и мы отлично работаем и по сей день.
У нас есть очередь задач (пара тысяч м.б. в очереди), которую бэкенд присылает каждый раз, когда одна из задач обновляется. Если статус какой-то задачи изменился, то на фронтенде нужно вывести уведомление. Раньше мы сравнивали статусы 2-х наборов задач с помощью цикла в цикле. А теперь используем решение, аналогичное представленному в ролике. Так что ролик довольно полезный даже для программиста за 180 К
@@MrDima123123из моего комментария Вам нужно было понять что на собеседовании спрашивали то, чем не занимаются, а занимаются тривиальными вещами. Но, видимо, Вы из тех клоунов, что для важности раздувают сопли.
Тогда, будь в слове 3 одинаковых символа, такой символ бы ывелся дважды. Самое простое решение - преобразовать строку во множество. Конечно, операция можно занять немного больше времени, но понять её будет намного проще.
Показанное решение прекрасно. Хочу добавить ещё одно, чтобы была возможность выбора. Суть решения такая: сортируем массив стандартной либой (в Java Arrays.sort(arr), сложность merge сортировки) и получаем что одинаковые символы стоят рядом, запускаем массив который будет считать повторяющиеся элементы и если больше одного одинакового подряд - сохраняем. Сложность: O(N)
Map построен на основе бинарного дерева. Скорость этого варианта будет хуже, так как при каждом добавлении элемента в список (ну и проверки на наличие) будет выполняться поиск этого самого элемента, а поиск в бинарном дереве - logN. В итоге алгоритм обретет сложность NlogN.
for i in range(len(word)) : key = word[i] map[key]++ проходимся по слову, и увеличиваем счетчик в мапе, где ключ - символ. если написал с ошибками сори, не на питоне пишу)
и для каждого символа считать по новой хеш и тд, зачем? каждый символ можно представить в виде числа (аски код), создаём массив с нужной длиной, заполняем нулями и затем добавляем 1, если попали в соотв. ячейку по индексу кода буквы, если в ячейке уже лежит 1, то нашли повтор
А ничего, что добавление в словарь приводит к memory reallocation (на что тратится хуева туча тактов ЦП) и для коротких строк типа ПОДПИШИСЬ цикл в цикле отработает быстрее?
@@Torbjorn-ph7rt Словарь устроен так, что выборка значения происходит, грубо говоря, методом половинного деления. То бишь, для находжения одного элемента из миллиона перебор будет состоять из максимум 15 итераций, что есть очень быстро. Но вот добавление в словарь это действительно тяжелая операция с высокой стоимостью выполнения.
А еще можно взять 32 битное число, и букву пихать в номер бита, соответствующий номеру буквы в алфавите, если бит итак равен 1, значит ранее буква встречалась, и выводим ее,
А в хеш-таблице тоже сложность своя присутствует, нужно захешировать ключ, получить ячейку массива, проверить на соответствие, т.к. два разных ключа могут иметь один хеш, ну и при заполнении тоже формируется массив в каждом элементе которого связные списки и другие сервисные данные.
При идеальном хешировании сложность в худшем случае все равно будет константой. Если использовать другое хеширование, цепочками, например, то амортизированная сложность будет константой, что на практике +- соответствует О(1) в среднем для каждого запроса. Поэтому в видео все сказано правильно.
А как работает применяемый метод containskey? Что под капотом? Прогонялось ли это через stopwatch относительно цикла в цикле? И насколько разница, если она вообще есть?
А ещё можно завести массив интов arr на 256 значений. И при чтении строки просто str в одном цикле делать arr[str[i] ]++. Сложность та же О(n), зато быстрее, чем со словарями.
В среднем поиск в хеш-таблице О(1) Так как под «капотом» там лежит все тот же массив, а ключ это адрес ячейки массива, который прошел через хеш функцию
зависит от реализации "словаря". Обычно там дерево или хэш-таблица. В данном случае конечно же хэш-таблица нужна, но и дерево сойдет. На миллионе дерево лишь в 20 раз проиграет
Слушай, а ты думаешь под капотом не происходит то же самое? Это не волшебная палочка все таки. Теперь уже внутри словарика при добавлении уже чужому коду надо определять была ли эта буква в словаре или нет.
Дело не в языке. Это лишь одна из списка задач на собесах. А не та задача, решив которую тебе дадут оффер). Зачастую на собесе целый ряд задач разного уровня сложности. Данная задача популярная из списка простых.
Зачем создавался массив characters? foreach прекрасно кушает строки. Плюс использование var крайне не рекомендую - читабельность и понятность кода резко снижается. До вывода на экран докапываться не буду, но по факту он очень долгий (лучше использовать StringBuilder). Да и задача, прошу прощения, для первокурсника. Не представляю кто вообще не способен такую задачу решить. По-моему такая задача бесполезна.
Можно еще отсортировать строку и если следующий элемент не больше предедущего, добалять его в овтет. Тогда сложностт по времени будет (n*logn) а по памяти O(1)
если предположить что старший бит не занят, то можно его использовать как признак повторения , а можно просто отсортировать массив и тогда вообще все просто ))
любая сортировка не сработает быстрее чем за линию, а если строка еще будет достаточно большой, то понадобится много памяти, когда для словаря нужна константная память
Это называется Big O нотация. Сильно углубляться в нее может и не стоит просто так, но базовое понимание точно должно быть, чтобы ты мог оценить примерно свой придуманный алгоритм при решении той или иной задачи на работе. Без такого понимания ты можешь выдать решение, оно будет медленным и ты не будешь понимать, что в нем не так и как исправить.
@@la_maksimвсего переборов будет n(n-1)/2, но для оценки сложности коэффициенты опускаются, получается n^2. Попросту это значит, что если увеличить число входных параметров (длину строки) в n раз, то время работы программы увеличится в n^2 раз
В коммерческом коде в веб разработке это используется только на бекенде, в высоконагруженных сервисах, фронтовичкам, которые инпуты вычисляют это ничего не даст, но если на собесах будет тим лид команды бекенда он скорее всего спросит
Алгоритмическая сложность воего решения О(N*logN) тк обращение к словарю производится за логарифм, лучше было бы создать массив в котором индекс будет равен инжексу буквы, и обращаться к этому за О(1), тогда ты получишь решение за линию и за столько же памяти
Это неправда. Словарь в питоне это хешмапа. А в хешмапа за единичку. В С++ это были бы правдой, там структура map построена на красно-черном дереве, и вставка в неё действительно за logn, но в тех же плюсах есть unordered_map, которая хешмапа, и в которую вставлять за единичку опять же Короче словарь в видео неправильное слово. Правильное - хешмапа
@@АнтонПичушкин-у6р это не правда. Прочитай про устройство хешмапы. Она не работает за единичку Так что надо пользоваться мапой обычной, а в данной задаче где входные значения сильно ограничены - можно просто создать массив и в нём хранить, что действительно будет работать суммарно за линию
@@ОлегАн-т5жесли строка содержит для примера только латиницу нижнего регистра, то создаёшь массив размера 26, ячейки в котором содержат количество вхождений символа в строку (в коде это выглядит как то так arr[ch-'a']++, где ch - символ строки). Что сложного? И максимум это задача для стажёра.
@@MikhailVinogradov-nk7kd Слышу звон но не знаю где он? Еще раз, мой вопрос адресован комментатору который предлагает создать ОДИН МАССИВ где по номеру индексу будет СОДЕРЖАТЬСЯ буква. Возникает вопрос ЕСЛИ У ТЕБЯ ТОЛЬКО ОДИН МАССИВ где уже СОДЕРЖАТЬСЯ БУКВЫ то где ты будешь хранить количество встреч этой буквы? Что сложного? Читай ВНИМАТЕЛЬНО ТЗ а не умничай.
Верно подметил. Сейчас страшно смотреть сколько браузер памяти кушает :D Как по мне на проц пофиг он невероятно мощный, а вот память по прежнему узкое место)
Переводим в массив или объект, используем set, потому что это даст нам только уникальные значения в коллекции, далее выводим те значения, которые убрал сет и получаем коллекцию уникальных значений и какую-то структуру на свой выбор из повторяющихся
@@vryaboshapko такого интерфейса, увы, нет, в моем комментарии предполагалось сравнить значения исходного массива с тем что вернул нам сет, обычно этот способ больше подходит для того чтобы убрать дубликаты и нам не важно что именно было удалено, если это критично, то самый лучший вариант использовать объект для подсчета вхождений элемента
@@drm365 Смысл был не в эффективности, а в том, чтобы вместить всё в одну инструкцию. Убрав переносы строк, ты не уменьшишь кол-во инструкций. Сложность O(N^2), да, неэффективно.
Делаем масив интов на 255 эллементов и делаем arr[ch[i]]++ для всех символов строки. Это, наверно, самый быстрый способ, у него гарантировано точность O(n), цикл прохода по строке содержит только 1 строку в которой нет ни условного оператора, ни вызова функций с неизвестной собственной сложностью. А использование метода из видоса вполне возможно имеет сложность O(n²).
Генератором посчитать 5 сек, так что не думаю, что тут можно говорить о 180к, ну а если и так, то я, заканчивающий 11 класс, могу прретендовать на должность мидла
Есть, но тогда на собесе могут попросить реализовывать данный функционал вручную. Как правило такие задачи запрещается решать с помощью готовых методов языка.
чел!!! O(N) - ты не получишь! А накладные расходы для поддержки хештаблицы? Те ты считаешь, что запись в хештаблицу моментально пишется? Говорить, что В РАЗЫ - автор, ты реально теоретик?
Друг, тут речь не идёт о том, что будет по факту исполняться в разы быстрее, а про чисто теоретическое big O. И автор все правильно сказал. Цикл в цикле это действительно сложность O(n²), а цикл с хэштейблом - O(n), что в чистой теории очевидно намного лучше. Хеш таблицы тут как пример и могут быть заменены, а подход действительно алгоритмически более правильный
Формально говоря, Хэш-таблица работает за О(1+а), где а - коэффициент заполнения, но ожидаемое время работы константное, при благоприятном(минимальном) числе коллизий
@@vvalik значит сначала нужно узнать алфавит, иначе считать алфавит как с бесконечным числом символов, для которого понадобится соответствующая хэш-таблица, и подход к решению задачи будет иным. Мне, конечно же, очень нужна хэш-таблица для алфавита с 1 символом. Точно так же, как она нужна мне и для алфавита с n количеством символов, где можно изначально использовать статическую структуру данных, работающую быстрее. А если бы нужно было слова посчитать - совсем другое дело
эм регулку, можно использовать нет? let a = 'подпишись'; for(let el of a) { let arr = a.match(new RegExp(`${el}`, 'gi')); if(arr.length >1) { console.log(el) } } на js вот так выглядит)
Решил но наверное не самым выгодным способом по памяти, создал массив длины 27 (колво букв в алфавите) и в а[0] добавлял +1 когда встречал букву a, в а[1] b и по аналогии, потом смотрел где больше 1, и выводил буквы
Идея хорошая, но надо брать не кол-во букв в алфавите, а кол-во ASCII символов, если кодировка строки в ASCII. Тогда и англ и русский и пробелы и другие символы тоже будут работать. Единственное если кодировка будет 4 байтовая, то такой массив получится в 4 гб и тут придется или хитрить с битами или еще что-то придумывать, в большинстве случаев при такой большой кодировке метод из видео будет эффективнее.
@@ОлегАн-т5жну, во-первых, никто не говорил про про неиспользование коллекций. во-вторых, задача действительно максимально простая, так еще и у автора видео не лучший вариант решения.
Да, но она предлагалась в качестве одной из задач на собесе. Нужно же понимать, что на собесе дается целый ряд задач разной сложности. Только решив ее оффер не получишь.
Надо бы проверять на реальное быстродействие. Какие там алгоритмы работают при составлении списков, добавлении, чтении... да чёрт его знает. Может быть рельно быстрее работает первый способ.
Это задача, которой бездельники-ютуберы, которым лень сделать что-то полезное, кормят своих подписчиков. Кстати, прикинь, в первом предложении есть вложенное лексическое условие. Я почти прошёл собес на филолога с зп 180к. И если тебе важно сохранить порядок символов, хеш таблица не подходит, тк она сортирует по значению хеш функции.
@@Neo-fi5zr и словарь и map, это структура данных с одинаковым интерфейсом, поэтому сложно сказать как и что правильнее называть, у всех по-разному. Но я придерживаюсь того, что словарь основан на хэш-таблице, а map основана на бинарном дереве поиска.
![เปิด อาณาจักร หมื่นล้าน "สาระตั้ม" l [Nickynachat]](http://i.ytimg.com/vi/3XE0nPF4YkQ/mqdefault.jpg)
📢 ССЫЛКА НА TELEGRAM канал по .NET разработке: t.me/lightcode_group
⚡ ПОДДЕРЖКА канала на boosty: boosty.to/lightcode
легкая программа
Если это задача на 180к, то задача на 80к - напишите программу выводящую "Hello World"😂😂😂
А за 40к?
@@binancetraider658 знать как включить компьютер. Что в общем то и указывается в вакансиях ("...уверенный пользователь ПК...")
@@binancetraider658Включите компьютер
Это задача на 180к, а не целое собеседование на 180к)
Мне интересно, как вы оцениваете свой уровень? Я не наезжаю, просто интересуюсь) просто я был на собесах даже больше, чем на 180к и там дают задачи не сильно сложнее этой. Обычно вообще собес на Джуна и Мидла отличается вопросами более глубокого понимания работы стека и в целом технологий, а задачки +- одни и те же
Ну да, всем известно же что на работе за 180к кодеры только и пишут код который буквы подсчитвает. Я проходил такие собесы, а потом смотришь на их реальные задачи, а они даже не близко к этому. Там на самом деле просто объёмные, но простые вещи. И эти задачи на собесе по итогу нафиг не упали. Я потом когда работу менял, то сразу извинялся, прощался и покидал зум когда они просилитна собесе вот такие вот тупые задачи решать, хотя портфолио моё видели заранее. В итоге остался в компании которая притащила на собес свою реальную задачу из своей такс-доски, я на словах рассказал чтобы и как решал и мы ударили по рукам. А зп там куда больше 180к и мы отлично работаем и по сей день.
У нас есть очередь задач (пара тысяч м.б. в очереди), которую бэкенд присылает каждый раз, когда одна из задач обновляется. Если статус какой-то задачи изменился, то на фронтенде нужно вывести уведомление. Раньше мы сравнивали статусы 2-х наборов задач с помощью цикла в цикле. А теперь используем решение, аналогичное представленному в ролике.
Так что ролик довольно полезный даже для программиста за 180 К
@@MrDima123123если это не стёб, то соболезную
правильный подход, мне одни клоуны предложили задачу по оптимизации кэша сервера, а реальные задачи: рисовать уи в хамле. было смешно.
@@dagaric2 какой ещё кэш сервера, какая оптимизация, ты о чем вообще?
Ты адекватно способен свою точку зрения донести?
@@MrDima123123из моего комментария Вам нужно было понять что на собеседовании спрашивали то, чем не занимаются, а занимаются тривиальными вещами. Но, видимо, Вы из тех клоунов, что для важности раздувают сопли.
Вот такие видео, отбивают у меня желание изучать программирование
Прикол в том, что чем больше зп и грейд, тем легче задачи на собесах
В основном на опыт смотрят. Задачу дают чтобы проверить что не совсем врешь
в одном случае экономим память тратя процессорное время, во втором наоборот. Все случаи хороши в определенных условиях
Братан, хорош, давай, давай, вперёд! Контент в кайф, можно ещё? Вообще красавчик! Можно вот этого вот почаще?
Спасибо, как раз изучал эту тему❤
Можно было бы просто попытаться добавить ключ символ в словарь, если уже есть просто выводить что этот символ повторяется😮
Тогда, будь в слове 3 одинаковых символа, такой символ бы ывелся дважды.
Самое простое решение - преобразовать строку во множество.
Конечно, операция можно занять немного больше времени, но понять её будет намного проще.
Показанное решение прекрасно. Хочу добавить ещё одно, чтобы была возможность выбора. Суть решения такая: сортируем массив стандартной либой (в Java Arrays.sort(arr), сложность merge сортировки) и получаем что одинаковые символы стоят рядом, запускаем массив который будет считать повторяющиеся элементы и если больше одного одинакового подряд - сохраняем. Сложность: O(N)
Сортировка nlogn
Можно в одну итерацию через map. Делаем +1 для map[element] и если map[element] ==2 , кладём элемент в результирующий массив)
нет разницы, и то и то - О(n)
@@leniviy_uebok да,но так не нужен второй цикл)
@@МаргаритаПодвигинабез разницы.
Лучше уже тогда >=2. Так как если будет 3 и более совпадающих элемента, у тебя из просто не выведет
Map построен на основе бинарного дерева. Скорость этого варианта будет хуже, так как при каждом добавлении элемента в список (ну и проверки на наличие) будет выполняться поиск этого самого элемента, а поиск в бинарном дереве - logN. В итоге алгоритм обретет сложность NlogN.
А откуда в словаре взялись числа, обозначающие количество включений?
В цикле прошли по списку с записали символы в словарь, это же сказали в ролике
for i in range(len(word)) :
key = word[i]
map[key]++
проходимся по слову, и увеличиваем счетчик в мапе, где ключ - символ. если написал с ошибками сори, не на питоне пишу)
@@VaeV1ct1s чтобы в словаре изменить число с 1 на 2, нужно найти в словаре, а это снова цикл. Никуда цикл не делся.
@@tupitochka8841 что ты несёшь? Обращение к элементу хешмапы по ключу за О(1)
@@tupitochka8841 в словаре не нужно ничего искать, на то он и словарь.
и для каждого символа считать по новой хеш и тд, зачем? каждый символ можно представить в виде числа (аски код), создаём массив с нужной длиной, заполняем нулями и затем добавляем 1, если попали в соотв. ячейку по индексу кода буквы, если в ячейке уже лежит 1, то нашли повтор
А ничего, что добавление в словарь приводит к memory reallocation (на что тратится хуева туча тактов ЦП) и для коротких строк типа ПОДПИШИСЬ цикл в цикле отработает быстрее?
Так ещё и выбор в словаре под капотом это по сути перебор
@@Torbjorn-ph7rt Словарь устроен так, что выборка значения происходит, грубо говоря, методом половинного деления. То бишь, для находжения одного элемента из миллиона перебор будет состоять из максимум 15 итераций, что есть очень быстро. Но вот добавление в словарь это действительно тяжелая операция с высокой стоимостью выполнения.
@@Torbjorn-ph7rt не перебор
А разве приведение строки к массиву чаров обязательно делать? String это же и так контейнер чаров, его сразу же в foreach и засунули бы...
Все верно, можно итерироваться по строке сразу. Тут больше для новичков, чтобы был алгоритм понятнее, поэтому явно работаем с массивом
А еще можно взять 32 битное число, и букву пихать в номер бита, соответствующий номеру буквы в алфавите, если бит итак равен 1, значит ранее буква встречалась, и выводим ее,
крестовый спалился
И на юникоде тебя попустят, а ещё это дополнительные такты на наложение маски и сдвиги.
А при чём здесь юникод или нет@@ДенисСомин
А в хеш-таблице тоже сложность своя присутствует, нужно захешировать ключ, получить ячейку массива, проверить на соответствие, т.к. два разных ключа могут иметь один хеш, ну и при заполнении тоже формируется массив в каждом элементе которого связные списки и другие сервисные данные.
При идеальном хешировании сложность в худшем случае все равно будет константой. Если использовать другое хеширование, цепочками, например, то амортизированная сложность будет константой, что на практике +- соответствует О(1) в среднем для каждого запроса. Поэтому в видео все сказано правильно.
А зачем словарь, можно и массивом обойтись, символы можно и числам привести…
А как работает применяемый метод containskey? Что под капотом? Прогонялось ли это через stopwatch относительно цикла в цикле? И насколько разница, если она вообще есть?
В хэш-таблицах традиционно обращение к ключу имеет сложность O(1)
А доступ к элементам словаря как я понимаю бесплатный?
Массив кортежей символ - кол-во: (char, int)[] (2 варианта):
s.Select(c => (c, s.Split(c).Length - 1)).Distinct().ToArray();
s.GroupBy(c => c).Select(g => (g.Key, g.Count())).ToArray();
А ещё можно завести массив интов arr на 256 значений. И при чтении строки просто str в одном цикле делать arr[str[i] ]++. Сложность та же О(n), зато быстрее, чем со словарями.
На 65536. Юникодные времена сейчас.
@@QwDragonюникод это не только мелкомягкий ucs-2, но и utf-8, и utf-16 с суррогатными парами, и utf-32, так что 4гб запасай
Интересно, а под капотом там что? То есть проверка, есть ли такой ключ или нет в словаре, это не такой же цикл?
В среднем поиск в хеш-таблице О(1)
Так как под «капотом» там лежит все тот же массив, а ключ это адрес ячейки массива, который прошел через хеш функцию
зависит от реализации "словаря". Обычно там дерево или хэш-таблица. В данном случае конечно же хэш-таблица нужна, но и дерево сойдет. На миллионе дерево лишь в 20 раз проиграет
Ага, и я который только только начал изучать программирование : угу, понял, спасибо ебать
Ну и не получишь ты 180т.р , или на 40т.р. Получай знания, матан тебе в помощь
@@АвамзачемЭто вы вообще о чём говорите ?
Слушай, а ты думаешь под капотом не происходит то же самое? Это не волшебная палочка все таки. Теперь уже внутри словарика при добавлении уже чужому коду надо определять была ли эта буква в словаре или нет.
Нифига у шарпистов задачи 😅
Дело не в языке. Это лишь одна из списка задач на собесах. А не та задача, решив которую тебе дадут оффер). Зачастую на собесе целый ряд задач разного уровня сложности. Данная задача популярная из списка простых.
Зачем создавался массив characters? foreach прекрасно кушает строки. Плюс использование var крайне не рекомендую - читабельность и понятность кода резко снижается. До вывода на экран докапываться не буду, но по факту он очень долгий (лучше использовать StringBuilder).
Да и задача, прошу прощения, для первокурсника. Не представляю кто вообще не способен такую задачу решить. По-моему такая задача бесполезна.
Класс, было интересно 🔥
Можно еще отсортировать строку и если следующий элемент не больше предедущего, добалять его в овтет. Тогда сложностт по времени будет (n*logn) а по памяти O(1)
Какие словари, какие хэши? Сортировка подсчётом.
Или символы какие-то особенные, unicode32?
Такие вещи нужно оговаривать.
если предположить что старший бит не занят, то можно его использовать как признак повторения , а можно просто отсортировать массив и тогда вообще все просто ))
любая сортировка не сработает быстрее чем за линию, а если строка еще будет достаточно большой, то понадобится много памяти, когда для словаря нужна константная память
@@vvalik какая сортировка у тебя память требует?
зачем второй проход? тупо кладёшь предыдущие символы в структуру, если символ уже там. то запоминаешь
А эти скорости типа n^2 или 2n где-то применяются? Стоит их учить?
Это называется Big O нотация. Сильно углубляться в нее может и не стоит просто так, но базовое понимание точно должно быть, чтобы ты мог оценить примерно свой придуманный алгоритм при решении той или иной задачи на работе. Без такого понимания ты можешь выдать решение, оно будет медленным и ты не будешь понимать, что в нем не так и как исправить.
@@lightcode-groupразве n^2 ? Мы же поидеи изменяем на -1 кол-во проверяемых символов, и в конце будет только 2 символа
@@la_maksimвсего переборов будет n(n-1)/2, но для оценки сложности коэффициенты опускаются, получается n^2. Попросту это значит, что если увеличить число входных параметров (длину строки) в n раз, то время работы программы увеличится в n^2 раз
В коммерческом коде в веб разработке это используется только на бекенде, в высоконагруженных сервисах, фронтовичкам, которые инпуты вычисляют это ничего не даст, но если на собесах будет тим лид команды бекенда он скорее всего спросит
Алгоритмическая сложность воего решения О(N*logN) тк обращение к словарю производится за логарифм, лучше было бы создать массив в котором индекс будет равен инжексу буквы, и обращаться к этому за О(1), тогда ты получишь решение за линию и за столько же памяти
Это неправда. Словарь в питоне это хешмапа. А в хешмапа за единичку. В С++ это были бы правдой, там структура map построена на красно-черном дереве, и вставка в неё действительно за logn, но в тех же плюсах есть unordered_map, которая хешмапа, и в которую вставлять за единичку опять же
Короче словарь в видео неправильное слово. Правильное - хешмапа
К чему обращаться? Где ты будеш хранить количество встреч с конкретной буквой? В массиве? Интересно как?
@@АнтонПичушкин-у6р это не правда. Прочитай про устройство хешмапы. Она не работает за единичку
Так что надо пользоваться мапой обычной, а в данной задаче где входные значения сильно ограничены - можно просто создать массив и в нём хранить, что действительно будет работать суммарно за линию
@@ОлегАн-т5жесли строка содержит для примера только латиницу нижнего регистра, то создаёшь массив размера 26, ячейки в котором содержат количество вхождений символа в строку (в коде это выглядит как то так arr[ch-'a']++, где ch - символ строки). Что сложного? И максимум это задача для стажёра.
@@MikhailVinogradov-nk7kd Слышу звон но не знаю где он? Еще раз, мой вопрос адресован комментатору который предлагает создать ОДИН МАССИВ где по номеру индексу будет СОДЕРЖАТЬСЯ буква. Возникает вопрос ЕСЛИ У ТЕБЯ ТОЛЬКО ОДИН МАССИВ где уже СОДЕРЖАТЬСЯ БУКВЫ то где ты будешь хранить количество встреч этой буквы? Что сложного? Читай ВНИМАТЕЛЬНО ТЗ а не умничай.
string = 'подпишись'
symbs = [i for i in string if string.count(i) > 1]
print(set(symbs))
Спасибо за разбор задачи! Можно больше таких видео?😅
Спасибо, все будет!
А ещё в модуле collection есть метод counter, который сразу выводит ключ- символ, значение - количество символов в строке.
Кста можешь помочь в алгоритме, мне надо найти все тоже самое как на видео, но только надо найти одинаковые куски слов а не буквы
Есть же встроенная функция подсчёта повторяющихся символов)
Так и на собесах в первую очередь спрашивают алгоритмическое мышление, а не знание методов🤷🏻♂️
Решить можно одним циклом, если при повторном появлении сразу принтить букву
а если 3 раза будет?
@@n1retна == 2 выводить только
Придется делать find на каждый символ. И тут уже будет зависеть от типа данных, где символы лежат. HashSet будет оптимальным наверное
Что это за сфера и язык?
ну, тут константа, плюс надо смотреть, что важнее память или время, потому что в первом случае её надо меньше
Верно подметил. Сейчас страшно смотреть сколько браузер памяти кушает :D Как по мне на проц пофиг он невероятно мощный, а вот память по прежнему узкое место)
Переводим в массив или объект, используем set, потому что это даст нам только уникальные значения в коллекции, далее выводим те значения, которые убрал сет и получаем коллекцию уникальных значений и какую-то структуру на свой выбор из повторяющихся
через hashmap быстрее будет
Я тоже так делал на курсах. Только у нас не слово было а массив из 25000 ip адресов. 😂
@@alexeikmw задачка фронтовичка помучить, с реальными тасками на бекенде ничего общего не имеет
Можно поподробнее про то, какие значения убрал сет? Никогда не видел интерфейса сета, который сообщает о том, какие именно значения он выкинул.
@@vryaboshapko такого интерфейса, увы, нет, в моем комментарии предполагалось сравнить значения исходного массива с тем что вернул нам сет, обычно этот способ больше подходит для того чтобы убрать дубликаты и нам не важно что именно было удалено, если это критично, то самый лучший вариант использовать объект для подсчета вхождений элемента
Хм, зная что будут оптимизации на распараллеливание или векторизации от языка, тупой алгоритм с не большими доработками сможет быстрея чем O(N)?
В пределе нет, всё равно будет квадратичная сложность
А правильро ли будет пройтись по СТРОКЕ двумя цыклами фор?
Ээ, почему лайк ставится сам по себе😁
Спасибо!)
Можно через каунт и условие мне кажется
Вспомнил видео от Алек Ос «как уместить программу в 8000 бит/байт»
Можно использовать битовые операции.
Какие все тут умные собрались 😂 один я ничего не понял?)
Python погнали
print(*set(filter(lambda x: a.count(x) > 1, a:=input())))
Как вариант)
print(* map(lambda x: x[0], filter(lambda x: x[1] > 1, Counter(input()).most_common())))
@@drm365 Смысл был не в эффективности, а в том, чтобы вместить всё в одну инструкцию. Убрав переносы строк, ты не уменьшишь кол-во инструкций. Сложность O(N^2), да, неэффективно.
Используем Counter из collections на питоне и решаем задачу в одну строку и за 3 секунды))
Ля, на бесплатных курсах задачи сложнее в разы😂
А в Set положить нельзя?)
можно
хитрец какой!
Крутоооо 😮
А зачем дважды проходить массив если мы можем каждое значение записать в массив и проверять каждое следующее существует ли оно в массиве
Проверка на наличие элемента в массиве или листе тоже работает через цикл. Алгоритмическая сложность та же.
Почему просто множеством нельзя было обойтись, зачем тут словарь городить?
Неупорядоченное множество, обычный set в плюсах за логарифм проверяет, с unordered set за О(1)
Делаем масив интов на 255 эллементов и делаем arr[ch[i]]++ для всех символов строки. Это, наверно, самый быстрый способ, у него гарантировано точность O(n), цикл прохода по строке содержит только 1 строку в которой нет ни условного оператора, ни вызова функций с неизвестной собственной сложностью. А использование метода из видоса вполне возможно имеет сложность O(n²).
Генератором посчитать 5 сек, так что не думаю, что тут можно говорить о 180к, ну а если и так, то я, заканчивающий 11 класс, могу прретендовать на должность мидла
а отсортировать и уплотнить нет такой возможности в языке?
Есть, но тогда на собесе могут попросить реализовывать данный функционал вручную. Как правило такие задачи запрещается решать с помощью готовых методов языка.
Сортировка - О(NlogN)
Только вот переход по ключю в словаре не O от единицы
Так можно просто регуляркой почистить строку
Можно, это уже более продвинутое решение.
Сложность по времени больше
180 тысяч чего? И за какой срок?
чел!!! O(N) - ты не получишь! А накладные расходы для поддержки хештаблицы? Те ты считаешь, что запись в хештаблицу моментально пишется?
Говорить, что В РАЗЫ - автор, ты реально теоретик?
Друг, тут речь не идёт о том, что будет по факту исполняться в разы быстрее, а про чисто теоретическое big O. И автор все правильно сказал. Цикл в цикле это действительно сложность O(n²), а цикл с хэштейблом - O(n), что в чистой теории очевидно намного лучше. Хеш таблицы тут как пример и могут быть заменены, а подход действительно алгоритмически более правильный
Формально говоря, Хэш-таблица работает за О(1+а), где а - коэффициент заполнения, но ожидаемое время работы константное, при благоприятном(минимальном) числе коллизий
Пипец дожили, детская задача на 180к 😂
А зачем хэш-таблица, а не просто массив? У нас же не бесконечное количество символов
а если алфавит неизвестен?
@@vvalik значит сначала нужно узнать алфавит, иначе считать алфавит как с бесконечным числом символов, для которого понадобится соответствующая хэш-таблица, и подход к решению задачи будет иным. Мне, конечно же, очень нужна хэш-таблица для алфавита с 1 символом. Точно так же, как она нужна мне и для алфавита с n количеством символов, где можно изначально использовать статическую структуру данных, работающую быстрее. А если бы нужно было слова посчитать - совсем другое дело
Лёгенькая задача, наверное для джунов такие дают
Без проблем, как опытному сразу после решение дополнение (А теперь за О(n) без коллекций) и тут все становиться не совсем так сладко.
test_list = list(set(test_list))
Ты убрал повторения, но не вывел их, аутист
Это YoptaSkript?
Просто перевести в сет мало, так мы получим все уникальные буквы. То есть, и те, что встречаются 5 раз, и те, что только по одному разу.
@@ОлегАн-т5ж xуёпта мудила
Берем жс, берем массив, пихаем в сет, Всё O(1)
Легче в сет добавлять и повторяющие вывести, один цикл
вам только дай памяти отожрать побольше. массив сортируешь и все повторы оказываются рядом, дальше парой переменных смотришь эти повторы
эм регулку, можно использовать нет?
let a = 'подпишись';
for(let el of a) {
let arr = a.match(new RegExp(`${el}`, 'gi'));
if(arr.length >1) {
console.log(el)
}
}
на js вот так выглядит)
Давай больше
прикольно
Решил но наверное не самым выгодным способом по памяти, создал массив длины 27 (колво букв в алфавите) и в а[0] добавлял +1 когда встречал букву a, в а[1] b и по аналогии, потом смотрел где больше 1, и выводил буквы
Это кстати самая простая имплементация хэш таблицы, где хэш функция - номер этой буквы)
Идея хорошая, но надо брать не кол-во букв в алфавите, а кол-во ASCII символов, если кодировка строки в ASCII. Тогда и англ и русский и пробелы и другие символы тоже будут работать. Единственное если кодировка будет 4 байтовая, то такой массив получится в 4 гб и тут придется или хитрить с битами или еще что-то придумывать, в большинстве случаев при такой большой кодировке метод из видео будет эффективнее.
Для больших строк space complexity будет неприемлемый. Есть более продвинутое и быстрое решение
Это шутка какая-то? Эту задачу решит 9классник без всяких квадратичных сложностей...
Вперёд, сложность О(n) без использования коллекций.
@@ОлегАн-т5жну, во-первых, никто не говорил про про неиспользование коллекций. во-вторых, задача действительно максимально простая, так еще и у автора видео не лучший вариант решения.
Это можно просто решить через сет циклом фор и принтовать с join
Фрост лист и всё дела. Сравни массивы получившийся и исходный и все
Ну хз мне на ум сразу же словарик пришел
А распиши этот алгоритм на си😂
Set ? XOR? Не?
Set медленно, XOR определит если было нечетное кол-во повторений. Или ты знаешь как им в принципе повторения спалить?
Как я сюда попал? Видимо, я тут, в комментариях, единственный не программист и ничего не понял
А есть решение на чистом C?
За такие простые задачи 180 платят? Ну и ну... Это обычная джуновская задачка 7-8kyu в code wars
Да, но она предлагалась в качестве одной из задач на собесе. Нужно же понимать, что на собесе дается целый ряд задач разной сложности. Только решив ее оффер не получишь.
Надо бы проверять на реальное быстродействие. Какие там алгоритмы работают при составлении списков, добавлении, чтении... да чёрт его знает. Может быть рельно быстрее работает первый способ.
Если проверять на большом слове из миллиона букв, то гораздо быстрее именно второй способ, какой бы ни была реализация
Это задача, которой бездельники-ютуберы, которым лень сделать что-то полезное, кормят своих подписчиков.
Кстати, прикинь, в первом предложении есть вложенное лексическое условие. Я почти прошёл собес на филолога с зп 180к.
И если тебе важно сохранить порядок символов, хеш таблица не подходит, тк она сортирует по значению хеш функции.
Так иди на cf за нормальными задачами, а не ной в коммах, его решение с хешмапой подходит, т.к. он два прохода делает.
Я ни хрена не понимаю в этих программах! Но скажите где это применяется, что за радость такая подсчитать колличество повторяющихся букв в слове?
Не будет первый вариант правильно работать когда буква больше 2 раз встретится.
Думал за 180 тыщ использт регулярные выражения
Решения бывают разные, но для регулярных выражений обычно есть более сложные задачи. Этой же проверятся умение правильно выбрать структуру данных.
Регулярка это на стажёра и бесплатно.
Чат гпт тебе любую регулярку напишет
Не надо идти к тем, кто на собесе задает такие задачи.Тем более и деньги небольшие.
Надо превратить каждый элемент в ассоциатывный массив. А потом просто его вывести по порядку, вск
всё@@drm365
С развитием ии, это будет вообще не нужно, важнее знание архитектуры и понимание задачи в целом. А код напишет чат бот.
Не досмотрел до конца, я бы создал ассоциативный массив ключ - символ, значение счетчик...
В видео такое решение и предлагалось)
А счетчик зачем? В задаче не нужен подсчет количества.
Пизец, где мои 180к$
Иди на собес, лутай 180к+
@@Wings_Vlog спасибо, сходил, правда 180к+ тенге, но тоже неплохо для стажа в 0 лет
@@Solaris5000 так автор может не про рубли говорил, все по факту😂
Через count решить можно
count курит в стороне
Зачем считать количество.Если буква уже есть то выводим ее и стами значение больще чем 2 чтобы не выводить опять. Один проход
Рискну предположить, что в мапе добавление n элементов за O(n * log n )
Мапа и хэш-таблица различаются. Добавление в хэш-таблицу - константа.
@@brinza888, в хэш-таблицу, ок, но под словарём я понимаю map, а там n log n
@@Neo-fi5zr и словарь и map, это структура данных с одинаковым интерфейсом, поэтому сложно сказать как и что правильнее называть, у всех по-разному.
Но я придерживаюсь того, что словарь основан на хэш-таблице, а map основана на бинарном дереве поиска.
У меня вопрос зачем это нужно
Чтобы выбирать правильную структуру данных. Не делать перебор по массиву, когда можно использовать словарь.