Предисловие

Моя предыдущая статья была посвящена внутреннему устройству чипа от Nvidia, да и, пожалуй, внутреннему устройству любого современного процессора. В этой статье мы перейдём к средствам хранения информации, и я расскажу, что представляют собой CD и HDD диски на микроуровне.

Итак, у вас есть чистая Ubuntu, в консоли открыто ssh-соединение с сервером и консоль вас заманчиво приглашает — «root@my-awesome-host:~#» — и больше ничего нет. А хочется запустить и показать всему миру какое-то рельсовое приложение. Поехали от супа до орехов.

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

Алгоритмы и концепции

Сортировка и поиск

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

Пост подготовлен с целью помочь программистам при подготовке к собеседованиям по программированию. Здесь рассматриваются все основные темы, которые, как минимум, желательно знать перед собеседованием. Использован собственный опыт, опыт и рассказы коллег, специализированная литература.
Некоторые рассмотренные здесь темы могут вообще не пригодиться некоторым программистам, а могут и быть обязательными, решать вам. Мой совет – старайтесь как можно больше изучать темы/разделы/аспекты указанные здесь.
И так, в качестве обязательных знаний:

• Структуры данных
• Алгоритмы и «концепции»
• Язык программирования

18 сентября состоялся финальный раунд всероссийского кубка по программированию Russian Code Cup. В этом году в финал олимпиады вышли 50 программистов — 27 из России, 11 из Украины, 7 из Беларуси, двое из США и по одному из Армении, Грузии и Швейцарии.



Победителем стал Петр Митричев из Москвы. Он получил приз в 10 тыс. долл. США. Второе место занял Евгений Капун из Санкт-Петербурга, он получил 5 тыс. долл. США. На третьем месте — Михаил Дворкин из Санкт-Петербурга с призом в 3 тыс. долл. США. Поздравляем ребят и желаем им дальнейших успехов!

В этой статье мы проведем разбор задач из финального раунда.

Архитектура и платформа проекта Одноклассники

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

Добрый день!
Последние два года я занимаюсь разработкой сервера игр на платформе RedDwarf – свободной (GPLv2) серверной платформе для создания онлайн-игр на Java. На Хабре очень мало информации об этой платформе, поэтому я решил исправить этот недостаток.

История

Разработка данного движка изначально велась компанией Sun, сама платформа называлась Sun Game Server (аббревиатура sgs до сих пор используется в наименованиях пакетов). В 2005 году сервер был представлен миру под названием Project Darkstar. После того, как Oracle купила Sun, от поддержки проекта сановцы отказались, платформа была переименована в RedDwarf Server и сейчас существует только при поддержке сообщества. Проект развивается сейчас гораздо медленней, но всё же развивается – в прошлом году вышла версия 0.10.2. Всех планируемых фишек (прозрачного масштабирования) в ней ещё нет, но как основа для игрового сервера используется во многих проектах.

Основные принципы

Игровой сервер на платформе RedDwarf состоит из следующих частей.

• Игровое приложение
• Расширения
• Ядро
• Внутренняя БД

• Почему в трейсроуте после узла X идут звездочки?
• Сервис не работает, а трейсроут обрывается на узле X — значит проблема в узле X?
• Почему одинаковые трейсроуты с Windows и Unix показывают разные результаты?
• Почему трейсроут показывает большие задержки на определенном узле?
• Почему трейсроут показывает «серые» адреса при трассировке через интернет?
• Почему маршрутизатор отвечает на трейсроут не тем адресом, каким я хочу?
• Почему трейсроут показывает какие-то «не такие» доменные имена?
• Почему вообще вывод трейсроута отличается от интуитивно ожидаемого чаще, чем хотелось бы?

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

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

Как-то на хабре уже пробегала новость (не смог ее найти поиском) по поводу намерений Стэнфордского университета организовать онлайн-классы по курсу «Machine learning». А теперь эти намерения стали реальностью — Стэнфордский университет в лице профессора Andrew Ng и лаборатории искусственного интеллекта Стэнфордского университета приглашает всех желающих зарегистрироваться на сайте этого курса.

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

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

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



Речь пойдёт об университете Aizu, где я тружусь в меру сил уже почти два года и, если не случится никаких неожиданностей, продолжу деятельность и в обозримом будущем. Кстати, на фотографии — наш кампус.

В мае 2011 года Google запустил поиск авиарейсов в виде текстовой подсказки при поисковом запросе (работает в том числе на русском языке для местных авиамаршрутов). Уже тогда стало ясно, что компания серьёзно работает в данном направлении и скоро турагентам придётся искать новую работу¹.

И продолжение не заставило долго ждать. Вчера открылся полноценный поиск авиабилетов с нормальным интерфейсом Google Flights. Он пока ограничен территорией США.

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

Часть 1: Архитектура
Часть 2: Протокол
Часть 4: Переходим в 3D

С третьей частью я немного задержался. Но как говорится лучше поздно чем никогда…

Итак, продолжаем разговор.

В третьей части нашей постановки мы реализуем протокол, напишем сервер и клиент которые будут взаимодействрвать по сети. И (ОМГ!) танки будут ездить!
Под катом то, что вы давно хотели, но боялись спросить…

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

Вопрос: Почему поиск в python dict на больших объемах данных быстрее чем итерация по индексированному массиву?

Ответ: В dict хранятся хэши от ключей. Каждый раз, когда мы ищем в dict значение по ключу, мы сначала вычисляем его хэш, а потом (внезапно), выполняем бинарный поиск. Таким образом, сложность составляет O(lg(N))!

На самом деле никакого бинарного поиска тут нет. И сложность алгоритма не O(lg(N)), а Amort. O(1) — так как в основе dict питона лежит структура под названием Hash Table.

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

С днем программиста, коллеги!

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

Алгоритмы. Задача №1, разминочная

Напишите код, который находит количество подчисел числа n, на которые это число делится без остатка.

Для числа n, подчисло — это такое число, запись которого является подстрокой записи числа n. К примеру, если n равняется 1938, то его подчислами будут являться: 1, 9, 3, 8, 19, 93, 38, 193 и 938. Без остатка 1938 делится на четыре из этих подчисел: 1, 3, 19 и 38. Соответственно, результатом работы программы должно быть число 4.
Если подчисла повторяются, каждое из них считается. Например, 101 делится без остатка на 1, 1 и 01, значит, ответ — 3.

Так как задача несложная, в решениях ценится краткость или нестандартный подход.

Несколько книг по разным темам, которые находятся в открытом доступе.

Основы программирования

• codebetter.com/karlseguin/2008/06/25/foundations-of-programming-ebook
• pine.fm/LearnToProgram
• netlib.bell-labs.com/cm/cs/pearls
• www.faqs.org/docs/artu
• savannah.nongnu.org/projects/pgubook

Приветствую вас, хабралюди!

Взбрело мне в голову написать несколько статей, о том как реализованы некоторые структуры данных в Java. Надеюсь, статьи будут полезны визуалам (картинки наше всё), начинающим java-визуалам а также тем кто уже умеет писать new ArrayList(), но слабо представляет что же происходит внутри.



Сегодня поговорим о ArrayList-ах

ArrayList — реализует интерфейс List. Как известно, в Java массивы имеют фиксированную длину, и после того как массив создан, он не может расти или уменьшаться. ArrayList может менять свой размер во время исполнения программы, при этом не обязательно указывать размерность при создании объекта. Элементы ArrayList могут быть абсолютно любых типов в том числе и null.

Под катом — список из 15 лучших ресурсов, посвящённых Спортивному Программированию.

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

Итого было решено поделиться знаниями, организовав бесплатные занятия по InfoSec для всех желающих. Под катом программа занятий и подробности.
Для тех, кто не из Томска — можете просто прокомментировать выбранные темы и возможно предложить свои.

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

В порядке эксперимента курс сопровождала аудио- и видеозапись лекций, а также вики для размещения материалов по курсу. Закончив за лето обработку видеоматериалов, предлагаем получившийся видеокурс широкой публике, то есть вам. Все материалы опубликованы под лицензией CC-BY-SA 3.0.

Я.Видео: первая часть, вторая часть.