Как стать автором
Обновить

Комментарии 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 и решаю всякие задачки, или играю в гольф там же. Иначе просто скучно все время заниматься разработкой, когда способы и типичные решения знаешь, и единственные умственные затраты лишь на чтение соответствующей документации.
НЛО прилетело и опубликовало эту надпись здесь
мозг развивается примерно до 25-26 лет…

как вы это поняли?
НЛО прилетело и опубликовало эту надпись здесь
Дайте ссылку на авторитетный источник.
Только, пожалуйста, не новости о британских ученых.
НЛО прилетело и опубликовало эту надпись здесь
Американские ученые из Арканзасского медицинского центра сойдут? =)
По их мнению «в среднем так называемое „белое вещество“, отвечающее за связь между разными частями мозга, продолжает развиваться до 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 /> ну нормально… а теперь без буфера хранящего позицию середины строки…
ой(
я хотела сказать «А зачемтакой буфер? „
Проще же посчитать знаки в строке и потом читать до последнего знака, его писать в новую “перевёрнутую», стирать, снова читать, и так по циклу.
Попробуйте решить эту задачу без второй строки. Тогда станет понятнее.
Записать строку в стек, и считать из стека.
Нда-а, ребят.
forth programmer detected :)
Хабр торт.
Программист старый на форте есть он просто ;)
(с) Тайна речи йоды =)
А на асме разве не так?
Ох что то обратная польская нотация вспомнилась сразу :)
И времена, когда программы были большими а библиотеки маленькими…
Именно так. Я на асме так и делаю. Один хрен потратим либо дофига памяти либо тактов. Памяти обычно много, а время дорого.
Я что-то не понимаю, или эта задача решается циклом от 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
Лучший вариант, однозначно
НЛО прилетело и опубликовало эту надпись здесь
Минимум отрицательных искать не надо.
Надо в цикле от 1 до н:
1. проверить на ноль, если ноль — запомнить позицию, если позиция уже запомнена — копировать от начала массива до н-1 в выходной массив (или куда там выбираем) и выйти из процедуры
2. Проверить на положительность числа.
2.а. Для положительного — сравниваем с минимальным положительным, если меньше — запоминаем позицию
2.б.1. Для отрицательного — добавляем 1 к счетчику отрицательных
2.б.2. Если число по модулю (-число) меньше минимального по модулю отрицательного — запомнить его позицию

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

НЛО прилетело и опубликовало эту надпись здесь
Потому что при втором нуле можно выбрасывать что угодно, результат не изменится. и процессор дальше мучить не нужно.
НЛО прилетело и опубликовало эту надпись здесь
А это уже от объемов данных зависит. и от типа.
Но это уже суровая прикладнуха пошла :)
НЛО прилетело и опубликовало эту надпись здесь
Не совсем. Отрицательные числа меньше 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
НЛО прилетело и опубликовало эту надпись здесь
Почти одновременно написал то же самое =)
Ну, разве что считать отрицательные, и правда, необязательно, достаточно булевой переменной.
Наличие в массиве нулей вообще ничего не меняет.
Разве что можно пока отрицательные числа считаем, если насчитали больше одного нуля — возвращаем 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$, при этом поиск решения в гугле занял бы, как минимум, вдвое меньше времени, в будущем его будет проще поддерживать, а за оставшееся время вы могли бы реализовать часть другой задачи. в итоге результат вашего труда для меня был бы вдвое-втрое дешевле за счет роста количества решенных задач на единицу выплаченных денег.

не?

НЛО прилетело и опубликовало эту надпись здесь
нет. это мы завернули в «плохо искали» и «как минимум, вдвое меньше времени»
Мне нужна была быстрая и надежная библиотека. Программе иногда приходится обрабатывать нескольких тысяч простых 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 — это скорее «с шибко умной девкой все лучше на сеновале разговаривать» :-)

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

Знаю, конечно, это он меня сюда привел. А что?
НЛО прилетело и опубликовало эту надпись здесь
не обязательно у каждого повара должен быть свой способ варить яйцо. Используя стандартные библиотеки можно сделать что-то более высокого уровня, автор абсолютно прав, я считаю.
НЛО прилетело и опубликовало эту надпись здесь
Я бы несколько расширил аналогию — просто повара покупают продукты в магазине. Хорошие повора покупают свежие продукты на деревенском рынке, выбирая все самое свежее. Отличные повара, бывает, выращивают продукты сами по мере сил.
НЛО прилетело и опубликовало эту надпись здесь
Заметка была именно о том, что прекрасно описал 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 воткнуть
Зачем менять местами? Абсолютно лишняя операция. Достаточно знать индекс максимума. Решение тоже самое что и это, только без присваиваний и лишнего второго цикла.
Можно запомнить индекс и после первого цикла поменять этот элемент с последним, и следующий цикл сделать до предпоследнего. Но это все равно менее эффективно, чем изначальный вар с 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 проверка.
можно еще сделать двойную проверку, т.е. если одно условие не сработает, то вызвать другое…
блин, опоздал…
Вот так вот и вербуют в К.
qsort()
n * log n
Это медленнее, чем 2N.
кроме того, что медленнее, так 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-м :)
НЛО прилетело и опубликовало эту надпись здесь
Напишите резюме в Microsoft или Google. Практический опыт коммерческой разработки софта их интересует в последнюю очередь. Удачи.
вы так это говорите, будто сами устанавливали правила найма в Microsoft и Google. круто!
Олимпиадные задчи имхо бесполезны. Они не научат, как писать читаемый, быстрый, легко поддерживаемый, разбитый на слабосвязанные модули код с аккуратной архитектурой. А переписывать руками алгоритм сортировки никому не надо.
Именно из-за таких мнений мы должны покупать новый компьютер раз в два года, чтобы наши любимые программы перестали тормозить.
Да не, не из-за этого. это из-за индусов, которые лепят не задумываясь абы как. Но все же, олимпиадные задачи — своя ниша, весьма делакая от реальных приложений.
Нужно четко разделать понятия «кодер» и «программист».
Кодер — он как раз и решает стандартные задачи,
а вот программист должен думать, он должен расти на таких книжках как Дональда Кнута и т.п.
НЛО прилетело и опубликовало эту надпись здесь
Меня попросили на последнем перевернуть все слова в строке. Оказалось довольно просто.
Работа программиста — это работа мысли, а мозг надо тренировать в любом случае. Иначе через 5-10 лет произойдет обновление технологии или моды, а думалка уже скукожилась.

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

Стандартные решения это хорошо во всех смыслах. Но надо уметь выбирать их. Изучать их и понимать что за ними стоит. Для новой задачи необходимо сначала мысленно сделать свой велосипед, но при наличии стандартных запчастей, собрать его и допилить напильником.
хех да парень не программист а сисадмин :) Любитель по компелить :)
НЛО прилетело и опубликовало эту надпись здесь
Сейчас программистом себя называют каждый кому ни лень… даже тот, кто только научился «винду» переставлять…
НЛО прилетело и опубликовало эту надпись здесь
разработчик — это специалист уже более широкого плана, чем программист, я так думаю
НЛО прилетело и опубликовало эту надпись здесь
силой мысли переставляет винду
силой воли настраивает линукс
Я бы взял на работу именно такого на Вы.
Я в принципе провожу много интервью и то, что я спрашиваю
1. Знание стандартных структур данных
2. Знание стандартных путей решения проблем

Все эти умники, которые знают супер пупер алгоритмы, но не знают про Hibernate мне не нужны.

Почему в микрософте задают вопросы на смекалку на интервью, я не знаю
НЛО прилетело и опубликовало эту надпись здесь
Я тоже когда-то так думал. что «заботать» Hibernate займет день-два :) Затем я убил на проект 6 месяцев и понял где я ошибался :) Сейчас я такие проекты недели за три поднимаю, с полпинка, левой рукой :) И я знаю, что человек без опыта работы с ORM системами потратит столько же времени, пусть он хоть в топе олимпиады по программированию. А еще я когда-то хвастался в фидошной эхе, что любую технологию за 2 недели осилю :)))

А на самом деле всё гораздо проще, каждого человека нужно подбирать под конкретные задачи.
может быть, у Microsoft и у вашей компании разные ниши?
отличный тест на смекалку:

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

a) бандитом
b) святым
c) тучей
не уловил связи с постом

p.s. ответ b, мне кажется… :)

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

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

Какой прогресс практически за год, неужто Шварценеггер?
шутку понял, смешно))

Вы знаете, у меня сложилось впечатление, что вас взяли не из-за того что вы долго или не оптимально решали задачи, а из-за того что вы за 4 года сменили 5 мест работы. Я считаю оптимальным для программиста менять место работы каждые два года. И если я вижу на собеседовании кандидата, который часто менял работу ( 2 -7 месяцев) то это меня настораживает. Тут либо человек неусидчивый, конфликтный, не командный или ещё чего.
Не думаю, что дело в этом. Они изучали моё резюме около недели перед тем, как устроить интервью.

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

Так было предыдущих 4 раза.
Вот! В этом то и ошибка, ни в коем случае не рассказывайте об этом на собеседовании. Компаниям нужны люди лояльные, которые примут ценности компании и будут следовать курсу компании. Они вас нанимают не для того чтобы вы самоутверждались или реализовывали свои цели. Они вас нанимают чтобы вы решали «их проблемы», до ваших проблем, мечтаний и целей им до лампочки. Если вы видите для себя перспективу в какой-то компании, то вам следует делать всё, для того чтобы ваше начальство думало, что ваш путь развития параллелен пути развития компании. Ну а дальше, берите то что вам нужно и уходите.
Очень любопытно было бы узнать что это за цель? =)
Научиться превращать программы в деньги.
Хорошая цель.
Не согласен.
Честность — это здорово.

А вот цель для вас как программиста…
это цель вряд ли будет плюсом при устройстве ;) а так хорошая цель :) в чем-то мы похожи :)
Тю, так это просто :)

1. Немножко фантазии и кругозора
2. Понимание где крутятся деньги (узнается из любых блогов программистов, которые хвастаются как гребут бабло :) )
3. Куча терпения
4. Немного наглости и понимания где водятся клиенты
5. ???
6. PROFIT!
Почитал резюме, год админства, полтора года работа программером в одной конторе, потом полгода фриланса, потом полгода ещё в одной конторе, потом 4 месяца ещё в одной конторе, и год в последней конторе. Я бы на собеседовании серьезно подошел к изучению вопроса «Почему меняете работу?» и «Почему ушли из компании ХХХ?»

Если ещё пойдете собеседоваться, то обязательно продумайте ответы на эти вопросы, попробуйте поставить себя на место интервьюеров и руководителей которые вас нанимают. Удачи!
И что такого, что меняет? Неинтересно же на одном месте сидеть ерундой заниматься, а в Яндекс сразу так не возьмут, а если и возьмут, у них тоже наверняка быдлокода достаточно. Вот и ищет человек где лучше. Я сам так же делаю и буду делать.

Хотя, конечно на собеседовании я всегда гогтов придумать пару причин, почему я хочу работать именно там до конца жизни. Так принято, что поделаешь.
вот и представь себе, ты руководитель бизнеса и нанимаешь себе в разработчика, это будет твой актив, и актив рисковый. И ты будешь десять раз думать, оправдает ли данный человек твои риски, потому как если ты вводишь человека в проект, то до момента когда человек будет полностью лоялен и от него будет 100% отдача — это от 3 месяцев до полугода. И ты будешь брать себе программера которому будешь платить деньги, будешь тратить время его коллег, тимлидов, пм-ов на то чтобы человек вошел в курс дела, изучил рабочую среду, изучил всю кухню отдела разработки, научился с ней работать, а потом сразу свалил? Не думаю.
Поставьте себя на место руководителя и вам станет понятно, почему не хотят брать «зайцев», которые прыгают из одной конторы в другую.
Кстати, в теории орг. поведения есть такой временной ограничитель — время которое один человек работает на одной должности в одной конторе, после которого человек начинает деградировать (как специалист), так вот в нашей с вами любимой IT сфере, в частности в программировании, я считаю что такой срок — 2 года. Дальше, либо растем в ширь (технолог, архитектор) либо вверх (тимлид, пм, руководитель отдела), либо меняем работу (т.е. меняем рабочую среду, коллектив, область деятельности).
Знаете, я за два года работы в Москве 6 раз меня работу. Из них:
1. Низкая оплата труда.
2. Участие в мертворожденном проекте частного предпринимателя.
3. Участие в мертворожденном проекте компании.
4, 5: Шарашкины конторы. 3 дня работы, неделя работы.
6. Неадекватное руководство. Аля 'пошли вы на ***, дельфины'.
7. ???

Может быть есть тому причины, почему люди уходят из компаний.
А вы куда смотрели когда устраивались на работу?
Вы же сами соглашались на зарплату, вы могли сами узнать многое о работе от человека который вас собеседовал, а до этого могли поискать инфу в инете. Вы могли оценить офис компании, попросить сделать для вас экскурсию в отдел разработки (чтобы понять как там вообще люди работают) и вообще много чего. От того что вас так надували — не делает плюсов вашему резюме и вашему рассказу о причинах смены мест работы. Вся информация от вас подвергается сомнению.
Интересно, Вы определите на собеседовании является ли проект мертворожденным — сразу попросите показать документацию? Либо то, что человек, который будет Вашим непосредственным начальником, хам и грубиян?
Думаю что определить прям всё-всё-всё нереально, это ваши риски старайтесь их прогнозировать оценивать и подстраховываться. В любом случае вы будете в проигрыше если лишний раз проверите контору на «вшивость» на практике.
>. И ты будешь брать себе программера которому будешь платить деньги, будешь тратить время его коллег, тимлидов, пм-ов на то чтобы человек вошел в курс дела, изучил рабочую среду, изучил всю кухню отдела разработки, научился с ней работать, а потом сразу свалил?

Ну не месяц же он все это изучать будет, что за бред? Мы ж не говорим про совсем начинающих.

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

Но я-то не руководитель. У меня свои интересы :)

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


Спасибо! ;)
Вы вот так под одну гребенку всех олимпиадников и выпускников мехмата замели… Словно на мехмате преподы только и делают, что учат «Не пользуйтесь дети Гибернейтом! Будут вам гвозди в руки вбивать, все равно не пользуйтесь!»
По-моему статья претендует на подпись капитана Очевидность. Это две совершенно разные профессии. Математически-творчески мыслящие хитроумно-оригинальные программисты-математики-художники и системно-мыслящие программисты-архитекторы-сборщики. И те и другие нужны и каждый должен заниматся своим делом. Когда первые берутся за дело вторых они превращаются в велосипедистов и начинают разрабатывать новые колёса причудливых форм и педали для трёхногих. К сожалению не все это понимают.
Самое интересное, но в 99% случаев интервьюеры забывают при даче такого рода задач указывать приоритеты в решении.
А именно, что важнее:
1. Время на обдумывание/имплементацию решения.
2. Производительность по времени, затраты памяти, потребление ресурсов процессора. Даже конкретная платформа играет роль.
4. Удобность тестирование, стабильность.
5. Удобность понимания, поддержка, расширение функционала в последующем.

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

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

т.е. нужно всегда видеть тонкую грань между тем что лучше — допилить под себя готовое или написать свое, пусть беднее, зато позволяющее решить именно эту задачу
Это действительно 2 разные специализации, я тоже подмечал их. Большие конторы как правило в поиске талантливых людей, с нацелом обучить их под себя, даже на сеньерских позициях. Фирмы помелче часто нацелены на порлучение непосредственно прибыли. Ну и там другие штуки тоже играют.
Кстати, подобные задачи ещё могут задавать не для того, чтобы их решили, а для того чтобы посмотреть, как кандидат будет их решать. Насколько быстро он сдастся, сколько будет задавать уточняющих вопросов, как будет отстаивать свое решение и т.п.
Так что не чморите олимпиадников, мехматовцев, физтехов и иже с ними, по чем зря :)
Иногда тренируюсь на Project Euler, чтобы эта мысль хоть на чуть-чуть отступала. А иногда завидую Game Developer`ам у них там каждый день алгоритмы да математика
Ненавижу таких, как вы, которые ради простой задачи используют тяжеленный, громоздкий, избыточный, тормозной Zend Framework или, что еще хуже, Doctrine. Doctrine вообще имхо по-идиотски написан, индусы писали наверно. Чего стоят только критерии.

Также, тем, кто любит всякие «OpenSource» фреймворки, хочу сказать, что половина их авторов — индусы, оставшаяся половина страдает слишком дотошным чтением Мартина Фаулера, дурными Java-привычками (на PHP портированный с явы код смотрится и работает как правило отвратительно), да и просто отсутвием адекватности. Порой смотришь. что они понаписали, страшно становится.

С таким кодом можно работать, только если не заглядывать внутрь. И если совесть где-нибудь оставить в стороне.

Вот и плодятся страшные громоздкие ORM-ы на PHP и Zend, у которого по 10 интефрейсов сделано ради одного простого класса. Зато документация простая и на русском.

Плодятся уродливые CMS типа Джумлы/Вордпресс/Друпал и, просто господи, ОСКоммерс. «Бесплатность» некоторым заменяет чувство здравого смысла.

Также эти «свободные » библиотеки любят страдать избыточностью: например, в jQuery встроена сложная selector engine, из которой 5% возможностей в основном и нужны. Однако ослепленные количеством фич и возможностью по-быстренькому слепить очередно унылосайт горе-разработчики даже об этом не задумаются.

И вообще, есть подозрение, что хорошие разработки просто так в OpenSource не отдадут, зачем, а отдают что похуже или что уже устарело. Например хороший плеер foobar2000 с закрытыми исходниками, а тормозной потребляющий память OpenOffice — с открытыми.
К сожалению, я увидел полное описание себя. Да, так и есть. Боюсь, что такими темпами осталось недолго до того, когда можно остановиться на развитии и остаться на чем-то одном. Это очень плачевно.
Дополню.

Пролистав комментарии, я увидел, что местный менталитет — говно. Они заметили только Zend и Doctrine.
Я вот не обиделся, но это вы зря;)
Зря вы так. Эту школоту довольно быстро загоняют в минус. А толковых комментариев на порядок больше.
Лично я бы стал учиться программированию, чтобы решать нестандартные задачи. Работа работой, а думать это уже интересно)
Изобретать, улучшать и созидать.

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

А узбеки — это как-раз те люди, которые STL по пятому кругу переписывают в каждом новом проекте.

И это, не выдержал… «Лично я бы стал учиться программированию» — как вы умудряетесь обсуждать то, чего не знаете, если еще не выучились?
Вот такое получилось решение задачки наибольшее произведение
с первой попытки…
#include
using namespace std;

int main()
{
int a[]={-1,1,2,0,-5,0,-7};
const int N=6;
int negative=0,nulls=-1,min=0,maxnegative=0;
for (int i=0;i0 && (a[i]
вы, батенька, и не программист вовсе, а копипастер!
Первый вопрос, который возник в голове: «На*уя? Зачем?»
Крайне правильная мысль, как мне кажется. Терпеть ненавижу такие высосанные из пальца задачи, ещё со времен школьных олимпиад. А умение собирать из готовых компонент рабочее решение — это не каждому дано. Особенно, если разбираешься в том, как такие компоненты работают и можешь при необходимости реализовать аналог, пускай и упрощённый. Задачи вроде Project Euler это скорее разминка для ума, нежели реальный показатель умения программировать. Самое главное, чтобы работа была сделана качественно и в срок, и приносила удовольствие.
P.S. А в мире веб-программирования 99% решений собраны из готового, так что не печальтесь :)
Молодец! Я бы о себе так откровенно не написал.
И с выводами согласен.
Вы — хороший программист. И умный человек. Приходите к нам на собеседование?

P.S. Правда статья лишена практического смысла, без одной указанной «мелочи»: а чем именно вы устраивались заниматься в MS? Все же к разработчикам highload-web-систем, компиляторов, десктоп-приложений и каких-нибудь opengl-движков предъявляются абсолютно разные требования. Вплоть до образа мышления. И большие компании просто очень хорошо знают «цену входа». Я видел много web-разработчиков, способных потенциально писать модули для kernel. Только они не смогут начать это делать в первый же день своей офисной жизни.
Я собеседовался в команду поисковой системы Bing.
Тогда в таком вопросе вполне может быть смысл. При разработке одной из крупнейших в мире систем должно хватать задач, где стандартного решения нет вообще. Вполне возможно, что интервьюирующего как-раз огонек вопроса «Нах*я?!» и не устроил ;]
Аж прослезился…
Нам преподаватели в университете часто говорят, что пока человек молод, голова соображает быстро и хорошо, поэтому ты можешь развиваться как программист, схватывать всё новое, быстро решать даже сложные алгоритмические задачи и т. д. Но, чем ближе ты подкатываешься к 30 с хвостиком годам, тем сложнее тебе придумать интересные и нестандартные решения, да и вообще следить за стремительным обновлением технологий.

Идея в том, что к 30 с хвостиком годам надо вырасти из простого программиста в нечто большее. Например, преподы предлагают нам податься в науку (утверждая, что там к 30 с хвостиком годам все только начинается), но, мне кажется, есть и другие интересные варианты.
Запишите в шпаргалку для собеседований:
Array.prototype.to_string = function() {
 var out = '';
 for (var i = 0; i < this.length; i++) {
  out += this[i];
 }
 return out;
}
String.prototype.reverse = function() {
 var i = 0;
 var j = this.length - 1;
 var output = [];
 while (i <= j) {
  var ch = this.charAt(i);
  output[i] = this.charAt(j);
  output[j] = ch;
  ++i;
  --j;
 }
 return output.to_string();
 
}

alert('hello yello'.reverse())


* This source code was highlighted with Source Code Highlighter.


А то, судя по всему, это любимый вопрос. Лично меня два раза спрашивали, причем один раз в Yandex-е.
Это не самое лучшее решение из того, что уже предложено в комментах. Читайте комменты.
Вы про обмен значений двух переменных? Тут можно без экзотики. Лично я довольно скептически отношусь к такому виду оптимизации.
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
По поводу решения задачи нахождения максимального произведения чисел, у меня получилось следующее:
/**
* Find subset with maximal product of numbers.
*/
function max_product(num) {
 var tmp = [],
  negNumCounter = 0,
  minNeg = 0,
  minAbs = num[0];
 
 for (var i = 0; i < num.length; i++) {
  // Rule out all zeros.
  if (!num[i]) {
   continue;
  }
  
  if (num[i] < 0) {
   // Minimal negative number.   
   if (num[i] < minNeg) {
    minNeg = num[i];
   }
   negNumCounter++;
  }

  // Minimal absolute value.   
  var abs = Math.abs(num[i]);
  if (abs < minAbs) { //
   minAbs = abs;
  }
  
  tmp.push(num[i]);
 }
 
 var negParity = negNumCounter % 2,
  result = [];

 for (var i = 0; i < tmp.length; i++) {
  var minValue = (!negParity && negNumCounter > 0) ? minNeg : minAbs;
  if (tmp[i] == minValue) {
   continue;
  }
  result.push(tmp[i]);
 }
 return result;
}

var number = [1, 2, 0, -7, -1, 4, 3, 32, 18, -2, -32];
alert(max_product(number));

* This source code was highlighted with Source Code Highlighter.


Решение за O(n2)
умение решать задачки на микрософтковских интервью говорит о человеке лишь, то, что он хорошо умеет решать задачки микрософтковских интервью. Эти собеседования как ни странно достаточно СТАНДАРТНЫ, и вопросы там вполне повторяющиеся. Желающие вполне могут к этим интервью подготовиться за неделю-две, проштудировав ГУГЛ («Microsoft interview questions») или книжку:
www.amazon.co.uk/Programming-Interviews-Exposed-John-Mongan/dp/0471383562/ref=sr_1_3?ie=UTF8&s=books&qid=1272535002&sr=8-3
www.amazon.co.uk/How-Would-Move-Mount-Fuji/dp/0316778494/ref=sr_1_4?ie=UTF8&s=books&qid=1272535002&sr=8-4

Блин! Ну, почем так мало таких программистов то?!!! Блин, прямо таки не знаю как словами выразить свой респект! Как бы всем нам легко жилось!
Нежелание придумывать велосипеды вполне даже приемлимо! А на счет зарядки для мозгов и так уже в теме кучу всего написали.
А теперь представьте как бы вам жилось без таких программистов, строящих велосипеды которыми вы потом пользуетесь :)
Ну, кагбэ, я считаю, что к велосипедам надо прибегать, только в случае, если нет приемлимового стандартного решения(имеется в виду если его нет или решение по какой либо причине не соответствует требованиям). Яркий пример — программеры 1С, вместо того, чтобы делать обработку данных путем составления SQL запросов они загружают всю таблицу в программу и внутри нее уже все обрабатывают. Такие велосипеды мне уж точно не нужны! Из-за этого, лично я получаю большую загрузку сети и большую загрузку клиентских машин, тогда как мне легче было бы один раз взять хороший мощный сервак и нормально его настроить. Это, к сожалению, не единичный случай. Ясное дело, что такой подход «расслабляет», но есть такое понятие, как самодисциплина…
Это не велосипедостроение а просто не правильные программисты.
блин, не к тому посту ответ прилепил, см. ниже
Ну, вопрос только в названии. Нормальный программист не должен строить велосипеды, он должен либо писать нормальный код, либо использовать существующие наработки. По Вашей логике все программисты велосипедостроители(ну, кроме тех, кто прогает на бинарном или псевдокоде). Все языки высшего уровня используют уже кем-то написанные библиотеки и модули. Согласитесь, вы же не будете писать на АСМе простую сортировку чисел от 1 до 10?
Это не я щитаю всех велосипедистами. Почему то сейчас почти у всех такое понятие если написал что уже было то велосипед.

А сортировку я и на С++ не буду сам писать так как пользуюсь stl. Я говорил про те вещи которые не так популярны и есть готовые решения при чем в том фраемворке который используешь. Я про те примеры про которые написал автор, про поиск наибольшего произведения. В данном случае проще взять и написать а не лесть в гугл. А сортировка не такая уж и пустяковая задача.
Хотя каждый уважающий себя программист хотя бы раз в жизни должен написать сортировку с нуля, хотя бы пузырьковую :).
Это же интересно тем более на асме.
Ну, в свое время, когда учился программить и слегка этим занимался(сейчас то я это дело забросил) меня оч сильно заинтересовала сортировка методом Шелла. Причем так заморочился, что хотел было все тома Кнута выписать… Но потом все прошло)
Это меня убило, в некотором смысле:
Я вообще не люблю писать исполняемый код, потому что я в нём постоянно делаю ошибки, которые потом нужно искать и исправлять. Я люблю дописывать xml-ные конфиги, идущие в пакете от разработчика.


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

У меня нет никакого особого опыта, но я прямо вижу здесь себя. Я никогда не увлекался спортивным программированием, не писал программы для себя, потому что не видел никогда в этом смысла — зачем изобретать велосипед? Толкового ведь не напишу, что было бы реально полезно. Недавно была статья про этапы программизма, она перекликается с этой во многом. Даже несмотря на малый опыт, мне понятно — нужно идти сразу на 3й этап, это правильный подход. Программирование — не цель, а средство. Код должен быть внятным, понятным, глаз должен четко цепляться за различные места, количество абстракций должно быть достаточным — именно просто достаточным. Система с хорошей архитектурой и кодом — как хорошо спланированное и качественно построенное здание. Чтобы, например, пол был хорошим, годным — перепад высот должен быть не более нескольких миллиметров, но — по всему этажу. Худший же вариант олимпиадника будет выравнивать пол до микронной точности, но успеет он это сделать только в одном углу.

Олимпиадные задачки — конечно, бывает интересно. Вопрос «зачем» тут еще стоит, но далеко не столь очевиден. Это разминка ума, а его разминать нужно всегда. Мне это как-то никогда не было интересно, сейчас немного сожалею. Впрочем, полагаю, разминать мозг не обязательно именно программированием — есть много и других видов задач на логику и/или смекалку.

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

«Прагматики» же не являются по призванию программистами, даже если у них это хорошо получается, они скорее сменят направление, возможно, будут ПМ, а может уйдут в нечто совсем иное. Как автор статьи пишет, что программирование это не то, чем он хотел бы заниматься до конца жизни, так и для меня программирование явно не самое интересное занятие. Я это просто могу, хоть и не обладаю большим опытом, но тем не менее это у меня получается, и я буду пока что этим заниматься. Но в будущем, скорее всего, уйду в другую сферу деятельности. Просто это в целом технически-прагматический склад ума, нежели радикально-математически-абстрактный.
моё решение на Си++

#include «stdafx.h»
#include «conio.h»

// сортировка массива mas размера size по возрастанию
// методом «пузырька»
void sort(int mas[], int size)
{
int tmp;
for (int i = 0; i < size; i++)
for (int j = size — 1; j > i; j--)
{
if (mas[j — 1] > mas[j])
{
tmp = mas[j — 1];
mas[j — 1] = mas[j];
mas[j] = tmp;
}
}
}

// вывод на экран массива mas размера size без элемента под номером ex
// вывод на экран произведения элементов
void result_output(int mas[], int size, int ex)
{
int res = 1;
for (int i = 0; i < size; i++)
{
if (ex != i)
{
printf("%d ", mas[i]);
res *= mas[i];
}
}
printf("\nMax product of numbers: %d", res);
}

void output(int mas[], int size)
{
for (int i = 0; i < size; i++)
printf("%d ", mas[i]);
printf("\n");
}

// функция модуля числа n
int abs(int n)
{
if (n < 0) return -n;
else return n;
}

int _tmain(int argc, _TCHAR* argv[])
{
int nsign_count = 0, // число отриц. элементов
zero_i = -1, // номер нулевого элемента
nzero_count = 0; // количество нулевых элементов
int size = 6; // размер массива

int mas[6] = {0, -3, 1, 1, 2, 1}; // исходный массив

sort(mas, size); // сортировка по возрастанию

output(mas, size); // вывод на экран исходного массива

for (int i = 0; i < size; i++)
{
// подсчёт количества отрицательных элементов
if (mas[i] < 0) nsign_count++;
// подсчёт количества нулевых элементов
if (mas[i] == 0)
{
zero_i = i;
nzero_count++;
}
}

// нет нулей и отрицательных элементов
if ((zero_i == -1) && (nsign_count == 0))
result_output(mas, size, 0);
// нет нулей, но есть отрицательные элементы
if ((zero_i == -1) && (nsign_count > 0))
{
// количество отриц. элементов нечётное
if ((nsign_count % 2 != 0)) result_output(mas, size, nsign_count — 1);
// количество отриц. элементов чётное
if (nsign_count % 2 == 0)
// положительные элементы есть
if (nsign_count < size)
result_output(mas, size, nsign_count);
else // положительных элементов нет
result_output(mas, size, 0);
}
// случай нескольких нулей
if (zero_i != -1)
{
if (nzero_count > 1)
result_output(mas, size, zero_i);
else // случай одного нуля
{
// количество отриц. элементов нечётное
if ((nsign_count % 2 != 0))
result_output(mas, size, 0);
// количество отриц. элементов чётное
if ((nsign_count % 2 == 0))
result_output(mas, size, zero_i);
}
}

_getch();
return 0;
}
«как перевернуть строку?». Я подумал, и написал псевдокод на ядерной смеси C++, Pascal и PHP

хм…
<?php
echo strrev('hello world');
выбрать из int ar[n] = {...} n-1 элементов так, чтобы произведение выбранных было максимальным

это случайно не все элементы кроме минимального? или я неправильно понял задание?

правда надо уточнить условия. все становится хуже, если в массиве могут быть отрицательные множители — если их нечетное количество, то надо будет убрать минимальный по модулю отрицательный множитель.
нужно учесть все эти случаи, а так же еще
если, например, есть ноль — там тоже свои ньюансы есть, т.к. ноль больше отрицательных чисел
Меня тоже удивило, что человек, который говорит, что толком не умеет программировать, написал программу на «смеси C++, Pascal и PHP», т.е. как-то их связал. А для этого не мало знаний надо.

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

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

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

Какие-то решения задачи кидают… куски кода…

Вас об этом кто-то просил?!

Я так понимаю, что автор решение и без вас найдёт в Гуугле, если ему оно понадобиться!
А сама проблема куда глубже, чем просто пройти интервью в какую-то некоторым НЕ НУЖНУЮ компанию типа Microsoft/Google/Apple/Яндекс/вписать_нужное_название

У меня такое впечатление, что мечта работать в вышеперечисленной компании — какой-то фетиш!

Публикации

Изменить настройки темы

Истории