Если да, то я не понимаю как быстрее чем за N * log N сделать, не то что за N. Надо ж сортировать так или иначе. Ну можно, наверное, какой-то бакет сорт прикрутить, но мне лень: взял обычный heap. Зато чистенько.

https://leetcode.com/discuss/general-discussion/645121/Sort-Characters-By-Frequency

Если да, то я не понимаю как быстрее чем за N * log N сделать, не то что за N. Надо ж сортировать так или иначе. Ну можно, наверное, какой-то бакет сорт прикрутить, но мне лень: взял обычный heap. Зато чистенько.

Ну одна Мапа считает, другой массив сэтов сортит за O(N)

Если да, то я не понимаю как быстрее чем за N * log N сделать, не то что за N. Надо ж сортировать так или иначе. Ну можно, наверное, какой-то бакет сорт прикрутить, но мне лень: взял обычный heap. Зато чистенько.

Ой, а бакет сорт это как я понял у меня с массивом, да?

https://leetcode.com/discuss/general-discussion/645121/Sort-Characters-By-Frequency

@vitkarpov I requst code review (please😊)

Еще меня раздрожает писать unordered_map и unordered_set… Как будто я пишу что-то типо DEPRICATED_NEVER_USE_set

Когда устроился стажёром в Яндекс

О! Это вы

И место знакомоме, в Я от метро идти)

Ага. В 2014 году, кажется.

Господи, я в офисе Я был уже раз 20

Уже разкрытыми глазами туда хожу, если меня не возьмут стажером, то устроюсь уборщиком и по ночам буду писать код 🤣🤣🤣 (шутка)

Ой, а бакет сорт это как я понял у меня с массивом, да?

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

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

Это мой фетишь 🤣

Уже разкрытыми глазами туда хожу, если меня не возьмут стажером, то устроюсь уборщиком и по ночам буду писать код 🤣🤣🤣 (шутка)

Точняк. За тем самым компом 😆

Все ради O

Ой, а машинка не спроста там стоит

https://youtu.be/2XLZ4Z8LpEE

🤣🤣🤣

https://youtu.be/2XLZ4Z8LpEE

Вы в Я таким не занимались?🤣

Вы в Я таким не занимались?🤣

Не, только на мусорке возле Я

https://youtu.be/2XLZ4Z8LpEE

Пердставьте top написать на этой машинке

Она наверное взорвется

А когда эту задачу выложили?

Давно, судя по номеру. Но условие чуть поправили за последний месяц. Добавили два последних ограничения

@KlenZeleny Как догадался, если не секрет?

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

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

Ну про вложенность понятно, только как такие гениально простые мысли приходят в голову

Прицените если ещё не видели дайджест в большой фанговской группе. Чувак пишет про опыт собеседования в Фейсбуке (на фронтендера, видимо) и у него спросил Roman to Integer, прямо первый вопрос из моего сборника 27 задач в канале 🤣

EЖЕНЕДЕЛЬНЫЙ ДАЙДЖЕСТ №4: https://www.notion.so/Digest-4-7da40db3f1624e52b7b0e06fbb6d94a8 Подборка самого интересного что было в наших чатах за последнюю неделю. Много инфы про то, как подготовиться Frontend Eng интервью, а также фидбек про facebook virtual onsite, amazon online assessment. И главное, как начать проходить моки🤓 (как собеседовать, и почему не надо бояться проходить мок даже с небольшим количеством задачек на литкоде), плюс ресурсы по system design, English, какие вопросы задают на первом интервью Google и др. +Добавили ссылки на прошлые дайжесты 🤓 Спасибо @kgusman @zero_in_zero @reallity_not_found @rosepetal2013 и @sergi_sema за то что сделали нам такую полезную вещь. Ребята, если вы активно читаете дайджест, и у вас есть фидбек - пишите! Мы очень хотим сделать дайджест лучше 🙂

Ну про вложенность понятно, только как такие гениально простые мысли приходят в голову

Не знаю. В школе любил геометрию

Прицените если ещё не видели дайджест в большой фанговской группе. Чувак пишет про опыт собеседования в Фейсбуке (на фронтендера, видимо) и у него спросил Roman to Integer, прямо первый вопрос из моего сборника 27 задач в канале 🤣

Спасибо, почитаем

Не знаю. В школе любил геометрию

Я думаю тут не геометрия, а common sense

Я зациклился на строжение рядов матрицы и все

И не видел такого очевижного решения

Сижу, делаю задачу Top K Frequent Elements. Код написал, выдает ошибку. Уже и так, и этак. Причем пишет, что не может привести IList<int> к int[]. То есть интерфейс к массиву. Причем, ошибку пишет в некоем Driver.cs. Но строка в моём коде подсвечена. Поменял порядок строк, стала подсвечиваться вообще пустая строка. И та же ошибка. Зашёл на сайт в другом браузере. Оказалось, что литкод умудрился изменить тип возвращаемого значения у функции c интерфейса на массив... А у меня интерфейс стоит. То ли это прямо сейчас вечером произошло, после того, как задачу открыл. То ли ранее открывал, и код сохранился в кеше браузера. В общем, поправил возвращаемое значение на массив и решение принято... Мораль: если выдает ошибку, не всегда виноваты вы)

В дайджесте упоминается эта задача как раз. Только для слов

Я зациклился на строжение рядов матрицы и все

А я как раз этого решения не увидел. Каждый по своему думает

Что-то она не понравилась людям

"Во второй за сколько проходов матрица заполнится единицами, если при нахождении единицы соседи тоже становятся единицами". Находили такую на литкоде?

Что-то она не понравилась людям

Наверное крайние случаи не понравились. Или предложенное официальное решение не очень

"Во второй за сколько проходов матрица заполнится единицами, если при нахождении единицы соседи тоже становятся единицами". Находили такую на литкоде?

Эта звучит как будто решается за 1 итерацию и 1 переменной

Comrades, did you get to look at in-place algorithm problems I sent the other day? 😊 If you have any questions feel free to ask (about them or anything else you want).

О, вот и приветствие стереотипное русское 🤣

"Во второй за сколько проходов матрица заполнится единицами, если при нахождении единицы соседи тоже становятся единицами". Находили такую на литкоде?

Это rotten oranges

О, вот и приветствие стереотипное русское 🤣

Надо соответствовать образу русского шпиона 🤣

Эта звучит как будто решается за 1 итерацию и 1 переменной

Это как?

Это rotten oranges

Спасибо! Думал что то похожее не острова

Это как?

Не знаю🤣 Кажется что можно так

Как-то хитро подсчитать 0

Как-то хитро подсчитать 0

Bfs тут подойдёт, думаю

Прицените если ещё не видели дайджест в большой фанговской группе. Чувак пишет про опыт собеседования в Фейсбуке (на фронтендера, видимо) и у него спросил Roman to Integer, прямо первый вопрос из моего сборника 27 задач в канале 🤣

Хороший дайджест, спасибо. Реальный опыт собеседований

Лучше чем O(N) O(N) нет?

за O(n)

https://leetcode.com/problems/sort-characters-by-frequency/discuss/645415/C-O(n)-solution-using-Dictionary

https://leetcode.com/problems/sort-characters-by-frequency/discuss/645415/C-O(n)-solution-using-Dictionary

Это еще хуже

Это O(NlogN) O(N)

Это O(NlogN) O(N)

нет

нет

Я увидел слово sort

Я увидел слово sort

там не по N сортируется

В шарпе оно магическое и сортирует за N?

там не по N сортируется

Ну да, за N logN

в данном случае это не nlogn

а sqrt(n)*log(n) < O(n)

а sqrt(n)*log(n) < O(n)

Это скорость сортировки?

итоговая сложность O(n)

Это скорость сортировки?

да

Ладно, не совсем понял как Array.sort ломает законы математики

Но кажетсч понял, вы поступили умнее

Вы сначала посчитали кол-во элеметнов, а потом уже через bucket отсортировали

итоговая сложность O(n)

Ну да, в итоге сложность такая же, но код по умнее

Даже попробую переделать сейчас

order[occs[ch]]->erase(ch);

а это не даст квадратичную сложность?

Даже попробую переделать сейчас

Попробуй. А я пока пытаюсь понять решение

а это не даст квадратичную сложность?

Кажется нет, это мы чистим сет

order[occs[ch]]->erase(ch);

Это Сэт

Как я понял, или O(N logN) O(1)

Или O(N) O(N)

https://leetcode.com/problems/sort-characters-by-frequency/discuss/645415/C-O(n)-solution-using-Dictionary

class Solution { public: string frequencySort(string s) { string result = ""; priority_queue<pair<int, char>> q; unordered_map<char, int> freq; for (auto ch : s) { freq[ch]++; } for (auto ch : s) { q.push({freq[ch], ch}); } while (!q.empty()) { result += q.top().second; q.pop(); } return result; } };

Я сортирую «хипом» 😄

class Solution { public: string frequencySort(string s) { string result = ""; priority_queue<pair<int, char>> q; unordered_map<char, int> freq; for (auto ch : s) { freq[ch]++; } for (auto ch : s) { q.push({freq[ch], ch}); } while (!q.empty()) { result += q.top().second; q.pop(); } return result; } };

Эй!

Меня опередили