alf
[fizzbuzz] Есть массив из трех видов элементов, R, G и B. Сделать так чтобы в начале массива были только R, потом G, потом все B.
Ээээ... Типа подобие Radix Sort вспомнить и суметь написать? ‎- seliv
А у элементов есть какие-то различия внутри типа? А то, это, посчитать и in place воссоздать. ‎- middle out-of-sight
ну, типа, в лоб: Seq("R", "B", "G", "G", "R", "B", "R", "B", "R").sortWith { case(a, b) => "RGB".indexOf(a) < "RGB".indexOf(b) } ‎- BSOD bluez
Я как Шурик. ‎- Lviv and let die
^^ like, красиво. ‎- seliv
А я ещё могу без дополнительной памяти в ровно один линейный проход, щас доеду до твёрдой земли, напишу, как. В двух словах: идти по массив сначала,, заполняя найденными B-шками его с конца, как стек, и единичными транспозициями обеспечивать, что слева от нас с сортировкой R/G всё ок и нет B. Как только дошли до верхушки стека B — готово. ‎- middle out-of-sight
^ зачот ‎- alf
^^ А я не согласен. Здесь есть скрытое использование дополнительной памяти (нужно по одному указателю на каждый тип элемента) - раз, и решение не масштабирается [тривиально] на большее количество типов элементов - два. Двухпроходный способ с подсчётом (то что я имел в виду, когда сказал radix sort) лучше. ‎- seliv
Ну без доп.памяти имеется ввиду что не маллочатся какие-то промежуточные буфера в памяти, кол-во указателей от размера исходного массива не зависит. Но то что не будет работать уже для 4 типов, это да. Но этого же и не было в условиях задачи :) ‎- BSOD bluez
сложнее и не быстрее, чем двухпроходный UPD хотя надо подумать UPD а ведь в два раза быстрей получается ‎- operazioni di FAP
^^^ Пф, да пожалуйста. Со "скрытым использованием доп. памяти" я не согласен, в этой задаче явственно O(1) цветов, а O(1) дополнительной памяти в привычной мне терминологией дополнительной памятью не считается. А так формализуйте констрейнты -- подгоним решение, под них подходящее, чо. :) Масштабироваться на более, чем три цвета, не масштабируется, но где ваша любовь к искусству? Для грустных есть radix sort, да. ‎- middle out-of-sight
Также это в целом, кажется, не очень годный физзбазз, поскольку годный не должен искушать праведного interviewee пользоваться библиотечными функциями, т.к. имеет целью проверить, хватает ли у того головы на придумать и реализовать простой алгоритм ручками. ‎- middle out-of-sight
^^ Да мы ж не критики ради, а так, разговор поддержать :-) Но стоит тогда и отметить, что один линейный проход не лучше двух, т.к. в привычной нотации О-больших константа не считается :-) ‎- seliv
(а fizzbuzz на самом деле был про разбор трехбайтной картинки на три однобайтных, гг) ‎- operazioni di FAP
всем по шоту бурбона в этом треде! ‎- госкомпиляторг
@metashuriсk: искушение было коротким ванлайнером на пост ответить, да :) ‎- BSOD bluez

2015-2016 Mokum.place