Re[3]: сгруппировать символы в строке - собеседование - О работе

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

V>Я тоже нет. Ну не умею я не задумываясь решать задачи. Мне надо сесть ,
V>подумать, посмотреть, что за входные данные у нас, какие требования не
V>функциональные есть и ...

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

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

V>За такую постановку задачи только в морду плюнуть. Или она на
V>собеседовании была не так поставлена?
При отсутсвии головного мозга можно и в морду плевать. А задача для собеседования прекрасная (забудем про требование написать код за 5 минут — сдается мне кто-то перенервничал, а на то, чтобы придумать алгоритм достаточно. Хотя лично я начал бы задавать вопросы что получается где-то через полчаса).
1. постановка задачи вполне понятная, а если нет, то всегда можно спросить — мы же не письменном экзамене (если соискатель не в состоянии задать вопрос о решаемой задаче, как он работать-то будет?). Факт задания или не задания вопроса об ограничениях тоже показателен.
2. решений море в зависимости от ограничений на алфавит, размер входной строки и доступной памяти, и в каждом есть о чем разговаривать.

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

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

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

Задача элементарная, но 5 минут маловато. Сгенерировать идею за 5 минут можно, но написать код — за пять минут только непродуманный быдлокод получится — нафига такой скилл? Они там что, скоростным программированием занимаются?
Да и 5 минут на генерацию идеи тоже сомнительным требованием выглядит — люди разные все, стиль мышления разный, соответственно разное время надо.
Разве что стрессоустойчивость кандидата потестить.

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, Vzhyk, Вы писали:
А>Именно ТАК был поставлен вопрос! Сгруппировать и что б первая группа была "vv" потом "a" потом "bbb" и "ccc" и т.д.
А>Дал 5 !!! минут ! Компашка "fixmo.com". Ходил просто "размяться" вобщем-то.
А>В нашем "канадастане" таких "mehirov" тучи. И ладно бы я был туп — дал 5!!! минут!!!
А>Я ведь переспросил "схематично набросать или прямо метод?" — ответил "метод" !
А>А потом рекрутер прислал ехидно — "не справился с тестом"
V>>On 21.02.2013 17:30, Аноним 471 wrote:

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

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

On 22.02.2013 13:33, jazzer wrote:

> Задача элементарная, но 5 минут маловато.
Задача не корректная.
Нельзя понять, что они имели в виду:
1. только из этой последовательности получить итоговую строку.
2. только в английском алфавите.
3. в алфавите размером M.
4. нужно ли сохранять последовательность всречаемости символов.
5. может их интересовала только частотность и все мудотня с сохранением
последовательности нафиг не нужна.
6. не говорю уже про нефункциональные, ограничение памяти,
быстродействие и т.д. В обсуждении уже говорилось о решении О(n^2), если
эта задача выполняется единожды при страте программы раз в несколько
лет, то хоть O(n^3) годится.

Это я так за 5 мин вариантов понимания задачи напсал, а за 30 мин...

Кстати, я постановку задачи понял благодаря местным телепатам и не
уверен, что оттелепатили они верно.

> Разве что стрессоустойчивость кандидата потестить.
Отсеять.

Posted via RSDN NNTP Server 2.1 beta

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

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

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

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

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

Так что не ведитесь на провокации молодых программистов, ну или кто там они, всегда были и есть люди которые чего — то не понимали и списывали это на мистику

, и это нормально !

Будьте Здоровы!

#include <stdio.h>
#include <assert.h>

char *group(char *S) {
    int i;
    char *p = S+1;
    for (; *p; ++p ) {
        char *pp = p-1;
        for (; pp >= S; --pp) {
            if ( *pp == *p ) // is not first
                memmove(pp+1,pp,p-pp);
        }
    }    
    return S;
}

int main() {
    int i;
    char test[5][30] = {
      "vvabbcbcc",
      "asdfrrafdsr",
      "abcdefgijkl",
      "010101010101",
      "totobobolol"
    };
    for ( i = 0; i < 5; ++i ) { 
      printf("%s\n",group(test[i]));
    }
}

Однако, можно и линейно

#include <stdio.h>
#include <assert.h>

char *group(char *S) {
    int i;
    char *p = S;
    char syms[256] = {0,};
    unsigned char count[256] = {0,};

    char *o = syms;
    *o = *p;

    while ( *p ) {
        if ( !count[*p] ) *o++ = *p;
        ++count[*p++];
    }

    p = S;
    o = syms;
    while ( *o ) {
       while ( count[*o]-- ) *p++ = *o;
       ++o;
    }

    return S;
}

int main() {
    int i;
    char test[5][30] = {
      "vvabbcbcc",
      "asdfrrafdsr",
      "abcdefgijkl",
      "010101010101",
      "totobobolol"
    };
    for ( i = 0; i < 5; ++i ) { 
      printf("%s\n",group(test[i]));
    }
}

За отсутствие багов не ручаюсь, но это именно решение за пять минут.

Dictionary? Map? Сборки строки заново?

Джентльмены, ну это просто неспортивно

. Что за детский сад?

On 22.02.2013 13:43, vvlad.net wrote:

> Это кстати не O(n^2) а O(2n)
Оооооо, можно сразу просить название конторы, куда идти не следует, если
там такие спецуги работают.

Posted via RSDN NNTP Server 2.1 beta

On 22.02.2013 14:15, ndev wrote:

> это называется до.ся до решения Как видите в задаче не указан словарь,
> значит предполагаем.
Тогда решение:
return "vvabbbccc"

Posted via RSDN NNTP Server 2.1 beta

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

V>И нормальных собеседовании сильно меньше, чем не нормальных.

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

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

>> ЧТо тут сложного то? За что в морду плевать-то?
V>Забыли упомянуть про алфавит размера N (например, 2^32) для начала.

Слабенькое начало. Для символов произвольной(неизвестной) длинны даных замукнутым списком...

Объяснять, почему ты не ну никак, ни за что не будешь это делать — ценный скил, но, видимо, искали других людей.

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

V>Учитывая, что ты проигнорил второй абзац, я могу сделать вывод
Ты делаешь слишком много выводов о людях по их репликам на форуме и даже по тому, что они не ответили на какую-то из твоих реплик.
Переход на личности тут ни к чему, продолжать не буду.

P.S. Если тебя что-то не устраивает в постановке задачи, ты всегда можешь высказать свою точку зрения, задать уточняющие вопросы. Плевать в лицо и называть людей дебилами тут необязательно. Это скорее говорит о твоей собственной агрессивности и неадекватности.

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

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

S>6 минут с момента открытия студии.
S>Писал первое, что приходит в голову, так как времени на подумать нет.

S>

S>        static void Main(string[] args)
S>        {
S>            string s1 = "vvabbcbcc";
S>            string s2 = Solve(s1);
S>        }

S>        static string Solve(string s)
S>        {
S>            Dictionary<char, int> w = new Dictionary<char, int>();
S>            int i = 0;
S>            foreach (char c in s)
S>            {
S>                if (!w.ContainsKey(c))
S>                {
S>                    w[c] = i;
S>                    i++;
S>                }
S>            }
S>            return string.Join("", s.OrderBy(c => w[c]));
S>        }

S>

S>Интересно посмотреть ожидаемое решение. ИМХО, требование уложиться во время — бред.
Сортировка работает за O(n*logn), можно за O(n) без сортировки, но тоже используя Dictionary<char, int>. Только писать туда не индекс, а частоту встречаемости символа.
Далее для генерации строки бежим по исходной строке и каждый раз когда встречаем новый символ, добавляем его в новую строку то количество раз, которое записано в Dictionary по этому ключу.

Здравствуйте, Аноним931, Вы писали:

А>Если реальной вакансии нет, то кто платит рекрутеру за пропускание через себя людей?
А>Т. е. откуда "физически" берутся эти деньги?

В аутсорсе необходимо иметь пул прособеседованных людей, которым в случае старта проекта, сразу можно будет делать оффер
Часто на собеседовании об этом прямо говорят, что мол сейчас открытой вакансии нет, но вот-вот откроется, "инфа 100%"

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

6 минут с момента открытия студии.
Писал первое, что приходит в голову, так как времени на подумать нет.

        static void Main(string[] args)
        {
            string s1 = "vvabbcbcc";
            string s2 = Solve(s1);
        }

        static string Solve(string s)
        {
            Dictionary<char, int> w = new Dictionary<char, int>();
            int i = 0;
            foreach (char c in s)
            {
                if (!w.ContainsKey(c))
                {
                    w[c] = i;
                    i++;
                }
            }
            return string.Join("", s.OrderBy(c => w[c]));
        }

Интересно посмотреть ожидаемое решение. ИМХО, требование уложиться во время — бред.

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

VN>За два прохода. тут есть решения за O(n) — один проход.
Два прохода это тоже O(n), если что. Константа отбрасывается.

On 21.02.2013 23:44, Аноним 471 wrote:

> Компашка "fixmo.com".
Этих сейчас вообще, имхо, имеет смысл обходить стороной. Сейчас растет
пузырь в секурити и очень быстро. По всем СМИ реклама: "вас пожирают
хомячки", тьфу вирусы и хакеры. В США начинают очередной большой попил в
этой области (выступления Обамы и др. важных их лиц). Для бизнеса грешно
от этого пирога не откусить, понятно, что при попиле ничего делать по
сути не надо, но нужна ИБД.

Posted via RSDN NNTP Server 2.1 beta

Hi,

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

V>За такую постановку задачи только в морду плюнуть. Или она на
V>собеседовании была не так поставлена?

Постановка (если решать на C) плоха только тем, что не указано какие возможны буквы. Если буквы только английские, то делаем структурку

typedef struct tag_entry {
  int nletters;
  int next;
} entry_t, *entry_p;

и массив из 128 (с запасом на всю ASCII) таких структур

entry_p entries[128];

Мемсеттим его нулями. Делаем также переменную для хранения первой и последней буквы

int firstentry = -1, lastentry = -1;

Далее идём по строке. Когда встретили букву с проверяем запись entries[c]. Если там ноль, создаём там entry_t с nletters = 1, пишем если lastentry не -1 в entries[lastentry]->next её адрес, иначе апдейтим firstentry. В противном случае апдейтим lastentry. Если же там вдруг не ноль, просто увеличиваем nletters. Строчка закончилась -- собираем новую строчку через последовательность strdup + strcpy из всех entryes, начиная с firstentry.

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

Нормальный вопрос, я бы тоже такой мог задать.

---
With best regards, Konstantin

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

Б>Я понял как — сгруппировать символы и вывести эти группы. С примером сходится.
Сохраняя порядок появления символов. У тебя порядок не гарантируется.

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

VN>5 min на такую задачу — вечность.

VN>map + list (для сохранения порядка) — все.

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

... << RSDN@Home 1.2.0 alpha 5 rev. 1539>>

On 22.02.2013 13:21, Быдлокодер wrote:

> Получилось 4-ре минуты.
>
> char[] array ="vvabbcbcc".AsEnumerable()
> .GroupBy(c => c)
> .SelectMany(g => g)
> .ToArray();
> string result =new string(array);
> Console.WriteLine(result);

Я в жабе не смыслю, но если на вход подать псевлдотекст из алфавита
размером 2^32?

Posted via RSDN NNTP Server 2.1 beta

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

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

Зачем? Все передельно просто и понятно. Решается за O(n) по времени и O(2*размер_словаря) по памяти. Решение: 2 массива размера словаря, один для подсчета элементов, второй для запоминания последовательности появления элементов. Идем по исходному массиву и делаем для каждого из элементов, если в массиве для подсчета занчение не нулевое, то увеличиваем его на 1; если нулевое — увеличиваем на 1 и добавляем элемент в массив восстановления последовательности. Восстанавливаем массив.
ЧТо тут сложного то? За что в морду плевать-то?

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

V>Вообще-то выделяешь два массива где-то по 40 (или сколько там символов в
V>алфавите).
V>Один держит индексы, второй для гистограммы (счетчиков).
V>Проходишь одним циклом. Все.

Можно подробней? Ну вот есть у вас счётчики. Как потом восстанавливать порядок будете?

У меня если что тоже один цикл.

V>Но, это при корректной постановке задаче, в не при типичном бреде "сходи
V>туда не знаю куда".

Ещё раз -- мне кажется задача поставлена вполне нормально даже в сумбурном изложении топикстартера.

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

V>Но вот тебе еще решение для некоего частного случая: return "vvabbbccc".

Hint: собеседование — это диалог, а не монолог.

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

V>Причем собеседователь, если хочет выяснить этот момент "как кандидат
V>уточняет задачу" должен намекнуть про этот момент, а не сидеть с
V>каменным лицом и ждать некоего решения в коде и сразу.
На любом собеседовании предполагается, что можно задавать вопросы.
А если это тестовое задание, то в идеале рассматривать различные варианты, или хотя бы указывать на свои предположения.

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

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

? Попробуйте включать голову

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

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

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

M>В голову ничего не приходит для общего случая. Для небольшого алфавита , сортировка подсчетом и затем второй проход , генерируем строку.

О! я подумал абсолютно также. Другое дело, что на бумажке за 5 мин не написал бы.

M>Если надо сделать in place , тоже не могу быстрого решения придумать.

Хе, а я как .Net-чик не только не вижу решения in place, а знаю о невозможности его сделать в рамках управляемого кода )

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

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

Posted via RSDN NNTP Server 2.1 beta

22.02.13 12:54: Ветка выделена из темы сгруппировать символы в строке — Blazkowicz

22.02.13 12:54: Перенесено модератором из 'Java' — Blazkowicz

Здравствуйте, Vzhyk, Вы писали:
Именно ТАК был поставлен вопрос! Сгруппировать и что б первая группа была "vv" потом "a" потом "bbb" и "ccc" и т.д.
Дал 5 !!! минут ! Компашка "fixmo.com". Ходил просто "размяться" вобщем-то.
В нашем "канадастане" таких "mehirov" тучи. И ладно бы я был туп — дал 5!!! минут!!!
Я ведь переспросил "схематично набросать или прямо метод?" — ответил "метод" !
А потом рекрутер прислал ехидно — "не справился с тестом"
V>On 21.02.2013 17:30, Аноним 471 wrote:

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

On 22.02.2013 8:49, Аноним 411 wrote:

> Вы слишком бурно реагируете. Очевидно, задача — простейшая. И много
> народу с ней справились бы за отведенное время.
Я тоже нет. Ну не умею я не задумываясь решать задачи. Мне надо сесть ,
подумать, посмотреть, что за входные данные у нас, какие требования не
функциональные есть и только после этого могу что-то написать. А сходу
— нуль выхода.

Posted via RSDN NNTP Server 2.1 beta

On 21.02.2013 23:44, Аноним 471 wrote:

> А потом рекрутер прислал ехидно — "не справился с тестом"
Ну, так они никого не набирают, рекрутер делает свою работу, пропускает
через себя максимльно возможное количество народа, чтобы начальство им
довольно было. А реальной вакансии нет.
Неужели ты первый раз с таким сталкиваешься?
Недавно вон даже вакансия у яндекса подобная висела (да еще и от 150000
зазывали), о том, что она фейковая есть инсайдерская инфа.

Posted via RSDN NNTP Server 2.1 beta

On 21.02.2013 23:44, Аноним 471 wrote:

> А потом рекрутер прислал ехидно — "не справился с тестом"
Ну и сама задачка бессмысленная, посему сразу и не вьезжаешь, чего
хотят. По сути им нужно было посчитать часточность символов в некотором
входном потоке, но в такой постановке эту задачу решат большинство, а от
них нужно избавиться всеми силами. Для тех, кто эту задачку им решит,
они добавят еще несколько, чтобы отсеивать всех.

Posted via RSDN NNTP Server 2.1 beta

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

V>За такую постановку задачи только в морду плюнуть. Или она на
V>собеседовании была не так поставлена?

Решил за 14 мин в студии, но с complexity O(N^2). no hire

. возможно в псевдокоде заняло бы меньше времени

On 22.02.2013 12:25, a_g_99 wrote:

> Решил за 14 мин в студии, но с complexity O(N^2). no hire . возможно в
> псевдокоде заняло бы меньше времени
Вот видишь, причем не на собеседовании, где так или иначе стресс.
Как ты O(N^2) получил? Строишь гистограмму — один проход O(n). Но ничего
не известно про входные данные, поэтому про остальное ничего сказать
толком нельзя.

Posted via RSDN NNTP Server 2.1 beta

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

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

В голову ничего не приходит для общего случая. Для небольшого алфавита , сортировка подсчетом и затем второй проход , генерируем строку.

Если надо сделать in place , тоже не могу быстрого решения придумать.

... << RSDN@Home 1.2.0 alpha 5 rev. 1539>>

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

V>Как ты O(N^2) получил? Строишь гистограмму — один проход O(n). Но ничего
V>не известно про входные данные, поэтому про остальное ничего сказать
V>толком нельзя.
Если завязываться на готовую структуру, Map не гарантирует порядок ключей, не выполнится требование сохранения порядка первого появления символа в строке.
Но это легко решается вторым проходом по исходной строке при генерации новой.

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

M>Если надо сделать in place , тоже не могу быстрого решения придумать.
Так вроде не сказано, что in place

char[] array = "vvabbcbcc".AsEnumerable()
                                      .GroupBy(c => c)
                                      .SelectMany(g => g)
                                      .ToArray();
            string result = new string(array);
            Console.WriteLine(result);

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

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

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

M>В голову ничего не приходит для общего случая. Для небольшого алфавита , сортировка подсчетом и затем второй проход , генерируем строку.

M>Если надо сделать in place , тоже не могу быстрого решения придумать.

5 min на такую задачу — вечность.

map + list (для сохранения порядка) — все.

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

Твое решение не гарантирует порядок, что требуется по условию.

5 мин — постановка собеседуемого в рамки стресса — интересно, какое решение он выдаст в этом случае.

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

Вы полностью оправдали свой ник — условие тоже невнимательно прочитали.

По честному вот так:
5 минут.

var map = new Dictionary<Char, List<Char>>();
            foreach (var c in "vvabbcbcc")
            {
                if (!map.ContainsKey(c))
                    map.Add(c, new List<char> {c});
                else
                    map[c].Add(c);
            }
            var builder = new StringBuilder();
            foreach (KeyValuePair<char, List<char>> pair in map)
                builder.Append(pair.Value.ToArray());
            Console.WriteLine(builder.ToString());

Лучше по ключу не хранить массив, а кол-во повторений ключа. Но это пришло на 4-ой минуте, так что в 5 мин. тогда бы мог не уложиться.
Не понятно, что они хотели проверить? Скоростное кодирование?

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

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

VN>Вы полностью оправдали свой ник — условие тоже невнимательно прочитали.

Я понял как — сгруппировать символы и вывести эти группы. С примером сходится.

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

VN>Твое решение не гарантирует порядок, что требуется по условию.
Гарантирует. Там же в конце сортировка по индексу первого появления символа в исходной строке.

Порядок формирования объектов IGrouping<TKey, TElement> зависит от порядка элементов последовательности source, определяющей первый ключ каждого объекта IGrouping<TKey, TElement>.Элементы внутри группы располагаются в том же порядке, что и в последовательности source.

http://msdn.microsoft.com/ru-ru/library/bb534501.aspx

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

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

VN>>Твое решение не гарантирует порядок, что требуется по условию.
N>Гарантирует. Там же в конце сортировка по индексу первого появления символа в исходной строке.

Точно, и решение хорошее

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

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

M>>Если надо сделать in place , тоже не могу быстрого решения придумать.
J>Так вроде не сказано, что in place

Без ограничений смысл такой задачи теряется. Если не дай бог, задача накидать решение за 5 мин, то я бы бежал от такой работы как ошпаренный

... << RSDN@Home 1.2.0 alpha 5 rev. 1539>>

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

__>Dictionary? Map? Сборки строки заново?

__>Джентльмены, ну это просто неспортивно

. Что за детский сад?

Это и есть спортивно. А на работе надо РАБОТАТЬ, а не спортом заниматься.

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

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

VN>>5 min на такую задачу — вечность.

VN>>map + list (для сохранения порядка) — все.

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

Априори, такое не принимается (я бы не принял) — слишком тупое и очевидное решение.

Это кстати не O(n^2) а O(2n)

On 22.02.2013 13:10, nile wrote:

> Но это легко решается вторым проходом по исходной строке при генерации
> новой.
Так как O(n^2) получить?

Posted via RSDN NNTP Server 2.1 beta

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

VN>Априори, такое не принимается (я бы не принял) — слишком тупое и очевидное решение.
А с мапкой типа легкое ?

VN>Это кстати не O(n^2) а O(2n)

Покажите как за O(2n)

... << RSDN@Home 1.2.0 alpha 5 rev. 1539>>

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

VN>Это и есть спортивно. А на работе надо РАБОТАТЬ, а не спортом заниматься.

Это знаете ли попахивает дебилизмом. Я думаю подразумевалось что задача должна быть решена с помощью мозгов, а не map и list. Давайте-ка заново — представим что у вас symbol array и нужно решить задачу with O(1) by memory.

On 22.02.2013 13:02, minorlogic wrote:

> В голову ничего не приходит для общего случая. Для небольшого алфавита ,
> сортировка подсчетом и затем второй проход , генерируем строку.
Второй не нужен, если взять еще один массив на размер алфавита.

> Если надо сделать in place , тоже не могу быстрого решения придумать.
Но зачем?

То бишь все уперлось в некорректную постановку задачи.

Posted via RSDN NNTP Server 2.1 beta

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

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

Б>>Я понял как — сгруппировать символы и вывести эти группы. С примером сходится.
N>Сохраняя порядок появления символов. У тебя порядок не гарантируется.

Так почему вы считаете, что не гарантируется?
В SQL бы да — не гарантировался, т.к. возвращается множество, а множество штука без порядка. Там нужен OrderBy.

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

Б>

Б>Порядок формирования объектов IGrouping<TKey, TElement> зависит от порядка элементов последовательности source, определяющей первый ключ каждого объекта IGrouping<TKey, TElement>.Элементы внутри группы располагаются в том же порядке, что и в последовательности source.

Б>http://msdn.microsoft.com/ru-ru/library/bb534501.aspx

Точно, забыл, GroupBy() дает O(log n)

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

V>Так как O(n^2) получить?
Легко) Например, запустить вложенный цикл, который будет бежать по исходной строке и искать встречаемость для каждого символа отдельно.

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

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

VN>>Априори, такое не принимается (я бы не принял) — слишком тупое и очевидное решение.
M>А с мапкой типа легкое ?

VN>>Это кстати не O(n^2) а O(2n)

M>Покажите как за O(2n)

За два прохода. тут есть решения за O(n) — один проход.

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

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

VN>>Это и есть спортивно. А на работе надо РАБОТАТЬ, а не спортом заниматься.

__>Это знаете ли попахивает дебилизмом. Я думаю подразумевалось что задача должна быть решена с помощью мозгов, а не map и list. Давайте-ка заново — представим что у вас symbol array и нужно решить задачу with O(1) by memory.

Тогда с O(log n) by time?

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

__>Это знаете ли попахивает дебилизмом. Я думаю подразумевалось что задача должна быть решена с помощью мозгов, а не map и list. Давайте-ка заново — представим что у вас symbol array и нужно решить задачу with O(1) by memory.
То есть представить себе, что структуры данных еще не придуманы, и изобрести их заново?

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

V>On 22.02.2013 13:43, vvlad.net wrote:

>> Это кстати не O(n^2) а O(2n)
V>Оооооо, можно сразу просить название конторы, куда идти не следует, если
V>там такие спецуги работают.

Что такое O(n), O(2n), O(n^2)
в студию.
Особенно интересует разница между линейной сложностью и квадратичной.

On 22.02.2013 13:17, Tilir wrote:

> Постановка (если решать на C) плоха только тем, что не указано какие
> возможны буквы. Если буквы только английские, то делаем структурку
Вообще-то выделяешь два массива где-то по 40 (или сколько там символов в
алфавите).
Один держит индексы, второй для гистограммы (счетчиков).
Проходишь одним циклом. Все.
Но, это при корректной постановке задаче, в не при типичном бреде "сходи
туда не знаю куда".

Posted via RSDN NNTP Server 2.1 beta

On 22.02.2013 13:39, vvlad.net wrote:

> Точно, и решение хорошее
Учитывая отсутсвие корректной постановки задачи, а теперь пусть размер
алфавита 2^32.

Posted via RSDN NNTP Server 2.1 beta

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

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

VN>>За два прохода. тут есть решения за O(n) — один проход.
N>Два прохода это тоже O(n), если что. Константа отбрасывается.

Ага — сложность то осталась линейной.

On 22.02.2013 13:28, Быдлокодер wrote:

> Не понятно, что они хотели проверить? Скоростное кодирование?
Отсеять.

Posted via RSDN NNTP Server 2.1 beta

void StringSorterByFirstEntry(const string& sInput)
{
    int nCharCount[256] = {0};
    bool nCharFound[256] = {false};
    string sOrder;
    for (size_t nId = 0; nId < sInput.size(); ++nId)
    {
        char cChar = sInput[nId];
        nCharCount[cChar]++;
        if (nCharFound[cChar] == false)
        {
            nCharFound[cChar] = true;
            sOrder.append(1, cChar);
        }
    }
    string sRes;
    for (size_t nId = 0; nId < sOrder.size(); ++nId)
    {
        char cChar = sOrder[nId];
        sRes.append(nCharCount[cChar], cChar);
    }
    printf("%s", sRes.c_str());
}

Сложность O(N)

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

N> int nCharCount[256] = {0};
N> bool nCharFound[256] = {false};

N>Сложность O(N)
Для ASCII пойдет, для Unicode не вариант, придется использовать Map или сортировку.

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

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

N>> int nCharCount[256] = {0};
N>> bool nCharFound[256] = {false};

N>>Сложность O(N)
N>Для ASCII пойдет, для Unicode не вариант, придется использовать Map или сортировку.

Давайте не влезать в дебри .... да и заделать под юникод\аскі 5 секунд, меняем 256 на 65536 и все работает.

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

N> bool nCharFound[256] = {false};
И да, зачем лишний буфер флагов boolean, если достаточно проверить nCharCount на 0?

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

VN>Твое решение не гарантирует порядок, что требуется по условию.

Вообще-то гарантирует.

VN>5 мин — постановка собеседуемого в рамки стресса — интересно, какое решение он выдаст в этом случае.

Собеседование само по себе некоторый стресс.

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

N>Давайте не влезать в дебри .... да и заделать под юникод\аскі 5 секунд, меняем 256 на 65536 и все работает.
UTF-32 тоже работает?
Это не дебри, это ограничения. Размер алфавита, размер строки.

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

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

N>> bool nCharFound[256] = {false};
N>И да, зачем лишний буфер флагов boolean, если достаточно проверить nCharCount на 0?
Забыл его удалить, после ввода переменной sOrder(поменял алгоритм сборкы выходной строки), как видите он не используется дальше.

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

N>Это не дебри, это ограничения. Размер алфавита, размер строки.
Туда же требования по быстродействию и памяти.

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

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

N>>Давайте не влезать в дебри .... да и заделать под юникод\аскі 5 секунд, меняем 256 на 65536 и все работает.
N>UTF-32 тоже работает?
N>Это не дебри, это ограничения. Размер алфавита, размер строки.

это называется до.ся до решения

Как видите в задаче не указан словарь, значит предполагаем или спрашиваем собеседующего.

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

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

N>>Это не дебри, это ограничения. Размер алфавита, размер строки.
N>Туда же требования по быстродействию и памяти.

я что-то не увидел Ваш вариант, только критика других ...

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

N>это называется до.ся до решения

Как видите в задаче не указан словарь, значит предполагаем или спрашиваем собеседующего.
Нет, у меня не было цели до*ся. На собеседовании не рекомендуется предполагать. Нужно уточнять подобные моменты. Иначе может оказаться, что задачу решил, да не ту.
Это особенность мозга считать некоторые вещи банальными и додумывать то, чего нет в условии. Поэтому зачастую изначально дается неполное условие в ожидании, что соискатель должен описать различные варианты в зависимости от дополнительных условий, или уточнить их у интервьюера. Но не за 5 минут, конечно.

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

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

N>>это называется до.ся до решения

Как видите в задаче не указан словарь, значит предполагаем или спрашиваем собеседующего.
N>Нет, у меня не было цели до*ся. На собеседовании не рекомендуется предполагать. Нужно уточнять подобные моменты. Иначе может оказаться, что задачу решил, да не ту.
N>Это особенность мозга считать некоторые вещи банальными и додумывать то, чего нет в условии. Поэтому зачастую изначально дается неполное условие в ожидании, что соискатель должен описать различные варианты в зависимости от дополнительных условий, или уточнить их у интервьюера. Но не за 5 минут, конечно.

nile, так это вы давали эту задачу?

On 22.02.2013 13:50, nile wrote:

> Легко) Например, запустить вложенный цикл, который будет бежать по
> исходной строке и искать встречаемость для каждого символа отдельно.
А, ну да. Причем не вижу ничего плохо в таком решении в каком-то случае.

Posted via RSDN NNTP Server 2.1 beta

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

VN>За два прохода. тут есть решения за O(n) — один проход.

Покажите решение, схему только

... << RSDN@Home 1.2.0 alpha 5 rev. 1539>>

On 22.02.2013 13:54, vvlad.net wrote:

> Что такое O(n), O(2n)
Второе — это неправильная запись первого.

З.Ы. Над тобой тут даже minologic сжалился и объяснил.

Posted via RSDN NNTP Server 2.1 beta

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

V>On 22.02.2013 13:33, jazzer wrote:

>> Задача элементарная, но 5 минут маловато.
V>Задача не корректная.
А где ты в жизни видел, чтоб задачи сразу были корректные? В работе, я имею в виду.
Очевидно, что надо задавать уточняющие вопросы, и это тоже одна из характеристик кандидата — он/она сразу бросается писать код или сначала проясняет требования к решению.

V>Нельзя понять, что они имели в виду:
Поэтому надо спросить. А пока спрашиваешь, думать варианты решения. Вполне возможно, что к моменту получения всех ответов у тебя решение в голове сложится и его достаточно будет только записать — на это 5 минут может и хватить.

V>1. только из этой последовательности получить итоговую строку.
V>2. только в английском алфавите.
V>3. в алфавите размером M.
V>4. нужно ли сохранять последовательность всречаемости символов.
судя по примеру — да, видно же.

V>5. может их интересовала только частотность и все мудотня с сохранением
V>последовательности нафиг не нужна.
V>6. не говорю уже про нефункциональные, ограничение памяти,
V>быстродействие и т.д. В обсуждении уже говорилось о решении О(n^2), если
V>эта задача выполняется единожды при страте программы раз в несколько
V>лет, то хоть O(n^3) годится.

+1. Поэтому надо спрашивать.

V>Отсеять.
Зачем?

On 22.02.2013 13:25, vvlad.net wrote:

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

Posted via RSDN NNTP Server 2.1 beta

On 22.02.2013 14:20, nile wrote:

> Это особенность мозга считать некоторые вещи банальными и додумывать то,
> чего нет в условии. Поэтому зачастую изначально дается неполное условие
> в ожидании, что соискатель должен описать различные варианты в
> зависимости от дополнительных условий, или уточнить их у интервьюера. Но
> не за 5 минут, конечно.
Причем собеседователь, если хочет выяснить этот момент "как кандидат
уточняет задачу" должен намекнуть про этот момент, а не сидеть с
каменным лицом и ждать некоего решения в коде и сразу.

Posted via RSDN NNTP Server 2.1 beta

On 22.02.2013 14:12, kaa.python wrote:

> ЧТо тут сложного то? За что в морду плевать-то?
Забыли упомянуть про алфавит размера N (например, 2^32) для начала.

А так да, молодец, некий частный случай решил.
Но вот тебе еще решение для некоего частного случая: return "vvabbbccc".

Posted via RSDN NNTP Server 2.1 beta

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

N>я что-то не увидел Ваш вариант, только критика других ...
Я текстом описывал.
Для случая, когда алфавит большой, но лишь малая их часть (заранее неизвестная) используются в строках (сделал на базе решения Spiceman):

static string Solve(string s)
{
    var w = new Dictionary<char, int>();
            
    //Строим гистограмму
    foreach (char c in s)
    {
        int count;

        if (!w.TryGetValue(c, out count))
        {
            w.Add(c, 1);
        }
        else
        {
            count++;
            w[c] = count;
        }
    }

    var builder = new StringBuilder();
    char? last = null;
    //Заполняем в порядке появления символа в строке
    foreach (char c in s)
    {
        if (!last.HasValue || last.Value != c)
        {
            int count;
            if (!w.TryGetValue(c, out count))
            {
                //Этот символ уже встречался и удален из Dictionary
                continue;
            }

            w.Remove(c);
            builder.Append(c, count);
            last = c;
        }
    }

    return builder.ToString();
}

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

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

V>Тогда решение:
V>return "vvabbbccc"
Вот, отличный пример того, как свести задачу к абсурду, делая свои предположения и не уточняя условие у интервьюера. Решил за O(1), молодец!

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

V>On 22.02.2013 13:39, vvlad.net wrote:

>> Точно, и решение хорошее
V>Учитывая отсутсвие корректной постановки задачи, а теперь пусть размер
V>алфавита 2^32.

Учитывая что я не сказал отличное (к сожалению, я забываю, что далеко не все воспринимают "хорошее", как "не отличное")...

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

VN>один проход по списку не равно два прохода по списку. (но зависимось от длины списка — линейная, это ты хочешь сказать?)
http://ru.wikipedia.org/wiki/%C2%ABO%C2%BB_%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%BE%D0%B5_%D0%B8_%C2%ABo%C2%BB_%D0%BC%D0%B0%D0%BB%D0%BE%D0%B5#.D0.94.D1.80.D1.83.D0.B3.D0.B8.D0.B5

On 22.02.2013 14:39, jazzer wrote:

> V>Задача не корректная.
> А где ты в жизни видел, чтоб задачи сразу были корректные? В работе, я
> имею в виду.
Видел я разные. И постановки задач в стиле "хочу чтобы было хорошо" —
это обычно от русскоязычных и четкие, внятные и полные ТЗ — это чаще от
белых иностранцев.

> Очевидно, что надо задавать уточняющие вопросы, и это тоже одна из
> характеристик кандидата — он/она сразу бросается писать код или сначала
> проясняет требования к решению.
Опять 25. Не надоело еще сначала придумывать сказку, а потом упорно с
ней спорить. В данном конкретном случае четко видно, что постановка
задачи на собеседовании некорректная.
А что нужно делать в некоей ситуации в работе сильно зависит от той
ситуации.

> Поэтому надо спросить. А пока спрашиваешь, думать варианты решения.
> Вполне возможно, что к моменту получения всех ответов у тебя решение в
> голове сложится и его достаточно будет только записать — на это 5 минут
> может и хватить.
Не многие программисты так могут. Обычно им надо время на подумать,
что-то нафантазировать, решить, что придумали, потом уточнить то-ли
решили. А тут еще и стресс собеседования (вот только не надо говорить,
что если у тебя на собеседовании нет стресса, то и у других тоже).

> V>1. только из этой последовательности получить итоговую строку.
> V>2. только в английском алфавите.
> V>3. в алфавите размером M.
> V>4. нужно ли сохранять последовательность всречаемости символов.
> судя по примеру — да, видно же.
У меня телепалка не настолько развита. Лично я из тех двух строк ничего
не увидел.

> V>Отсеять.
> Зачем?
Уже же обсуждали.
1. Нужно рассказывать начальству, как много работы, но брать никого
нельзя, ибо в реальности работы не много.
2. ХР нужно показывать свою деятельность, чтобы не уволили.
3. Фейковая вакансия для оценки рынка.
4. Думаю еще можно много причин найти.

Posted via RSDN NNTP Server 2.1 beta

On 22.02.2013 14:55, Tilir wrote:

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

> Ещё раз -- мне кажется задача поставлена вполне нормально даже в
> сумбурном изложении топикстартера.
В такой постановке допустимо решение return "vvabbbccc".

Posted via RSDN NNTP Server 2.1 beta

On 22.02.2013 15:26, nile wrote:

> На любом собеседовании предполагается, что можно задавать вопросы.
> А если это тестовое задание, то в идеале рассматривать различные
> варианты, или хотя бы указывать на свои предположения.
От ТС мы знаем, что на все про все было 5 мин и собеседователь ждал кода
и был сильно счастлив, когда ТС не сделал.
В такой ситуации я тоже не смогу ничего написать.

Posted via RSDN NNTP Server 2.1 beta

On 22.02.2013 15:39, nile wrote:

> Вот, отличный пример того, как свести задачу к абсурду, делая свои
> предположения и не уточняя условие у интервьюера. Решил за O(1), молодец!
Угу. К этому приводит некорректная постановка задачи. Неужели в работе
никогда с таким не сталкивался?
Начальник всегда может сказать, хочу "чтобы мне стало хорошо" и чаще
всего, если он мазохист, ему становиться в итоге хорошо. Нормальный же
начальник, когда ставит задачу, обычно убеждается, что исполнитель
понял, что нужно сделать.

Posted via RSDN NNTP Server 2.1 beta

On 22.02.2013 15:01, kaa.python wrote:

> Hint: собеседование — это диалог, а не монолог.
Когда как. Бывает, что весь диалог заключается в вопросах с одной
стороны и ответах с другой.
И нормальных собеседовании сильно меньше, чем не нормальных.

Posted via RSDN NNTP Server 2.1 beta

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

V>Угу. К этому приводит некорректная постановка задачи. Неужели в работе
V>никогда с таким не сталкивался?
Постоянно сталкиваюсь, и все сталкиваются. Потому и проверяется заодно, ты сразу бежишь кодить решение криво поставленной задачи, или пытаешься сначала устранить все противоречия и домыслы.
Я не говорю про требование "решить за 5 минут". Это уже признак неадекватности. Но если такого требования нет, указанное условие вполне допустимо, и располагает к диалогу, а не молчаливому кодингу, основанному на предположениях.

On 22.02.2013 15:41, vvlad.net wrote:

> один проход по списку не равно два прохода по списку. (но зависимось от
> длины списка — линейная, это ты хочешь сказать?)
В o-нотации равно. Я хотел сказать, что нотацию o-большого ты
используешь, но не понимаешь, что она значит. Ну как бы это мелочи, если
бы ты не требовал это незнание от других.
И даже больше того, двойной проход по списку может ускорить программу
(prefetch), но это к о-нотации отношения не имеет.

> Где? не замечал подобного.
В соседней ветке http://rsdn.ru/forum/message/5078763.aspx. Я ошибся, не
minotlogic, а nile.

Posted via RSDN NNTP Server 2.1 beta

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

V>Начальник всегда может сказать, хочу "чтобы мне стало хорошо" и чаще
V>всего, если он мазохист, ему становиться в итоге хорошо. Нормальный же
V>начальник, когда ставит задачу, обычно убеждается, что исполнитель
V>понял, что нужно сделать.
Более того, он отдаст задачу на выполение тому, кто сможет её выполнить.

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

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

VN>>один проход по списку не равно два прохода по списку. (но зависимось от длины списка — линейная, это ты хочешь сказать?)
N>http://ru.wikipedia.org/wiki/%C2%ABO%C2%BB_%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%BE%D0%B5_%D0%B8_%C2%ABo%C2%BB_%D0%BC%D0%B0%D0%BB%D0%BE%D0%B5#.D0.94.D1.80.D1.83.D0.B3.D0.B8.D0.B5

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

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

On 22.02.2013 15:33, nile wrote:

> Если и алфавит большой, и он может целиком присутствовать во входной
> строке, то тут придется экономить память, и использовать банальный
> двойной проход за O(n^2) или сортировать блоками. Но это уже конечно
> далеко не за 5 минут.
Я бы попроще пошел для начала. Заюзал бы разреженный массив (благо для
плюсов их реализаций море). Ну а если "он может целиком присутствовать
во входной строке", тут уже крутиться придется.

Posted via RSDN NNTP Server 2.1 beta

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

T>Можно подробней? Ну вот есть у вас счётчики. Как потом восстанавливать порядок будете?

source = "vvabbcbcc"

count = {}
order = []

for char in source:
    n = count.get(char, 0)
    if n == 0:
        order.append(char)
    count[char] = n + 1

result = ""
for char in order:
    result += char * count[char]

print result

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

V>On 22.02.2013 15:41, vvlad.net wrote:

>> один проход по списку не равно два прохода по списку. (но зависимось от
>> длины списка — линейная, это ты хочешь сказать?)
V>В o-нотации равно.
Да, поскольку описывается тип зависимости.

V>Я хотел сказать, что нотацию o-большого ты
V>используешь, но не понимаешь, что она значит.
Блин, ты евангелист O-нотации? Я то как раз и понимаю, и может даже и не хуже, а то и лучше тебя.
И знаю о некорректности такой записи (но это не ашипка, а уточнение).
Но говорить что двойной проход по циклу — O(n^2) это действительно неправильно.

Ну как бы это мелочи, если
V>бы ты не требовал это незнание от других.
Где я этого требую?

V>И даже больше того, двойной проход по списку может ускорить программу
V>(prefetch), но это к о-нотации отношения не имеет.
Да, не имеет. Да, возможно. Да, формально это O(n). Да, в зависимотсти от алгоритма, это может быть быстрее.
А теперь... Пример в студию! (это я у тебя спрашиваю).

>> Где? не замечал подобного.
V>В соседней ветке http://rsdn.ru/forum/message/5078763.aspx. Я ошибся, не
V>minotlogic, а nile.
Ошибся? Да... слишком быстро думаешь и принимаешь сходу неверные решения. Понятно, почему ты считаешь, что такой вариант вопроса неприемлен. Ведь вполне возможно, что собеседователь хочет узнать какие решения приходят человеку в голову в первую очередь — фактически, какая у человека база по алгоритмам и типам данных, насколько он этой темой владеет. А для тебя такой вопрос — это возможный фейл (не утверждаю, что epic).

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

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

V>>Угу. К этому приводит некорректная постановка задачи. Неужели в работе
V>>никогда с таким не сталкивался?
N>Постоянно сталкиваюсь, и все сталкиваются. Потому и проверяется заодно, ты сразу бежишь кодить решение криво поставленной задачи, или пытаешься сначала устранить все противоречия и домыслы.
N>Я не говорю про требование "решить за 5 минут". Это уже признак неадекватности. Но если такого требования нет, указанное условие вполне допустимо, и располагает к диалогу, а не молчаливому кодингу, основанному на предположениях.

Согласен, но я бы еще поговорил о том решении, которое применил кандидат, даже если бы он не уточнял требования.

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

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

N>>я что-то не увидел Ваш вариант, только критика других ...
N>Я текстом описывал.
..
N>
N>Если и алфавит большой, и он может целиком присутствовать во входной строке, то тут придется экономить память, и использовать банальный двойной проход за O(n^2) или сортировать блоками. Но это уже конечно далеко не за 5 минут.

Во как все обернулось ... Вы у всех искали проблемы, даже в постановке задачи, а сами сделали кривое решения ... Для чего делать 2 прохода по входной строке ? Что будет если она занимает 1ТB ??!!!

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

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

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

N>>>я что-то не увидел Ваш вариант, только критика других ...
N>>Я текстом описывал.
N>..
N>>
N>>Если и алфавит большой, и он может целиком присутствовать во входной строке, то тут придется экономить память, и использовать банальный двойной проход за O(n^2) или сортировать блоками. Но это уже конечно далеко не за 5 минут.

N>Во как все обернулось ... Вы у всех искали проблемы, даже в постановке задачи, а сами сделали кривое решения ... Для чего делать 2 прохода по входной строке ? Что будет если она занимает 1ТB ??!!!

Во-во, спецы называется. map + list (ordering) — все что требуется, и именно этого, как правило, и ждет собеседователь.

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

Решил меньше чем за 5 мин:

template<typename BidirectionalIterator>
void group(BidirectionalIterator first,BidirectionalIterator last)
{
    while(first!=last)
        first = partition
        (
            first, last,
            bind1st
            (
                equal_to<typename iterator_traits<BidirectionalIterator>::value_type>(),
                *first
            )
        );
}

На написание кода ушло минуты две, остальную часть времени обдумывал. Суммарно минуты 4.
Из compile error — забыл выделенную ;. live-test
Если был бы Boost, то кода было бы намного меньше:

template<typename BidirectionalIterator>
void group(BidirectionalIterator first,BidirectionalIterator last)
{
    while(first!=last)
        first = partition
        (
            first,last,
            _1 == *first
        );
}

Решение квадратичное, но inplace.
Можно сделать не inplace — average O( N ), что-то типа:

template<typename BidirectionalIterator>
void group(BidirectionalIterator first,BidirectionalIterator last)
{
    typedef typename iterator_traits<BidirectionalIterator>::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)
    {
        auto n = hist[v];
        fill_n(first,n,v);
        first+=n;
    }
}

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

VN>>>map + list (для сохранения порядка) — все.

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

VN>Априори, такое не принимается (я бы не принял) — слишком тупое и очевидное решение.

VN>Это кстати не O(n^2) а O(2n)
Как считал? Особенно с учётом использования map.

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

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

VN>>>>map + list (для сохранения порядка) — все.

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

VN>>Априори, такое не принимается (я бы не принял) — слишком тупое и очевидное решение.

VN>>Это кстати не O(n^2) а O(2n)
A>Как считал? Особенно с учётом использования map.

если один проход — n то два это в два раза больше. в два (2) раза, не болле и не менее.

А если ты говоришь о стоимости одного прохода — то там оно линейно от количества элементов — map это O(1), пора бы уже и знать.

On 22.02.2013 16:10, nile wrote:

> Постоянно сталкиваюсь, и все сталкиваются. Потому и проверяется заодно,
> ты сразу бежишь кодить решение криво поставленной задачи, или пытаешься
> сначала устранить все противоречия и домыслы.
Учитывая, что ты проигнорил второй абзац, я могу сделать вывод, что
постановки задач там, где ты работаешь отсутвуют и начальник там
выполняет одну функцию — недопустить программиста к заказчику.

Posted via RSDN NNTP Server 2.1 beta

On 22.02.2013 16:58, vvlad.net wrote:

> Во-во, спецы называется. map + list (ordering) — все что требуется, и
> именно этого, как правило, и ждет собеседователь.
То бишь проверка навыка телепатии? Угадать, что ждет собеседователь.

Posted via RSDN NNTP Server 2.1 beta

On 22.02.2013 17:18, Yoriсk wrote:

> Слабенькое начало.
Я же нежно.

> Для символов произвольной(неизвестной) длинны даных
> замукнутым списком...
Пофиг. Все определяется размером алфавита.

Posted via RSDN NNTP Server 2.1 beta

On 22.02.2013 16:48, vvlad.net wrote:

> Блин, ты евангелист O-нотации? Я то как раз и понимаю, и может даже и не
> хуже, а то и лучше тебя.
Да не волнуйся, у тебя больше — это же все знают.
Я всего-лишь напомнил тебе о том, что запись O(2n) — некорректа и
бессмысленна.

Posted via RSDN NNTP Server 2.1 beta

On 22.02.2013 17:22, vvlad.net wrote:

> map это O(1), пора бы уже и знать.
И эти люди запрещают нам ковыряться в носу.

Posted via RSDN NNTP Server 2.1 beta

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

EP> while(first!=last)
EP> first = partition
EP> (
EP> first,last,
EP> _1 == *first
EP> );

ошибка — должно быть stable_partition

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

N>Во как все обернулось ... Вы у всех искали проблемы, даже в постановке задачи, а сами сделали кривое решения ... Для чего делать 2 прохода по входной строке ? Что будет если она занимает 1ТB ??!!!
Второй проход не увеличивает асимптотическую сложность алгоритма, так и остается O(n), так что Ваш сарказм неуместен. Да, можно при первом проходе заполнять список символов в порядке появления, и потом по нему генерировать новую строку. Но, повторюсь, сложность алгоритма останется той же, поэтому это дело вкуса.

И замечу, что я нигде не сказал, что Ваше решение некорректно, не надо так болезненно реагировать. Наоборот, я сказал, что решение корректное, но работает только при предположении, что строка содержит только ASCII-символы, а об этом в условии не сказано ни слова. Мое решение покрывает и случай ASCII, и Unicode, при этом имеет ту же сложность.

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

V>On 22.02.2013 16:48, vvlad.net wrote:

>> Блин, ты евангелист O-нотации? Я то как раз и понимаю, и может даже и не
>> хуже, а то и лучше тебя.
V>Да не волнуйся, у тебя больше — это же все знают.
V>Я всего-лишь напомнил тебе о том, что запись O(2n) — некорректа и
V>бессмысленна.

А два прохода в данном случае смысл именют?

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

V>On 22.02.2013 17:22, vvlad.net wrote:

>> map это O(1), пора бы уже и знать.
V>И эти люди запрещают нам ковыряться в носу.

map — aka hashtable — запись и доступ за O(1). ЧЯДНТ?

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

V>On 22.02.2013 16:58, vvlad.net wrote:

>> Во-во, спецы называется. map + list (ordering) — все что требуется, и
>> именно этого, как правило, и ждет собеседователь.
V>То бишь проверка навыка телепатии? Угадать, что ждет собеседователь.

Средний вариант решения — на большинство кейсов.

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

VN>Во-во, спецы называется. map + list (ordering) — все что требуется, и именно этого, как правило, и ждет собеседователь.
Собственно, у меня map и используется. Только вместо list второй проход по строке. Ок, твоя правда, с list будет чуток побыстрее.
И "как правило" еще не означает, что интервьюер ожидает именно это решение. Скорее он ожидает, что ты будешь исходить из конкретной задачи, а не выполнять любую перестановку строки используя map и list, не задумываясь.
ndev вообще предложил узкоспециализированное решение, которое подойдет далеко не в каждой ситуации. Хотя с учетом ограничений, которые он почему-то посчитал очевидными в век юникода, действительно хорошее решение.

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

>>> map это O(1), пора бы уже и знать.
V>>И эти люди запрещают нам ковыряться в носу.
VN>map — aka hashtable — запись и доступ за O(1). ЧЯДНТ?

В C++ map это не hashtable, там O(ln N).
hashtable — unordered_map.

On 22.02.2013 17:46, vvlad.net wrote:

> А два прохода в данном случае смысл именют?
Без понятия. Зависит от постановки задачи. В данной же может быть все
что угодно.

Posted via RSDN NNTP Server 2.1 beta

Чего-то я все больше убеждаюсь, что проще дать тест на codility.com в качестве первого этапа...

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

V>On 22.02.2013 15:26, nile wrote:

>> На любом собеседовании предполагается, что можно задавать вопросы.
>> А если это тестовое задание, то в идеале рассматривать различные
>> варианты, или хотя бы указывать на свои предположения.
V>От ТС мы знаем, что на все про все было 5 мин и собеседователь ждал кода
V>и был сильно счастлив, когда ТС не сделал.
V>В такой ситуации я тоже не смогу ничего написать.

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

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

VN>>Во-во, спецы называется. map + list (ordering) — все что требуется, и именно этого, как правило, и ждет собеседователь.
N>Собственно, у меня map и используется. Только вместо list второй проход по строке. Ок, твоя правда, с list будет чуток побыстрее.
N>И "как правило" еще не означает, что интервьюер ожидает именно это решение. Скорее он ожидает, что ты будешь исходить из конкретной задачи, а не выполнять любую перестановку строки используя map и list, не задумываясь.

Я уже много людей прособеседовал. я всегда жду ответ для most-common case.

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

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

Здравствуйте, 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.

А мы говорим о common data structures. там map и hashtable эквивалентны. а сишный map это либо бинарный поиск, либо дерево (в STL не силен)

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

V>On 22.02.2013 17:46, vvlad.net wrote:

>> А два прохода в данном случае смысл именют?
V>Без понятия. Зависит от постановки задачи. В данной же может быть все
V>что угодно.

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

Здравствуйте, 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х вложенных циклах.

... << RSDN@Home 1.2.0 alpha 5 rev. 1539>>

Здравствуйте, 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);
}

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

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

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

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

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

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

? Попробуйте включать голову

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

On 23.02.2013 11:34, artem.komisarenko wrote:

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

Posted via RSDN NNTP Server 2.1 beta

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

VN>Я уже много людей прособеседовал. я всегда жду ответ для most-common case.
Это же не очень осмысленно в реальной жизни. Значительно лучше решать задачу не в вакууме, а при реальных ограничениях. И было бы хорошо, чтобы собеседуемый прежде чем решать задачу в общем виде немного подумал.

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

Поддерживаю по всем пунктам.

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

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

Ну вот смотрите вы сами ответили на свой вопрос — вам не известны входные условия. И в этих условиях вы пытаетесь выдать интервьюеру самый простой вариант решения с использованием стандартных data structures. То бишь вместо того, чтобы обдумать решение задачи и дать решение для общего случая вы даете частное решение, в котором за вас половину работы сделал фрэймворк.
Интервьюер наоборот хочет увидеть как именно вы будете решать задачу максимально эффективно для общего случая. Увидеть ваш скилл, а не скилл фрэймворка. Поэтому на мой взгляд, лучшее решение в данной ситуации реализовать in-place алгоритм с O(N^2) by time & O(1) by memory а потом уже порассудить на тему в каких случаях реализовать less O(N^2) by time

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

__>Интервьюер наоборот хочет увидеть как именно вы будете решать задачу максимально эффективно для общего случая. Увидеть ваш скилл, а не скилл фрэймворка. Поэтому на мой взгляд, лучшее решение в данной ситуации реализовать in-place алгоритм с O(N^2) by time & O(1) by memory а потом уже порассудить на тему в каких случаях реализовать less O(N^2) by time
Да не надо телепатией страдать. Просто уточнить детали у интервьюера, а до этого не писать ни строчки кода. Если он скажет, что запрещено использовать дополнительные буферы, это равносильно запрету на использование data structures, и только в этом случае писать реализацию O(N^2) by time & O(1) by memory. Выбирать самое неэффективное по быстродействию решение просто ради того, чтобы не использовать data structures и якобы продемонстрировать свои скиллы — идиотизм.

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

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

VN>>Я уже много людей прособеседовал. я всегда жду ответ для most-common case.
W>Это же не очень осмысленно в реальной жизни. Значительно лучше решать задачу не в вакууме, а при реальных ограничениях. И было бы хорошо, чтобы собеседуемый прежде чем решать задачу в общем виде немного подумал.

Если собеседуемый знает решение для most-common case — можно и глубже пойти. А если и этого не знает — то и напрягаться нет смысла.
Кроме того, most-common case — это фактически паттерн, и в коде зразу видно что делается. А оптимизации идут уже тогда, когда была проверена работоспособность системы/модуля, да и то, если они реально нужны.

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

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

__>>Интервьюер наоборот хочет увидеть как именно вы будете решать задачу максимально эффективно для общего случая. Увидеть ваш скилл, а не скилл фрэймворка. Поэтому на мой взгляд, лучшее решение в данной ситуации реализовать in-place алгоритм с O(N^2) by time & O(1) by memory а потом уже порассудить на тему в каких случаях реализовать less O(N^2) by time
N>Да не надо телепатией страдать. Просто уточнить детали у интервьюера, а до этого не писать ни строчки кода. Если он скажет, что запрещено использовать дополнительные буферы, это равносильно запрету на использование data structures, и только в этом случае писать реализацию O(N^2) by time & O(1) by memory. Выбирать самое неэффективное по быстродействию решение просто ради того, чтобы не использовать data structures и якобы продемонстрировать свои скиллы — идиотизм.

Именно. Я уже приводил в одной из веток свои соображения с точки зрения интервьювера. В общем, если собеседуемый спрашивает — это плюс, но мой стандартный ответ — most common case. Меня как раз интересует data structures в подобных задачах.

Еще вариант:

string Solve(string str)
{
    var list = new List<char>();
    foreach (var ch in str)
    {
        var idx = list.IndexOf(ch);
        if (idx >= 0)
        {
            list.Insert(idx, ch);
            continue;
        }
        list.Add(ch);
    }
    return new String(list.ToArray());           
}

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

>>> map это O(1), пора бы уже и знать.
V>>И эти люди запрещают нам ковыряться в носу.

VN>map — aka hashtable — запись и доступ за O(1). ЧЯДНТ?
Тут вообще контекст непонятен. Я прежде всего подумал об stl, если брать java, то писать надо с большой буквы Map. Но там Map — это всего-лишь интерфейс, реализация разная бывает HashMap лишь одна из них.
Фактически это просто словарь, некоторое отображение из ключа в значение. Реализовать можно сильно по разному, и нет универсальной реализации на все случаи.

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

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

>>>> map это O(1), пора бы уже и знать.
V>>>И эти люди запрещают нам ковыряться в носу.

VN>>map — aka hashtable — запись и доступ за O(1). ЧЯДНТ?
A>Тут вообще контекст непонятен. Я прежде всего подумал об stl, если брать java, то писать надо с большой буквы Map. Но там Map — это всего-лишь интерфейс, реализация разная бывает HashMap лишь одна из них.
A>Фактически это просто словарь, некоторое отображение из ключа в значение. Реализовать можно сильно по разному, и нет универсальной реализации на все случаи.

В принципе верно, это дело привычки, кто что под этим понимает.

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

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

V>>Я тоже нет. Ну не умею я не задумываясь решать задачи. Мне надо сесть ,
V>>подумать, посмотреть, что за входные данные у нас, какие требования не
V>>функциональные есть и ...

AT>... написать письмо наверх с уточняющими вопросами, сходить покурить, получить ответ сверху с упоминаем, что некая команда недавно решала подобную проблему, предложить переиспользовать их подход, сходить на обед, получить приглашение на митинг с другой командой для обсуждения интеграции, покопаться в интернетах и подоготовиться к митингу, выдвинуть "свое" решение на совещании, поделиться идей "своего" решения с коллегами, назначить совещание на завтрашнее утро по вопросам использования "своего" протокола в других проектах ... а там и день закончился и уже пора домой идти

неплохо бы выделить еще пару дней на составление архитектурной и диаграммы действия
выбрать язык отвечающий задаче
и выделить время на написание прототипа

On 22.02.2013 15:14, andrey.t wrote:

> ... написать письмо наверх с уточняющими вопросами, сходить покурить,
> получить ответ сверху с упоминаем, что некая команда недавно решала
> подобную проблему, предложить переиспользовать их подход, сходить на
> обед, получить приглашение на митинг с другой командой для обсуждения
> интеграции, покопаться в интернетах и подоготовиться к митингу,
> выдвинуть "свое" решение на совещании, поделиться идей "своего" решения
> с коллегами, назначить совещание на завтрашнее утро по вопросам
> использования "своего" протокола в других проектах ... а там и день
> закончился и уже пора домой идти
Не. Вот за это и ненавижу офисы с их планктоном.

Posted via RSDN NNTP Server 2.1 beta

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

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

V>>Но вот тебе еще решение для некоего частного случая: return "vvabbbccc".

KP>Hint: собеседование — это диалог, а не монолог.

по разному бывает, иногда собеседование проводит девочка HR, которая даёт кем-то написанные задания

On 25.02.2013 15:45, Философ wrote:

> по разному бывает, иногда собеседование проводит девочка HR, которая
> даёт кем-то написанные задания
Это очень много говорит о конторе. И соответсвенно сразу ясно имеет ли
смысл в такую контору собеседоваться или нет.

Posted via RSDN NNTP Server 2.1 beta

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

Может рекрутер выбрав оптимальнейшее решение кадидатов хочет усовершествовать свой код ???

V>Ну, так они никого не набирают, рекрутер делает свою работу, пропускает
V>через себя максимльно возможное количество народа, чтобы начальство им
V>довольно было. А реальной вакансии нет.
V>Неужели ты первый раз с таким сталкиваешься?
V>Недавно вон даже вакансия у яндекса подобная висела (да еще и от 150000
V>зазывали), о том, что она фейковая есть инсайдерская инфа.

On 26.02.2013 18:04, PageMaker wrote:

> Может рекрутер выбрав оптимальнейшее решение кадидатов хочет
> усовершествовать свой код ???
Думаешь в этот темной комнате есть черная кошка?

Posted via RSDN NNTP Server 2.1 beta

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

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

Если реальной вакансии нет, то кто платит рекрутеру за пропускание через себя людей?
Т. е. откуда "физически" берутся эти деньги?

On 28.02.2013 12:27, Аноним931 wrote:

> Если реальной вакансии нет, то кто платит рекрутеру за пропускание через
> себя людей?
> Т. е. откуда "физически" берутся эти деньги?
А сам подумай откуда кто платит.

Posted via RSDN NNTP Server 2.1 beta

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

V>За такую постановку задачи только в морду плюнуть. Или она на
V>собеседовании была не так поставлена?

Вроде поставленна корректно, хотя, imho, просить писать рабочий код на бумаге — не совсем корректно
В спокойной обстановке, имея под боком документацию написал за ~ 4 минуты. На собеседовании, думаю, не написал бы

для groovy:

 'vvabbcbcc'.toList().countBy{it}.collect { a, b -> a * b }.join()

к стати, в описаниях вакансий встречается что-то вроде "able to work under pressure". Наверно это так и проверяется

On 28.02.2013 13:06, megapoliss wrote:

> Вроде поставленна корректно,
Нет, ибо в той постановке задаче в возможный ответ return "результат".
И говорит только об одном, на конторе (по крайней мере в подражделении,
где работает этот собеседователь) все задачи в такой же постановке,
кому-то это нравиться, кому-то нет.

> к стати, в описаниях вакансий встречается что-то вроде "able to work
> under pressure".
Какие хорошие вакансии, но это не для меня, например.

Posted via RSDN NNTP Server 2.1 beta

On 13.03.2013 9:28, Gradient wrote:

> О! я подумал абсолютно также. Другое дело, что на бумажке за 5 мин не
> написал бы.
Тут уже обсудили это 100 раз и пришли к выводу, что ты не подходишь тому
работодателю.

Posted via RSDN NNTP Server 2.1 beta

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

V>On 13.03.2013 9:28, Gradient wrote:

>> О! я подумал абсолютно также. Другое дело, что на бумажке за 5 мин не
>> написал бы.
V>Тут уже обсудили это 100 раз и пришли к выводу, что ты не подходишь тому
V>работодателю.

Ну и слава яйцам!
Если бы подходил — это было бы симптоматично...

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

M>>Если надо сделать in place , тоже не могу быстрого решения придумать.
G>Хе, а я как .Net-чик не только не вижу решения in place, а знаю о невозможности его сделать в рамках управляемого кода )

Что-то мне подсказывает, что .NET не настолько убог, например:

char[] input = { 'v','v','a','b','b','c','b','c','c' };

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

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

M>>>Если надо сделать in place , тоже не могу быстрого решения придумать.
G>>Хе, а я как .Net-чик не только не вижу решения in place, а знаю о невозможности его сделать в рамках управляемого кода )

EP>Что-то мне подсказывает, что .NET не настолько убог, например:
EP>

EP>char[] input = { 'v','v','a','b','b','c','b','c','c' };
EP>

EP>

Ну, если это считать строкой...
У топикстартера же явно сказано

например есть "vvabbcbcc"

Боюсь, мы сейчас начинаем додумывать условия задачи

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

>> Легко) Например, запустить вложенный цикл, который будет бежать по
>> исходной строке и искать встречаемость для каждого символа отдельно.
V>А, ну да. Причем не вижу ничего плохо в таком решении в каком-то случае.

Квадратичная сложность — вот что плохо. Решить можно в два прохода.

On 18.03.2013 14:31, Ikemefula wrote:

> Квадратичная сложность — вот что плохо. Решить можно в два прохода.
Тебя самого не достала твоя безграмостность?

Posted via RSDN NNTP Server 2.1 beta

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

>> Квадратичная сложность — вот что плохо. Решить можно в два прохода.
V>Тебя самого не достала твоя безграмостность?

Да ты не волнуйся, все уже знают, что ты тут самый умный, так что по дефолту тут все кроме тебя дураки

On 18.03.2013 18:56, Ikemefula wrote:

> Да ты не волнуйся, все уже знают, что ты тут самый умный,
Согласен.

> так что по
> дефолту тут все кроме тебя дураки
Но всех вокруг я бы не оскорблял. Это раз. И два, среди них много умных
людей.

Posted via RSDN NNTP Server 2.1 beta

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

G>Ну, если это считать строкой...
G>У топикстартера же явно сказано

например есть "vvabbcbcc"

G>Боюсь, мы сейчас начинаем додумывать условия задачи

Тут вроде как ведутся разговоры про сложность, то есть в общем случае данные приходят из вне, а не закодированы в огромном литерале (который и в C++ const).
Да и вообще, причём тут строки?

Эта задача элементарно обобщается на любые последовательности элементов (удовлетворяющие определённым требованиям(в зависимости от алгоритма)).

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

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

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

тревиальнейшая задача же, сначала обойти один раз весь массив, и составить карту, типа
v — 0
a — 1
b — 2
c — 3,
потом используя эту карту написать компортор, типа
return map[first] < map[second]

затем вызвать std::sort с его использованием,
тоесть сложность O(N) по памяти и O(n ln(N)) по скорости, разумеется если человек на такой простой ответить не может- то разве можно ему доверить код сложнее чем hello world?

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

S>затем вызвать std::sort с его использованием,
S>тоесть сложность O(N) по памяти и O(n ln(N)) по скорости, разумеется если человек на такой простой ответить не может- то разве можно ему доверить код сложнее чем hello world?

Сортировка не нужна, задача в два прохода == сложность O(N)

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

I>Сортировка не нужна, задача в два прохода == сложность O(N)

аха, тут вы правы, можно на самом деле даже в 1 проход массива, и потом 1 проход массива фиксированного размера в sizeof(char)

AS>char *group(char *S) {
AS>    int i;
AS>    char *p = S+1;
AS>    for (; *p; ++p ) {
AS>        char *pp = p-1;
AS>        for (; pp >= S; --pp) {
AS>            if ( *pp == *p ) // is not first
AS>                memmove(pp+1,pp,p-pp);
AS>        }
AS>    }    
AS>    return S;
AS>}
AS>

Оригинальный in-place — если за 5 мин — то

.
Но он O(N^3). Переводится в O(N^2) добавлением break в if, после memmove.
Ну и если переписать на человеческий язык

, то получается:

template<typename ForwardIterator>
void group(ForwardIterator first,ForwardIterator last)
{
    ForwardIterator i=first,current;
    while(i != last)
    {
       current = i++;
       rotate(find(first,current,*current), current, i);
    }
}

full

#include <algorithm>
#include <iostream>
#include <iterator>
#include <ostream>

using namespace std;

template<typename ForwardIterator>
void group(ForwardIterator first,ForwardIterator last)
{
    ForwardIterator i=first,current;
    while(i != last)
    {
       current = i++;
       rotate(find(first,current,*current), current, i);
    }
}

int main()
{
    char tests[][20] =
    {
        "vvabcbbcc",
        "asdfrrafdsr",
        "abcdefgijkl",
        "010101010101",
        "totobobolol"
    };
    for(auto &&s : tests)
    {
        group(begin(s),end(s));
        cout << s << endl;
    }
}

Здравствуйте, Alexéy Sudachén, Вы писали: [...]

Если range — bidirectional, то можно искать назад, как у тебя. Например:

template<typename BidirectionalIterator>
void group(BidirectionalIterator first,BidirectionalIterator last)
{
    typedef reverse_iterator<BidirectionalIterator> ReverseIterator;
    BidirectionalIterator i=first,current,next_to_same;
    while(i != last)
    {
       current = i++;
       next_to_same = find(ReverseIterator(current),ReverseIterator(first),*current).base();
       if(next_to_same!=first)
           rotate(next_to_same,current,i);
    }
}

full

#include <algorithm>
#include <iostream>
#include <iterator>
#include <ostream>
#include <string>

using namespace std;

template<typename BidirectionalIterator>
void group(BidirectionalIterator first,BidirectionalIterator last)
{
    typedef reverse_iterator<BidirectionalIterator> ReverseIterator;
    BidirectionalIterator i=first,current,next_to_same;
    while(i != last)
    {
       current = i++;
       next_to_same = find(ReverseIterator(current),ReverseIterator(first),*current).base();
       if(next_to_same!=first)
           rotate(next_to_same,current,i);
    }
}

int main()
{
    string tests[] =
    {
        "vvabcbbcc",
        "asdfrrafdsr",
        "abcdefgijkl",
        "010101010101",
        "totobobolol"
    };
    for(auto &&s : tests)
    {
        group(begin(s),end(s));
        cout << s << endl;
    }
}

Это, например, оптимизирует случай когда все элементы равны.

Здравствуйте, Alexéy Sudachén, Вы писали:

AS>Хм, ну почему? есть строка из неё надо получить сгруппированную посимволам, с сохранением последовательности появления.
AS>За 5 минут элементарно решается, там же никаких других условий нет, вот и не надо их придумывать )))

AS>За отсутствие багов не ручаюсь, но это именно решение за пять минут.

Жесть какая-то. Для такой простой задачи, такой нечитабельный код.

Если просили придумать решение задачи, то 5 минут более чем достаточно. Задача решается со скоростью речи, т.е. можно мыслить вслух. Если им нужен был именно код на бумаге, то мне такая вакансия скорее всего была бы совершенно не интересна. Набирание кода на время — скучно.

EP>Оригинальный in-place — если за 5 мин — то

.
EP>Но он O(N^3). Переводится в O(N^2) добавлением break в if, после memmove.

блин, точно! про бряк забыл )))

Здравствуйте, Alexéy Sudachén, Вы писали:

EP>>Оригинальный in-place — если за 5 мин — то

.
EP>>Но он O(N^3). Переводится в O(N^2) добавлением break в if, после memmove.
AS>блин, точно! про бряк забыл )))

я когда делал на время, вообще про стабильность забыл

template<typename BidirectionalIterator>
void group(BidirectionalIterator first,BidirectionalIterator last)
{
    while(first!=last)
        first = stable_partition( first, last, _1 == *first );
}

RNS>Если просили придумать решение задачи, то 5 минут более чем достаточно. Задача решается со скоростью речи, т.е. можно мыслить вслух. Если им нужен был именно код на бумаге, то мне такая вакансия скорее всего была бы совершенно не интересна. Набирание кода на время — скучно.

Знать путь и пройти его — зело разные вещи )

Могу точно сказать — ты не программист ) Манагер, аналитЕГ, или просто философ? Я к тому, что когда сам проводил собеседования, в первую очередь смотрел сможет ли подопытный написать код, причём совершенно любой. Пока нет демонстрации что есть способность писать код, о философии говорить бесполезно. Как бы у программера результатом работы является код, а не философские трактаты о пользе сортировке в задачах частичного упорядочивания сферических объектов в вакууме.

Здравствуйте, Alexéy Sudachén, Вы писали:

RNS>>Если просили придумать решение задачи, то 5 минут более чем достаточно. Задача решается со скоростью речи, т.е. можно мыслить вслух. Если им нужен был именно код на бумаге, то мне такая вакансия скорее всего была бы совершенно не интересна. Набирание кода на время — скучно.

AS>Знать путь и пройти его — зело разные вещи )

AS>Могу точно сказать — ты не программист ) Манагер, аналитЕГ, или просто философ? Я к тому, что когда сам проводил собеседования, в первую очередь смотрел сможет ли подопытный написать код, причём совершенно любой. Пока нет демонстрации что есть способность писать код, о философии говорить бесполезно. Как бы у программера результатом работы является код, а не философские трактаты о пользе сортировке в задачах частичного упорядочивания сферических объектов в вакууме.

Всё, конечно, зависит от задач, которые нужно решать, но мне важнее оценить способность адекватно мыслить, умение быстро обучаться и желание работать. А знание конкретных языков и технологий вторично — эти навыки легко подхватить, если, конечно, проект не хардкорный. Но я набирал людей себе в стартап, небольшую команду. И я наверное да, не программист — на порядок больше времени уходит на думание и исследование, чем на собственно написание кода. Если бы я набирал людей на написание кода под спецификации, я бы с вами согласился — важно было бы именно оценить умение написание хорошего кода.

RNS>Всё, конечно, зависит от задач, которые нужно решать, но мне важнее оценить способность адекватно мыслить, умение быстро обучаться и желание работать. А знание конкретных языков и технологий вторично — эти навыки легко подхватить, если, конечно, проект не хардкорный. Но я набирал людей себе в стартап, небольшую команду. И я наверное да, не программист — на порядок больше времени уходит на думание и исследование, чем на собственно написание кода. Если бы я набирал людей на написание кода под спецификации, я бы с вами согласился — важно было бы именно оценить умение написание хорошего кода.

Ну, как бы умение программировать ни есть знание языка и технологий. Это скил уровня умения думать. Опыт пропущенный через призму сознания. Такой штуке нельзя научиться за пару дней, недель, месяцев... годы нужны. Опять же хороший код это что-то из области литературы. ) Штука сильно субьективная. Код должен быть написанным за оговоренное время, соответствовать гайдлайнам и ТЗ, ну и самое главное — работать.

Как бы я тоже в основном занимаюсь исследованиями. Даже кода я читаю в несколько раз больше чем пишу ))). Что по времени, что по объёму. Но у меня очевидно нет проблем решить задачку на 5 мин не методом выпускника ФМШ'а и без запарок на тему 'хорошего' кода ))))

recursive stable in-place divide and conqueror grouping

повороты теперь делаются для целых групп/подгрупп, а не по одному элементу за раз

возможность распараллелить

возможность использовать non-inplace алгоритм на нижних уровнях, допустим на константной, логарифмической или линейной длине от общей.

// _____________________[ recursive stable group ]___________________________ //

// stable merge of adjacent groups
template<typename BidirectionalIterator>
void merge_groups(BidirectionalIterator first,BidirectionalIterator middle,BidirectionalIterator last)
{
    typedef reverse_iterator<BidirectionalIterator> ReverseIterator;
    BidirectionalIterator i=middle,current,sub_last,next_to_same;
    while(i != last)
    {
        current = i++;
        sub_last=find(i,last,*current);
        if(sub_last!=last)
            i = sub_last;
        next_to_same = find(ReverseIterator(current),ReverseIterator(first),*current).base();
        if(next_to_same!=first)
           rotate(next_to_same,current,i);
    }
}

template<typename BidirectionalIterator>
void stable_group(BidirectionalIterator first,BidirectionalIterator last)
{
    if(first!=last)
    {
        BidirectionalIterator middle=first;
        typename iterator_traits<BidirectionalIterator>::difference_type range_size = distance(first,last);
        if(range_size>2)
        {
            advance(middle,range_size/2);
            stable_group(first,middle);
            stable_group(middle,last);
            merge_groups(first,middle,last);
        }
    }
}

// __________________________________________________________________________ //

full

#include <functional>
#include <algorithm>
#include <iostream>
#include <iterator>
#include <ostream>
#include <string>

using namespace std;

// _____________________[ recursive stable group ]___________________________ //

// stable merge of adjacent groups
template<typename BidirectionalIterator>
void merge_groups(BidirectionalIterator first,BidirectionalIterator middle,BidirectionalIterator last)
{
    typedef reverse_iterator<BidirectionalIterator> ReverseIterator;
    BidirectionalIterator i=middle,current,sub_last,next_to_same;
    while(i != last)
    {
        current = i++;
        sub_last=find(i,last,*current);
        if(sub_last!=last)
            i = sub_last;
        next_to_same = find(ReverseIterator(current),ReverseIterator(first),*current).base();
        if(next_to_same!=first)
           rotate(next_to_same,current,i);
    }
}

template<typename BidirectionalIterator>
void stable_group(BidirectionalIterator first,BidirectionalIterator last)
{
    if(first!=last)
    {
        BidirectionalIterator middle=first;
        typename iterator_traits<BidirectionalIterator>::difference_type range_size = distance(first,last);
        if(range_size>2)
        {
            advance(middle,range_size/2);
            stable_group(first,middle);
            stable_group(middle,last);
            merge_groups(first,middle,last);
        }
    }
}

// __________________________________________________________________________ //

template<typename BidirectionalIterator>
void group_gold(BidirectionalIterator first,BidirectionalIterator last)
{
    typedef typename iterator_traits<BidirectionalIterator>::value_type value_type;
    while(first!=last)
        first = stable_partition(first, last, bind1st(equal_to<value_type>(),*first));
}

template<typename Range>
void test_with_gold(const Range &s)
{
    Range p = s;
    do
    {
        next_permutation(begin(p),end(p));
        auto gold = p, recursive = p;
        group_gold(begin(gold),end(gold));
        stable_group(begin(recursive),end(recursive));
        if(gold!=recursive)
        {
            cout << "Error, gold and recursive result differs" << endl;
            cout << "Gold=" << gold << endl;
            cout << "Recursive=" << recursive << endl;
        }
    }while(p!=s);
}

int main()
{
    string tests[] =
    {
        "vvabcbbcc",
        "asdfrrafdsr",
        "abcdefgijkl",
        "010101010101",
        "totobobolol"
    };
    for(auto &&s : tests)
    {
        test_with_gold(s);
        stable_group(begin(s),end(s));
        cout << s << endl;
    }
}

А>Если реальной вакансии нет, то кто платит рекрутеру за пропускание через себя людей?
А>Т. е. откуда "физически" берутся эти деньги?
Ежегодно выделяется некоторый бюджет на HR, они должны его освоить. Если не освоят, на следующий год не дадут.

using System;
using System.Collections.Generic;

namespace GroupChars
{
    class Program
    {
        static void Main(string[] args)
        {
            var chars = "vvabbcbcc".ToCharArray();

            var orders = new Dictionary<char, int>();
            for (int i = 0; i < chars.Length; ++i)
            {
                var ch = chars[i];
                if (!orders.ContainsKey(ch))
                    orders.Add(ch, i);
            }

            Array.Sort(chars, (a, b) => orders[a] - orders[b]);

            Console.WriteLine(new string(chars));
        }
    }
}

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

>> Это кстати не O(n^2) а O(2n)
V>Оооооо, можно сразу просить название конторы, куда идти не следует, если
V>там такие спецуги работают.

Заметь, кстати, что если типичное время вычисления меряется не десятками секунд, а днями или неделями, через некоторое время все начинают применять O(5*n) совершенно естественно. Формально вроде как и неправильно, но пренебрегать константами выходит еще более неправильно. Формально правильная запись была бы, конечно, t~5*n, но никто особо не парится.

On 21.03.2013 1:16, Sharowarsheg wrote:

> Заметь, кстати, что если типичное время вычисления меряется не десятками
> секунд, а днями или неделями, через некоторое время все начинают
> применять O(5*n) совершенно естественно. Формально вроде как и
> неправильно, но пренебрегать константами выходит еще более неправильно.
> Формально правильная запись была бы, конечно, t~5*n, но никто особо не
> парится.
Я в ауте. Не, точно, сейчас, чем меньше знаний и умении и опыта, тем
лучше, главно гномиков переворачивать, как начальник попросит.

Posted via RSDN NNTP Server 2.1 beta

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

>> Если надо сделать in place , тоже не могу быстрого решения придумать.
V>Но зачем?

V>То бишь все уперлось в некорректную постановку задачи.

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

Дело в том, что заказчик большей частью никогда не дает задачи в корректной форме. Если ты работаешь кодером не включая мозг, то конечно, иди ищи того, кто будет тебе ставить задачи в максимально корректной форме.

Да и вообще, у инженера большей частью все задачи с неполным, нечетким и тд. условием.

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

Поиски максимально корректных заданий это просто форма ухода от ответственности.

P.S. Собтсвенно бизнес-приложения все до одного "иди туда не знаю куда, принеси то не знаю что".

	От:	vvlad.net
	Дата:	22.02.13 12:41
	Оценка:	-1

	От:	andrey.t
	Дата:	22.02.13 12:14
	Оценка:	1 (1) +2

От:	qxWork	http://www.jetbrains.com/company/people/Coox_Sergey.html
Дата:	23.02.13 12:37
Оценка:	8 (2) +3

От:	jazzer	Skype: enerjazzer
Дата:	22.02.13 10:33
Оценка:	+5

	От:	Аноним
	Дата:	22.02.13 05:49
	Оценка:	1 (1) +2

	От:	Alexéy Sudachén
	Дата:	18.03.13 20:26
	Оценка:	15 (1) -1

От:	a_g_99	http://www.hooli.xyz/
Дата:	22.02.13 10:36
Оценка:	+2

	От:	megapoliss
	Дата:	28.02.13 10:16
	Оценка:	2 (1)

От:	Tilir	http://tilir.livejournal.com
Дата:	22.02.13 10:17
Оценка:	+1

От:	kaa.python	РСДН профессионально мёртв и завален ватой.
Дата:	22.02.13 11:12
Оценка:	+1

От:	Gradient	http://www.x-trips.com/
Дата:	13.03.13 06:28
Оценка:

	От:	Быдлокодер
	Дата:	22.02.13 10:21
	Оценка:

От:	Kernan	https://rsdn.ru/forum/flame.politics/
Дата:	22.02.13 10:56
Оценка:

От:	MTD	https://github.com/mtrempoltsev
Дата:	22.02.13 13:39
Оценка:

	От:	Evgeny.Panasyuk
	Дата:	22.02.13 14:05
	Оценка:

	От:	Vzhyk
	Дата:	21.02.13 18:55
	Оценка:

	От:	artem.komisarenko
	Дата:	23.02.13 08:34
	Оценка:

От:	Философ	http://vk.com/id10256428
Дата:	25.02.13 12:45
Оценка:

	От:	Аноним931
	Дата:	28.02.13 09:27
	Оценка:

От:	Ikemefula	http://blogs.rsdn.org/ikemefula
Дата:	18.03.13 11:31
Оценка:

От:	alexanderfedin	http://alexander-fedin.pixels.com/
Дата:	20.03.13 18:50
Оценка: