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

Здравствуйте, 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 по этому ключу.

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

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

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

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

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

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

jazzer (Skype: enerjazzer) Ночная тема для RSDN

You will always get what you always got
  If you always do  what you always did

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

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

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

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

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

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

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

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

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

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

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

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

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

On 22.02.2013 13:43, vvlad.net wrote:

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

Posted via RSDN NNTP Server 2.1 beta

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

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

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

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

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

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

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

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

	От:	nile
	Дата:	22.02.13 10:31
	Оценка:	6 (1)

	От:	nile
	Дата:	22.02.13 10:32
	Оценка:

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

	От:	nile
	Дата:	22.02.13 10:33
	Оценка:	-1

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

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