Издательство Питер решило представить недавно выведшую книгу от автора бестселлера «Карьера программиста», которая поможет вам наилучшим образом подготовиться к собеседованию при приеме на работу менеджером проекта в крупную IT-организацию или перспективный стартап. Основную часть книги составляют ответы на технические вопросы и задания, которые обычно получают соискатели на собеседовании в таких компаниях, как Google, Microsoft, Apple, Amazon и других. Рассмотрены типичные ошибки, которые допускают кандидаты, а также эффективные методики поlготовки к собеседованию.

Дисклеймер от автора (автор — девушка): Я не разрабатываю движки баз данных. Я создаю веб-приложения. Я участвую в 4-6 разных проектах каждый год, то есть создаю много веб-приложений. Я вижу много приложений с различными требованиями и различными потребностями хранения данных. Я разворачивала большинство хранилищ, о которых вы слышали, и несколько, о которых даже не подозреваете.

Несколько раз я делала неправильный выбор СУБД. Эта история об одном таком выборе — почему мы сделали такой выбор, как бы узнали что выбор был неверен и как мы с этим боролись.Это все произошло на проекте с открытым исходным кодом, называемым Diaspora.

Не знаю, как у вас, но у меня любимая часть интервью — логические задачи.
Довелось пройти немало собеседований на вакансию разработчика, поэтому набралась небольшая коллекция.
Спешу поделиться с вами!

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

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

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

Балансировать структуру данных вероятностно проще, чем явно обеспечивать баланс. Для многих задач списки пропуска это более естественное представление данных по сравнению с деревьями. Алгоритмы получаются более простыми для реализации и, на практике, более быстрыми по сравнению со сбалансированными деревьями. Кроме того, списки с пропусками очень эффективно используют память. Они могут быть реализованы так, чтобы на один элемент приходился в среднем примерно 1.33 указатель (или даже меньше) и не требуют хранения для каждого элемента дополнительной информации о балансе или приоритете.

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

По крайней мере, таков план.

Но как же именно вам, как разработчику игры, отрендерить такой эффект?

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

До весны 2012 года у нас вместо такой базы существовали две базы данных разного уровня — со стороны спайдера, который имел свою собственную базу URL-ов, и со стороны индексатора. Это было крайне неудобно: допустим, если пользователь жаловался, что его сайт не индексируется, то для того, чтобы найти причину, при старой архитектуре пришлось бы анализировать массу данных. На это требовалось день-два, иногда даже неделя.

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

Последний месяц в армии. Постепенно освобождается время для разных интересных проектов. Остается только определиться, чем именно занять мозги. Закончил читать «Эгоистичный ген» Ричарда Докинза и идея была сформулирована – хочу сделать визуализацию, использующую принципы эволюции.


Рисунок 1. Популяция бактерий перестраивает среду под свои нужды.

Итак, вперед!

С древних времен человек хотел разговаривать с окружающим миром. Говорящие вещи окружали его в сказках и легендах. Злая королева общается с говорящим зеркалом, Горлум жалуется на тяготы и невзгоды бытия Кольцу Всевластья, Тамерлан разговаривал с камнями и давал им имена.

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

В Cubic Robotics мы верим, что скорейший путь к “говорящему миру” лежит через создание универсальной голосовой операционной системы, которую с одной стороны можно было бы установить на любое устройство. С другой стороны такую систему могли бы развивать независимые разработчики по всему миру. Именно такой является разработанная и запатентованная нами голосовая операционная система V.O.I.S. (Voice Operation Intellectual System).



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

Также на базе V.O.I.S. уже создаются и проектируются разговаривающие автомобили, интеллектуальные помощники для смартфонов и носимых гаджетов.

Привет, Хабр! Я Андрей Фролов, ведущий программист, работаю в Mail.Ru над Next-Gen MMORPG Skyforge. Вы могли читать мою статью про архитектуру баз данных в онлайн-играх. Сегодня я буду раскрывать секреты, касающиеся устройства сервера Skyforge. Постараюсь рассказать максимально подробно, с примерами, а также объясню, почему было принято то или иное архитектурное решение. По нашему серверу без преувеличения можно написать целую книгу, поэтому для того, чтобы уложиться в статью, мне придется пройтись только по основным моментам.

В последнее время на Хабре появилось множество статей о нейронных сетях. Из них очень интересными показались статьи о Перцептроне Розенблатта: Перцептрон Розенблатта — что забыто и придумано историей? и Какова роль первого «случайного» слоя в перцептроне Розенблатта. В них, как и во многих других очень много написано о том, что сети справляются с решением задач, и обобщают до некоторой степени свои знания. Но хотелось бы как-то визуализировать эти обобщения и процесс решения. Увидеть на практике, чему там научился перцептрон, и почувствовать, насколько успешно ему это удалось. Возможно, испытать горькую иронию относительно достижения человечества в области ИИ.
Языком у нас будет С#, только потому что я недавно решил его выучить. Я разобрал два наиболее простых примера: однослойный перцептрон Розенблатта, обучаемый коррекцией ошибки, и многослойный перцептрон Румельхарта, обучаемый методом обратного распространения ошибки. Для тех, кому, как и мне, стало интересно, чему они там на самом деле обучились, и насколько они на самом деле способны обобщать – добро пожаловать под кат.

ОСТОРОЖНО! Много картинок. Куски кода.

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

Речь сегодня пойдёт о генерации изображений с картой расстояний (Signed Distance Field). Данный вид изображений примечателен тем, что фактически позволяет получить «векторную» графику на видеоускорителе, причём даром. Одной из первых данный метод растеризации предложила компания Valve в игре Team Fortress 2 для масштабируемых декалей в 2007 году, но до сих пор он не пользуется особой популярностью, хотя позволяет рендерить прекрасного качества шрифты, используя текстуру всего 256х256 точек. Данный метод прекрасно подходит для современных экранов высокой чёткости и позволяет серьёзно сэкономить на текстурах в играх, он не требователен к железу и прекрасно работает на смартфонах.



Хитрость заключается в создании такой специально подготовленной карты расстояний, что при использовании простейшего шейдера получается идеальная векторная картинка. Более того, с помощью шейдеров можно получить эффекты тени, свечения, объёма и т. п.

Как же создавать такие изображения? Очень просто, ImageMagick позволяет сделать это одной командой:

convert in.png -filter Jinc -resize 400% -threshold 30% \( +clone -negate -morphology Distance Euclidean -level 50%,-50% \) -morphology Distance Euclidean -compose Plus -composite -level 45%,55% -resize 25% out.png

На этом можно было бы поставить точку, но так полноценного топика не получится. Что ж, под катом — описание быстрого алгоритма расчёта SDF, пример на C++ и немного шейдеров для OpenGL.

На конференции SIGGRAPH ASIA 2013 Thomas Geijtenbeek, Michiel van de Panne и Frank van der Stappen представили метод симуляции физики двуногих существ на основе мускульного контроля с оптимизацией перемещения мышц и других контролируемых параметров. В результате был получен метод управления передвижением для множества двуногих существ. Все приводящие в действие силы являются результатом работы симулированных 3D-мускул и модели нейронных задержек, включенных в цепи ответных реакций. Перечисленные контроллеры генерируют вращающие движения, которые учитывают биомеханические ограничения. Контроллеры находят различные походки на основе требуемой скорости, могут учитывать неровные поверхности и внешние возмущения, способны следовать в задаваемом направлении.

Как только я заинтересовался lock-free алгоритмами, меня стал мучить вопрос – а откуда взялась необходимость в барьерах памяти, в «наведении порядка» в коде?
Конечно, прочитав несколько тысяч страниц руководств по конкретной архитектуре, мы найдем ответ. Но этот ответ будет годен для этой конкретной архитектуры. Есть ли общий? В конце концов, мы же хотим, чтобы наш код был портабелен. Да и модель памяти C++11 не заточена под конкретный процессор.
Наиболее приемлемый общий ответ дал мне мистер Paul McKenney в своей статье 2010 года Memory Barriers: a Hardware View of Software Hackers. Ценность его статьи – в общности: он построил некоторую упрощенную абстрактную архитектуру, на примере которой и разбирает, что такое барьер памяти и зачем он был введен.
Вообще, Paul McKenney – известная личность. Он является разработчиком и активным пропагандистом технологии RCU, которая активно используется в ядре Linux, а также реализована в последней версии libcds в качестве ещё одного подхода к безопасному освобождению памяти (вообще, о RCU я хотел бы рассказать отдельно). Также принимал участие в работе над моделью памяти C++11.
Статья большая, я даю перевод только первой половины. Я позволил себе добавить некоторые комментарии, [которые выделены в тексте так].

Не стоит преследовать цели, которые легко достичь. Стоит нацеливаться на то, что удается сделать с трудом, приложив немалые усилия — Альберт Эйнштейн

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

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

Я расскажу о следующем:

• что такое перекрестные ссылки;
• чем опасны безымянные shared_ptr;
• какие опасности подстерегают при использовании shared_ptr в многопоточной среде;
• о чем важно помнить, создавая свою собственную освобождающую функцию для shared_ptr;
• какие существуют особенности использования шаблона enable_shared_from_this.

Оригинальный pdf (на английском)
Переведённый pdf (на русском)

Представьте себе игру с огромным разнообразием оружия, путешествиями во времени, вторжением пришельцев, и всё на движке Skyrim.

Это — Backspace, проект, который разрабатывался в Obsidian. Малочисленная команда разрабатывала дизайн и концепт игры в 2011 году. И хотя дальше концепта игра не ушла, но она бы заинтересовала многих. Obsidian многие должны знать по Fallout: New Vegas и недавнему Project Eternity (про NWN 2 думаю и напоминать не стоит).

Одиночная ролевая игра, действия которой разворачиваются в эпоху космической эры с боевой системой похожей на Skyrim, но несколько динамичней. Что-то вроде смеси Mass Effect+Borderland+System Shock 2. С учётом движка, можно сказать, что это Sci-Fi Skyrim.

Вот и отгремело первое апреля. Кто-то в этот день нюхал свои девайсы в новом сервисе Google Nose, кто-то играл в «Поле чудес», а кто-то, позабыв о роковой дате, просто угрюмо отряхивал спину от мела…

Я же, воодушевлённый статьёй про скрытые возможности кастомизации процесса explorer.exe, тоже решил сделать что-нибудь забавное.
Пусть сегодня моя секундная стрелка часов в Windows идёт в обратную сторону! Не самый, конечно, полезный в хозяйстве мод, но в академических и рекреационных целях вполне сгодится :)

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

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

Продолжение перевода здесь

В нашей сфере деятельности нам доступны огромные объёмы знаний, в особенности тех, которые позволяют разработчику стать эффективным. Но почему-то, несмотря на существование множества книг о специфических задачах и обязанностях менеджеров в нетехнических областях, я практически не вижу новых книг или статей о том, как стать хорошим ведущим разработчиком. Замечательным исключением, конечно, являются статьи Кейт Maцудайры [от переводчика: на фотографии, кстати, именно она], немало написавшей о культурных составляющих инженерии.

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