Pull to refresh

Comments 396

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

на это конечно нужно время, но зато возможно будете в тонусе неком
Постараюсь выработать такую привычку. Появилась ясность — такая встряска для мозга периодически просто необходима. Мне давненько не приходилось так много думать, как в 3 дня до подготовки + 40 минут самого собеседования.
такие задачки мне кажется фирме (которая проводит собеседование) нужны больше для оценки потенциала человека, посмотреть как он может думать и анализировать нестандартно, а в реальной работе я уверен больше столкнётесь как раз со стандартными решениями, имхо
Абсолютно согласен.

Но если контора решает стандартные задачи, то человек который слишком много мыслит не стандартно будет в команде лишним. Я видел, как таких людей увольняли, потому что их код слишком сложный, его никто не понимает, они большую часть рабочего времени изобретают велосипеды, а не решают бизнес задачи. И в таких конторах обычно задают просят рассказать о реальном опыте применения boost, Spring, Hibernate и т.д. Там очень редко просят разрезать прямоугольный пирог с прямоугольной дыркой в произвольном месте пополам одним прямолинейным разрезом.

Другое дело флагманы разработки софта. Стандартные решения им как раз не нужны. Им нужно что-то инновационное, передовое, не стандартное.
Просто также, как когда-то было с инженерами, происходит и с программистами (сисадмины выделились из «компьютерщиков» уже в прошлом веке). Первые инженеры были на все руки мастера, а сейчас есть и сантехники, от которых требуется лишь привинтить стандартный смеситель к стандартному трубопроводу, ничего при этом не разрушив, и разработчики ракетных двигателей, которым надо думать, что бы трубопровод не прогорел и не развалился от вибрации во время ресурса движка, поэтому этот трубопровод надо хитро изогнуть и снабдить охладительными каналами. Это не плохо, просто чем дальше, тем бОльшая будет специализация.
Мне кажется, я догадываюсь о ком ты :)
:) Ну не совсем.

В той конторе была зеркальная ситуация: там был неадекватный тим-лид, который сам очень любил изобретать велосипеды, писать свои CMS и страдать прочей хернёй. Разбираться в разработках людей, которые (о ужас!) поумнее него не имел никакого желания, так как считал себя самым умным.

Ниже есть представители такой конфессии. Я не разделяю их религии и в холивары не вступаю.
А не поделитесь опытом что делать с такими топ-тимами?
А то я сам инет сёрфер и постановщик для кодеров, задачи прикладные.
А топ тим бракует решения именно от нежелания в них вникать и допускать существование других умных (действительно, о ужас! :) ) людей.
С небольшим уточнением — вероятнее всего или в большинстве случаев. Но есть и исключения. Очень приятные, кстати. Особенно когда решишь.

Например, реализация web-интерфейса сравнения текстовых файлов с максимальным приближением к TortoiseDiff — две панельки, синхронный интерактивный просмотр, постраничное разбиение, навигация по изменившимся фрагментам. Очень много подводных камней. Особенно, если файлы имеют много различий вплоть до количества страниц.

Самым интересной показалась подзадача когда контролы «пред./след. различие» необходимо было синхронизировать с просматриваемыми блоками текста. Например, если мы прокрутили первое различие — активировать ссылку «предыдущее изменение». При сравнении ряда документов выявилось, что IE, очень медленно работающий с массивами, требует применения ряда оптимизаций поиска.
Для меня на одном из интервью наиболее стрессовым моментом было то, что за мной наблюдают и поправляют еще раньше, чем я соображу, где ошибка. Аж синтаксис INNER JOIN забыл..(

В отместку написал им "«как перевернуть строку?». Я подумал, и написал псевдокод на ядерной смеси C++, Pascal и PHP." так, что пришлось пояснять, как работает:)

Аналогичная ситуация. У меня на собеседовании абсолютно не соображает голова по причине пребывания в ступоре, особенно когда кто-то висит над тобой и ждет ответа.
нет. Когда-то придумывал ник для форума, в голове вертелась музычка из Insult MD. Вот и обозвался…
ясно. а я уж было подумал…
а beeruser это не от BeermanZ?:)
Начните писать свою игру, вообще без использования фреймворков.
Я специально для этого хожу на всякие acm.mipt.ru, acm.timus.ru и решаю всякие задачки, или играю в гольф там же. Иначе просто скучно все время заниматься разработкой, когда способы и типичные решения знаешь, и единственные умственные затраты лишь на чтение соответствующей документации.
UFO just landed and posted this here
мозг развивается примерно до 25-26 лет…

как вы это поняли?
UFO just landed and posted this here
Дайте ссылку на авторитетный источник.
Только, пожалуйста, не новости о британских ученых.
UFO just landed and posted this here
Американские ученые из Арканзасского медицинского центра сойдут? =)
По их мнению «в среднем так называемое „белое вещество“, отвечающее за связь между разными частями мозга, продолжает развиваться до 48-летнего возраста.»
palm.newsru.com/world/16may2001/mozg.html
Я, например, по себе вижу. Мне 24, спортивным программированием занимаюсь с 19, и четко видно, что теперь я думаю иначе — больше пытаюсь вспомнить/найти похожую задачу, чем придумать свое решение. Плохо. Но факт.
В том то и дело, что иначе, а не неэффективнее.
Заодно падает эффективность освоения принципиально новой информации, чтения научных статей и действительно творческой работы. Что однозначно плохо.
Все мы люди, все мы разные… И программисты бывают разные — одни изобретают велосипеды, а другие ими пользуются. В конце концов «стандартные решения стандартных задач» тоже кто то написал =)
добавлю:
появляются новые языки, новые фишки, и велосипеды «стандартные решения стандартных задач» нужно переписывать заново
Для работы с БД — symfony, для отправки почты — Zend Framework. Да вы, батенька, монстр…
Лол, это всё что вы поняли из статьи. Небогато… :D
Я понял то, что symfony это не ORM, symfony — фреймворк, который содержит в себе такие ORM, как Doctrine и Propel. А Zend Framework это не библиотека для отправки почты, а framework.

В связи с этим автор либо мудак, не знающий о чем речь, либо просто не дружит с головой и сам не понимает о чем пишет.
Из Zend Framework'а очень органично выдирается практически любой компонент и не менее органично втыкается в любой код/фреймворк, спасибо архитектуре ZF. Так что отправка почты через Zend_Mail — вполне себе здравая мысль. В туторе к тому же Symfony в версии 1.4, если не ошибаюсь, использовался Zend_Search_Lucene для организации поиска по сайту и PHPMailer для отправки почты. Почему нет? Или стандартные решения нужно применять исключительно целиком без изменений?
А кто с этим спорит? Я говорю о неверном употребление «об использовании Zend Framework для отправки почты», другое дело «использование компонента Zend_Mail из Zend Framework». Точно так же, абсурдно звучит речь об использовании symfony для работы с БД.
Может быть пост подкорректировали с того момента, как вы его прочитали, но я лично там увидел и прочитал Doctrine, а не Symfony :-) Так что написано вполне логично :-)
В том то и дело, что подредактировали… и мне минусов налепили.
Эмммм, Поздравляю.
(вы это хотели услышать?))
<hr /> ну нормально… а теперь без буфера хранящего позицию середины строки…
ой(
я хотела сказать «А зачемтакой буфер? „
Проще же посчитать знаки в строке и потом читать до последнего знака, его писать в новую “перевёрнутую», стирать, снова читать, и так по циклу.
Попробуйте решить эту задачу без второй строки. Тогда станет понятнее.
Записать строку в стек, и считать из стека.
Программист старый на форте есть он просто ;)
(с) Тайна речи йоды =)
А на асме разве не так?
Ох что то обратная польская нотация вспомнилась сразу :)
И времена, когда программы были большими а библиотеки маленькими…
Именно так. Я на асме так и делаю. Один хрен потратим либо дофига памяти либо тактов. Памяти обычно много, а время дорого.
Я что-то не понимаю, или эта задача решается циклом от 0 до n/2 c телом swap(a[i], a[n — i — 1])?
а можно без буфера еще и использовать свойство сложения
пусть
а=7
b=5
тогда
a=a+b
b=a-b
a=a-b
имеем
a=5+7=12
b=12-5=7
a=12-7=5
как-то так))
При сложении может произойти переполнение ;)
Есть другой вариант:
a = a ^ b;
b = a ^ b;
a = a ^ b;

(^ = xor, искл. или, мин. сумма, сумма по модулю 2, ...)
Эта штука намного медленнее работает, чем с дополнительной ячейкой вариант. Хотя интересно, да:) a^=b^=a^=b; :D
А почему намного медленнее? XOR, вроде как, довольно быстрая операция. Или я ошибаюсь?
Это всё все равно упирается в особенности компилятора.
на современных ЦП XOR-техника значительно медленнее, чем использование временной переменной для обмена. Это происходит по причине распараллеливания выполнения команд. В XOR-технике операнды всех команд зависят от результатов предыдущих команд, поэтому они должны быть выполнены в строго последовательном порядке
Никогда не пишите a^=b^=a^=b; это UB.
Вариант с хогом работает быстрее в принципе, но даже сложение сработает. После сложения. При переполнении вы потеряете единичку впереди, но при вычитании все опять станет нормально.
рапространенное заблуждение.

переполнение ничего не портит, потому что числа ограниченной разрядности по сложению образуют циклическую группу.
Портить-то не портит, а исключение сгенерировано может быть. В .NET, например, есть checked и unchecked режимы. Выполнять такой код следует в unchecked режиме, и это нужно прописать руками. В противном случае режим определяется настройками компилятора, а тут как повезёт.
только можем получить опять же переполнение
Можно два char* использовать — на индексах и их вычислениях сэкономим. :)
а зачем вторая строка?
Длина строки же известна? например n
берем и меняем местами 1 и n
потом 1+1 и n-1
и так до тех пор пока 1+k<n-k
пока писал уже написали мое решение :)
Подбор персонала наука точная, только что-то не сходится… ©

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

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

Так вот каждый раз жалуясь на то что на собеседовании от вас «хотят не того» или «задают глупые вопросы» задумайтесь, эти люди тоже на работе, и их работа по своему тоже требует навыков и знаний, спросите сначала себя «а как бы я подбирал человека на эту должность ?»

Когда вы ответите на этот простой вопрос, вы сможете ответить на главный вопрос «интервьювера» который интересует его куда важнее чем ваши навыки в решении стандартных задач, «чем вы можете быть полезны нашей фирме ?» или другими словами «почему мы должны взять именно вас ?»
Чуть выше я ответил на этот вопрос. Для работы в Microsoft в текущей форме я точно не гожусь — им нужны новаторы.
скорее им не нужны библиотечники. у них почти весь код закрыт и поговаривают на опенсурсный код им запрещают даже смотреть.
Таким образом, они наощупь находят вдохновение в оном, не забывая закрыть и запатентовать его.
Да, так и есть, в этом есть свои минусы, но цель компании тоже ясна — минимизировать риски возможных конфликтов с GPL кодом.
Хороший совет, спасибо. Где-то читал рекомендацию тем, кто проводит собеседование: вместо выяснения того, какую литературу читает программист и чем занимается в свободное время, объяснить ему в чем будет заключаться работа и спросить, сможет ли он ее делать. Дальше уже можно заняться проверкой честности и трезвости его мнения.
Меня например бесит, когда собеседующие не способны объяснить чем они вообще занимаются, и что конкретно требуется от меня.
+1

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

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

Удивительно, но майкрасофт на очном собеседовании спрашивает вопросы парой на столько простые, что это обескураживает. Стандартные структуры, сортировки, вызовы конструкторов, ряд фурье… Многие готовятся решать задачки на логику — зря. Это все на этапе телефонного интервью.
На собеседовании — университетский курс. По крайне мере так было у джунеоров.
Хз, меня в микрософте вообще ничего сложного или на смекалку не спрашивали. Ну почти ничего и это на собесе длиной в 8 часов.
Жутко знакома история про строку )
Как на экзамене на первом курсе декан дал это же задание, и я должен был написать на паскале, а я даже типов паскалевских толком не знал. Были за плечами только воспоминания о бейсике 7-10 летней давности.
Я написал какой-то бред, тоже заминался, а он мне пятерку поставил )
Наверное что-то в этой задаче в качестве тестирования есть…
как выбрать из int ar[n] = {...} n-1 элементов так, чтобы произведение выбранных было максимальным

Просто выкинуть элемент с минимальным значением?
+учесть что могут быть нули и отрицательные
а для особо крутых — учесть переполнение при умножении… :)

Одна из замечательных задачек, с помощью которых интервьюер ничего не узнает, но может показать свое превосходство.
Как раз-таки его учитывать не надо. Нам же не надо его находить
А вот это как раз тот ответ, после которого шансы пройти собеседование у меня падают вдвое.

Мне не нужны абстрактные теоретики. Мне нужны люди, решающие задачи. Если человек решает задачу «абстрактно» без учета факторов, которые приведут к неверному конечному ответу — он будет работать где-нибудь, где результат неважен. В госконторе какой-нибудь.
Просто в задаче не сказано, что нам вообще нужно само произведение. Только набор чисел.
В таком случае чем Вас не устраивает первое из предложенных решений? Оно тоже дает неправильный ответ, но набор чисел оно тоже порождает. :)
С чего вы взяли что ответ неправильный, если при произведения порождает переполнение? Во-первых, если у вас проблемы с переполнением, то есть всякие BigInteger'ы, BIgDecimal'ы, во-вторых, хороший программист может и сам написать такие классы, если надо, в-третьих, ищется набор чисел, а не произведение, и вовсе не факт, что при этом обязательно будет нужно само их произведение.
Попробуйте int32_t a[] = {INT_MAX, 2, -1}
p = INT_MAX * 2 * -1 = 2
p / INT_MAX = 0
p / 2 = 1
p / -1 = -2

Тогда, по логике, выкидывать надо 2.
INT_MAX * -1 — ну точно не правильный ответ в этом случае :)
Вы не ошиблись кому пишете?
Нет, это был ответ на
>С чего вы взяли что ответ неправильный, если при произведения порождает переполнение?
Речь не о конкретном решении, а о подходе. Читайте выше.
Стоп, а где сказано какой тип у результата? Если бы было сказано, чтобы получился максимальный результат типа int, то тогда да.
А так, не важно как их будут умножать, и что с ними будут делать.
Вы пытаетесь придумать ограничения, которых не было в задаче.

Если же всё сводить к вопросу: я тут написал вот такую хреновину, отгадайте что это на самом деле значит, то это уже собеседование скорее на менеджера.
То есть? Видимо, я неверно сформулировал свою мысль:
Правильным ответом будет выкидывание -1.
Но алгоритм, который считает p как int32_t, выкинет 2.
Это уже не надуманное ограничение, а неправильный результат.
для решения этой задачи вовсе не обязательно что-то умножать
С чего вы взяли что ответ неправильный, если при произведения порождает переполнение?

Я ответил на этот вопрос выше.

и вовсе не факт, что при этом обязательно будет нужно само их произведение

Это я также прокомментировал выше.
Черт… Про переполнение я и не подумал

Задачка интереснее чем я думал :) Буду думать еще
Переполнение фигня. Было бы желание, а умножить можно любые числа.
дело в том, что они проверяют еще и умение тестировать: найти, что есть переполнение, что есть отрицательные числа, 0…
Еще раз повторю. Есть переполнение или нет, зависит от задачи. Как то в школе еще (не помню зачем) делал умножение двух чисел в строковых переменных. То есть поразрядно. Получить там переполнение практически невозможно. А если и возможно и его можно обойти. Так что зависит от задачи.
что значит зависит от задачи? вы умножаете 2 числа и ожидаете произведение число, большее, чем множетели. В данном случае роль играет здравая логика. А если бы нужно было не учитывать переполнение, то это бы было явно указано в задаче.
Вы делаете 100% предположения, где вероятны и другие варианты. Это не есть гуд.
просто я читал у маерса, что хороший алгоритм должен покрывать максимум адекватных тесткейсов. в данном случае не учитывать переполнение — не верно.
тогда еще не плохо было бы уточнить в условии идет ли речь о максимальном произведении по модулю или в принципе ;)
Дополнительные вопросы приветствуются. Речь идёт об абсолютном значении. Без взятия модуля.
ну ну тогда общий алгорит примерно такой, как мне кажется:
смотрим есть ли у нас нули, если есть — убираем, иначе задача не имеет смысла
смотрим есть ли отрицательные значения
если отрицательное одно — выкидываем его — задача решена
если отрицательных более одного — определяем четное их число или нет, если четное — выкидываем наименьшее положительное число — задача решена
если нечетное число отрицательных — выкидываем наибольшее отрицательное (т.е. в последовательности -4,-3,-2 выкидываем -2) — задача решена

вроде ничего не упустил
подозреваю что я все дико усложняю, но математически алгоритм должен быть верным -_-
Вынесение случая с одним отрицательным в отдельный случай не имеет смысла :)

Правда, это придется делать достаточно сложно по количеству действий — при проходе по массиву надо:
1) проверить число на равенство нулю
2) проверить на отрицательность
3) найти минимум и максимум среди отрицательных
4) найти минимум среди положительных.
Это — 5*n.

А если не заботиться о переполнении, то можно за один проход найти произведение всех чисел, за второй — найти максимальное p / a[i].
я бы сделал в два прохода. Сперва все перемножил (кроме нулей, если есть хоть один ноль — задача решается тривиально, сразу заканчиваем), а потом по очереди делил бы получившееся число на все значения, запоминая те, при которых произведение больше предыдущего «рекорда». Да, это тупо, деление стоит дорого, согласен.
Зачем всё это «щупание» в виде умножения и деления, если мы и так знаем как числа ведут себя? Считаем количество отрицательных и нулей за один проход и действуем по схеме, предложенной mukizu
а зачем усложнять? В решении mukizu нет элегантности :)
Фактически это значит, что его будет сложнее реализовать, труднее поддерживать, проще совершить ошибку.
«Элегантно» это в лоб все перемножить?
«В решении mukizu нет элегантности :)»
«Да, это тупо, деление стоит дорого, согласен.»

Всегда в решении можно найти минусы. Я свое никак не позиционировал как «идеал», более того с вариантом p/a[i] тоже согласен.

решение тупое, но элегантное :)
тупое элегантным не бывает ;)

+ я не думаю что решение хорошо подойдет если массив, скажем, из миллионов чисел, а не из десятков ;)
пусть результат хранится в байтовой переменной

массив: 4, 4, 16

сумма всех элементов: 4 * 4 * 16 = 256 = #100 или 0, обрезанное до байта.

дальше делить бессмысленно.
опетачка: не сумма, а произведение
согласен, просто хотелось максимально подробно расписать, и о такой детали не задумывался. my bad :)

c p/a[i] тоже хорошо придумано, да :D
Лучший вариант, однозначно
UFO just landed and posted this here
Минимум отрицательных искать не надо.
Надо в цикле от 1 до н:
1. проверить на ноль, если ноль — запомнить позицию, если позиция уже запомнена — копировать от начала массива до н-1 в выходной массив (или куда там выбираем) и выйти из процедуры
2. Проверить на положительность числа.
2.а. Для положительного — сравниваем с минимальным положительным, если меньше — запоминаем позицию
2.б.1. Для отрицательного — добавляем 1 к счетчику отрицательных
2.б.2. Если число по модулю (-число) меньше минимального по модулю отрицательного — запомнить его позицию

3. по окончании цикла — если отрицательных нечетное число — убираем минимальное отрицательное
3. иначе, если есть ноль — убираем ноль
3. иначе убираем минимальное положительное
остальное копируем куда надо.

UFO just landed and posted this here
Потому что при втором нуле можно выбрасывать что угодно, результат не изменится. и процессор дальше мучить не нужно.
UFO just landed and posted this here
А это уже от объемов данных зависит. и от типа.
Но это уже суровая прикладнуха пошла :)
UFO just landed and posted this here
Не совсем. Отрицательные числа меньше 0. То есть если у нас есть набор из 0 и нечетного числа отрицательных чисел (положительных нет совсем), то нужно убрать любое отрицательное. Получим 0. Кажется вы этот вариант не учли.
согласен.

по-моему описанию получается что нулевое решение я не рассматриваю как верное вообще.
Выше автор отписался, что произведение должно быть максимальным по молулю.
Он написал, что модуль брать не нужно. Или я что-то не так понял?..
Наконец-то кто-то на хабре озвучил верный путь )))
а если нулей больше одного? ;) в задаче просят выбросить один элемент, при двух нулях становится пофиг что выбрасывать ;)
потому я и написал — выбрасываем «нули». Если в массиве больше одного нуля, а выбросить можно строго один элемент — задача на максимальное произведение теряет смысл.
оба неправы, ноль больше отрицательного числа. Если у нас один ноль и нечетной число отрицательных чисел, отбрасывая ноль — получим отрицательное произведение. Тут еще парочка краевых условий, которые вы упустили ;)
ниже уже написали, да.
Я просто нулевое вообще выбросил как ложное, не подумав. Т.е. у меня нулевое — неверное)
По-моему, все немного проще.
Определяем число отрицательных элементов.
Если четное — выбрасываем наименьший неотрицательный (не путать с положительным) элемент, если нечетное — наименьший.
Ошибка: в случае нечетного количества, надо выкидывать наибольший отрицательный.
Если количество отрицательных — нечётное, то выбрасывать нужно наибольшее отрицательное число. А вот по модулю оно будет наименьшим (из отрицательных).
=) Ведь крутилось же в голове. Да, наибольший из отрицательных
не увидел, написал ли кто еще:
Ноль можно выкидывать, только если оставшееся произведение не отрицательно. мложно это правило выкинуть, так как ноль ведет себя как положительное число в другои правилах.
Задача имеет смысл если есть нули.
0 > -|x| ;)
вот пока пишешь, всё уже напишут до тебя… :)
включая именно эту фразу
у меня сократилось до следующего:
если отрицательных нечетное количество, выкидываем наибольшее отрицательное
иначе выкидываем наименьшее неотрицательное
было очень наивно надеятся, что я единственный, кто об этом догадался :)
Про неотрицательное — хорошо.
Так можно сократить пару проверочек. Но ноль я бы всё-таки проверял… :)
если отрицательных нечетное количество, и нет нуля выкидываем наибольшее отрицательное
иначе выкидываем наименьшее неотрицательное
выкидываем число, для которого минимально его произведение на знак произведения списка
если один 0, то надо смотреть что лучше — выкидывать его или оставлять
абсолютное значение — это и есть по модулю ;)
А если при это произведение оставшихся окажется отрицательным?
не забываем про отрицательные числа :)
Вы на правильном пути. Дополнительные вопросы всегда приветствуются.
Подсказка: int это не то же самое, что unsigned int.
Тогда как то так…

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

Сравниваем следующим образом:

1. Получаем знак умножения всех чисел, кроме i и j. Это либо неотрицательное число, либо отрицательное.
2. Если это отрицательное число, то наибольшее произведение будет с тем числом, которое меньше, с учетом знака.
3. Если это неотрицательное число, то наибольшее произведение будет с тем числом, которое больше, с учетом знака.
4. Если текущее число дало большую сумму чем j, то в j ставим i

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

Как то так…
4. Если текущее число дало большую сумму чем j, то в j ставим i

Сумму исправить на произведение
я бы сделал так
отсортировать массив по возрастанию, а дальше: если отрицательных нечетное количество — выкинуть наименьший отрицательный, если четное — выкинуть наименьшее по модклю
хммм, я кажется, ошибся
если отрицательных нечетное количество — выкинуть наименьший отрицательный, если четное — выкинуть наименьший положительный
А если в массиве есть 0?
итак, с 3 попытки:
1)если отрицательных четное кол-во и присутствует 0 — выкидываем 0
2)если отрицательных нечетное кол-во и присутствует 0 — выкидываем что-то кроме 0
3)если отрицательных нечетное кол-во — выкидываем максимальное отрицательное
4)если отрицательных четное кол-во — выкидываем минимальное положительное
0) если нулей больше одного, то…
без разницы что выкидывать, всегда будет 0
UFO just landed and posted this here
Почти одновременно написал то же самое =)
Ну, разве что считать отрицательные, и правда, необязательно, достаточно булевой переменной.
Наличие в массиве нулей вообще ничего не меняет.
Разве что можно пока отрицательные числа считаем, если насчитали больше одного нуля — возвращаем 0 (ведь если первый элемент выкинем — произведение будет максимальным). Это немножно сэкономит процессорное время.
Если в массиве есть ноль и одно отрицательное значение, то надо оставить именно 0.
Может быть наименьший по модулю отрицательный? домножить на -100 выгоднее, чем на -1.
Я бы сказал так:
Если число отрицательных чётно, то выкидываем наименьший НЕотрицательный.
Если число отрицательный нечётно, то выкидываем наименьший ПО МОДУЛЮ отрицательный. (читай самый близкий к нулю отрицательны член)
Какая сложность вашего решения?
нифига. {-2, -5, 10 }, выкинув минимальное (-5) получим -20, а выкинув максимальное (10), получим 10.
тоже не понял подвоха, может, автор топика пояснит?
Эх, написал, не обновив комментарии…

1. Если 0 больше одного, выкидываем любой элемент.
2. Если 0 один, считаем произведение без него. Если получилось <0, то выкидываем любой элемент кроме нуля, если >0, то выкидываем 0.
3. Считаем произведение всех n чисел, допустим, оно = M
4. Проходим по массиву, вычисляем M/ar[i], это будет произведение всех чисел без i-го элемента, его и нужно оптимизировать, дальше понятно.
Первое, что пришло на ум — двухпроходный алгоритм.
Сначала проходим по массиву, подсчитывая произведение P всех n элементов.
Затем проходим еще раз, для каждого arr[i] находим частное P / arr[i].
Индекс, по которому частное будет максимальным — выбираем за лишний элемент и берем все остальные n-1.

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

А отрицательное обработается нормально.
А, про отрицательное не сообразил. Произведение ж тогда тоже отрицательным будет.
Да, с нулем обида будет ) Эх, значит все же придется цифры считать — хотя бы в плане — если есть больше одного нуля, то решение — любое подмножество {n-1}, если нуль один — то он и будет лишним. Если же нулей нет, то делаем второй проход.
много делений => процессор будет больше париться, чем с вышеизложенными алгоритмами => больше угля сожжётся из-за этого алгоритма. Ну и дольше на пяток миллисекунд будет, если массив длиной в 10-15 элементов) А вот со строкой в пару миллионов…
Не считаю себя программистом, но ради интереса накидал алгоритм:

Взлетит?

Можно обойтись без правой ветки. Просто удалить наименьшее неотрицательное число
если в массиве содержится четное количество отрицательных числе (правая ветка), то «просто удалив наименьшее неотрицательное число» в итоге получим отрицательное произведение.
Как же это у нас получится) чтобы произведение было отрицательным нужно убрать одно из отрицательных(при четном количестве). А мы удаляем меньшее НЕотрицательное число.
т.е. по-вашему для решения задачи достаточно удалить из массива наименьшее положительное число и все?
Если в массиве четное количество отрицательных. То наименьшее неотрицательное(т.к. 0 не положительное). То есть вместо правого условия(есть 0 или нет) будет просто — «Удалить наименьшее неотрицательное».
В споре родилась истина), ну или хотя бы, небольшая оптимизация
Вот приведи кто-нибудь в топике для примера какую-нибудь задачу, и ее ну обязательно кинуться решать в комментариях.

Если есть ноль, выкинуть из ряда ноль.
Если нет, то перемножить весь ряд. Если результат положительный, выкинуть наименьшее положительное, если отрицательный — наименьшее отрицательное.

Все!
*** наименьшее по модулю отрицательное конечно. То есть наибольшее отрицательное. :-)
Да пожалуй, еще момент. Если выкидываем 0, то оставшееся тоже перемножить надо. Если результат отрицательный, выкидываем любое другое число кроме нуля. Теперь точно все. :-)
Мне импонирует Ваш подход. Намного проще поддерживать и расширять код, использующий известные framework'и и стандарты, нежели что-то самописное. За Microsoft не скажу, но зачастую интервьюеры, в т.ч. и специалисты, бывают уровнем ниже, нежели соискатель. И бывает разговор вида «ты мне про Фому, а я — про Ерёму». Если человек последние несколько лет работал с какими-нибудь framework'ами (а такое случается сплошь и рядом) и, не дай Бог, в каком-нибудь нормальном редакторе или IDE, то через эти два года он позабудет низкоуровневое программирование, названия сотни функций, ищущихся в Интернете за 10 секунд или autocomplete IDE. Собеседование должно отражать реальный уровень не знаний, а умений. Хорошим вариантом является свободная реализация тестовой задачи. С любым framework'ом и/или IDE.
другая крайность, когда человек не то то библиотеками, но даже встроенными конструкциями языка пользоваться не умеет и пишет с нуля не толлько «рукосуйные протоколы» но и свой switch/case о_0
Уверен, что это не правильно, но я люблю знать на 100%, как и что у меня работает.

Из последнего. Надо было в программе работать с json-объектами (и парсить, и сохранять). Скачал чью-то монстрообразную библиотеку (несколько тысяч строк), потестировал, столкнулся с багом и удалил, а потом написал свою на 500 строк. Да, потратил сутки. Но зато я уверен в своем классе, он не содержит лишних методов, работает максимально эффективно и оптимален для моего случая… мне с ним приятно работать.

Если мне надо написать небольшое веб-приложение, то я скорее возьму свой мини-велосипед (простенький MVC-фреймворк), чей создам новый проект в symfony.
Я думаю автор имел ввиду не то, что для решения задачи нужно использовать готовое решение, а то, что прежде чем начинать изобретать велосипед нужно хорошенько ознакомиться с предметной областью. Если для решения стоящей задачи есть стандартное решение, а не множество, среди которых нет одного единственного общепризнанного, следует использовать это решение.

У меня тоже такой подход — даже если задача простейшая и я сам за короткое время могу её решить, всё равно — первым делом google. Есть стандартное решение — использую его, нет — знакомлюсь с парой-тройкой самых распространённых решений и если есть какие-то сомнения по поводу эффективности/сложности — реализую собственное решение.
Из последнего. Надо было в программе работать с json-объектами (и парсить, и сохранять). Скачал чью-то монстрообразную библиотеку (несколько тысяч строк), потестировал, столкнулся с багом и удалил, а потом написал свою на 500 строк. Да, потратил сутки. Но зато я уверен в своем классе, он не содержит лишних методов, работает максимально эффективно и оптимален для моего случая… мне с ним приятно работать.


плохо искали или обладаете избытком свободного времени и средств.

прикинем стоимость вашего решения из расчета что в месяц такой кодер будет стоить нам 1500$:
1500*1/25 = 60$ (а если бы вы решали задачу только в рабочее время, то и все 120-150$)

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

не?

UFO just landed and posted this here
нет. это мы завернули в «плохо искали» и «как минимум, вдвое меньше времени»
Мне нужна была быстрая и надежная библиотека. Программе иногда приходится обрабатывать нескольких тысяч простых json-строк в секунду, поэтому быстродействие класса, работающего с json, играет роль.

Пару часов потратил на поиск готовых решений, проверку нескольких библиотек, тестирование классов на сложных строках с «подвохом». Библиотека, устраивающая по скорости работы, провалила тесты. Другая же не устраивала своей архитектурой и тормознутостью (каждый элемент json-объекта, даже простые числа, является отдельным экземпляром класса).

Да, я мог закрыть на что-то глаза, но я решил написать решение, которое устроило бы меня на 100%. В итоге, мой класс разбирает нужные мне json-строки почти в 10 раз быстрее, чем сторонний (на котором была возможность остановиться при поиске готового решения).

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

пускать пыль в глаза не надо :)
есть ТЗ, есть требования, если задача решена в рамках ТЗ и требования то это именно то что нужно. да, такое решение может быть далеким от идеального, но рынку не нужны идеальные решения, рынку нужны решения работающие

>Мне нужна была быстрая и надежная библиотека. Программе иногда приходится
>обрабатывать нескольких тысяч простых json-строк в секунду, поэтому быстродействие
>класса, работающего с json, играет роль.
в первом сообщение об этом ограничении не было ни слова, написали бы сразу и не пришлось бы разводить полемику :) согласен, бывают ситуации когда готовые решения не подходят по определенным критериям и приходится их дорабатывать или писать свои.

Не:
1. «Просто найти» раскладывается на: найти, скачать, вкурить доку, попробовать, сравнить с другими.
2. Пункт 1 нужно повторить несколько раз для получения оптимального результата
3. Нужно учитывать контекст задачи и архитектуру найденных решений т.к. на вскидку могу предложить 2 практически противоположных случая — нужно парсить в абстрактный DOM и оттуда выдергивать нужное значение или нужно поднимать свою структуру объектов, для этого больше подходит событийный парсер без построения DOM.
4. Нужно учесть наличие готовых частей в проекте или наоборот, можно ли применить часть разрабатываемого для решения похожей проблемы в другой части системы.
5. Стоимость решения нельзя считать напрямую т.к. в случае ошибки и ликвидации/замены используемого нами стороннего решения таки придется дополнительно потратить деньги. Так же существует риск прекращения стороннего проекта.

На самом деле выбор между своим и сторонним весьма творческое занятие и простых решений тут нет. Самое главное — не впадать в крайности. И еще не экспериментировать в выпускаемом продукте.
Интересным моментом является следующее: можно отпарсить сразу весь json во внутреннее представление (так делали все классы, которые я успел посмотреть), а можно только верхний уровень, а потом уже углубляться по необходимости («углубление» происходит автоматически, незаметно для внешнего кода). Именно за счет этого мой класс работает на порядок быстрее (в конкретной программе, где крайне редко приходится обращаться ко всем вложенным элементам). При разборе очередного уровня, сложные объекты копируются «как есть» (в виде строки), а разбираются только при прямом обращении.
Тоже вариант — DOM с ленивым парсингом вложенных эленентов, однако тут тоже ведь нужно не просто так строку пропустить, а с учетом вложенности и т.п., да и весь JSON будет в памяти висеть. Мне больше нравится работать с событийными парсерами — экономия ресурсов и возможно обрабатывать огромные объемы, например сильно удобно при загрузке инфы в базу: DOM для миллиона записей построить можно, но несколько нецелесообразно, а вот по мере сборки нужной части данных сбрасывать ее в БД, освобождая память — самое то. А еще из событийного парсера генерить DOM — простая задача, а вот наоборот уже сложно.
п.1-5 в контексте «первого варианта постановки задачи» можно было не рассматривать, т.к. цель была читать/писать, отказ был продиктован наличием бага, анализ нескольких вариантов не упоминался.

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

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

З.Ы.: п.5 имеет смысл рассматривать в случаях когда конечный продукт не может включать в себя найденное решение целиком, если же у меня есть возможность встроить стороннюю либу, то как изменения которые в дальнейшем произойдут «где то там» могут повлиять на то что у меня уже есть «здесь»?
На самом деле я стараюсь придерживаться той точки зрения, что у нас всегда есть 3 варианта: использовать чье-то готовое, придумать и написать свое и (достаточно редко рассматриваемый) написать свое по всем известному алгоритму или подходу. Плюс поиск решения должен начинаться с анализа того, что у нас уже есть, а не с поиска уже готового.

На самом деле в больших проектах в полный рост стоит проблема использования сторонних наработок т.к. просчитать последствия решения очень сложно и можно не только не получить желаемый результат, а поиметь массу проблем. Предположим у нас есть проект, в котором уже давно живет стороннее решение (обозначим его А) строго определенной задачи, нам нужно реализовать доп. функции, которые есть в готовом стороннем решении (назовем его Б), но это готовое решение использует другую наработку (назовем ее В), которая полностью повторяет решение А, и пусть даже они не конфликтуют, тогда у нас получается куча вариантов:
1. Развести зоопарк — в проекте будут решения А, Б и В, тогда нам нужно строго регламентировать использование решений А и В, иначе получим проблемы. Так же нам нужно конфигурить при установке оба практически одинаковых решения, что может повлечь ошибки.
2. Если можно, то заменяем решение А на решение В с переписыванием соответствующих частей, в проекте останется решения Б и В.
3. Можно попытаться решение Б заставить работать не с В, а с решением А.
4. Можно попытаться написать аналог решения Б, но с учетом использования нами решения А, после чего выложить его в свободный доступ и еще чуть-чуть увеличить хаос.

Есть, конечно, решения, которые самому писать нецелесообразно по причине огромного объема работ, или попытаться заменить широко используемые решения. Я не думаю, что целесообразно писать что-то свое для работы (например) с ЭЦП, работы с SMTP или Jabber протоколами или парсер XLS файлов (или совсем для одержимых — свою реализацию VM), однако написать парсер JSON или логгер под конкретную задачу в строго определенном контексте — почему бы и нет.

Как я уже говорил: самое главное — не впадать в крайности.
Потом вам понадобилось добавить немного функций и проверок в вашу библиотеку, потом еще немного и она разрослась. Вы ее выложили в интернет из добрых побуждений. Кто-то скачал, посмотрел, нашел багу и пошел писать свой маленький скрипт…
Все мы так или иначе стандартизируемся. Под рабочее место как минимум.
Если очень хочется поддерживать себя в форме — придётся тратить на это дополнительное время. Перед тем как начать, стоит чётко понять: а нужно ли оно Вам?
Хороший вопрос. Я пока не могу на него ответить. С одной стороны, как инженер я посредственность. То есть я не плох, но лучшим стать мне явно не суждено. Я знаю прекрасных инженеров из того же Microsoft и мне до их уровня, как до Альфы Центавра. Поэтому повышать свой профессиональный уровень мне выгоднее в ширину — то есть изучать больше стандартных библиотек.

С другой стороны Microsoft бросил мне вызов. Который я, как бы, принял. Отступить на половине пути считаю малодушием. :)
У Вас в резюме написано, что Вы позиционируете себя не только как программист, но и как менеджер небольшого проекта. Как мне кажется, «олимпиадные» задачки на собеседовании на неруководящую позицию сработали для Вас в качестве фильтра на излишнюю амбициозность. Ну то есть Ваших способностей и навыков хватает их решать, но пресловутое «Зачем?», очень мне близкое, мешает это делать.

У меня это из-за фриланса и постоянного контакта с конечными пользователями. При виде абстрактной задачи, которая не учитывает реальных условий окружающего мира, всегда хочется воскликнуть Ваше «Зачем?». И я не понимаю, почему здесь на хабре все так восторгаются Petr с топкодера и прочими чемпионами олимпиад по программированию.

Для людей с менеджерскими задатками, но которые при этом любят программировать, единственный способ попасть в компании уровня Google, Apple или Microsoft, как по мне — это создать стартап и продать его. Плюс после этого место в корпоративной иерархии будет выше, чем куда бы можно было добраться с помощью карьеры.
Я в данный момент как раз стараюсь делать упор на принятие правильных управленческих решений. Это получается не всегда, потому что гиковская (инженерная) жилка зачастую одерживает верх.

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

Занять руководящую должность в гиганте можно. Я знаю по крайней мере одного человека, которому это удалось. (Правда, он стоял у истоков стартапа, в котором я сейчас работаю. Но продать этот стартап пока не удалось вообще никому. Потом совет директоров его уволил и он пошёл работать в Microsoft.) На эти должности тоже набирают людей для которых тоже проводят собеседования, задают вопросы. Но они кардинально отличаются от вопросов для соискателей на инженерные позиции.
О, на хабре ими еще не так восторгаются, как ими должно и подобает восторгаться! В основном потому, что как раз они умеют думать, а не ограничиваются применением стандартных шаблонов для решения стандартных задач. Кстати, где ими действительно восторгаются — так это в компаниях типа Гугла и Микрософта. Наверно, все-таки что-то в них есть, а?
Вы, Мария, кажется не правильно меня поняли. Я не утверждал, что такие инженеры не достойны восхищения. Я говорил о том, что мне административные задачи оказались ближе к сердцу, чем инженерные.

И безусловно в них что-то есть.
Да нет, как раз вас я поняла правильно, и ваш подход имеет право на жизнь. По задумке, я комментила товарища rubyman
И я не понимаю, почему здесь на хабре все так восторгаются Petr с топкодера и прочими чемпионами олимпиад по программированию.

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

Да, не сочтите за harassment, первый раз приходится участвовать в дискуссии с девушкой на технические-бизнес темы. Возможно, сейчас единственный раз в жизни я сожалею, что сам не чемпион олимпиад по программированию. =))

Вот по сути, я очень далек от спортивного программирования, но видел задачи от ACM и именно они мне кажутся «применением стандартных шаблонов для решения стандартных задач». Да, я сам могу делать CRUD web-сайт в этот момент, это еще более «стандартно» и еще больше пахнет «индусятиной». Но мне вот кажется, что то, о чем говорят на Hacker News — это более сложные задачи, плюс там очень много по-настоящему умных людей. Даже есть брать самый последний аргумент в любом споре, насколько социум принимает людей с HN (не забываем про Перельмана) — там куда не плюнь — в миллионера попадешь. =))

Кстати, а раз Вы живете на Украине и занимаетесь спортивным программированием, то может вы знаете kit?
Про Яндекс — согласна; сейчас они спонсируют ТСО и набирают людей оттуда с ограничением по рейтингу, в переводе с чисел — уровня Топ-300 алгоритмистов по миру.

Не сочту :-) Я ж не американка, для меня harassment — это скорее «с шибко умной девкой все лучше на сеновале разговаривать» :-)

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

Знаю, конечно, это он меня сюда привел. А что?
UFO just landed and posted this here
не обязательно у каждого повара должен быть свой способ варить яйцо. Используя стандартные библиотеки можно сделать что-то более высокого уровня, автор абсолютно прав, я считаю.
UFO just landed and posted this here
Я бы несколько расширил аналогию — просто повара покупают продукты в магазине. Хорошие повора покупают свежие продукты на деревенском рынке, выбирая все самое свежее. Отличные повара, бывает, выращивают продукты сами по мере сил.
UFO just landed and posted this here
Заметка была именно о том, что прекрасно описал nekt своей метафорой. Я хороший повар. До прекрасных мне очень далеко. Скорее всего, прекрасным мне не быть никогда.
отличные повара продукты никогда не выращивают, что за бред. так же как архитекторы никогда не пишут стандартного кода. более того, иногда архитекторы вообще кода не пишут, но это не мешает им оставаться высококлассными спецами.

подход автора считаю очень правильным и рефлексы по поводу необходимости изобретать велосипеды — абсолютно ненужными.

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

Иногда проще вырастить свежую зелень самому, нежели отыскать ее.

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

Если такой причины нет, лучше и дешевле взять готовое. Работа программиста ведь не в том, чтобы все написать, а чтобы в заданный бюджет реализовать максимально качественное/быстрое решение.
Почему-то все тут разделяют «стандартные решения» и «самописные». Все эти «стандартные решения» обычно open source, и если что-то в них не нравится — лучше исправить/дописать и помочь проекту (ну если он хороший, конечно, и почти устраивает, если там здравые вещи есть), а не делать свой велосипед с 0, писать в десятый раз никому не нужный код, напарываясь на разные грабли и обитая исключительно в своем личном болотце. В эпоху гитхабов, битбакетов и ланчпадов это все довольно просто, коммуникации упрощены до предела.
Особенно люто я ненавидел выпускников мехмата и бывших олимпиадников.

True, true…

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

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

Но а в плане «большинства случаев», конечно, не спорю, не всем же в Microsoft работать )
Скорее надо рассматривать и изучать как эти песчинки складываются в кирпичики :).
Есть еще одна интересная задача на «подумать».
Дан массив длинны от N. Можно найти в нем минимум и максимум простым способом:
<code>for(i = 0; i < n; ++i)
{
    if(a[i] > a[max]) max = i;
    if(a[i] < a[min]) min = i;
}</code>

Несложно посчитать, что программа будет производить 2*n сравнений.
Можно ли решить задачу за меньшее число сравнений?
если сделать два прохода «методом пузырька», то можно сэкономить пару проверок, посуольку во втором проходе мы имеем дело с массивом короче на один элемент :)
сперва делаем первый проход: сравниваем в цикле a[i] и a[i+1] и если первый больше — меняем их местами. Это n-1 проверок. Максимальное значение теперь a[n-1]. Потом цикл от n-1 до 0, делая то же самое, это даст n-2 проверок (цикл теперь короче), теперь минимальное значение в a[0]. Итого — 2n-3 проверок.
Интересное решение, согласен с ним.
А можно ли еще быстрее? :)
хм. Интересный вопрос :)
Не уверен, что это правильный способ, но может быть сработает что-то типа:

Допустим, массив состоит из трех частей:

(a[0], a[1..m], a[m+1...n-1]) при этом все числа a[m+1...n-1] меньше a[0]. Скажем, мы проверили, что a[0]>a[n-1], a[0]>a[n-2]… и т.д., пока не нашли m такое, что a[m]>a[0]. В элементах a[m+1...n-1] максимума заведомо нет, в a[0] заведомо нет минимума. Временно отбросим все члены от m+1 до n-1.

Снова разделим массив на три части:

(a[0...m1], a[m1+1...m-1], a[m]), теперь все элементы a[0...m1]<a[m] и в них заведомо нет максимума, тут разветвим алгоритм, будем искать теперь минимум в a[0...m1], а максимум в a[m1+1...m].

Как-то так. Сейчас я не очень хорошо соображаю, так что может тут и косяк какой в логике, да и с числом сравнений не понятно.

Кроме того, пора домой уже, кажется :)
Интересное решение! Увы, сегодня все еще не получается понять его :) Попробую сделать это завтра еще раз.
суть в том, что мы последовательно укорачиваем массив с двух сторон, чтобы локализовать максимум или минимум. Не уверен, правда, что это решение будет давать меньшее число сравнений, чем 2n-3
Зачем менять местами? Абсолютно лишняя операция. Достаточно знать индекс максимума. Решение тоже самое что и это, только без присваиваний и лишнего второго цикла.
Можно запомнить индекс и после первого цикла поменять этот элемент с последним, и следующий цикл сделать до предпоследнего. Но это все равно менее эффективно, чем изначальный вар с else.
Вы забываете, что каждый обмен местами — это 3 операции присваивания ( tmp = a[i]; a[i] = a[i+1]; a[i+1] = tmp; ) вместо одного (max = i). Кроме того, мы получаем еще один цикл for, короче на 1, и пропускаем одну проверку.
Не буду считать операции, но изначальный вариант + else выглядит самым быстрым.
в условиях задачи речь шла именно о минимальном числе проверок. Да и в реальной жизни может встретиться ситуация, когда каждая проверка стоит очень дорого, по сравнению с другими операциями.
Да, тут границы не ясны. Я решал, считая все операции равноценными. Так можно сразу несколько задач сделать: если сравнение элементов во много раз затратней всех остальных операций; если они равноценны; если переприсвоение намного затратней…
Тогда есть еще одно решение. В первом проходе запомнить индекс максимального. Во втором перед сравнением проверять по индексу, не максимальный ли мы сравниваем.
Навскидку, если число больше какого-то другого, оно не может быть минимумом, поэтому:

for(i = 0; i < n; ++i)
{
    if(a[i] > a[max]) max = i;
    else
    if(a[i] < a[min]) min = i;
}
не будет работать, если массив отсортирован по возрастанию
Почему?
Конечно, min и max сначала надо забить нулями, так как в противном случае программа будет падать при доступе к непонятному a[min] на первой итерации :)
да, тогда будет работать и в этом случае.
А если массив весь меньше нуля?
Первое значение надо присваивать в min и max
Прочитайте еще раз программу :)
в min и max хранятся индексы, а не значения.
Точно :)
Ну тогда массив может от -100 до -1 номера иметь :)
Да, получается немного быстрее — 2 * n — 1 в худшем и n в лучшем случае.

А можно сделать еще быстрее?
это не быстрее. условный переход быстрее переприсваиваний.
сдается мне, что нет, но задам уточняющие вопросы: «за меньшее число сравнений» означает ли «за меньшее число операций», или сравнение можно заменить на сложение/вычитания/побитовые операции, главное, чтобы знаков <> не было?
Других операций нет — в a у нас абстрактные элементы, для которых определены только < и >.
Хотя, о такой задаче для чисел с использованием других свойств я не думал.

Решение есть, и время его работы не выражается в виде 2 * n — C.
Неверно, в худшем 2*(N-1) в лучшем N-1, т.к. идти надо с 1.
Да, Вы правы. И тут, и в моей первой программе, можно идти с 1 и сократить количество операций. Но это — не окончательная оптимизация.
найти максимум а потом исключить его из поиска минимума= -1 проверка.
можно еще сделать двойную проверку, т.е. если одно условие не сработает, то вызвать другое…
кроме того, что медленнее, так n * log n — это еще и оценка количества обменов, а не сравнений, сравнений там значительно больше
идём с друх концов. делаем n/2+1 сравнение, после чего большие части ззаписываем в начало массива, меньшие в конец.
После чего в первой половине массива будет максимальный.
Это n/2+1 сравнение.
И то же самое в нижней.
n/2+1

итого 3n/2+3 сравнения. Возможно даже на пару меньше, но это нужно рассматривать случаи чётной и нечётной длинны, что неинтересно.

btw, а проверку i<n в цикле мы почему не считаем за проверку?
Поздравляю, это правильное решение, правда немного извращенное, от чего и появились «лишние» +3.

Основная идея верна — мы должны сравнить два элемента, и больший из них сравнивать с максимумом, а меньший — с минимумом. Тогда коэффициент при N получится 3/2 — на каждые два элемента мы тратим три сравнения.
Мое решение делало эту же идею, только «в лоб»:
min = max = 0;
for(i = 1; i < n; i += 2)
{
    if(a[i] < a[i + 1])
    {
        if(a[i] < a[min]) min = i;
        if(a[i + 1] > a[max]) max = i + 1;
    }
    else
    {
        if(a[i + 1] < a[min]) min = i + 1;
        if(a[i] > a[max]) max = i;
    }
}


i<n я не учитывал из практических соображений — сравнение интов происходит быстро, в то время как сравнение произвольных объектов может происходить очень долго. Но если i учитывать, то Ваше решение делает 3n/2 сравнений с i, а мое — n/2 :)
Да, +3 явно многовато.
тут так:
1) если n — чётное, то тогда будет ровно 3n/2
2) если n — нечётное, то делаем (n-1)/2 сравнений, когда идём с двух концов.
А потом нам нужно пройти с каждой стороны (n-1)/2 + 1, поскольку центральный может оказаться как максимальным так и минимальным.
получается в сумме (n-1)/2+n+1, ну или используя целочисленное деление 3n/2+1

А у Вас, если, например, n=2, то будет обращение по номеру a[1+1]=a[2], что уже за пределом массива.

это решение тоже дает 1.5*n проверок. Улучшить невозможно. Хотя и полтора уже отлично.
Ночью до того же решения, что и steck, додумался, но уже написали. Спасибо вам за задачу!
омг, что за бред?

max = a[0];
maxI = 0;
min = a[0];
minI = 0;

for(i = 0; i < n; ++i)
{
if(a[i] > max) max = a[i], maxI = i;
if(a[i] < min) min = a[i], minI = i;
}
3N сравнений, включая проверку условия цикла
блин, я категорически неверно прочитал условие! Прошу прощения
Чем описанное здесь отличается от приведенного мной, кроме лишней операции копирования неизвестного объекта?
ничем — я совсем неправильно прочитал условие. А вот ниже — таки отличается
Можно развить решение borisko:

if(a[i+2] > a[i])
{
if(a[i+1] > a[i])
{
if(a[i+1] > a[max]) max = i+1;
if(a[i] < a[min]) min = i;
}
else
{
if(a[i+2] > a[max]) max = i+2;
}
}
else
{
if(a[i+1] > a[i])
{
if(a[i+1] > a[max]) max = i+1;
}
else
{
if(a[i+2] < a[min]) min = i+2;
if(a[i+1] < a[min]) min = i+1;
}
}

не хуже чем 4/3n — на каждые 3 элемента не более 4х сравнений.
мда, не следует ввязываться в споры об алгоритмах, читая хабр перед уходом с работы в 10 вечера. Я тут пропустил пару важных строчек, на самом деле у меня будет 5/3 N.
И я в маршрутке немного прикинул, какие есть варианты комбинировать операции — ничего лучше 3/2 N не выходит.
Собственно, за первые N/2 операций мы разделяем числа на множества бОльших и меньших, каждое размером N/2, а потом в одном ищем только минимум, во втором только максимум, за N/2 операций в каждой части. Итого 3/2 N, и никуда от этого не деться…
www.coranac.com/documents/bittrick/
Пункт 2.4 Branchless min/max

Т.е. можно сделать за 0 сравнений. Это трюк в чистом виде, программировать так надо очень-очень редко, но для общего развития знать надо.
Ой, жесть :)

Но это пройдет для чисел, но не пройдет для непонятных объектов.
С практической точки зрения такая задача вреданая. Чем меньше зависимостей в коде, тем быстрее суперскаляр выполняет код. Так что все предложенные ниже решения, скорее всего, будут выполняться дольше и потреблять больше электроэнергии.
Зато если вместо интов у нас массив строк, то это выполняится быстрее.
Выполняется/выполнится*
Я для себя эту проблему решаю так: стараюсь разбираться, как работают библиотеки, которые я использую. Конечно, хитрым математическим алгоритмам это не научит, но и думать не разучусь, и свое при условии специфичных требований смогу написать.
На самом деле вы всё делаете правильно. Ну кроме того что забыли алгоритмы — забывать их не нужно и вредно.
Но самописные решения на коленке в 80 процентах случаев будут хуже открытых «стандартных» аналогов и технологий, в которых кто-то поленился разбиратся, и решил написать вместо них велосипед.
Не так давно в нете были статьи по поводу «никто из программистов не хочет разбиратся в нашем програмном решении — все сволочи предлагают переписать с нуля! как быть?»
Эта проблема особо актуальна для самописных решений. В мире есть сотни тысяч разработчиков, знакомых с «стандартными» откртыми и не очень решениями и технологиями, которые могут в считанные дни влится в проект, на таких решениях построеный. Никто не переозобретает джаву, XML, SOAP, WSDL, поэтому никто не переизобретает DOM, SAX, JAX-WS и т.п.
Особенно это касается вещей вроде дотнета и джавы — богатых платформ, для которых существуют сотни распространённых решений, одних только открытых от разкиданих по сорсфоржу библиотек и Jakarta Commons до технологий от Spring и т.п. Решения с открытым кодом часто отточены, оттестированы и «вылизаны» до такой степени, что на написание и тестирование самописного аналога уйдут если не годы то месяцы точно.

Другое дело, что иногда стоит полезть и самому в код используемого решения (а иногда это даже приходится делать, потому что что-то работает не так как надо, или не работает вообще, а «спрыгивать» на другие решения уже поздно). Это очень полезно. Научится програмировать можно только читая код — я так считаю.
Обожаю копаться в исходниках библиотек.
Алгоритмы (наверное, большую часть из того, чему меня научили на курсе дискретной математики, которую я сдал с четвёртого раза) я не забыл. Я всё ещё помню что такое бинарная и пирамидальная сортировка, бинарное и красно-чёрное дерево. Но я утратил навык изобретать новые алгоритмы на вскидку.

В остальном, подписываюсь под каждым словом. По иронии судьбы, сейчас я работаю над проектом, состоящем сплошь из велосипедов. Проект реализован на Java. :) Правда, заложен проект был 10 лет назад. Наверное, тогда Java не была на столько богата библиотеками.
> Правда, заложен проект был 10 лет назад.
> Наверное, тогда Java не была на столько богата библиотеками.
Предпочитаю слово «решение», т.к. вещи вроде Томкета, Глассфиша или OSGI-контейнеров наприме это уже не библиотеки, но в остальном согласен абсолютно — 10 лет назад Джава как палтформа не была настолько богатой как теперь (тем более дотнет). Например первая версия Spring IoC датируется 2002-м годом согласно Википедии.
Вот вы все время говорите о какой-то бинарной сортировке. Никогда не слышал про такую. Проясните?
не читал каменты, так на всякий случай.

про массив из a[n], было ли ограничение на тип данных в котором будет результат произведения хранится? можно ли было определить свой тип данных? тип int подразумевает то что хранятся отрицательные числа тоже или же это просто огрех при составлении задачки? присутствует ли число ноль, как элемент массива? скольки разрядный int?
возможное решение — определить свой тип данных uint64, в случае если хранятся отрицательные числа, выбрать четное количество наименьших отрицательных чисел и все положительные(обратить внимание на не включение нуля), если же все положительные — выбрать наименьшее и отбросить его.

вы молодец что старались, от себя могу пожелать решать интересные задачи — что будет очень полезно :) в интернете их полно к примеру классическая задача, которую дают в SPB Software :) ну и в конце-концов воспитывая в себе свободу мышления, возможно будет с временем формировать большое количество решений.

к тому же — так как вы изучаете много технологий, смотрите в их суть, и тогда будет все очень предельно понятно с остальными задачами.
успехов :)
За советы и пожелания спасибо.
Но комменты всё же лучше прочитать. Там есть ответы на все ваши вопросы.
по минусам уже понял :) времени было жалко, да и зачем-то решил как-то поразмышлять вслух, для кого — сам не понимаю :)

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

ну а просто развивать не стандартное мышление можно чем-нибудь типа: braingames.ru
в конце-концов типов головоломок тоже конечное множество, и их тоже можно научиться решать :)

не останавливайтесь на достигнутом, не успешный опыт- один из самых ценных опытов :)
Уберите слово «программист». Этот пост на 99% касается и системного администрирования. Чем меньше в созданной системе «полёта фантазии», тем эта система лучше.

Думаю, то же может сказать и инженер про конструкцию моста (там, правда, легче, потому что всякая херня быстрее падает и её не восстанавливают каждую неделю с матюгами).
Я как админ тоже самое подмечаю за собой.
Я считаю что это не плохо, это просто другой уровень.
Когда работаешь с десятками различных систем различного назначения, унификация — единственный способ сохранить остатки разума (а раз в админы пошел, значит его и так немного ;)).
А я что-то сначала не очень внимательно прочитал, и решил, что задача формулируется так:

Имеется массив arr[N], и нужно выбрать M < N элементов так, чтобы их произведение было максимальным :). При этом необязательно, чтобы M = N — 1


Вот это действительно достаточно сложная и интересная задачка :).

Идея решения очень простая, и для простоты рассмотрим случай с положительными элементами:

1. Выбираем M элементов, да так, чтобы их значения были больше всех остальных оставшихся (N — M) элементов
2. Печатаем ответ :))

Собственно, как это реализовать — довольно просто, надо отсортировать массив (по убыванию) и выбрать первые M элементов. Сложность сортировки Qsort — N*log(N), что, в общем-то, прекрасно :). При этом, сортировку уже можно закончить, когда получены первые M отсортированных элементов. В зависимости от соотношений между M и N, будет быстрее либо Qsort (N*log(N)), либо обычный метод, не помню как называется, вроде бы вставки :), дающий M^2 с учетом того, что нам не нужно получить весь массив, а только первые M членов.

Если же массив содержит нули или отрицательные элементы, то тут возможны варианты:

1. Количество нулей больше (N-M) — тогда можем сразу писать, что ответом является первая попавшаяся выборка
2. Иначе: опять же возможны варианты:
2.1. Отрицательных элементов четное число — переходим к пункту 3 :)
2.2. Отрицательных элементов нечетное число — находим наименьшее по модулю отрицательное число (т.е. наиболее близкое к нулю) и заменяем его на ноль. Заново проверяем условие в пункте 1.
3. Сортируем массив по убыванию, используя сравнение по модулю (сами знаки у чисел должны остаться, они нам пригодятся).
4. Считаем количество отрицательных чисел в первых M элементах массиве — четное число или нет
4.1. Если четное, то печатаем эти элементы как ответ
4.2. Если нечетное, то ищем замену самому маленькому по модулю элементу в массиве из первых M чисел — если последний элемент был отрицательным, то ищем самое большое положительное число среди оставшихся элементов, если же последний элемент был положительным, то ищем самое большое по модулю отрицательное число среди оставшихся. Таким образом, опять получаем четное число отрицательных элементов в ответе.

Возможно, в пункте 4.2 будет найдена не самая лучшая последовательность (в смысле максимизации произведения) из-за того, что я мог не учесть ещё какие-то варианты :). Но, в целом, алгоритм должен быть такой. И реализовать его тоже не очень сложно :).
Маленькая поправка — пункт 2.2 делать не надо! А то можно получить неправильный ответ. А в пункте 4.2. не учитывается, что среди оставшихся элементов может не оказаться нужных (положительных или отрицательных, в зависимости от того, что ищется). В этом случае надо немного подумать и тоже решить, что делать :)). Всегда можно воспользоваться методом полного перебора, если только вы абсолютно точно уверены, что такие ситуации будут возникать редко.
Навскидку — такие задачи обычно решаются способом динамического программирования. То есть решается сначала для n первых элементов массива в нашем случае, потом для n+1 и так далее. Эдакая рекурсия наоборот. Сложность будет для вышеприведенной задачи O(n^2). Хуже чем в простейшем алгоритме, описанном выше (с помощью сортировки), но встречаются задачки, которые решаются с хорошей асимптотикой этим методом. Например, определение соответствия шаблону, заданному с использованием wildcard'ов.
Может Вас не взяли потому что Майкрософту понадобились программисты которые создают эти стандартные решения, стандартные библиотеки.
Конкретной причины мне не озвучили. Но я подозреваю, что вы совершенно правы.
Тяжела и неказиста жизнь простого программиста (с)
После прочтения сего, у меня сложилось впечатление, что программирование — не ваша стезя. Может, я ошибаюсь, конечно. Просто хотелось бы чтобы у вас всё сложилось. :)
Поднятая вами тема стандартизации, безусловно, интересна. Я считаю, что в данном случае программистов стоит разделить на 2 типа — стандартные и нестандартные. И для каждого давать задачу, соответствующую его типу.
Да. Я тоже думаю, что это не совсем то, чем бы я хотел заниматься до старости.

При таком делении, я думаю, расклад будет 99 стандартных / 1 нестандартному. И этот один процент и ищут флагманы разработки софта.
да чо за проблемы — переформатирование своего мозга занимает 2-3 дня, а интервью, они такие — к ним нужно готовиться
Напишите книгу «переформатирование мозга для работы на Microsoft за 2 дня», и мы все ее обязательно прочтем )
Программированием занимался давно, но соглашусь с citius. Это разные уровни.
Есть железо — один уровень.
Ассемблер и компиляторы — другой.
Написания языка верхнего уровня и его компонентов — еще выше.
Написание модулей и фреймворков — следующий.
Создание приложений — последний.

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

А так, помню как после изучения ассемблера на втором курсе, считали что ООП отстой и все надо писать на асме. :) Ибо работает молниеносно, весит микроскопически, ресурсов почти не ест. Затем, разумеется, подход поменялся. Хотя, ностальгия осталась. Конечно трудно представить, чтобы такую вещь как Windows 7 написать на asm, но если такое случилось бы, думаю, она бы уместилась на дискету и работала б на 386-м :)
UFO just landed and posted this here
Напишите резюме в Microsoft или Google. Практический опыт коммерческой разработки софта их интересует в последнюю очередь. Удачи.
вы так это говорите, будто сами устанавливали правила найма в Microsoft и Google. круто!
Олимпиадные задчи имхо бесполезны. Они не научат, как писать читаемый, быстрый, легко поддерживаемый, разбитый на слабосвязанные модули код с аккуратной архитектурой. А переписывать руками алгоритм сортировки никому не надо.
Именно из-за таких мнений мы должны покупать новый компьютер раз в два года, чтобы наши любимые программы перестали тормозить.
Да не, не из-за этого. это из-за индусов, которые лепят не задумываясь абы как. Но все же, олимпиадные задачи — своя ниша, весьма делакая от реальных приложений.