Здравствуйте, vvlad.net, Вы писали:

>>>>> map это O(1), пора бы уже и знать.
V>>>>И эти люди запрещают нам ковыряться в носу.
VN>>>map — aka hashtable — запись и доступ за O(1). ЧЯДНТ?
EP>>В C++ map это не hashtable, там O(ln N).
EP>>hashtable — unordered_map.
VN>А мы говорим о common data structures. там map и hashtable эквивалентны.

Что это? Ты так говоришь, что где-то есть всеобъемлющее определение map.
Судя по названию, там скорей всего не map, а Binary Search Tree.
В Haskell и Python map это вообще std::transform.
Очевидно, что согласия в терминах нет, поэтому я и пояснил.

VN>а сишный map
не сишный, а C++

VN>это либо бинарный поиск, либо дерево (в STL не силен)

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

Здравствуйте, vvlad.net, Вы писали:

VN>Я уже много людей прособеседовал. я всегда жду ответ для most-common case.
Проблема в том, что человек может просто зазубрить most-common case, а под конкретную задачу адаптировать алгоритм не сможет. Хорошо бы это проверить на собеседовании. Например, после того как он приведет решение с использованием map и list, спросить, как решить задачу с дополнительным условием, что алфавит огромен и используется целиком, или запрещено использовать дополнительные буферы.

VN>Тут ведь какая закавыка — я сейчас работаю с поисковым движком, и время ответа должно быть действительно быстрым. а вот память еще есть, потому предпочтение отдается более быстрому алгоритму.
Ты определись, какое решение ты считаешь most-common case и правильным ответом на собеседовании — твой вариант решения с map и list, или ответ ndev с двумя массивами.
Я считаю, что твой вариант в общем случае более предпочтителен, а вариант ndev хорош с оговорками.
Задать интервьюеру вопрос об алфавите. Если ответит, к примеру, что используются только латинские буквы — забить на универсальность и использовать два массива фиксированной длины.
Но это противоречит твоему утверждению, что правильно всегда приводить most-common case.

Здравствуйте, Vzhyk, Вы писали:

V>On 21.02.2013 17:30, Аноним 471 wrote:

>> например есть "vvabbcbcc"
>> Надо получить строку где сохранена "последовательность" — т.е. "vvabbbccc"
>> Есть какой-то быстрый способ?

C#:
string.Join(string.Empty, "vvabbcbcc".GroupBy(ch => ch).Select(g => new string(g.Key, g.Count())))

2 минуты

Здравствуйте, Быдлокодер, Вы писали:

Б>nile, так это вы давали эту задачу?
Нет конечно, я в целом рассуждаю на тему процедуры проведения собеседований.

Здравствуйте, vvlad.net, Вы писали:


VN>Не собираюсь спорить о константах, но два прохода по списку это не O(n^2):

VN>

VN>Если делать чтобы просто работало то можно и 2 цикла прокрутить O(n^2).

Речь конечно шла о 2х вложенных циклах.

Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>Здравствуйте, vvlad.net, Вы писали:

>>>>>> map это O(1), пора бы уже и знать.
V>>>>>И эти люди запрещают нам ковыряться в носу.
VN>>>>map — aka hashtable — запись и доступ за O(1). ЧЯДНТ?
EP>>>В C++ map это не hashtable, там O(ln N).
EP>>>hashtable — unordered_map.
VN>>А мы говорим о common data structures. там map и hashtable эквивалентны.

EP>Что это? Ты так говоришь, что где-то есть всеобъемлющее определение map.
EP>Судя по названию, там скорей всего не map, а Binary Search Tree.
EP>В Haskell и Python map это вообще std::transform.
EP>Очевидно, что согласия в терминах нет, поэтому я и пояснил.

Ну а я понимаю map как hashtable, вот о том и говорю. если дерево — то это tree.

VN>>а сишный map
EP>не сишный, а C++
Какая разница? могу сиплюсплюсный сказать. только это длинно.

VN>>это либо бинарный поиск, либо дерево (в STL не силен)

EP>да, обычно дерево (в стандарте про реализацию ничего не говорится, только сложность на поиск, вставку и т.п.).
Ну о чем и речь — уточнять надо.
Кстати, если вставка и поиск O(log n) — то это не обязательно дерево.

Здравствуйте, vvlad.net, Вы писали:

VN>Тут нужен common case. Для такого случая двойной проход нужен?

Если задача сделать это без использования дополнительной памяти — то самый очевидный вариант, и таки за O(n^2)

Здравствуйте, nile, Вы писали:

N>Здравствуйте, vvlad.net, Вы писали:

VN>>Я уже много людей прособеседовал. я всегда жду ответ для most-common case.
N>Проблема в том, что человек может просто зазубрить most-common case, а под конкретную задачу адаптировать алгоритм не сможет. Хорошо бы это проверить на собеседовании. Например, после того как он приведет решение с использованием map и list, спросить, как решить задачу с дополнительным условием, что алфавит огромен и используется целиком, или запрещено использовать дополнительные буферы.

VN>>Тут ведь какая закавыка — я сейчас работаю с поисковым движком, и время ответа должно быть действительно быстрым. а вот память еще есть, потому предпочтение отдается более быстрому алгоритму.
N>Ты определись, какое решение ты считаешь most-common case и правильным ответом на собеседовании — твой вариант решения с map и list, или ответ ndev с двумя массивами.
N>Я считаю, что твой вариант в общем случае более предпочтителен, а вариант ndev хорош с оговорками.
N>Задать интервьюеру вопрос об алфавите. Если ответит, к примеру, что используются только латинские буквы — забить на универсальность и использовать два массива фиксированной длины.
N>Но это противоречит твоему утверждению, что правильно всегда приводить most-common case.

Я не говорил всегда. я говорил, что достаточно. и это кейс с map+list — работает в большинстве случаев без оговорок. По поводу алфавита — только после решенной первой части, если собеседуемый ее решил быстро и корректно. Кстати, как для меня, если эта задача будет решена на пальцах — мне достаточно (я не жду код за 5 минут).

Здравствуйте, superman, Вы писали:

S>Если задача сделать это без использования дополнительной памяти — то самый очевидный вариант, и таки за O(n^2)

Хотя нет, секундочку. Упустил одну деталь. Если говорить о настоящем алфавите, то там количество букв фиксированно, соответственно фиксированно и количество "вложенных" итераций, тогда таки выходит O(n). Поправте если ошибаюсь

Здравствуйте, minorlogic, Вы писали:

M>Здравствуйте, vvlad.net, Вы писали:


VN>>Не собираюсь спорить о константах, но два прохода по списку это не O(n^2):

VN>>

VN>>Если делать чтобы просто работало то можно и 2 цикла прокрутить O(n^2).

M>Речь конечно шла о 2х вложенных циклах.

Тогда конечно O(n^2). Только я бы такой вариант решения не принял — не показатель опыта, скорее наоборот, отсутствия опыта работы с данными.

Здравствуйте, superman, Вы писали:

S>Здравствуйте, superman, Вы писали:

S>>Если задача сделать это без использования дополнительной памяти — то самый очевидный вариант, и таки за O(n^2)

S>Хотя нет, секундочку. Упустил одну деталь. Если говорить о настоящем алфавите, то там количество букв фиксированно, соответственно фиксированно и количество "вложенных" итераций, тогда таки выходит O(n). Поправте если ошибаюсь

Для "настоящего" алфавита лучше всего использовать решение от ndev — с двумя массивами и одним проходом, O(n).

Здравствуйте, vvlad.net, Вы писали:

VN>>>А мы говорим о common data structures. там map и hashtable эквивалентны.
EP>>Что это? Ты так говоришь, что где-то есть всеобъемлющее определение map.
EP>>Судя по названию, там скорей всего не map, а Binary Search Tree.
EP>>В Haskell и Python map это вообще std::transform.
EP>>Очевидно, что согласия в терминах нет, поэтому я и пояснил.
VN>Ну а я понимаю map как hashtable, вот о том и говорю. если дерево — то это tree.

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

VN>>>а сишный map
EP>>не сишный, а C++
VN>Какая разница? могу сиплюсплюсный сказать. только это длинно.

C — это другой язык В его библиотеке нет встроенного "контейнера" map.

VN>>>это либо бинарный поиск, либо дерево (в STL не силен)
EP>>да, обычно дерево (в стандарте про реализацию ничего не говорится, только сложность на поиск, вставку и т.п.).
VN>Ну о чем и речь — уточнять надо.
VN>Кстати, если вставка и поиск O(log n) — то это не обязательно дерево.

Ну так о том и речь, реализация может быть любой, необязательно BST.
Кстати, я рад что в STL map не назвали Binary Search Tree, а unordered_map не назвали Hash Table — есть чёткое отделение интерфейса от реализации.

Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>Здравствуйте, vvlad.net, Вы писали:

VN>>>>А мы говорим о common data structures. там map и hashtable эквивалентны.
EP>>>Что это? Ты так говоришь, что где-то есть всеобъемлющее определение map.
EP>>>Судя по названию, там скорей всего не map, а Binary Search Tree.
EP>>>В Haskell и Python map это вообще std::transform.
EP>>>Очевидно, что согласия в терминах нет, поэтому я и пояснил.
VN>>Ну а я понимаю map как hashtable, вот о том и говорю. если дерево — то это tree.

EP>Ну так я поэтому и пояснил — видно было, что вы о разных вещах говорите.
Вот и ладно.

VN>>>>а сишный map
EP>>>не сишный, а C++
VN>>Какая разница? могу сиплюсплюсный сказать. только это длинно.

EP>C — это другой язык В его библиотеке нет встроенного "контейнера" map.
Знаю, конечно. Но есть такая фраза С++ это С с классами.
Если чо, я с С начинал, и С++/QT пользовал, а вот STL и Boost не трогал — переметнулся на шарп (еще первой версии, в 2001-ом).

VN>>>>это либо бинарный поиск, либо дерево (в STL не силен)
EP>>>да, обычно дерево (в стандарте про реализацию ничего не говорится, только сложность на поиск, вставку и т.п.).
VN>>Ну о чем и речь — уточнять надо.
VN>>Кстати, если вставка и поиск O(log n) — то это не обязательно дерево.

EP>Ну так о том и речь, реализация может быть любой, необязательно BST.
EP>Кстати, я рад что в STL map не назвали Binary Search Tree, а unordered_map не назвали Hash Table — есть чёткое отделение интерфейса от реализации.
Здесь я четырмя лапами за.

Здравствуйте, vvlad.net, Вы писали:

VN>>>>>а сишный map
EP>>>>не сишный, а C++
VN>>>Какая разница? могу сиплюсплюсный сказать. только это длинно.
EP>>C — это другой язык В его библиотеке нет встроенного "контейнера" map.
VN>Знаю, конечно. Но есть такая фраза С++ это С с классами.

То что называют "С с классами" — относится к диалекту 20-25 летней давности.
(если же формально говорить про язык C with Classes — то он переименовывался в C++ в 1983)

Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>>> while(first!=last)
EP>>> first = partition
EP>>> (
EP>>> first,last,
EP>>> _1 == *first
EP>>> );
EP>>ошибка — должно быть stable_partition

Итак, если брать stable_partition, и рассматривать полностью in-place случай, то общая сложность получается O(N^2*ln(N)).

Теперь сделаем in-place алгоритм с O(N^2).

При использовании stable_partition, не меняется относительный порядок элементов в обоих range'ах. Для нашей же задачи, нам достаточно иметь устойчивость только в хвосте (судя по условию задачи, порядок элементов внутри каждой из результирующих групп — не важен).
Александр Степанов называет такой partition — semi-stable.
Пример реализации semi-stable partition:

template<typename ForwardIterator,typename Predicate>
ForwardIterator semi_stable_partition(ForwardIterator first,ForwardIterator last,Predicate p)
{
   ForwardIterator middle = first;
   while( (first = find_if(first,last,p)) != last )
   {
       using std::swap;
       swap(*first,*middle);
       ++middle;
       ++first;
   }
   return middle;
}

Сложность O(N). Стабильной остаётся первая часть, поэтому воспользуемся reverse_iterator и противоположным предикатом:

template<typename BidirectionalIterator>
void group(BidirectionalIterator first,BidirectionalIterator last)
{
    typedef reverse_iterator<BidirectionalIterator> ReverseIterator;
    while(first!=last)
        first = semi_stable_partition
        (
            ReverseIterator(last), ReverseIterator(first),
            _1 != *first
        ).base();
}

Итог: in-place <b>O(N^2)</b>.

Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>Можно сделать не inplace — average O( N ), что-то типа:

EP>template<typename BidirectionalIterator>

не in-place версия и для ForwardIterator работает

EP>first+=n;

а тут естественно — advance (а в C++11 у fill_n есть return value).
http://ideone.com/zATe8h

template<typename ForwardIterator>
void group(ForwardIterator first,ForwardIterator last)
{
    typedef typename iterator_traits<ForwardIterator>::value_type Value;
    unordered_map<Value,unsigned> hist;
    vector<Value> seq;
    for(auto i=first; i!=last; ++i)
        if( (++hist[*i]) == 1 )
            seq.push_back(*i);
    for(auto &&v : seq)
        first = fill_n(first, hist[v], v);
}

Здравствуйте, vvlad.net, Вы писали:

VN>Тогда конечно O(n^2). Только я бы такой вариант решения не принял — не показатель опыта, скорее наоборот, отсутствия опыта работы с данными.
Что за глупость? Откуда такой вывод ? Попробуйте включать голову

Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>Здравствуйте, vvlad.net, Вы писали:

VN>>>>>>а сишный map
EP>>>>>не сишный, а C++
VN>>>>Какая разница? могу сиплюсплюсный сказать. только это длинно.
EP>>>C — это другой язык В его библиотеке нет встроенного "контейнера" map.
VN>>Знаю, конечно. Но есть такая фраза С++ это С с классами.

EP>То что называют "С с классами" — относится к диалекту 20-25 летней давности.
EP>(если же формально говорить про язык C with Classes — то он переименовывался в C++ в 1983)

Я ЗНАЮ. но для простоты пишу сишный, подразумевая С++ (который с STL). Дальнейший спор считаю бессмысленным.

Здравствуйте, Vzhyk, Вы писали:

>> Есть какой-то быстрый способ? Мне дали 5 минут написать метод

Здесь неподалеку статья была http://www.rsdn.ru/forum/job/5059427

Автор: ResidentR6
Дата: 06.02.13

про извращенную систему. Вот это оно и есть на практике: поставить задачу и кандидата раком в условия цейтнота, заставить его ошибаться, после чего — в зависимости от целей собеседующих — потешить ЧСВ, сбить зарплатные ожидания, показать начальству, что приходят одни дураки, а у нынешняя команда — д'Артаньяны, проверить, является ли кандидат овцой, которая все стерпит и не станет конкурентом хорошим ответственным исполнителем и т. д. и т. п.
Выше по топику кто-то оправдывал собесудующего, мол, показывает умения быстро работать с задачами, а не переписываться месяцами для уточнения требований. Конечно, бывает и такое, но я чаще сталкивался со следующим:

Менеджер(М): Сколько необходимо времени на эту задачу?
Разработчик(Р): Ну, сложно сказать, это зависит от <перечисление незафиксированных требований, перечисление технологий с которыми разработчик еще не работал и т. д.>
М: Сколько?
Р: Надо бы подумать.
М: Сколько ты будешь думать? У меня тут клиент спрашиват, а тебе еще таску критическую на завтра надо закрыть.
Р: От недели, если все будет нормально, до двух месяцев, если что-то вылезет.
М: Ты с дуба упал? Какие два месяца? ОК, давай накинем риски, пусть будет полторы недели.

На самом деле задача займет два месяца, т. к. эстимируя в уме за пять минут разработчик обязательно что-нибудь забудет посчитать, в результате разработчик, в зависимости от темперамента либо пошлет всех и пойдет по собеседованиям или же будет чувствовать вину (точнее его заставят: "ты же сам назвал эстимейт!"), овертаймить и забудет попросить прибавку к зарплате.

Здравствуйте, a_g_99, Вы писали:

__>Здравствуйте, vvlad.net, Вы писали:

VN>>Тогда конечно O(n^2). Только я бы такой вариант решения не принял — не показатель опыта, скорее наоборот, отсутствия опыта работы с данными.
__>Что за глупость? Откуда такой вывод ? Попробуйте включать голову

А то, что если есть решение (подходящее) лучше чем O(n^2), то его и надо давать. Вариант со вложенными циклами — экономен по памяти, его можно давать только тогда, когда алфавит занимает кучу места (больше доступной оперативы, например) при старте приложения, но никак не во время работы, когда важна скорость. При этом если входной массив символов не слишком большой — то только решение за O(n).