Мы подготовили для вас новый сет задач и вопросов, задаваемых на собеседованиях в ведущих IT-компаниях.



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

Пока мозг ещё не окончательно превратился в оливье, самое время немного заставить его поработать. Новая подборка логических и алгоритмических задач, предлагаемых на собеседованиях в известные IT-компании.



В нашу первую в новом году подборку попали вопросы и задачи, задаваемые в Alcatel-Lucent (Nokia).
Задачи мы постарись подобрать с различным уровнем сложности. На некоторые (а, может быть, и на все) вопросы можно найти ответ на просторах интернета, но это ведь не наш путь, верно?
Предлагаем интеллектуально размяться и попробовать самостоятельно решить приведённые задачи.

Всем привет! В нескольких статьях я хотел бы поделиться опытом создания подобия ММО игры используя Unreal Engine и Netty. Возможно архитектура и мой опыт кому-то пригодится и поможет начать создавать свой игровой сервер в противовес unreal dedicated server, который слегка прожорлив или заменить собой фреймворки для разработки многопользовательских игр такие как Photon.

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

Часть 1. Общая картина, сборка библиотек, подготовка клиента и сервера к обмену сообщениями
Часть 2. Наращивание игрового функционала + алгоритм Diamond Square

Когда-то давно я много играл в компьютерные игры (в основном — соревновательные), но несколько лет назад открыл для себя жанр Survival Game (выживалки «в простонародье»). Поиграв в несколько разных игр (ARK, Conan Exiles и другие, менее находящиеся на слуху), я понял, что это все же не совсем то, чего бы мне хотелось.

Как и многие ребята, в детстве (прошедшем еще в большой и сильной стране из 4 букв) я зачитывался книгами пиратской тематики: Одиссея Капитана Блада, Остров Сокровищ, да даже Гулливер, в какой-то степени, повлиял на мое мировоззрение и отношение к теме дальних странствий и опасных морских приключений.

И вот примерно полгода назад звезды сошлись. Я решил объединить свои страсти к пиратской тематике и компьютерным играм из жанра «выживалок». Я начал делать свою игру в этом сеттинге, с преферансом и куртизанками.

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


Серия будет состоять из следующих частей:

• Часть 1. Введение в процедурную анимацию
• Часть 2. Математика прямой кинематики
• Часть 3. Реализация прямой кинематики
• Часть 4. Введение в градиентный спуск
• Часть 5. Инверсная кинематика для робота-манипулятора
• Часть 6. Инверсная кинематика щупалец
• Часть 7. Инверсная кинематика лап паука

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

— Что, даже на том нечитаемом эзотерическом языке, где есть всего пара команд, которые едва-едва симулируют машину Тьюринга?
— Да, этот язык называется brainfuck. Я знаю brainfuck.

И это был не трюк — мы проверили. Я называл известный мне язык программирования, он тратил пару минут в Интернете на то, чтобы освежить свои знания по нему — и был способен писать на этом языке работающие алгоритмы. Я никак не мог понять этого. Ему, как и мне, было тогда около 18 лет — как он мог в этом возрасте знать все эти языки?


Интерпретатор brainfuck, написанный на brainfuck

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

Сегодня я советую своим студентам «постараться изучить все языки программирования». Подумайте сами — ведь эта идея лучше, чем все вот эти «В этом году я выучу Go! Ой, нет, теперь говорят что в моде Rust — выучу лучше Rust! Или Swift ...». Просто выучите все — не ошибётесь. А эта статья, возможно, вам в этом немного поможет.

[Примечание переводчика: перевод первой части этой статьи уже есть на Хабре, но её автор почему-то не завершил работу.]

Рендерер Quake III

Рендерер Quake III стал эволюционным развитием рендерера Quake II с аппаратным ускорением: классическая часть построена на архитектуре «двоичного разбиения»/«потенциально видимых наборов», но добавлены два новых заметных ключевых аспекта:

• Система шейдеров, построенная поверх фиксированного конвейера OpenGL 1.X. Это было большим достижением для 1999 года. Она обеспечивала большое пространство для инноваций в эру до повсеместно распространённых сегодня вершинных, геометрических и фрагментных шейдеров.
  
• Поддержка многоядерной архитектуры: клиент-серверная модель OpenGL блокирует некоторые методы и система потоков частично решает эту проблему.

Вы когда-нибудь задумывались о том, как загружается компьютер? Независимо от аппаратуры и операционной системы, все компьютеры при загрузке используют или традиционный метод BIOS-MBR, или более современный UEFI-GPT, реализованный в последних версиях ОС.

В этой статье мы сравним структуры разделов GPT и MBR; GPT означает GUID Partition Table, а MBR — Master Boot Record. Начнём с того, что разберём сам процесс загрузки.

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

Введение

В мае далёкого 2015 года я заканчивал бакалавриат факультета общей и прикладной физики МФТИ. В основном я занимаюсь квантовой теорией поля, но в тот момент я решил, что хотелось бы больше вникнуть в современный мир компьютерных наук, что можно попробовать совместить МФТИ с ШАД Yandex (две магистратуры). ШАД тогда уже был у всех на слуху, вокруг только и твердили, какой там жёсткий курс алгоритмов, мне понравился сайт (лол), тематика курсов, и я решился поступать.

В этом посте я хотел бы рассказать о том, как происходило моё поступление в ШАД, рассказать своё решение экзаменационного варианта (разборов ШАДовских заданий на просторах рунета не очень-то много) и поговорить о том, что понравилось / не понравилось в этом замечательном заведении.

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

• «Введение. Исполнители. Абстракции интерфейсов. Рекурсия»;
• «Жадные алгоритмы»;
• «Сортировки»;
• «Поиск. Списки»;
• «Деревья»;
• «Хеш-таблицы».

Четыре лекции курса читает Степан Мацкевич, руководитель группы извлечения онтологической информации в компании ABBYY. Он был ведущим программистом при написании серверной части продукта ABBYY InfoExtractor на основе технологии ABBYY Compreno (анализ текстов и перевода).

Еще две лекции ведет Георгий Иванов, разработчик Поиска Mail.Ru, занимающийся задачами обработки поисковых запросов.

Из-за падающего курса рубля многие фрилансеры уже давно работают на зарубежных клиентов. Среди них не все желают сотрудничать с обычными физлицами: крупные заказчики требуют оформлять контракт и оплачивать работы в иностранной валюте. Чтобы охватить новый рынок, придётся зарегистрироваться как предприниматель и соблюдать серьезное валютное законодательство. Обо всех этих правилах мы постарались рассказать понятными словами.

«Платить налоги – обязанность, платить мало налогов – искусство! » (с)

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

Задача стояла следующая — найти юрисдикцию, в которой не нужно платить налог на прибыль, при этом клиентам из США, Канады и ЕС удобно было с ней работать. Реальный офис открывать в этой стране задачи не стояло.

Основная деятельность компании — разработка ПО (классическая аутсорс компания со штатом ~20 девелоперов).

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

Сразу скажу, что получение денег на пластиковую карту без уплаты налогов может вылиться в серьезные проблемы (про ответственность написано в конце топика). Объяснения, что деньги «от бабушки внучку на мороженное» при суммах больше 10К$ в год уже не прокатывают, особенно если в реквизитах «бабушки» будет стоять что-то вроде «GMBH Star Development» Вероятность того, что возьмут за задницу достаточно высокая и поэтому лучше не рисковать и делать все по Закону, тем более, что ничего сложного в этом нет

Тема написания своего ЯПа не дает мне покоя уже около полугода. Я не ставил перед собой цель "убить" CoffeeScript, TypeScript, ELM, тысячи их, я просто хотел понять кухню и как они вообще пишутся.

К моему неприятному удивлению, большинство из этих языков используют Jison (Bison для JavaScript), а это не совсем попадало под мою задачу — "понять", так как по сути дела Jison делает все за вас, собирает AST по заданным вами правилам (Jison как таковой отличный инструмент, который делает за вас львиную долю работы, но сейчас не о нем).

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

Стоит заметить, что данное руководство не привязано к JavaScript, он выбран исключительно из соображений скорости разработки и читаемости, так что вы можете написать свой "лисп"/"питон"/"ваш абсолютно новый синтаксис" на любом знакомом вам языке.

Также до момента написании компилятора (в нашем случае транслятора), процесс написания языка не отличается от процессов создания языков компилируемых в ASM/JVM bitcode/LLVM bitcode/etc, а это значит, что данное руководство не ограничивается созданием языка трансляцируемого в JavaScript.

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

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

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

Друг наших образовательных программ Михаил Пименов,  CEO компании Wonder Games и Team Lead инди-проекта "Guard of Wonderland" сам не раз задававший себе эти вопросы, создал для себя выборку всевозможных материалов по индустрии геймдева. От полезных ресурсов, до сообществ, подкастов, книг и фильмов, которые призваны помочь понять, с чего начинается и чем заканчивается разработка игрового проекта. Объединив наши силы, мы с Мишей сделали эту статью с подборкой полезных материалов по игровой индустрии. Вы найдете подборку под катом.

Мне очень приятно, что мою последнюю статью про продвижение игры на Steam Greenlight, которую я писал на хабр чуть больше года назад, прочитали почти 50k раз и как мне кажется в итоге она была написана не зря. Тогда наша маленькая команда только-только получила зелёный свет. С того момента произошло еще много событий, но одним из самых интересных и значимых было то, что мы также прошли в программу ID@Xbox для независимых разработчиков, с возможностью выпуска своей игры на консоли Xbox One. И вот неделю назад игра все-таки увидела свет.



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

• Сколько может стоить разработка консольного проекта
• Где мы взяли такие деньги
• Как все подсчитать и иметь представление на что рассчитывать
• Почему мы решили работать без издателя и внешних инвестиций
• Как мы попали в Steam и на Xbox One
• Почему нужно платить и получать возрастные рейтинги
• В чем разница между Steam и Xbox — минусы и плюсы консольной разработки для инди

Серия игр Grand Theft Auto прошла долгий путь с момента своего первого релиза в 1997 году. Примерно 2 года назад Rockstar выпустила GTA V. Просто невероятный успех: за 24 часа игру купило 11 миллионов пользователей, побито 7 мировых рекордов подряд. Опробовав новинку на PS3, я был весьма впечатлен как общей картинкой, так и, собственно, техническими характеристиками игры.

Ничто так не портит впечатление от процесса, как экран загрузки, но в GTA V вы можете играть часами, преодолевая бескрайние сотни километров без перебоев. Учитывая передачу солидного потока информации и свойства PS3 (256 Mb оперативной памяти и видеокарта на 256 Mb), я и вовсе удивился, как меня не выбросило из игры на 20-ой минуте. Вот где чудеса техники.

В этой статье я расскажу о проведенном анализе кадра в версии для ПК в среде DirectX 11, которая съедает пару гигов как оперативки, так и графического процессора. Несмотря на то, что мой обзор идет со ссылкой на ПК, я уверен, что большинство пунктов применимо к PS4 и в определенной степени к PS3.

Анализ кадра

Итак, рассмотрим следующий кадр: Майкл на фоне любимого Rapid GT, на заднем плане прекрасный Лос-Сантос.



Осторожно! Трафик!

Введение

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

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

Метод будет описываться на примере вычислении силы заклинаний питомцев от интеллекта, и процент снижения получаемого урона игроком от суммарной величины защиты в игре ArcheAge. Собственно основа метода это «Метод наименьших квадратов», который очень широко известен и очень часто используется в разных областях. Для вычислений будет использоваться Wolfram Mathematica (любая версия). Собственно пошаговое описание того, что нужно делать для получения интересуемого закона и является основной ценностью данной статьи. Те, кто знаком с МНК и Wolfram Mathematica, могут перейти непосредственно к примерам.

Метод наименьших квадратов (МНК)

Пролог

Эта история началась более трех лет назад. Наша небольшая компания DAVA стала частью Wargaming, и мы начали обдумывать, какие проекты делать дальше. Чтобы напомнить, каким был мобайл три года назад, скажу, что тогда не было ни Clash Of Clans, ни Puzzle & Dragons, ни многих очень известных сегодня проектов. Mid-core тогда только-только начинался. Рынок был в разы меньше сегодняшнего.

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

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

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

С этого все и началось!

Когда мы начинали разработку “Снайпера”, то рассматривали технологии, которые тогда были доступны для мобильных платформ. На тот момент Unity был еще на достаточно ранней стадии своего развития: по сути, необходимых нам технологий еще не было.

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

Также мы понимали, что на C# мы не сможем выжать максимум из устройств, под которые мы разрабатываем, и всегда будем ограничены.
Unreal Engine 3 тоже не подходил по ряду похожих причин.

В итоге, мы решили дорабатывать свой движок!