Здравствуйте, 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. Думаю еще можно много причин найти.

On 22.02.2013 14:55, Tilir wrote:

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

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

On 22.02.2013 15:26, nile wrote:

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

On 22.02.2013 15:39, nile wrote:

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

On 22.02.2013 15:01, kaa.python wrote:

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

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

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

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

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

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

On 22.02.2013 15:41, vvlad.net wrote:

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

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

Автор: nile
Дата: 22.02.13

. Я ошибся, не
minotlogic, а nile.

Здравствуйте, 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 минут.
Я бы попроще пошел для начала. Заюзал бы разреженный массив (благо для
плюсов их реализаций море). Ну а если "он может целиком присутствовать
во входной строке", тут уже крутиться придется.

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

Автор: nile
Дата: 22.02.13

. Я ошибся, не
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.