Комментарии 396
Для этого стоит иногда брать какую-нить олимпиадную задачу с того же TopCoder, например или вообще не олимпиадную, а какую-то конкретную задачу прикладную, вообщем неважно какого ресурса и пытаться её самостоятельно раскрутить, без помощи гугла и еще чего-либо
возможно придумать и реализовать несколько решений, а потом как-то проконсультироваться с народом.
на это конечно нужно время, но зато возможно будете в тонусе неком
возможно придумать и реализовать несколько решений, а потом как-то проконсультироваться с народом.
на это конечно нужно время, но зато возможно будете в тонусе неком
Постараюсь выработать такую привычку. Появилась ясность — такая встряска для мозга периодически просто необходима. Мне давненько не приходилось так много думать, как в 3 дня до подготовки + 40 минут самого собеседования.
такие задачки мне кажется фирме (которая проводит собеседование) нужны больше для оценки потенциала человека, посмотреть как он может думать и анализировать нестандартно, а в реальной работе я уверен больше столкнётесь как раз со стандартными решениями, имхо
Абсолютно согласен.
Но если контора решает стандартные задачи, то человек который слишком много мыслит не стандартно будет в команде лишним. Я видел, как таких людей увольняли, потому что их код слишком сложный, его никто не понимает, они большую часть рабочего времени изобретают велосипеды, а не решают бизнес задачи. И в таких конторах обычно задают просят рассказать о реальном опыте применения boost, Spring, Hibernate и т.д. Там очень редко просят разрезать прямоугольный пирог с прямоугольной дыркой в произвольном месте пополам одним прямолинейным разрезом.
Другое дело флагманы разработки софта. Стандартные решения им как раз не нужны. Им нужно что-то инновационное, передовое, не стандартное.
Но если контора решает стандартные задачи, то человек который слишком много мыслит не стандартно будет в команде лишним. Я видел, как таких людей увольняли, потому что их код слишком сложный, его никто не понимает, они большую часть рабочего времени изобретают велосипеды, а не решают бизнес задачи. И в таких конторах обычно задают просят рассказать о реальном опыте применения boost, Spring, Hibernate и т.д. Там очень редко просят разрезать прямоугольный пирог с прямоугольной дыркой в произвольном месте пополам одним прямолинейным разрезом.
Другое дело флагманы разработки софта. Стандартные решения им как раз не нужны. Им нужно что-то инновационное, передовое, не стандартное.
Просто также, как когда-то было с инженерами, происходит и с программистами (сисадмины выделились из «компьютерщиков» уже в прошлом веке). Первые инженеры были на все руки мастера, а сейчас есть и сантехники, от которых требуется лишь привинтить стандартный смеситель к стандартному трубопроводу, ничего при этом не разрушив, и разработчики ракетных двигателей, которым надо думать, что бы трубопровод не прогорел и не развалился от вибрации во время ресурса движка, поэтому этот трубопровод надо хитро изогнуть и снабдить охладительными каналами. Это не плохо, просто чем дальше, тем бОльшая будет специализация.
Мне кажется, я догадываюсь о ком ты :)
:) Ну не совсем.
В той конторе была зеркальная ситуация: там был неадекватный тим-лид, который сам очень любил изобретать велосипеды, писать свои CMS и страдать прочей хернёй. Разбираться в разработках людей, которые (о ужас!) поумнее него не имел никакого желания, так как считал себя самым умным.
Ниже есть представители такой конфессии. Я не разделяю их религии и в холивары не вступаю.
В той конторе была зеркальная ситуация: там был неадекватный тим-лид, который сам очень любил изобретать велосипеды, писать свои CMS и страдать прочей хернёй. Разбираться в разработках людей, которые (о ужас!) поумнее него не имел никакого желания, так как считал себя самым умным.
Ниже есть представители такой конфессии. Я не разделяю их религии и в холивары не вступаю.
С небольшим уточнением — вероятнее всего или в большинстве случаев. Но есть и исключения. Очень приятные, кстати. Особенно когда решишь.
Например, реализация web-интерфейса сравнения текстовых файлов с максимальным приближением к TortoiseDiff — две панельки, синхронный интерактивный просмотр, постраничное разбиение, навигация по изменившимся фрагментам. Очень много подводных камней. Особенно, если файлы имеют много различий вплоть до количества страниц.
Самым интересной показалась подзадача когда контролы «пред./след. различие» необходимо было синхронизировать с просматриваемыми блоками текста. Например, если мы прокрутили первое различие — активировать ссылку «предыдущее изменение». При сравнении ряда документов выявилось, что IE, очень медленно работающий с массивами, требует применения ряда оптимизаций поиска.
Например, реализация web-интерфейса сравнения текстовых файлов с максимальным приближением к TortoiseDiff — две панельки, синхронный интерактивный просмотр, постраничное разбиение, навигация по изменившимся фрагментам. Очень много подводных камней. Особенно, если файлы имеют много различий вплоть до количества страниц.
Самым интересной показалась подзадача когда контролы «пред./след. различие» необходимо было синхронизировать с просматриваемыми блоками текста. Например, если мы прокрутили первое различие — активировать ссылку «предыдущее изменение». При сравнении ряда документов выявилось, что IE, очень медленно работающий с массивами, требует применения ряда оптимизаций поиска.
Для меня на одном из интервью наиболее стрессовым моментом было то, что за мной наблюдают и поправляют еще раньше, чем я соображу, где ошибка. Аж синтаксис INNER JOIN забыл..(
В отместку написал им "«как перевернуть строку?». Я подумал, и написал псевдокод на ядерной смеси C++, Pascal и PHP." так, что пришлось пояснять, как работает:)
В отместку написал им "«как перевернуть строку?». Я подумал, и написал псевдокод на ядерной смеси C++, Pascal и PHP." так, что пришлось пояснять, как работает:)
Начните писать свою игру, вообще без использования фреймворков.
Я специально для этого хожу на всякие acm.mipt.ru, acm.timus.ru и решаю всякие задачки, или играю в гольф там же. Иначе просто скучно все время заниматься разработкой, когда способы и типичные решения знаешь, и единственные умственные затраты лишь на чтение соответствующей документации.
НЛО прилетело и опубликовало эту надпись здесь
мозг развивается примерно до 25-26 лет…
как вы это поняли?
НЛО прилетело и опубликовало эту надпись здесь
Дайте ссылку на авторитетный источник.
Только, пожалуйста, не новости о британских ученых.
Только, пожалуйста, не новости о британских ученых.
НЛО прилетело и опубликовало эту надпись здесь
Американские ученые из Арканзасского медицинского центра сойдут? =)
По их мнению «в среднем так называемое „белое вещество“, отвечающее за связь между разными частями мозга, продолжает развиваться до 48-летнего возраста.»
palm.newsru.com/world/16may2001/mozg.html
По их мнению «в среднем так называемое „белое вещество“, отвечающее за связь между разными частями мозга, продолжает развиваться до 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 для отправки почты. Почему нет? Или стандартные решения нужно применять исключительно целиком без изменений?
Эмммм, Поздравляю.
(вы это хотели услышать?))
(вы это хотели услышать?))
<hr /> ну нормально… а теперь без буфера хранящего позицию середины строки…
ой(
я хотела сказать «А зачемтакой буфер? „
Проще же посчитать знаки в строке и потом читать до последнего знака, его писать в новую “перевёрнутую», стирать, снова читать, и так по циклу.
я хотела сказать «А зачемтакой буфер? „
Проще же посчитать знаки в строке и потом читать до последнего знака, его писать в новую “перевёрнутую», стирать, снова читать, и так по циклу.
Попробуйте решить эту задачу без второй строки. Тогда станет понятнее.
Записать строку в стек, и считать из стека.
Я что-то не понимаю, или эта задача решается циклом от 0 до n/2 c телом swap(a[i], a[n — i — 1])?
а можно без буфера еще и использовать свойство сложения
пусть
а=7
b=5
тогда
a=a+b
b=a-b
a=a-b
имеем
a=5+7=12
b=12-5=7
a=12-7=5
как-то так))
пусть
а=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 = a ^ b;
b = a ^ b;
a = a ^ b;
(^ = xor, искл. или, мин. сумма, сумма по модулю 2, ...)
Эта штука намного медленнее работает, чем с дополнительной ячейкой вариант. Хотя интересно, да:) a^=b^=a^=b; :D
А почему намного медленнее? XOR, вроде как, довольно быстрая операция. Или я ошибаюсь?
Это всё все равно упирается в особенности компилятора.
Алгоритм обмена при помощи исключающего ИЛИ
XOR очень быстрая, но в один поток.
В общем все зависит от архитектуры.
XOR очень быстрая, но в один поток.
В общем все зависит от архитектуры.
на современных ЦП XOR-техника значительно медленнее, чем использование временной переменной для обмена. Это происходит по причине распараллеливания выполнения команд. В XOR-технике операнды всех команд зависят от результатов предыдущих команд, поэтому они должны быть выполнены в строго последовательном порядке
Никогда не пишите a^=b^=a^=b; это UB.
Вариант с хогом работает быстрее в принципе, но даже сложение сработает. После сложения. При переполнении вы потеряете единичку впереди, но при вычитании все опять станет нормально.
рапространенное заблуждение.
переполнение ничего не портит, потому что числа ограниченной разрядности по сложению образуют циклическую группу.
переполнение ничего не портит, потому что числа ограниченной разрядности по сложению образуют циклическую группу.
только можем получить опять же переполнение
Можно два char* использовать — на индексах и их вычислениях сэкономим. :)
а зачем вторая строка?
Длина строки же известна? например n
берем и меняем местами 1 и n
потом 1+1 и n-1
и так до тех пор пока 1+k<n-k
Длина строки же известна? например n
берем и меняем местами 1 и n
потом 1+1 и n-1
и так до тех пор пока 1+k<n-k
Подбор персонала наука точная, только что-то не сходится… ©
На самом деле сложно выбирать вопросы для программиста, всякие «резюме» и прочее могут сказать что «на прошлой работе вы справлялись» всякие «сертификаты» и «задачи из учебника» могут сказать что «сферического коня в вакууме» вы напишете, а вот как подобрать программиста под свои задачи?
Вопрос сложный, и на практике решается весьма неэффективно, ищется «хороший программист» причём даже на «фиговую работу» (куда можно смело брать новичка, главное взять такого чтоб с энтузиазмом работал и желал учиться) в результате недовольны обе стороны, программист скучает на работе и мало получает, работодатель же получает вялого сотрудника которого не интересует ни выпускаемый продукт, ни сроки, ни даже повышение по службе. (Нет мотивации к работе.)
Так вот каждый раз жалуясь на то что на собеседовании от вас «хотят не того» или «задают глупые вопросы» задумайтесь, эти люди тоже на работе, и их работа по своему тоже требует навыков и знаний, спросите сначала себя «а как бы я подбирал человека на эту должность ?»
Когда вы ответите на этот простой вопрос, вы сможете ответить на главный вопрос «интервьювера» который интересует его куда важнее чем ваши навыки в решении стандартных задач, «чем вы можете быть полезны нашей фирме ?» или другими словами «почему мы должны взять именно вас ?»
На самом деле сложно выбирать вопросы для программиста, всякие «резюме» и прочее могут сказать что «на прошлой работе вы справлялись» всякие «сертификаты» и «задачи из учебника» могут сказать что «сферического коня в вакууме» вы напишете, а вот как подобрать программиста под свои задачи?
Вопрос сложный, и на практике решается весьма неэффективно, ищется «хороший программист» причём даже на «фиговую работу» (куда можно смело брать новичка, главное взять такого чтоб с энтузиазмом работал и желал учиться) в результате недовольны обе стороны, программист скучает на работе и мало получает, работодатель же получает вялого сотрудника которого не интересует ни выпускаемый продукт, ни сроки, ни даже повышение по службе. (Нет мотивации к работе.)
Так вот каждый раз жалуясь на то что на собеседовании от вас «хотят не того» или «задают глупые вопросы» задумайтесь, эти люди тоже на работе, и их работа по своему тоже требует навыков и знаний, спросите сначала себя «а как бы я подбирал человека на эту должность ?»
Когда вы ответите на этот простой вопрос, вы сможете ответить на главный вопрос «интервьювера» который интересует его куда важнее чем ваши навыки в решении стандартных задач, «чем вы можете быть полезны нашей фирме ?» или другими словами «почему мы должны взять именно вас ?»
Чуть выше я ответил на этот вопрос. Для работы в Microsoft в текущей форме я точно не гожусь — им нужны новаторы.
Хороший совет, спасибо. Где-то читал рекомендацию тем, кто проводит собеседование: вместо выяснения того, какую литературу читает программист и чем занимается в свободное время, объяснить ему в чем будет заключаться работа и спросить, сможет ли он ее делать. Дальше уже можно заняться проверкой честности и трезвости его мнения.
Меня например бесит, когда собеседующие не способны объяснить чем они вообще занимаются, и что конкретно требуется от меня.
Меня например бесит, когда собеседующие не способны объяснить чем они вообще занимаются, и что конкретно требуется от меня.
Удивительно, но майкрасофт на очном собеседовании спрашивает вопросы парой на столько простые, что это обескураживает. Стандартные структуры, сортировки, вызовы конструкторов, ряд фурье… Многие готовятся решать задачки на логику — зря. Это все на этапе телефонного интервью.
На собеседовании — университетский курс. По крайне мере так было у джунеоров.
На собеседовании — университетский курс. По крайне мере так было у джунеоров.
Жутко знакома история про строку )
Как на экзамене на первом курсе декан дал это же задание, и я должен был написать на паскале, а я даже типов паскалевских толком не знал. Были за плечами только воспоминания о бейсике 7-10 летней давности.
Я написал какой-то бред, тоже заминался, а он мне пятерку поставил )
Наверное что-то в этой задаче в качестве тестирования есть…
Как на экзамене на первом курсе декан дал это же задание, и я должен был написать на паскале, а я даже типов паскалевских толком не знал. Были за плечами только воспоминания о бейсике 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 — ну точно не правильный ответ в этом случае :)
p = INT_MAX * 2 * -1 = 2
p / INT_MAX = 0
p / 2 = 1
p / -1 = -2
Тогда, по логике, выкидывать надо 2.
INT_MAX * -1 — ну точно не правильный ответ в этом случае :)
Вы не ошиблись кому пишете?
Стоп, а где сказано какой тип у результата? Если бы было сказано, чтобы получился максимальный результат типа int, то тогда да.
А так, не важно как их будут умножать, и что с ними будут делать.
Вы пытаетесь придумать ограничения, которых не было в задаче.
Если же всё сводить к вопросу: я тут написал вот такую хреновину, отгадайте что это на самом деле значит, то это уже собеседование скорее на менеджера.
А так, не важно как их будут умножать, и что с ними будут делать.
Вы пытаетесь придумать ограничения, которых не было в задаче.
Если же всё сводить к вопросу: я тут написал вот такую хреновину, отгадайте что это на самом деле значит, то это уже собеседование скорее на менеджера.
С чего вы взяли что ответ неправильный, если при произведения порождает переполнение?
Я ответил на этот вопрос выше.
и вовсе не факт, что при этом обязательно будет нужно само их произведение
Это я также прокомментировал выше.
Черт… Про переполнение я и не подумал
Задачка интереснее чем я думал :) Буду думать еще
Задачка интереснее чем я думал :) Буду думать еще
Переполнение фигня. Было бы желание, а умножить можно любые числа.
дело в том, что они проверяют еще и умение тестировать: найти, что есть переполнение, что есть отрицательные числа, 0…
Еще раз повторю. Есть переполнение или нет, зависит от задачи. Как то в школе еще (не помню зачем) делал умножение двух чисел в строковых переменных. То есть поразрядно. Получить там переполнение практически невозможно. А если и возможно и его можно обойти. Так что зависит от задачи.
тогда еще не плохо было бы уточнить в условии идет ли речь о максимальном произведении по модулю или в принципе ;)
Дополнительные вопросы приветствуются. Речь идёт об абсолютном значении. Без взятия модуля.
ну ну тогда общий алгорит примерно такой, как мне кажется:
смотрим есть ли у нас нули, если есть — убираем, иначе задача не имеет смысла
смотрим есть ли отрицательные значения
если отрицательное одно — выкидываем его — задача решена
если отрицательных более одного — определяем четное их число или нет, если четное — выкидываем наименьшее положительное число — задача решена
если нечетное число отрицательных — выкидываем наибольшее отрицательное (т.е. в последовательности -4,-3,-2 выкидываем -2) — задача решена
вроде ничего не упустил
смотрим есть ли у нас нули, если есть — убираем, иначе задача не имеет смысла
смотрим есть ли отрицательные значения
если отрицательное одно — выкидываем его — задача решена
если отрицательных более одного — определяем четное их число или нет, если четное — выкидываем наименьшее положительное число — задача решена
если нечетное число отрицательных — выкидываем наибольшее отрицательное (т.е. в последовательности -4,-3,-2 выкидываем -2) — задача решена
вроде ничего не упустил
подозреваю что я все дико усложняю, но математически алгоритм должен быть верным -_-
Вынесение случая с одним отрицательным в отдельный случай не имеет смысла :)
Правда, это придется делать достаточно сложно по количеству действий — при проходе по массиву надо:
1) проверить число на равенство нулю
2) проверить на отрицательность
3) найти минимум и максимум среди отрицательных
4) найти минимум среди положительных.
Это — 5*n.
А если не заботиться о переполнении, то можно за один проход найти произведение всех чисел, за второй — найти максимальное p / a[i].
Правда, это придется делать достаточно сложно по количеству действий — при проходе по массиву надо:
1) проверить число на равенство нулю
2) проверить на отрицательность
3) найти минимум и максимум среди отрицательных
4) найти минимум среди положительных.
Это — 5*n.
А если не заботиться о переполнении, то можно за один проход найти произведение всех чисел, за второй — найти максимальное p / a[i].
я бы сделал в два прохода. Сперва все перемножил (кроме нулей, если есть хоть один ноль — задача решается тривиально, сразу заканчиваем), а потом по очереди делил бы получившееся число на все значения, запоминая те, при которых произведение больше предыдущего «рекорда». Да, это тупо, деление стоит дорого, согласен.
Зачем всё это «щупание» в виде умножения и деления, если мы и так знаем как числа ведут себя? Считаем количество отрицательных и нулей за один проход и действуем по схеме, предложенной mukizu
а зачем усложнять? В решении mukizu нет элегантности :)
Фактически это значит, что его будет сложнее реализовать, труднее поддерживать, проще совершить ошибку.
Фактически это значит, что его будет сложнее реализовать, труднее поддерживать, проще совершить ошибку.
пусть результат хранится в байтовой переменной
массив: 4, 4, 16
сумма всех элементов: 4 * 4 * 16 = 256 = #100 или 0, обрезанное до байта.
дальше делить бессмысленно.
массив: 4, 4, 16
сумма всех элементов: 4 * 4 * 16 = 256 = #100 или 0, обрезанное до байта.
дальше делить бессмысленно.
согласен, просто хотелось максимально подробно расписать, и о такой детали не задумывался. my bad :)
c p/a[i] тоже хорошо придумано, да :D
c p/a[i] тоже хорошо придумано, да :D
Лучший вариант, однозначно
НЛО прилетело и опубликовало эту надпись здесь
Минимум отрицательных искать не надо.
Надо в цикле от 1 до н:
1. проверить на ноль, если ноль — запомнить позицию, если позиция уже запомнена — копировать от начала массива до н-1 в выходной массив (или куда там выбираем) и выйти из процедуры
2. Проверить на положительность числа.
2.а. Для положительного — сравниваем с минимальным положительным, если меньше — запоминаем позицию
2.б.1. Для отрицательного — добавляем 1 к счетчику отрицательных
2.б.2. Если число по модулю (-число) меньше минимального по модулю отрицательного — запомнить его позицию
3. по окончании цикла — если отрицательных нечетное число — убираем минимальное отрицательное
3. иначе, если есть ноль — убираем ноль
3. иначе убираем минимальное положительное
остальное копируем куда надо.
Надо в цикле от 1 до н:
1. проверить на ноль, если ноль — запомнить позицию, если позиция уже запомнена — копировать от начала массива до н-1 в выходной массив (или куда там выбираем) и выйти из процедуры
2. Проверить на положительность числа.
2.а. Для положительного — сравниваем с минимальным положительным, если меньше — запоминаем позицию
2.б.1. Для отрицательного — добавляем 1 к счетчику отрицательных
2.б.2. Если число по модулю (-число) меньше минимального по модулю отрицательного — запомнить его позицию
3. по окончании цикла — если отрицательных нечетное число — убираем минимальное отрицательное
3. иначе, если есть ноль — убираем ноль
3. иначе убираем минимальное положительное
остальное копируем куда надо.
Не совсем. Отрицательные числа меньше 0. То есть если у нас есть набор из 0 и нечетного числа отрицательных чисел (положительных нет совсем), то нужно убрать любое отрицательное. Получим 0. Кажется вы этот вариант не учли.
согласен.
по-моему описанию получается что нулевое решение я не рассматриваю как верное вообще.
по-моему описанию получается что нулевое решение я не рассматриваю как верное вообще.
Выше автор отписался, что произведение должно быть максимальным по молулю.
Он написал, что модуль брать не нужно. Или я что-то не так понял?..
Вот тут говорится именно об абсолютном значении.
Наконец-то кто-то на хабре озвучил верный путь )))
а если нулей больше одного? ;) в задаче просят выбросить один элемент, при двух нулях становится пофиг что выбрасывать ;)
потому я и написал — выбрасываем «нули». Если в массиве больше одного нуля, а выбросить можно строго один элемент — задача на максимальное произведение теряет смысл.
По-моему, все немного проще.
Определяем число отрицательных элементов.
Если четное — выбрасываем наименьший неотрицательный (не путать с положительным) элемент, если нечетное — наименьший.
Определяем число отрицательных элементов.
Если четное — выбрасываем наименьший неотрицательный (не путать с положительным) элемент, если нечетное — наименьший.
не увидел, написал ли кто еще:
Ноль можно выкидывать, только если оставшееся произведение не отрицательно. мложно это правило выкинуть, так как ноль ведет себя как положительное число в другои правилах.
Ноль можно выкидывать, только если оставшееся произведение не отрицательно. мложно это правило выкинуть, так как ноль ведет себя как положительное число в другои правилах.
Задача имеет смысл если есть нули.
0 > -|x| ;)
0 > -|x| ;)
у меня сократилось до следующего:
если отрицательных нечетное количество, выкидываем наибольшее отрицательное
иначе выкидываем наименьшее неотрицательное
если отрицательных нечетное количество, выкидываем наибольшее отрицательное
иначе выкидываем наименьшее неотрицательное
если один 0, то надо смотреть что лучше — выкидывать его или оставлять
абсолютное значение — это и есть по модулю ;)
А если при это произведение оставшихся окажется отрицательным?
не забываем про отрицательные числа :)
Вы на правильном пути. Дополнительные вопросы всегда приветствуются.
Подсказка: int это не то же самое, что unsigned int.
Подсказка: int это не то же самое, что unsigned int.
Тогда как то так…
Прогоняем по массиву цикл, по всем элементам, сравнивая, в каком случае сумма получится больше, если взять текущий элемент i, и элемент, который как мы считаем даст наибольшую сумму j. По умолчанию это первый элемент, прогон делаем от второго элемента до последнего
Сравниваем следующим образом:
1. Получаем знак умножения всех чисел, кроме i и j. Это либо неотрицательное число, либо отрицательное.
2. Если это отрицательное число, то наибольшее произведение будет с тем числом, которое меньше, с учетом знака.
3. Если это неотрицательное число, то наибольшее произведение будет с тем числом, которое больше, с учетом знака.
4. Если текущее число дало большую сумму чем j, то в j ставим i
Сложность алгоритма линейная, на выходе из цикла в j будет номер того элемента, с которым произведение наибольшее. Если решение не строгое, ответ тоже будет получен, один из возможных
Как то так…
Прогоняем по массиву цикл, по всем элементам, сравнивая, в каком случае сумма получится больше, если взять текущий элемент i, и элемент, который как мы считаем даст наибольшую сумму j. По умолчанию это первый элемент, прогон делаем от второго элемента до последнего
Сравниваем следующим образом:
1. Получаем знак умножения всех чисел, кроме i и j. Это либо неотрицательное число, либо отрицательное.
2. Если это отрицательное число, то наибольшее произведение будет с тем числом, которое меньше, с учетом знака.
3. Если это неотрицательное число, то наибольшее произведение будет с тем числом, которое больше, с учетом знака.
4. Если текущее число дало большую сумму чем j, то в j ставим i
Сложность алгоритма линейная, на выходе из цикла в j будет номер того элемента, с которым произведение наибольшее. Если решение не строгое, ответ тоже будет получен, один из возможных
Как то так…
я бы сделал так
отсортировать массив по возрастанию, а дальше: если отрицательных нечетное количество — выкинуть наименьший отрицательный, если четное — выкинуть наименьшее по модклю
отсортировать массив по возрастанию, а дальше: если отрицательных нечетное количество — выкинуть наименьший отрицательный, если четное — выкинуть наименьшее по модклю
хммм, я кажется, ошибся
если отрицательных нечетное количество — выкинуть наименьший отрицательный, если четное — выкинуть наименьший положительный
если отрицательных нечетное количество — выкинуть наименьший отрицательный, если четное — выкинуть наименьший положительный
А если в массиве есть 0?
итак, с 3 попытки:
1)если отрицательных четное кол-во и присутствует 0 — выкидываем 0
2)если отрицательных нечетное кол-во и присутствует 0 — выкидываем что-то кроме 0
3)если отрицательных нечетное кол-во — выкидываем максимальное отрицательное
4)если отрицательных четное кол-во — выкидываем минимальное положительное
1)если отрицательных четное кол-во и присутствует 0 — выкидываем 0
2)если отрицательных нечетное кол-во и присутствует 0 — выкидываем что-то кроме 0
3)если отрицательных нечетное кол-во — выкидываем максимальное отрицательное
4)если отрицательных четное кол-во — выкидываем минимальное положительное
Наличие в массиве нулей вообще ничего не меняет.
Разве что можно пока отрицательные числа считаем, если насчитали больше одного нуля — возвращаем 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-го элемента, его и нужно оптимизировать, дальше понятно.
1. Если 0 больше одного, выкидываем любой элемент.
2. Если 0 один, считаем произведение без него. Если получилось <0, то выкидываем любой элемент кроме нуля, если >0, то выкидываем 0.
3. Считаем произведение всех n чисел, допустим, оно = M
4. Проходим по массиву, вычисляем M/ar[i], это будет произведение всех чисел без i-го элемента, его и нужно оптимизировать, дальше понятно.
Первое, что пришло на ум — двухпроходный алгоритм.
Сначала проходим по массиву, подсчитывая произведение P всех n элементов.
Затем проходим еще раз, для каждого arr[i] находим частное P / arr[i].
Индекс, по которому частное будет максимальным — выбираем за лишний элемент и берем все остальные n-1.
Имхо, достоинства алгоритма: простота понимания, быстрота разработки (не нужно париться и прикидывать, что произойдет, если там будут нули, отриц числа итд), ну и меньшая плотность багов (по сравнению с более сложными для понимания алгоритмами).
Сначала проходим по массиву, подсчитывая произведение P всех n элементов.
Затем проходим еще раз, для каждого arr[i] находим частное P / arr[i].
Индекс, по которому частное будет максимальным — выбираем за лишний элемент и берем все остальные n-1.
Имхо, достоинства алгоритма: простота понимания, быстрота разработки (не нужно париться и прикидывать, что произойдет, если там будут нули, отриц числа итд), ну и меньшая плотность багов (по сравнению с более сложными для понимания алгоритмами).
А таки что произойдет, если в массиве будет нуль или одно отрицательное число, мм?
Нуль — да, не учтется.
А отрицательное обработается нормально.
А отрицательное обработается нормально.
Да, с нулем обида будет ) Эх, значит все же придется цифры считать — хотя бы в плане — если есть больше одного нуля, то решение — любое подмножество {n-1}, если нуль один — то он и будет лишним. Если же нулей нет, то делаем второй проход.
много делений => процессор будет больше париться, чем с вышеизложенными алгоритмами => больше угля сожжётся из-за этого алгоритма. Ну и дольше на пяток миллисекунд будет, если массив длиной в 10-15 элементов) А вот со строкой в пару миллионов…
Не считаю себя программистом, но ради интереса накидал алгоритм:
Взлетит?
Взлетит?
Можно обойтись без правой ветки. Просто удалить наименьшее неотрицательное число
если в массиве содержится четное количество отрицательных числе (правая ветка), то «просто удалив наименьшее неотрицательное число» в итоге получим отрицательное произведение.
Вот приведи кто-нибудь в топике для примера какую-нибудь задачу, и ее ну обязательно кинуться решать в комментариях.
Если есть ноль, выкинуть из ряда ноль.
Если нет, то перемножить весь ряд. Если результат положительный, выкинуть наименьшее положительное, если отрицательный — наименьшее отрицательное.
Все!
Если есть ноль, выкинуть из ряда ноль.
Если нет, то перемножить весь ряд. Если результат положительный, выкинуть наименьшее положительное, если отрицательный — наименьшее отрицательное.
Все!
Мне импонирует Ваш подход. Намного проще поддерживать и расширять код, использующий известные framework'и и стандарты, нежели что-то самописное. За Microsoft не скажу, но зачастую интервьюеры, в т.ч. и специалисты, бывают уровнем ниже, нежели соискатель. И бывает разговор вида «ты мне про Фому, а я — про Ерёму». Если человек последние несколько лет работал с какими-нибудь framework'ами (а такое случается сплошь и рядом) и, не дай Бог, в каком-нибудь нормальном редакторе или IDE, то через эти два года он позабудет низкоуровневое программирование, названия сотни функций, ищущихся в Интернете за 10 секунд или autocomplete IDE. Собеседование должно отражать реальный уровень не знаний, а умений. Хорошим вариантом является свободная реализация тестовой задачи. С любым framework'ом и/или IDE.
другая крайность, когда человек не то то библиотеками, но даже встроенными конструкциями языка пользоваться не умеет и пишет с нуля не толлько «рукосуйные протоколы» но и свой switch/case о_0
Уверен, что это не правильно, но я люблю знать на 100%, как и что у меня работает.
Из последнего. Надо было в программе работать с json-объектами (и парсить, и сохранять). Скачал чью-то монстрообразную библиотеку (несколько тысяч строк), потестировал, столкнулся с багом и удалил, а потом написал свою на 500 строк. Да, потратил сутки. Но зато я уверен в своем классе, он не содержит лишних методов, работает максимально эффективно и оптимален для моего случая… мне с ним приятно работать.
Если мне надо написать небольшое веб-приложение, то я скорее возьму свой мини-велосипед (простенький MVC-фреймворк), чей создам новый проект в symfony.
Из последнего. Надо было в программе работать с json-объектами (и парсить, и сохранять). Скачал чью-то монстрообразную библиотеку (несколько тысяч строк), потестировал, столкнулся с багом и удалил, а потом написал свою на 500 строк. Да, потратил сутки. Но зато я уверен в своем классе, он не содержит лишних методов, работает максимально эффективно и оптимален для моего случая… мне с ним приятно работать.
Если мне надо написать небольшое веб-приложение, то я скорее возьму свой мини-велосипед (простенький MVC-фреймворк), чей создам новый проект в symfony.
Я думаю автор имел ввиду не то, что для решения задачи нужно использовать готовое решение, а то, что прежде чем начинать изобретать велосипед нужно хорошенько ознакомиться с предметной областью. Если для решения стоящей задачи есть стандартное решение, а не множество, среди которых нет одного единственного общепризнанного, следует использовать это решение.
У меня тоже такой подход — даже если задача простейшая и я сам за короткое время могу её решить, всё равно — первым делом google. Есть стандартное решение — использую его, нет — знакомлюсь с парой-тройкой самых распространённых решений и если есть какие-то сомнения по поводу эффективности/сложности — реализую собственное решение.
У меня тоже такой подход — даже если задача простейшая и я сам за короткое время могу её решить, всё равно — первым делом google. Есть стандартное решение — использую его, нет — знакомлюсь с парой-тройкой самых распространённых решений и если есть какие-то сомнения по поводу эффективности/сложности — реализую собственное решение.
Из последнего. Надо было в программе работать с json-объектами (и парсить, и сохранять). Скачал чью-то монстрообразную библиотеку (несколько тысяч строк), потестировал, столкнулся с багом и удалил, а потом написал свою на 500 строк. Да, потратил сутки. Но зато я уверен в своем классе, он не содержит лишних методов, работает максимально эффективно и оптимален для моего случая… мне с ним приятно работать.
плохо искали или обладаете избытком свободного времени и средств.
прикинем стоимость вашего решения из расчета что в месяц такой кодер будет стоить нам 1500$:
1500*1/25 = 60$ (а если бы вы решали задачу только в рабочее время, то и все 120-150$)
т.е. ваша библиотека стоит мне как работодателю 60$, при этом поиск решения в гугле занял бы, как минимум, вдвое меньше времени, в будущем его будет проще поддерживать, а за оставшееся время вы могли бы реализовать часть другой задачи. в итоге результат вашего труда для меня был бы вдвое-втрое дешевле за счет роста количества решенных задач на единицу выплаченных денег.
не?
НЛО прилетело и опубликовало эту надпись здесь
Мне нужна была быстрая и надежная библиотека. Программе иногда приходится обрабатывать нескольких тысяч простых json-строк в секунду, поэтому быстродействие класса, работающего с json, играет роль.
Пару часов потратил на поиск готовых решений, проверку нескольких библиотек, тестирование классов на сложных строках с «подвохом». Библиотека, устраивающая по скорости работы, провалила тесты. Другая же не устраивала своей архитектурой и тормознутостью (каждый элемент json-объекта, даже простые числа, является отдельным экземпляром класса).
Да, я мог закрыть на что-то глаза, но я решил написать решение, которое устроило бы меня на 100%. В итоге, мой класс разбирает нужные мне json-строки почти в 10 раз быстрее, чем сторонний (на котором была возможность остановиться при поиске готового решения).
Возможно, дело в том, что я работаю на себя, поэтому заинтересован в качестве разрабатываемого продукта. В противном случае (к примеру, работая на вас =), мне целесообразнее было бы максимально быстро выполнять поставленные задачи, пуская пыль в глаза.
Пару часов потратил на поиск готовых решений, проверку нескольких библиотек, тестирование классов на сложных строках с «подвохом». Библиотека, устраивающая по скорости работы, провалила тесты. Другая же не устраивала своей архитектурой и тормознутостью (каждый элемент json-объекта, даже простые числа, является отдельным экземпляром класса).
Да, я мог закрыть на что-то глаза, но я решил написать решение, которое устроило бы меня на 100%. В итоге, мой класс разбирает нужные мне json-строки почти в 10 раз быстрее, чем сторонний (на котором была возможность остановиться при поиске готового решения).
Возможно, дело в том, что я работаю на себя, поэтому заинтересован в качестве разрабатываемого продукта. В противном случае (к примеру, работая на вас =), мне целесообразнее было бы максимально быстро выполнять поставленные задачи, пуская пыль в глаза.
>Возможно, дело в том, что я работаю на себя, поэтому заинтересован в качестве
>разрабатываемого продукта. В противном случае (к примеру, работая на вас =),
>мне целесообразнее было бы максимально быстро выполнять поставленные задачи,
>пуская пыль в глаза.
пускать пыль в глаза не надо :)
есть ТЗ, есть требования, если задача решена в рамках ТЗ и требования то это именно то что нужно. да, такое решение может быть далеким от идеального, но рынку не нужны идеальные решения, рынку нужны решения работающие
>Мне нужна была быстрая и надежная библиотека. Программе иногда приходится
>обрабатывать нескольких тысяч простых json-строк в секунду, поэтому быстродействие
>класса, работающего с json, играет роль.
в первом сообщение об этом ограничении не было ни слова, написали бы сразу и не пришлось бы разводить полемику :) согласен, бывают ситуации когда готовые решения не подходят по определенным критериям и приходится их дорабатывать или писать свои.
>разрабатываемого продукта. В противном случае (к примеру, работая на вас =),
>мне целесообразнее было бы максимально быстро выполнять поставленные задачи,
>пуская пыль в глаза.
пускать пыль в глаза не надо :)
есть ТЗ, есть требования, если задача решена в рамках ТЗ и требования то это именно то что нужно. да, такое решение может быть далеким от идеального, но рынку не нужны идеальные решения, рынку нужны решения работающие
>Мне нужна была быстрая и надежная библиотека. Программе иногда приходится
>обрабатывать нескольких тысяч простых json-строк в секунду, поэтому быстродействие
>класса, работающего с json, играет роль.
в первом сообщение об этом ограничении не было ни слова, написали бы сразу и не пришлось бы разводить полемику :) согласен, бывают ситуации когда готовые решения не подходят по определенным критериям и приходится их дорабатывать или писать свои.
Не:
1. «Просто найти» раскладывается на: найти, скачать, вкурить доку, попробовать, сравнить с другими.
2. Пункт 1 нужно повторить несколько раз для получения оптимального результата
3. Нужно учитывать контекст задачи и архитектуру найденных решений т.к. на вскидку могу предложить 2 практически противоположных случая — нужно парсить в абстрактный DOM и оттуда выдергивать нужное значение или нужно поднимать свою структуру объектов, для этого больше подходит событийный парсер без построения DOM.
4. Нужно учесть наличие готовых частей в проекте или наоборот, можно ли применить часть разрабатываемого для решения похожей проблемы в другой части системы.
5. Стоимость решения нельзя считать напрямую т.к. в случае ошибки и ликвидации/замены используемого нами стороннего решения таки придется дополнительно потратить деньги. Так же существует риск прекращения стороннего проекта.
На самом деле выбор между своим и сторонним весьма творческое занятие и простых решений тут нет. Самое главное — не впадать в крайности. И еще не экспериментировать в выпускаемом продукте.
1. «Просто найти» раскладывается на: найти, скачать, вкурить доку, попробовать, сравнить с другими.
2. Пункт 1 нужно повторить несколько раз для получения оптимального результата
3. Нужно учитывать контекст задачи и архитектуру найденных решений т.к. на вскидку могу предложить 2 практически противоположных случая — нужно парсить в абстрактный DOM и оттуда выдергивать нужное значение или нужно поднимать свою структуру объектов, для этого больше подходит событийный парсер без построения DOM.
4. Нужно учесть наличие готовых частей в проекте или наоборот, можно ли применить часть разрабатываемого для решения похожей проблемы в другой части системы.
5. Стоимость решения нельзя считать напрямую т.к. в случае ошибки и ликвидации/замены используемого нами стороннего решения таки придется дополнительно потратить деньги. Так же существует риск прекращения стороннего проекта.
На самом деле выбор между своим и сторонним весьма творческое занятие и простых решений тут нет. Самое главное — не впадать в крайности. И еще не экспериментировать в выпускаемом продукте.
Интересным моментом является следующее: можно отпарсить сразу весь json во внутреннее представление (так делали все классы, которые я успел посмотреть), а можно только верхний уровень, а потом уже углубляться по необходимости («углубление» происходит автоматически, незаметно для внешнего кода). Именно за счет этого мой класс работает на порядок быстрее (в конкретной программе, где крайне редко приходится обращаться ко всем вложенным элементам). При разборе очередного уровня, сложные объекты копируются «как есть» (в виде строки), а разбираются только при прямом обращении.
Тоже вариант — DOM с ленивым парсингом вложенных эленентов, однако тут тоже ведь нужно не просто так строку пропустить, а с учетом вложенности и т.п., да и весь JSON будет в памяти висеть. Мне больше нравится работать с событийными парсерами — экономия ресурсов и возможно обрабатывать огромные объемы, например сильно удобно при загрузке инфы в базу: DOM для миллиона записей построить можно, но несколько нецелесообразно, а вот по мере сборки нужной части данных сбрасывать ее в БД, освобождая память — самое то. А еще из событийного парсера генерить DOM — простая задача, а вот наоборот уже сложно.
п.1-5 в контексте «первого варианта постановки задачи» можно было не рассматривать, т.к. цель была читать/писать, отказ был продиктован наличием бага, анализ нескольких вариантов не упоминался.
все мои замечания относятся к «первому варианту», после уточнений о наличии жестких требований к быстродействию и отсутствии необходимости полного парсинга актуальность моего замечания резко упала до нуля.
естественно, сложность подбора готового решения сильно зависит от многих параметров и иногда на подбор может требоваться очень много времени, но в большинстве ситуаций, когда задача не является чем-то уникальным это время обычно меньше чем требуется на изготовление собственного.
З.Ы.: п.5 имеет смысл рассматривать в случаях когда конечный продукт не может включать в себя найденное решение целиком, если же у меня есть возможность встроить стороннюю либу, то как изменения которые в дальнейшем произойдут «где то там» могут повлиять на то что у меня уже есть «здесь»?
все мои замечания относятся к «первому варианту», после уточнений о наличии жестких требований к быстродействию и отсутствии необходимости полного парсинга актуальность моего замечания резко упала до нуля.
естественно, сложность подбора готового решения сильно зависит от многих параметров и иногда на подбор может требоваться очень много времени, но в большинстве ситуаций, когда задача не является чем-то уникальным это время обычно меньше чем требуется на изготовление собственного.
З.Ы.: п.5 имеет смысл рассматривать в случаях когда конечный продукт не может включать в себя найденное решение целиком, если же у меня есть возможность встроить стороннюю либу, то как изменения которые в дальнейшем произойдут «где то там» могут повлиять на то что у меня уже есть «здесь»?
На самом деле я стараюсь придерживаться той точки зрения, что у нас всегда есть 3 варианта: использовать чье-то готовое, придумать и написать свое и (достаточно редко рассматриваемый) написать свое по всем известному алгоритму или подходу. Плюс поиск решения должен начинаться с анализа того, что у нас уже есть, а не с поиска уже готового.
На самом деле в больших проектах в полный рост стоит проблема использования сторонних наработок т.к. просчитать последствия решения очень сложно и можно не только не получить желаемый результат, а поиметь массу проблем. Предположим у нас есть проект, в котором уже давно живет стороннее решение (обозначим его А) строго определенной задачи, нам нужно реализовать доп. функции, которые есть в готовом стороннем решении (назовем его Б), но это готовое решение использует другую наработку (назовем ее В), которая полностью повторяет решение А, и пусть даже они не конфликтуют, тогда у нас получается куча вариантов:
1. Развести зоопарк — в проекте будут решения А, Б и В, тогда нам нужно строго регламентировать использование решений А и В, иначе получим проблемы. Так же нам нужно конфигурить при установке оба практически одинаковых решения, что может повлечь ошибки.
2. Если можно, то заменяем решение А на решение В с переписыванием соответствующих частей, в проекте останется решения Б и В.
3. Можно попытаться решение Б заставить работать не с В, а с решением А.
4. Можно попытаться написать аналог решения Б, но с учетом использования нами решения А, после чего выложить его в свободный доступ и еще чуть-чуть увеличить хаос.
Есть, конечно, решения, которые самому писать нецелесообразно по причине огромного объема работ, или попытаться заменить широко используемые решения. Я не думаю, что целесообразно писать что-то свое для работы (например) с ЭЦП, работы с SMTP или Jabber протоколами или парсер XLS файлов (или совсем для одержимых — свою реализацию VM), однако написать парсер JSON или логгер под конкретную задачу в строго определенном контексте — почему бы и нет.
Как я уже говорил: самое главное — не впадать в крайности.
На самом деле в больших проектах в полный рост стоит проблема использования сторонних наработок т.к. просчитать последствия решения очень сложно и можно не только не получить желаемый результат, а поиметь массу проблем. Предположим у нас есть проект, в котором уже давно живет стороннее решение (обозначим его А) строго определенной задачи, нам нужно реализовать доп. функции, которые есть в готовом стороннем решении (назовем его Б), но это готовое решение использует другую наработку (назовем ее В), которая полностью повторяет решение А, и пусть даже они не конфликтуют, тогда у нас получается куча вариантов:
1. Развести зоопарк — в проекте будут решения А, Б и В, тогда нам нужно строго регламентировать использование решений А и В, иначе получим проблемы. Так же нам нужно конфигурить при установке оба практически одинаковых решения, что может повлечь ошибки.
2. Если можно, то заменяем решение А на решение В с переписыванием соответствующих частей, в проекте останется решения Б и В.
3. Можно попытаться решение Б заставить работать не с В, а с решением А.
4. Можно попытаться написать аналог решения Б, но с учетом использования нами решения А, после чего выложить его в свободный доступ и еще чуть-чуть увеличить хаос.
Есть, конечно, решения, которые самому писать нецелесообразно по причине огромного объема работ, или попытаться заменить широко используемые решения. Я не думаю, что целесообразно писать что-то свое для работы (например) с ЭЦП, работы с SMTP или Jabber протоколами или парсер XLS файлов (или совсем для одержимых — свою реализацию VM), однако написать парсер JSON или логгер под конкретную задачу в строго определенном контексте — почему бы и нет.
Как я уже говорил: самое главное — не впадать в крайности.
Потом вам понадобилось добавить немного функций и проверок в вашу библиотеку, потом еще немного и она разрослась. Вы ее выложили в интернет из добрых побуждений. Кто-то скачал, посмотрел, нашел багу и пошел писать свой маленький скрипт…
Все мы так или иначе стандартизируемся. Под рабочее место как минимум.
Если очень хочется поддерживать себя в форме — придётся тратить на это дополнительное время. Перед тем как начать, стоит чётко понять: а нужно ли оно Вам?
Если очень хочется поддерживать себя в форме — придётся тратить на это дополнительное время. Перед тем как начать, стоит чётко понять: а нужно ли оно Вам?
Хороший вопрос. Я пока не могу на него ответить. С одной стороны, как инженер я посредственность. То есть я не плох, но лучшим стать мне явно не суждено. Я знаю прекрасных инженеров из того же Microsoft и мне до их уровня, как до Альфы Центавра. Поэтому повышать свой профессиональный уровень мне выгоднее в ширину — то есть изучать больше стандартных библиотек.
С другой стороны Microsoft бросил мне вызов. Который я, как бы, принял. Отступить на половине пути считаю малодушием. :)
С другой стороны Microsoft бросил мне вызов. Который я, как бы, принял. Отступить на половине пути считаю малодушием. :)
У Вас в резюме написано, что Вы позиционируете себя не только как программист, но и как менеджер небольшого проекта. Как мне кажется, «олимпиадные» задачки на собеседовании на неруководящую позицию сработали для Вас в качестве фильтра на излишнюю амбициозность. Ну то есть Ваших способностей и навыков хватает их решать, но пресловутое «Зачем?», очень мне близкое, мешает это делать.
У меня это из-за фриланса и постоянного контакта с конечными пользователями. При виде абстрактной задачи, которая не учитывает реальных условий окружающего мира, всегда хочется воскликнуть Ваше «Зачем?». И я не понимаю, почему здесь на хабре все так восторгаются Petr с топкодера и прочими чемпионами олимпиад по программированию.
Для людей с менеджерскими задатками, но которые при этом любят программировать, единственный способ попасть в компании уровня Google, Apple или Microsoft, как по мне — это создать стартап и продать его. Плюс после этого место в корпоративной иерархии будет выше, чем куда бы можно было добраться с помощью карьеры.
У меня это из-за фриланса и постоянного контакта с конечными пользователями. При виде абстрактной задачи, которая не учитывает реальных условий окружающего мира, всегда хочется воскликнуть Ваше «Зачем?». И я не понимаю, почему здесь на хабре все так восторгаются Petr с топкодера и прочими чемпионами олимпиад по программированию.
Для людей с менеджерскими задатками, но которые при этом любят программировать, единственный способ попасть в компании уровня Google, Apple или Microsoft, как по мне — это создать стартап и продать его. Плюс после этого место в корпоративной иерархии будет выше, чем куда бы можно было добраться с помощью карьеры.
Я в данный момент как раз стараюсь делать упор на принятие правильных управленческих решений. Это получается не всегда, потому что гиковская (инженерная) жилка зачастую одерживает верх.
И восхищаются topcoder-ом, я полагаю, по большей части именно люди с инженерным складом ума.
Занять руководящую должность в гиганте можно. Я знаю по крайней мере одного человека, которому это удалось. (Правда, он стоял у истоков стартапа, в котором я сейчас работаю. Но продать этот стартап пока не удалось вообще никому. Потом совет директоров его уволил и он пошёл работать в Microsoft.) На эти должности тоже набирают людей для которых тоже проводят собеседования, задают вопросы. Но они кардинально отличаются от вопросов для соискателей на инженерные позиции.
И восхищаются topcoder-ом, я полагаю, по большей части именно люди с инженерным складом ума.
Занять руководящую должность в гиганте можно. Я знаю по крайней мере одного человека, которому это удалось. (Правда, он стоял у истоков стартапа, в котором я сейчас работаю. Но продать этот стартап пока не удалось вообще никому. Потом совет директоров его уволил и он пошёл работать в Microsoft.) На эти должности тоже набирают людей для которых тоже проводят собеседования, задают вопросы. Но они кардинально отличаются от вопросов для соискателей на инженерные позиции.
О, на хабре ими еще не так восторгаются, как ими должно и подобает восторгаться! В основном потому, что как раз они умеют думать, а не ограничиваются применением стандартных шаблонов для решения стандартных задач. Кстати, где ими действительно восторгаются — так это в компаниях типа Гугла и Микрософта. Наверно, все-таки что-то в них есть, а?
Вы, Мария, кажется не правильно меня поняли. Я не утверждал, что такие инженеры не достойны восхищения. Я говорил о том, что мне административные задачи оказались ближе к сердцу, чем инженерные.
И безусловно в них что-то есть.
И безусловно в них что-то есть.
Да нет, как раз вас я поняла правильно, и ваш подход имеет право на жизнь. По задумке, я комментила товарища rubyman
Возиожно, погорячилась в формулировании (и определенно забыла указать в комменте цитату), но это простительно — я-то чемпионами восхищаюсь искренне и от души :-)
И я не понимаю, почему здесь на хабре все так восторгаются Petr с топкодера и прочими чемпионами олимпиад по программированию.
Возиожно, погорячилась в формулировании (и определенно забыла указать в комменте цитату), но это простительно — я-то чемпионами восхищаюсь искренне и от души :-)
Я поставил Вам плюсик, потому что согласен с Вами в том, что есть задачи, часто очень важные, решение которых «по зубам» только специалистам, имеющим «олимпиадную» подготовку. Насколько я знаю, например, инженерная верхушка Яндекса, за исключением основателей и около того, состоит из «олимпиадников».
Да, не сочтите за harassment, первый раз приходится участвовать в дискуссии с девушкой на технические-бизнес темы. Возможно, сейчас единственный раз в жизни я сожалею, что сам не чемпион олимпиад по программированию. =))
Вот по сути, я очень далек от спортивного программирования, но видел задачи от ACM и именно они мне кажутся «применением стандартных шаблонов для решения стандартных задач». Да, я сам могу делать CRUD web-сайт в этот момент, это еще более «стандартно» и еще больше пахнет «индусятиной». Но мне вот кажется, что то, о чем говорят на Hacker News — это более сложные задачи, плюс там очень много по-настоящему умных людей. Даже есть брать самый последний аргумент в любом споре, насколько социум принимает людей с HN (не забываем про Перельмана) — там куда не плюнь — в миллионера попадешь. =))
Кстати, а раз Вы живете на Украине и занимаетесь спортивным программированием, то может вы знаете kit?
Да, не сочтите за harassment, первый раз приходится участвовать в дискуссии с девушкой на технические-бизнес темы. Возможно, сейчас единственный раз в жизни я сожалею, что сам не чемпион олимпиад по программированию. =))
Вот по сути, я очень далек от спортивного программирования, но видел задачи от ACM и именно они мне кажутся «применением стандартных шаблонов для решения стандартных задач». Да, я сам могу делать CRUD web-сайт в этот момент, это еще более «стандартно» и еще больше пахнет «индусятиной». Но мне вот кажется, что то, о чем говорят на Hacker News — это более сложные задачи, плюс там очень много по-настоящему умных людей. Даже есть брать самый последний аргумент в любом споре, насколько социум принимает людей с HN (не забываем про Перельмана) — там куда не плюнь — в миллионера попадешь. =))
Кстати, а раз Вы живете на Украине и занимаетесь спортивным программированием, то может вы знаете kit?
Про Яндекс — согласна; сейчас они спонсируют ТСО и набирают людей оттуда с ограничением по рейтингу, в переводе с чисел — уровня Топ-300 алгоритмистов по миру.
Не сочту :-) Я ж не американка, для меня harassment — это скорее «с шибко умной девкой все лучше на сеновале разговаривать» :-)
Более растяжимое понятие «стандартного шаблона». Например, динамическое программирование — вроде бы стандартный шаблон, но настолько высокоуровневый, что его применение к задачам, хотя бы минимально отличающимся от базовых — это уже целое искусство, которое многие не способны освоить в принципе.
Знаю, конечно, это он меня сюда привел. А что?
Не сочту :-) Я ж не американка, для меня harassment — это скорее «с шибко умной девкой все лучше на сеновале разговаривать» :-)
Более растяжимое понятие «стандартного шаблона». Например, динамическое программирование — вроде бы стандартный шаблон, но настолько высокоуровневый, что его применение к задачам, хотя бы минимально отличающимся от базовых — это уже целое искусство, которое многие не способны освоить в принципе.
Знаю, конечно, это он меня сюда привел. А что?
НЛО прилетело и опубликовало эту надпись здесь
не обязательно у каждого повара должен быть свой способ варить яйцо. Используя стандартные библиотеки можно сделать что-то более высокого уровня, автор абсолютно прав, я считаю.
НЛО прилетело и опубликовало эту надпись здесь
Я бы несколько расширил аналогию — просто повара покупают продукты в магазине. Хорошие повора покупают свежие продукты на деревенском рынке, выбирая все самое свежее. Отличные повара, бывает, выращивают продукты сами по мере сил.
НЛО прилетело и опубликовало эту надпись здесь
отличные повара продукты никогда не выращивают, что за бред. так же как архитекторы никогда не пишут стандартного кода. более того, иногда архитекторы вообще кода не пишут, но это не мешает им оставаться высококлассными спецами.
подход автора считаю очень правильным и рефлексы по поводу необходимости изобретать велосипеды — абсолютно ненужными.
более того, если внимательно посмотреть, то интервью против такого подхода никак не выступает, и поэтому должен сказать, что автор делает неправильные выводы.
подход автора считаю очень правильным и рефлексы по поводу необходимости изобретать велосипеды — абсолютно ненужными.
более того, если внимательно посмотреть, то интервью против такого подхода никак не выступает, и поэтому должен сказать, что автор делает неправильные выводы.
Ну автор топика прав в том смысле, что чтобы писать самому что-то уже реализованное, нужна причина. Ей могут быть: стандартные решение не готово к промышленному использованию, оно платное а мы жадные или оно нас не удовлетворяет в части некоторых своих функций/показателей.
Если такой причины нет, лучше и дешевле взять готовое. Работа программиста ведь не в том, чтобы все написать, а чтобы в заданный бюджет реализовать максимально качественное/быстрое решение.
Если такой причины нет, лучше и дешевле взять готовое. Работа программиста ведь не в том, чтобы все написать, а чтобы в заданный бюджет реализовать максимально качественное/быстрое решение.
Почему-то все тут разделяют «стандартные решения» и «самописные». Все эти «стандартные решения» обычно open source, и если что-то в них не нравится — лучше исправить/дописать и помочь проекту (ну если он хороший, конечно, и почти устраивает, если там здравые вещи есть), а не делать свой велосипед с 0, писать в десятый раз никому не нужный код, напарываясь на разные грабли и обитая исключительно в своем личном болотце. В эпоху гитхабов, битбакетов и ланчпадов это все довольно просто, коммуникации упрощены до предела.
Особенно люто я ненавидел выпускников мехмата и бывших олимпиадников.
True, true…
Я непротив нестандартности и интересных идей, но в умеренных количествах. Вообще разработка похожа на строительство. У кого-то из кирпичей получается лачуга, у кого-то из тех же самых кирпичей шикарный дворец, а кто-то эти кирпичи сперва сам изготавливает.
За статью спасибо.
Этот шикарный дворец шикарно будет рушиться, если не знать о свойствах кирпичей, и не представлять себе, из чего они и как сделаны.
Тоже верно. Тут в комментариях народ пришел к общему мнению, что в большинстве случаев все-таки лучше готовыми решениями, однако знать, как они работют (смотреть их код).
Есть еще одна интересная задача на «подумать».
Дан массив длинны от N. Можно найти в нем минимум и максимум простым способом:
Несложно посчитать, что программа будет производить 2*n сравнений.
Можно ли решить задачу за меньшее число сравнений?
Дан массив длинны от 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].
Как-то так. Сейчас я не очень хорошо соображаю, так что может тут и косяк какой в логике, да и с числом сравнений не понятно.
Кроме того, пора домой уже, кажется :)
Не уверен, что это правильный способ, но может быть сработает что-то типа:
Допустим, массив состоит из трех частей:
(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].
Как-то так. Сейчас я не очень хорошо соображаю, так что может тут и косяк какой в логике, да и с числом сравнений не понятно.
Кроме того, пора домой уже, кажется :)
else воткнуть
Зачем менять местами? Абсолютно лишняя операция. Достаточно знать индекс максимума. Решение тоже самое что и это, только без присваиваний и лишнего второго цикла.
Вы забываете, что каждый обмен местами — это 3 операции присваивания ( tmp = a[i]; a[i] = a[i+1]; a[i+1] = tmp; ) вместо одного (max = i). Кроме того, мы получаем еще один цикл for, короче на 1, и пропускаем одну проверку.
Не буду считать операции, но изначальный вариант + else выглядит самым быстрым.
Не буду считать операции, но изначальный вариант + else выглядит самым быстрым.
в условиях задачи речь шла именно о минимальном числе проверок. Да и в реальной жизни может встретиться ситуация, когда каждая проверка стоит очень дорого, по сравнению с другими операциями.
Да, тут границы не ясны. Я решал, считая все операции равноценными. Так можно сразу несколько задач сделать: если сравнение элементов во много раз затратней всех остальных операций; если они равноценны; если переприсвоение намного затратней…
Тогда есть еще одно решение. В первом проходе запомнить индекс максимального. Во втором перед сравнением проверять по индексу, не максимальный ли мы сравниваем.
Тогда есть еще одно решение. В первом проходе запомнить индекс максимального. Во втором перед сравнением проверять по индексу, не максимальный ли мы сравниваем.
Навскидку, если число больше какого-то другого, оно не может быть минимумом, поэтому:
for(i = 0; i < n; ++i)
{
if(a[i] > a[max]) max = i;
else
if(a[i] < a[min]) min = i;
}не будет работать, если массив отсортирован по возрастанию
Да, получается немного быстрее — 2 * n — 1 в худшем и n в лучшем случае.
А можно сделать еще быстрее?
А можно сделать еще быстрее?
найти максимум а потом исключить его из поиска минимума= -1 проверка.
Вот так вот и вербуют в К.
qsort()
n * log n
n * log n
идём с друх концов. делаем n/2+1 сравнение, после чего большие части ззаписываем в начало массива, меньшие в конец.
После чего в первой половине массива будет максимальный.
Это n/2+1 сравнение.
И то же самое в нижней.
n/2+1
итого 3n/2+3 сравнения. Возможно даже на пару меньше, но это нужно рассматривать случаи чётной и нечётной длинны, что неинтересно.
btw, а проверку i<n в цикле мы почему не считаем за проверку?
После чего в первой половине массива будет максимальный.
Это n/2+1 сравнение.
И то же самое в нижней.
n/2+1
итого 3n/2+3 сравнения. Возможно даже на пару меньше, но это нужно рассматривать случаи чётной и нечётной длинны, что неинтересно.
btw, а проверку i<n в цикле мы почему не считаем за проверку?
Поздравляю, это правильное решение, правда немного извращенное, от чего и появились «лишние» +3.
Основная идея верна — мы должны сравнить два элемента, и больший из них сравнивать с максимумом, а меньший — с минимумом. Тогда коэффициент при N получится 3/2 — на каждые два элемента мы тратим три сравнения.
Мое решение делало эту же идею, только «в лоб»:
i<n я не учитывал из практических соображений — сравнение интов происходит быстро, в то время как сравнение произвольных объектов может происходить очень долго. Но если i учитывать, то Ваше решение делает 3n/2 сравнений с i, а мое — n/2 :)
Основная идея верна — мы должны сравнить два элемента, и больший из них сравнивать с максимумом, а меньший — с минимумом. Тогда коэффициент при 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) если 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 сравнений, включая проверку условия цикла
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х сравнений.
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, и никуда от этого не деться…
И я в маршрутке немного прикинул, какие есть варианты комбинировать операции — ничего лучше 3/2 N не выходит.
Собственно, за первые N/2 операций мы разделяем числа на множества бОльших и меньших, каждое размером N/2, а потом в одном ищем только минимум, во втором только максимум, за N/2 операций в каждой части. Итого 3/2 N, и никуда от этого не деться…
www.coranac.com/documents/bittrick/
Пункт 2.4 Branchless min/max
Т.е. можно сделать за 0 сравнений. Это трюк в чистом виде, программировать так надо очень-очень редко, но для общего развития знать надо.
Пункт 2.4 Branchless min/max
Т.е. можно сделать за 0 сравнений. Это трюк в чистом виде, программировать так надо очень-очень редко, но для общего развития знать надо.
С практической точки зрения такая задача вреданая. Чем меньше зависимостей в коде, тем быстрее суперскаляр выполняет код. Так что все предложенные ниже решения, скорее всего, будут выполняться дольше и потреблять больше электроэнергии.
Я для себя эту проблему решаю так: стараюсь разбираться, как работают библиотеки, которые я использую. Конечно, хитрым математическим алгоритмам это не научит, но и думать не разучусь, и свое при условии специфичных требований смогу написать.
На самом деле вы всё делаете правильно. Ну кроме того что забыли алгоритмы — забывать их не нужно и вредно.
Но самописные решения на коленке в 80 процентах случаев будут хуже открытых «стандартных» аналогов и технологий, в которых кто-то поленился разбиратся, и решил написать вместо них велосипед.
Не так давно в нете были статьи по поводу «никто из программистов не хочет разбиратся в нашем програмном решении — все сволочи предлагают переписать с нуля! как быть?»
Эта проблема особо актуальна для самописных решений. В мире есть сотни тысяч разработчиков, знакомых с «стандартными» откртыми и не очень решениями и технологиями, которые могут в считанные дни влится в проект, на таких решениях построеный. Никто не переозобретает джаву, XML, SOAP, WSDL, поэтому никто не переизобретает DOM, SAX, JAX-WS и т.п.
Особенно это касается вещей вроде дотнета и джавы — богатых платформ, для которых существуют сотни распространённых решений, одних только открытых от разкиданих по сорсфоржу библиотек и Jakarta Commons до технологий от Spring и т.п. Решения с открытым кодом часто отточены, оттестированы и «вылизаны» до такой степени, что на написание и тестирование самописного аналога уйдут если не годы то месяцы точно.
Другое дело, что иногда стоит полезть и самому в код используемого решения (а иногда это даже приходится делать, потому что что-то работает не так как надо, или не работает вообще, а «спрыгивать» на другие решения уже поздно). Это очень полезно. Научится програмировать можно только читая код — я так считаю.
Но самописные решения на коленке в 80 процентах случаев будут хуже открытых «стандартных» аналогов и технологий, в которых кто-то поленился разбиратся, и решил написать вместо них велосипед.
Не так давно в нете были статьи по поводу «никто из программистов не хочет разбиратся в нашем програмном решении — все сволочи предлагают переписать с нуля! как быть?»
Эта проблема особо актуальна для самописных решений. В мире есть сотни тысяч разработчиков, знакомых с «стандартными» откртыми и не очень решениями и технологиями, которые могут в считанные дни влится в проект, на таких решениях построеный. Никто не переозобретает джаву, XML, SOAP, WSDL, поэтому никто не переизобретает DOM, SAX, JAX-WS и т.п.
Особенно это касается вещей вроде дотнета и джавы — богатых платформ, для которых существуют сотни распространённых решений, одних только открытых от разкиданих по сорсфоржу библиотек и Jakarta Commons до технологий от Spring и т.п. Решения с открытым кодом часто отточены, оттестированы и «вылизаны» до такой степени, что на написание и тестирование самописного аналога уйдут если не годы то месяцы точно.
Другое дело, что иногда стоит полезть и самому в код используемого решения (а иногда это даже приходится делать, потому что что-то работает не так как надо, или не работает вообще, а «спрыгивать» на другие решения уже поздно). Это очень полезно. Научится програмировать можно только читая код — я так считаю.
Обожаю копаться в исходниках библиотек.
Алгоритмы (наверное, большую часть из того, чему меня научили на курсе дискретной математики, которую я сдал с четвёртого раза) я не забыл. Я всё ещё помню что такое бинарная и пирамидальная сортировка, бинарное и красно-чёрное дерево. Но я утратил навык изобретать новые алгоритмы на вскидку.
В остальном, подписываюсь под каждым словом. По иронии судьбы, сейчас я работаю над проектом, состоящем сплошь из велосипедов. Проект реализован на Java. :) Правда, заложен проект был 10 лет назад. Наверное, тогда Java не была на столько богата библиотеками.
В остальном, подписываюсь под каждым словом. По иронии судьбы, сейчас я работаю над проектом, состоящем сплошь из велосипедов. Проект реализован на Java. :) Правда, заложен проект был 10 лет назад. Наверное, тогда Java не была на столько богата библиотеками.
> Правда, заложен проект был 10 лет назад.
> Наверное, тогда Java не была на столько богата библиотеками.
Предпочитаю слово «решение», т.к. вещи вроде Томкета, Глассфиша или OSGI-контейнеров наприме это уже не библиотеки, но в остальном согласен абсолютно — 10 лет назад Джава как палтформа не была настолько богатой как теперь (тем более дотнет). Например первая версия Spring IoC датируется 2002-м годом согласно Википедии.
> Наверное, тогда Java не была на столько богата библиотеками.
Предпочитаю слово «решение», т.к. вещи вроде Томкета, Глассфиша или OSGI-контейнеров наприме это уже не библиотеки, но в остальном согласен абсолютно — 10 лет назад Джава как палтформа не была настолько богатой как теперь (тем более дотнет). Например первая версия Spring IoC датируется 2002-м годом согласно Википедии.
Вот вы все время говорите о какой-то бинарной сортировке. Никогда не слышал про такую. Проясните?
не читал каменты, так на всякий случай.
про массив из a[n], было ли ограничение на тип данных в котором будет результат произведения хранится? можно ли было определить свой тип данных? тип int подразумевает то что хранятся отрицательные числа тоже или же это просто огрех при составлении задачки? присутствует ли число ноль, как элемент массива? скольки разрядный int?
возможное решение — определить свой тип данных uint64, в случае если хранятся отрицательные числа, выбрать четное количество наименьших отрицательных чисел и все положительные(обратить внимание на не включение нуля), если же все положительные — выбрать наименьшее и отбросить его.
вы молодец что старались, от себя могу пожелать решать интересные задачи — что будет очень полезно :) в интернете их полно к примеру классическая задача, которую дают в SPB Software :) ну и в конце-концов воспитывая в себе свободу мышления, возможно будет с временем формировать большое количество решений.
к тому же — так как вы изучаете много технологий, смотрите в их суть, и тогда будет все очень предельно понятно с остальными задачами.
успехов :)
про массив из a[n], было ли ограничение на тип данных в котором будет результат произведения хранится? можно ли было определить свой тип данных? тип int подразумевает то что хранятся отрицательные числа тоже или же это просто огрех при составлении задачки? присутствует ли число ноль, как элемент массива? скольки разрядный int?
возможное решение — определить свой тип данных uint64, в случае если хранятся отрицательные числа, выбрать четное количество наименьших отрицательных чисел и все положительные(обратить внимание на не включение нуля), если же все положительные — выбрать наименьшее и отбросить его.
вы молодец что старались, от себя могу пожелать решать интересные задачи — что будет очень полезно :) в интернете их полно к примеру классическая задача, которую дают в SPB Software :) ну и в конце-концов воспитывая в себе свободу мышления, возможно будет с временем формировать большое количество решений.
к тому же — так как вы изучаете много технологий, смотрите в их суть, и тогда будет все очень предельно понятно с остальными задачами.
успехов :)
За советы и пожелания спасибо.
Но комменты всё же лучше прочитать. Там есть ответы на все ваши вопросы.
Но комменты всё же лучше прочитать. Там есть ответы на все ваши вопросы.
по минусам уже понял :) времени было жалко, да и зачем-то решил как-то поразмышлять вслух, для кого — сам не понимаю :)
не останавливайтесь на микрософте.
главное есть опыт решения стандартных задач, а если действительно хочется развиваться и пойти работать в большую компанию с нестандартными задачами на интервью, то по вечерам можно заниматься решением разных задач, хотя бы по 2 часа в день — не так уж и много. гимнастика ума :))
ну а просто развивать не стандартное мышление можно чем-нибудь типа: braingames.ru
в конце-концов типов головоломок тоже конечное множество, и их тоже можно научиться решать :)
не останавливайтесь на достигнутом, не успешный опыт- один из самых ценных опытов :)
не останавливайтесь на микрософте.
главное есть опыт решения стандартных задач, а если действительно хочется развиваться и пойти работать в большую компанию с нестандартными задачами на интервью, то по вечерам можно заниматься решением разных задач, хотя бы по 2 часа в день — не так уж и много. гимнастика ума :))
ну а просто развивать не стандартное мышление можно чем-нибудь типа: braingames.ru
в конце-концов типов головоломок тоже конечное множество, и их тоже можно научиться решать :)
не останавливайтесь на достигнутом, не успешный опыт- один из самых ценных опытов :)
Уберите слово «программист». Этот пост на 99% касается и системного администрирования. Чем меньше в созданной системе «полёта фантазии», тем эта система лучше.
Думаю, то же может сказать и инженер про конструкцию моста (там, правда, легче, потому что всякая херня быстрее падает и её не восстанавливают каждую неделю с матюгами).
Думаю, то же может сказать и инженер про конструкцию моста (там, правда, легче, потому что всякая херня быстрее падает и её не восстанавливают каждую неделю с матюгами).
Я как админ тоже самое подмечаю за собой.
Я считаю что это не плохо, это просто другой уровень.
Когда работаешь с десятками различных систем различного назначения, унификация — единственный способ сохранить остатки разума (а раз в админы пошел, значит его и так немного ;)).
Я считаю что это не плохо, это просто другой уровень.
Когда работаешь с десятками различных систем различного назначения, унификация — единственный способ сохранить остатки разума (а раз в админы пошел, значит его и так немного ;)).
А я что-то сначала не очень внимательно прочитал, и решил, что задача формулируется так:
Вот это действительно достаточно сложная и интересная задачка :).
Идея решения очень простая, и для простоты рассмотрим случай с положительными элементами:
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 будет найдена не самая лучшая последовательность (в смысле максимизации произведения) из-за того, что я мог не учесть ещё какие-то варианты :). Но, в целом, алгоритм должен быть такой. И реализовать его тоже не очень сложно :).
Имеется массив 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). Хуже чем в простейшем алгоритме, описанном вы
Стандартный программист