Задача: в массиве длиной N найти элемент, который повторяется больше N/2 раз.

Казалось бы, чего тут думать? Возьмём Dictionary<значение элемента, число появлений>, за один проход по массиву сосчитаем появления каждого элемента, потом выберем из словаря искомый элемент. Решение за O(N), куда может быть ещё быстрее?

Есть один нюанс: для словаря нам потребуется O(N) дополнительной памяти — в несколько раз больше размера исходного массива, и это при реализации словаря хоть хэш-таблицей, хоть деревом. Что будем делать, если наша цель — обработка сигнала неким устройством с маленькой памятью? Массив — замеры уровня сигнала, из которых один — «настоящий» передаваемый уровень, а остальные — шум и помехи. Неужели придётся для определения «настоящего» уровня возиться с хэш-таблицами и деревьями?

К счастью, нет: достаточно O(1) дополнительной памяти, и по-прежнему одного прохода по массиву.

Одиннадцатого декабря прошлого года вышел бюллетень Microsoft, связанный с уязвимостью, обнаруженной в Microsoft File Handling Component. Уязвимости был присвоен ранг критической и категория Remote code execution. Удаленное выполнение кода происходит при открытии жертвой общего сетевого ресурса с содержимым, сформированным злоумышленником особым образом. Подробности эксплуатации приводятся в данном отчете.

Результаты, были получены на Windows XP SP3 x86. Сама уязвимость находится в функциях FindFirstFileExW и FindNextFileExW библиотеки kernel32.dll, которые осуществляют копирование данных, полученных из нативной функции NtQueryDirectoryFile, с помощью memmove. Проблема заключается в том, что в качестве размера буфера-источника для функции копирования передается число, полученное из NtQueryDirectoryFile, хотя возможна ситуация, при которой размер буфера-приемника может быть меньше, чем результат выдачи NtQueryDirectoryFile.

Влияние данной уязвимости распространяется на все приложения, использующие функции семейства FindFirstFile/FindNextFile. Первым таким приложением, которое пришло мне в голову, было explorer.exe. Для эксплуатации злоумышленнику достаточно будет заставить пользователя открыть ссылку на зловредный ресурс, и при удачном исходе он сможет получить возможность исполнить код с правами пользователя, открывшего ссылку. Сценарий удаленной эксплуатации, как подсказывает раздел FAQ бюллетеня Microsoft, возможен через UNC share или через WebDAV-путь. Путь UNC (Universal Naming Convention) может указывать на сетевой ресурс обмена файлами, который работает на основе протокола SMB. Для теста был выбран Linux с сервисом Samba, который позволяет создавать «расшаренные» папки на основе этого протокола. В итоге хотелось смоделировать следующую схему удаленной атаки.

Наша команда занимается удаленным администрированием серверов и не так давно к нам обратились представители сервиса WebConsult с задачей построить легко масштабируемую серверную архитектуру, которая будет выдерживать серьезные нагрузки. Мы решили, что возможно это будет интересно пользователям Хабрахабра, которые так или иначе связаны с администрированием Highload проектов. Проект оказался быстрорастущим и имеющаяся на тот момент структура уже работала на пределе, поэтому нам пришлось в ускоренном режиме запускать новую.

Недавно наткнулся на ошибку в Android приложении Яндекс.Метро. Если бы был чемпионкой мира по синхронному плаванию, то обязательно спросил бы: «Кто создавал программу „для галочки“? Кто работал „на отшибись“? Кто слабое звено?». Недоумение вызывала не сама ошибка, а то, что она попала в приложение и всё ещё не исправлена.

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

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

В статье же мы будем рассматривать распространённые приложения, которые протестировать может любой участник команды. Давайте проведём небольшой эксперимент. Если у вас нет Android устройства, то попросите минут на десять у коллег или друзей. Скачайте приложение Яндекс.Метро и попробуйте его протестировать. Интересует актуальная на текущий момент версия 1.63 от 02.11.2012 сборка 159 (на Google Play стоит дата 21.01.2013). Для корректности проверки предлагаю снять галочку «Автообновление» в настройках Google Play.

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

Эта же ошибка может проявить себя не так явно:

Тихим утром третьего января, когда Москва уже дремала после новогодних праздников, в нашей квартире раздался звонок в дверь. Почта наконец-то доставила посылку с новогодними подарками, заказанными на Амазоне. Среди прочего в ней находился и подарок для сына — электронный питомец Furby. Покупка его была, в общем-то импульсной. Игрушка значилась в бестселлерах новогоднего сезона и стоила относительно недорого. В сортах Furby я не разбирался, но когда-то давно что-то позитивное об игрушке слышал.

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

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



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

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



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

Посмотрим как они выкрутятся?

Опять на собеседованиях по Java спрашивают про hashCode и equals? А кто из собеседующих сам ответит на вопрос, как вычисляется Object.hashCode() и System.identityHashCode()? Насколько дорог вызов этих методов? Как их можно ускорить в HotSpot JVM? Держу пари, едва ли кто даст правильный ответ. Разве что, кто прочитает эту статью.

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

TL;DR
Эта обзорная статья. Такое себе "краткое содержание предыдущих серий". Она будет полезна для новичков, или тех, кто не следил за отраслью в последнее время. Для новичков это будет первый шаг во "Вселенную JavaScript", бывалые смогут освежить свои знания.

У JavaScript очень удивительная судьба. Он преодолел путь от самого не понимаемого до самого удивительного языка. У него было тяжелое детство:
Изначально Автор хотел написать функциональный язык. Но менеджеры хотели получить, «обычный» объектно-ориентированный. И чтобы было легко искать разработчиков для новоиспеченного языка синтаксис решили сделать похожим на Java и даже название сделали похожим.
Но на этом история не заканчивается. Java, JavaScript это торговые марки Sun (а теперь Oracle). Microsoft не мог воспользоваться именем JavaScript (Netcape и Sun дружили против Microsoft). В результате Microsoft решил сделать реверс инжиниринг JavaScript и назвал его JScript. Сделали реверс инжиниринг, и сделали его настолько хорошо, что даже содрали все баги в реализации. Позже решили сделать стандарт и назвали его ECMAScript.

После приобретения компанией Mail.ru некогда популярного сервиса обмена сообщениями ICQ был изменен способ передачи файлов между пользователями мессенджера. Если раньше файлы пересылались напрямую между отправителем и получателем, то сейчас отправитель закачивает файл на сервер компании, а получатель скачивает его по публичной ссылке. Ссылка на файл имеет вид http://files.icq.net/files/get?fileId=XXXXXX и для получения доступа к закачанному на сервер файлу необходимо знать только её, так как никаких мер, обеспечивающих ограничение доступа к файлу, не предпринимается. Поскольку динамически генерируемая часть ссылки состоит всего из шести символов (цифры или английские буквы в верхнем регистре), это дает возможность получения доступа ко всему архиву переданных в последнее время через ICQ файлов методом перебора. Несложно подсчитать, что всего таким образом доступно чуть более двух миллиардов комбинаций.

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

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

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

Если вы нашли себя — поделитесь в комментариях!

Добрый день хабр. В статье я расскажу, как используя синтаксис php, можно написать функцию для вывода переданной ей строковой переменной, не использующую в своем теле символы «a-zA-Z0-9<>?»

Вообще на хабре уже проскальзывали ссылки на статьи об использовании undefined variable, так что ничего нового я скорее всего не открою.

Я прочитал пост «13 причин не быть управленцем» и хочу написать ответ.

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

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

Весь вопрос в том, чтобы освоить азы профессии, и если она нравится — ей и нужно заниматься. Если нет — пробовать себя в чем-то другом.

Поэтому универсальных советов нет, каждому нужно искать свое дело.

Это было предисловие, а теперь про плюшки работы управленцем.

Итак, что в управлении проектами круто.

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

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

А сейчас, в период между Рождеством и Новым Годом, когда особенно обострена склонность к углублённой рефлексии, приходит понимание того, что, знай я некоторые «инсайдерские» подробности управленческой деятельности заранее – сделал бы совсем другой выбор лет эдак семь назад.

Вот поэтому и родился этот немного хаотичный и очень разнокалиберный список моментов, которые очень хотелось бы передать куда-то обратно, примерно в 2005 год – дайте знать, если кто-то вдруг уже научился это делать! А пока, может быть кто-то найдёт некоторые из перечисленных ниже пунктов не до конца очевидными, или даже полезными для себя; было бы приятно осознавать, что удалось помочь кому-то сделать более осознанный выбор профессии – или просто о чём-нибудь важном задуматься.

Заказ

Одним прекрасным летним днём 2010 года у меня зазвонил телефон.
Это был он. Заказ, который ты обычно ждешь, разгребая горы рутины.
«Требуется встроить компьютер в литой автомобильный диск».


Это звучало как вызов.
Такое спрашивают не каждый день. Я, ни секунды не раздумывая, согласился взяться за работу.
А потом заказчик пропал. Он просто больше не звонил мне. У меня был его номер, но я никогда не навязываюсь, поэтому все радостные переживания, связанные с предстоящей работой над интересным проектом тихо улеглись и забылись.
Прошел год.
Звонит заказчик. Оказывается, он потерял мой номер. И спустя год поисков – нашел!
И закипела работа!

Сразу уточнение: Bitmap 200x100 на компе с быстрой памятью и i7 3930K на 1366. Но, это честный System.Drawing.Bitmap.
Вводная: приложение типа осциллографа. Ссылка на готовый проект с фронтэндом в конце статьи.
Как же быстро рисовать его на экран? WriteableBitmap хорош, быстр, и он лучшее решение для WP, WinRT, WPF. Но занудного старпёра-кодера также волнует WinForms, .Net 2.0, Win2K (да-да, в некоторых гос.органах до сих пор теплый ламповый Win2K).
Далее, я обратил внимание на DirectX, тем более у нас для WPF появился полезный контрол D3DImage. Я перепробовал много движков, но ни один из них не давал удобного изящного способа рисовать GDI+ Bitmap из памяти. Некоторые работали и вовсе только с DX10-11. Ближе всех к цели оказался SlimDX. В любом случае, фронтэнд для контрола оказывался некрасивым. Все эти движки… мягко говоря избыточны, для моей простой задачи.

Каждый год 31 декабря David Eppstein публикует обзор препринтов за прошедший год, посвященных структурам данных и алгоритмам, опубликованным на arxiv.org. По ссылкам можно познакомиться с материалами за 2010 и 2011 (мой перевод) годы.

Раздел cs.DS развивается хорошими темпами: в этом году появилось 935 препринтов по алгоритмам и структурам данных, в то время как за 2011 их было 798. Раздел пока не дотягивает до сотни в месяц, хотя в июле (98 препринтов) этот порог был очень близок.

Это мой личный список из десятка препринтов, которые кажутся мне особенно интересными. Как обычно, я не вношу в него мои собственные работы и некоторые другие, о которых я писал раньше. Кроме того, здесь нет результатов (например, более быстрый алгоритм нахождения максимального потока), не появлявшихся на arxiv.org.

Вот они, в хронологическом порядке:

Добрый день, уважаемые хабровчане. В прошлой статье мы с вами разработали простую USB-видеокарту на базе STM32F103 и китайского дисплейного модуля на контроллере ILI9325.
Проверяли мы его из юзерспейса, при помощи LibUSB. Ну что ж, пришло время нам написать свой собственный драйвер, который позволит делать все то же самое, но из-под Linux и без дополнительных библиотек. Этот драйвер мы внесем в дерево исходников OpenWRT и он поселится там наравне со всеми остальными.
Начнем.

Лирическое вступление

Не люблю гонку версий, своей бессмысленностью отдаленно напоминающую гонку вооружений. Не успели как следует довести до ума текущую версию — выпускают новую, с новыми багами, уязвимостями и «особенностями». Для таких как я — любителей стабильных и проверенных решений для корпоративной среды, да и для себя тоже — у команды Мозилы есть сборка типа ESR: в течение длительного времени для нее выходят обновления, устраняющие ошибки и уязвимости, сама же major версия браузера не обновляется! Вот ссылка на страницу оф.сайта, откуда можно скачать эту замечательную ESR-версию (достигается путем не слишком очевидных ходов), также, ESR можно скачать с официального FTP ftp.mozilla.org/pub/firefox/releases/latest-esr/
Только что вышла давно мной ожидавшаяся 17-я ESR версия (предыдущая была только 10-я). В связи с этим событием решил написать подробное руководство по оптимизации нашего (не)любимого браузера — с разбором всех параметров, что каждый из них делает и откуда он получен.