Здравствуйте, Vzhyk, Вы писали:
V>On 22.02.2013 13:23, jazzer wrote:
>> 2 массива размером character set (т.е. 256 для ASCII) — один массив >> счетчиков и один массив для хранения последовательности. O(n). V>Затем тебе 256, если алфавит английского около 30?
а заглавные буквы? а знаки препинания? В общем, нужно знать character set.
Здравствуйте, kaa.python, Вы писали:
KP>Все передельно просто и понятно. Решается за O(n) по времени и O(2*размер_словаря) по памяти. Решение: 2 массива размера словаря, один для подсчета элементов, второй для запоминания последовательности появления элементов. Идем по исходному массиву и делаем для каждого из элементов, если в массиве для подсчета занчение не нулевое, то увеличиваем его на 1; если нулевое — увеличиваем на 1 и добавляем элемент в массив восстановления последовательности. Восстанавливаем массив.
Здравствуйте, kaa.python, Вы писали:
KP>Здравствуйте, PZI, Вы писали:
PZI>>Размер словаря какой?
KP>Не знаю, спросил бы у интервьювера. Собеседование — это диалог, вобщем-то.
Ну собственно речь как раз об этом. Люди сами придумывают какой-то словарь, о котором в задаче речи не шло, и строят свой алгоритм на собственных допущениях.
Кстате, очень интересно посчитать эффективность вашего алгоритма по памяти при полном наборе UTF-16, особенно если строка состоит из 1000 раз повторяющейся буквы.
Здравствуйте, PZI, Вы писали:
PZI>Ну собственно речь как раз об этом. Люди сами придумывают какой-то словарь, о котором в задаче речи не шло, и строят свой алгоритм на собственных допущениях.
А ничего что ты тоже предложил решение исходя из собственных допущений? Вообще, задачи на алгоритмы это скорее на подумать, предложить оригинальное решение, узнать граничные условия и т.д., так что именно для данного класса задачь словарь выглядит более подходящим нежели дерево, хотя вариант с деревом тоже удачен, но тут возникнет вопрос с учетом порядка добавления элементов и его стоимости.
PZI>Кстате, очень интересно посчитать эффективность вашего алгоритма по памяти при полном наборе UTF-16, особенно если строка состоит из 1000 раз повторяющейся буквы.
Давай посчитаем. O(n) по скорости против (даже и не знаю, что там внутри мапы? красно-черное дерево? O(n log n) в твоем случае и O(k) = 2*2^16 по памяти против O(k) = сколько_там_займет_мапа_с_одним_элементом. Как-то так
Здравствуйте, kaa.python, Вы писали:
KP>Здравствуйте, PZI, Вы писали:
PZI>>Ну собственно речь как раз об этом. Люди сами придумывают какой-то словарь, о котором в задаче речи не шло, и строят свой алгоритм на собственных допущениях.
KP>А ничего что ты тоже предложил решение исходя из собственных допущений?
Да ну, а мне показалось, что я ничего не придумывал. Не написано, значит этого, т.е. ограничений, нет. Более того, с мапкой, не зависимо от того есть ограничения или нет будет работать.
KP>Вообще, задачи на алгоритмы это скорее на подумать, предложить оригинальное решение, узнать граничные условия и т.д., так что именно для данного класса задачь словарь выглядит более подходящим нежели дерево, хотя вариант с деревом тоже удачен, но тут возникнет вопрос с учетом порядка добавления элементов и его стоимости.
Дерево... а кто говорил про дерево?
PZI>>Кстате, очень интересно посчитать эффективность вашего алгоритма по памяти при полном наборе UTF-16, особенно если строка состоит из 1000 раз повторяющейся буквы.
KP>Давай посчитаем. O(n) по скорости против (даже и не знаю, что там внутри мапы? красно-черное дерево? O(n log n) в твоем случае и O(k) = 2*2^16 по памяти против O(k) = сколько_там_займет_мапа_с_одним_элементом. Как-то так
"и эти люди мне запрещают ковыряться в носу?" (с) по скорости плохо посчитали, да и по памяти чет не видно ренджа утф16
Здравствуйте, PZI, Вы писали:
PZI>"и эти люди мне запрещают ковыряться в носу?" (с) по скорости плохо посчитали, да и по памяти чет не видно ренджа утф16
Здравствуйте, kaa.python, Вы писали:
KP>Здравствуйте, PZI, Вы писали:
PZI>>"и эти люди мне запрещают ковыряться в носу?" (с) по скорости плохо посчитали, да и по памяти чет не видно ренджа утф16
KP>Ну так дай правильный ответ, не стесняся
Сложность поиска/вставки по/в хешмапу(причем тут дерево?) в основном О(1). С помощью утф16 можно закодировать 1112064 символов. Дальше считайте сами.
On 22.02.2013 14:27, jazzer wrote:
> а заглавные буквы? а знаки препинания? В общем, нужно знать character set.
Во-во. В задаче-то было всего 3 или 4 символа. А может это они так
цепочки ДНК обозначают, чтобы никто не догадался.
Здравствуйте, Vzhyk, Вы писали:
V>On 22.02.2013 14:27, jazzer wrote:
>> а заглавные буквы? а знаки препинания? В общем, нужно знать character set. V>Во-во. В задаче-то было всего 3 или 4 символа. А может это они так V>цепочки ДНК обозначают, чтобы никто не догадался.
Может. Поэтому я и сказал про character set.
Здравствуйте, Аноним, Вы писали:
А>например есть "vvabbcbcc" А>Надо получить строку где сохранена "последовательность" — т.е. "vvabbbccc" А>Есть какой-то быстрый способ? Мне дали 5 минут написать метод
Ну если так и было сказано:"за 5 минут" то это прикол работодателя. Тут тогда PZI правильное решение привел. Я читал про это в какой-то книге по TDD.
Вообще, задачи на алгоритмы это скорее на подумать, предложить оригинальное решение, узнать граничные условия и т.д., так что именно для данного класса задачь словарь выглядит более подходящим нежели дерево, хотя вариант с деревом тоже удачен, но тут возникнет вопрос с учетом порядка добавления элементов и его стоимости.
Тут тогда PZI правильное решение привел. Я читал про это в какой-то книге по TDD. 