Где размять мозги программисту? Тренировочный полигон для айтишников

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

А программистам и похвастаться нечем. Они не бегают и стрелять не умеют, а сидят сгорбленные, уставившись красными глазами в монитор и что-то пишут. Чем он занят? Зачем он здесь? Никто не знает.

А работодатель хочет знать как определить сильного программиста. По хиленьким ручкам, красным глазкам, горбатой спине или катышкам на свитере? Ну, допустим, текущему работодателю определить просто — надо брать того, кто не слишком сильно пахнет, а как быть с новым работодателем?

Вот пришёл ты такой красивый на собес и тебе прямо с порога — давай сортировку пузырьком пиши в уме! А ты работаешь в своём НИИ уже пятый десяток и всегда использовал метод sort() из вашей секретной сверхбыстрой библиотеки на Фортране и знать не знаешь что у неё внутри. И библиотека та написана учёным седовласым мужем, чьё имя с отчеством произносятся в конторе с придыханием и пиететом и бюст евоный стоит сразу при входе в холле. И значит это ровно то, что часть мозга, которая отвечает за простейшие алгоритмы атрофировалась за ненадобностью. Потому что все эти вещи пишутся один раз и навсегда, а не каждый день, как полагает потенциальный работодатель. Посему надо держать себя в тонусе. И помогут нам в этом два сайта LeetCode и HackerRank. Оба сайта, в принципе, одинаковые, но работодателя больше возбуждает HackerRank почему-то. Может из-за названия?

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

Кому интересно, мой профиль на LeetCode и HackerRank.

Онлайн книжка по неопределённому поведению C++

Всем привет!

Буду краток, товарищ поделился ссылкой (спасибо, Влад!) на труд другого умного товарища.
Эта книга пригодится каждому программисту C++: Путеводитель C++ программиста по неопределенному поведению.

Вопросы программистам С++ на собеседованиях. Часть вторая

Здравствуй, дорогой читатель, вот и родилась вторая часть моего шедевра девятилетней давности. Только теперь формат статьи поменялся — ответы я буду писать в свободное время в очень ленивом режиме, потому что работу я не ищу и вопросы передо мной стоят совершенно другие (например, хитромудрый рендеринг в текстуру), а свободного времени у меня немного, потому что я во время него обычно сплю и само собой мне лень. При появлении ответа на какой-нибудь пункт, я буду его выделять, а ответ прятать под катом. И, разумеется, я не знаю ответов на абсолютно все эти вопросы и меня это нисколько не смущает, потому что я милорд синьор рисёрч инженер, а не Си плюс плюс задрот.

Алгоритмы

  • LRU кеш ограниченного размера
  • Что такое хеш таблица
  • Сделать дерево поиска в отсортированном массиве
  • Структура с указателем на parent и надо найти наименьшего общего предка
  • Вывести матрицу по спирали внутрь
  • Убрать элементы нулевые элементы в std::vector
  • Развернуть односвязный список
  • Исходный список содержит цифры, конечный i-й элемент содержит произведение всех элементов кроме i-того в исходном списке
  • Рисование закрашенного треугольника

Программирование

  • Бесконечная рекурсивная функция (в какие моменты может произойти, как сделать)
  • Написать свой std::shared_ptr
  • Отличие структуры от класса
    Ответ
    По умолчанию все члены struct имеют видимость public, а classprivate. Наследование от struct по умолчанию public, от classprivate. В остальном никакой разницы.
  • Выравнивание, размер структуры
  • volatile и mutable
  • Что такое pure virtual call
  • Вызов виртуальных функций из конструктора и деструктора
  • Таблица виртуальных функций
  • Как работает dynamic_cast, static_cast, reinterptet_cast, const_cast. Что происходит в случае ошибки приведения типа, работа со ссылкой и указателем
  • В чем отличие ссылки от указателя
  • Многопоточность std::shared_ptr
  • Факториал итеративно, рекурсия, на шаблонах
Курсовая работа (ТКУиК, 2002 год)

Одним «прекрасным» днём задали нам в техникуме сделать курсовую работу. Тема была простой: «Графическое приложение».

Загрузочный экран (640x480)Точки на экране представляют собой вращающийся трехмерный куб

Можно было использовать любой язык, который нам преподавали. Почему-то выбрал C/C++, вместо Turbo Pascal, как все остальные и потратил примерно 20 дней чистого времени для этой работы (потому что нечего было выпендриваться).

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

Окно регистрации пользователяРегистрация пользователя (для преподавателей есть специальный аккаунт)

Затем можно выбрать тему обучения:

Выбор темы обученияБез интернета можно найти только темы, которые знаешь сам

Процесс обучения по выбранной теме:

После обучения, можно пройти тестирование по выбранному материалу:

Прошёл буквально только что тесты — результат удручает. Надо подучиться. :)

Статистика прохождения тестов

В конце концов, сделал специальный пункт «Об авторе», чтобы помнили.

Привет, Ксю! :)

Данные для анализа и системные требования:

  • CPU: минимально Intel 80286
  • IDE: MS-DOS 7.0, Norton Commander и Borland C++ & Application Frameworks 3.1
  • Screen Resolution: 640×480
  • Опции комммандной строки: /nologo

Bugs and features:

  • русская буква «д» заменена на английскую «d»
  • экран перерисовывается частями
  • оглавление нарисовано два раза одним шрифтом
  • изображения двух цветов, чёрный и alpha

Описание формата ZIP файла. Часть 2 (расширение ZIP64, поддержка больших файлов)

Давным-давно, когда создавался формат ZIP и всем хватало 640KB памяти, никто не задумывался, что файл может быть >4GB и содержать в себе больше 65535 элементов, поэтому поддержка таких объемов прикручена костылями и называется ZIP64. До сих пор этот формат плохо понимают Far Manager, 7-Zip и проводник седьмой винды (а говорят, что в Microsoft берут только гениальных программистов, возьмите меня, я умнее, чем выгляжу).

Расширение ZIP64 добавляет две основные фичи:

  • структура ZIP64 End Of Central Directory Record (EOCD64) с 64-битными полями и ZIP64 End Of Central Directory Locator для поиска структуры EOCD64
  • если значения некоторых полей Central Directory Header и Local File Header превышают максимальный, то эти значения записываются в Extra Field этих структур в специальном формате ZIP64 Extended Extra Field

А теперь подробнее про эти нововведения.

ZIP64 End Of Central Directory Locator

Используется для поиска структуры EOCD64 и находится сразу перед стандартным End Of Central Directory Record.

EOCD64Locator

struct EOCD64Locator
{
    // Обязательная сигнатура, равна 0x07064b50
    uint32_t signature;
    // Номер диска для поиска EOCD64
    uint32_t diskNumber;
    // Смещение от начала файла до EOCD64
    uint64_t eocd64Offset;
    // Количество дисков
    uint32_t totalDiskCount;
};

Определить, что наш ZIP файл содержит такую запись просто: проверьте поля стандартного End of central directory record. Если 16-битные поля равны 0xFFFF или 32-битные — 0xFFFFFFFF, значит такая запись должна быть.

ZIP64 End Of Central Directory Record

Эта структура представляет собой 64-битную версию стандартного End Of Central Directory Record. Находится по адресу EOCD64Locator.eocd64Offset.

EOCD64

struct EOCD64
{
    // Обязательная сигнатура, равна 0x06064b50
    uint32_t signature;
    // Размер записи EOCD64
    uint64_t eocd64Size;
    // Версия для создания
    uint16_t versionMadeBy;
    // Версия для распаковки
    uint16_t versionToExtract;
    // Номер текущего диска
    uint32_t diskNumber;
    // Номер диска для поиска Central Directory
    uint32_t startDiskNumber;
    // Количество записей в Central Directory
    uint64_t numberCentralDirectoryRecord;
    // Всего записей в Central Directory
    uint64_t totalCentralDirectoryRecord;
    // Размер Central Directory
    uint64_t sizeOfCentralDirectory;
    // Смещение Central Directory
    uint64_t centralDirectoryOffset;
    // zip64 extensible data sector (переменной длины)
    uint8_t *dataSector;
};

Extra Field

Если вы внимательно читали мои предыдущие заметки на тему ZIP формата (описание формата ZIP, чтение ZIP файла, запись ZIP файла), то могли заметить, что у записей типа Local File Header и Central directory file header есть поля под названием extraField.

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

ExtraFieldRecord

struct ExtraFieldRecord
{
    // Заголовок (для ZIP64 extended information равен 0x0001)
    uint16_t headerId;
    // Размер данных
    uint16_t dataSize;
    // Какие-то данные размером dataSize
    uint8_t *data;
};

Данные ExtraFieldRecord.data для ZIP64 extended information выглядят так:

ZIP64ExtendInformation
struct ZIP64ExtendInformation
{
    // Размер несжатых данных
    uint64_t uncompressedSize;
    // Размер сжатых данных
    uint64_t compressedSize;
    // Смещение Local File Header от начала файла
    uint64_t localFileHeaderOffset;
    // Номер диска для поиска
    uint32_t diskNumber;
};

Обратите внимание — в это записи важен лишь порядок полей. Все поля необязательно будут присутствовать.

Например, структура Central directory file header будет содержать 0xFFFFFFFF только в поле localFileHeaderOffset, значит в Extra Field будет лежать только значение localFileHeaderOffset, а остальные поля будут отсутствовать.

Порядок действий

  • определить наличие EOCD64 проверкой полей EOCD на переполнение и считать сначала EOCD64Locator, затем EOCD64
  • для каждой структуры типа Central directory file header и Local File Header определить поля на переполнение и, если таковые присутствуют, то считать их значения из ExtraField

Вот, в принципе, и вся наука. Вы не подумайте, что я нашел эту информацию тщательным изучением ZIP файлов, просто читайте спецификацию ZIP формата (на английском).

Блог Евгения Жирнова