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

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

Алгоритмы

  • 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 формата (на английском).

Рисуем сферу с помощью двух треугольников

Сфера в трехмерной графике обычно состоит из сотни-другой треугольников, при этом половина из них не видна человеку, поскольку их отсекает face culling и/или zbuffer.

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

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

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

(далее…)

Установка Python в режиме portable под Windows

Установка Python

  1. Скачать инсталлятор в формате MSI отсюда: https://python.org/downloads/
  2. Установить полученный дистрибутив <python.msi> в папку <INSTALLDIR> командой:
    msiexec /a <python.msi> /qn TARGETDIR="<INSTALLDIR>"

    , где /a — команда на установку с админскими правами, /qn — не задавать лишних вопросов, TARGETDIR — конечная папка

Установка Python Package Index

  1. Скачать файл getpip.py: https://bootstrap.pypa.io/get-pip.py
  2. Установить pip командой:
    <INSTALLDIR>\python.exe getpip.py
  3. Теперь любые пакеты можно устанавливать командой:
    <INSTALLDIR>\Scripts\pip.exe install <package name>

В итоге у вас есть обособленный Python интерпретатор любой версии с любыми пакетами в комплекте.

Также у вас есть возможность запускать *.py файлы с помощью установленного дистрибутива по клику мыши. Для этого вам понадобится PyLauncher.

Установка и настройка PyLauncher

  1. Скачать и установить pylauncer отсюда: https://bitbucket.org/vinay.sajip/pylauncher/downloads
  2. Открыть/создать файл %LOCALAPPDATA%\py.ini и добавить строку:
    [commands]
    mypython=<INSTALLDIR>\python.exe
  3. Добавить/поменять первую строку запускаемых *.py файлов на такую:
    #!mypython

    Теперь при запуске этих файлов их будет обрабатывать ваш интерпретатор (<INSTALLDIR>\python.exe)

Как это работает?

Первая строчка в формате #!<program name> используется в *nix подобных системах для автоматического выбора интерпретатора во время запуска и называется она, кстати, «shebang». В Windows системах эта строка игнорируется. PyLauncher просто перехватывает обработку *.py файлов и вызывает правильный Python интерпретатор.

Ускорение работы Python

Я рекомендую отключать создание и обновление *.pyc и *.pyo файлов в процессе работы Python. Аргументы могу привести следующие: оперативной памяти сейчас у всех хватает, процессор достаточно быстрый. Но устройство хранения данных (в народе флешка, жёсткий диск, SSD) по-прежнему слабовато.

Поэтому не выпендривайтесь и запускайте python с параметром -B или добавьте параметр PYTHONDONTWRITEBYTECODE в переменную окружения с любым непустым значением. Например, PYTHONDONTWRITEBYTECODE=Non_empty_string.

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