Ещё пара задач с собеседований

[hitech]

В своем резюме вы указали, что хотели бы поработать на интересном проекте… Вы этот проект с собой принесли?

Вопрос на собеседовании.

Давненько в этом журнале не было задач с собеседований…

Напоминаю, что полная подборка задач с собеседований доступна по соответствующей метке.

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

Задача первая, логическая:

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

Вопрос: существует ли выигрышная стратегия для какого-нибудь из игроков? Если да, то в чём она заключается?

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

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

Решение работает не только с радиальной симметрией, но и с симметрией относительно любого произвольно выбранного диаметра. Главное для первого игрока — не забыть, где ось симметрии проходит…

Эта простая задача проверяет логическое мышление кандидата и умение использовать для решения логических задач математические свойства упоминаемых объектов.

Задача вторая, программерская низкоуровневая:

Основную работу по внесению багов в программу выполняют программисты. Основную работу по вычищению багов из программы выполняют те же программисты с помощью дебаггеров. Переход в дебаггер в архитектуре x86 реализован следующим образом: существует специальное прерывание, int 3, которое передаёт контроль дебаггеру. Вызов этого прерывания состоит из однобайтного кода операции 0xCC.

Вопрос: обычно прерывание в x86 вызывается двухбайтной инструкцией: 0xCD, после чего идёт порядковый номер прерывания. То есть int 3 можно было бы вызвать двухбайтной инструкцией CD 03. Зачем понадобился специальный однобайтный вызов CC?

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

Представим себе кусок кода на ассемблере:

  . . .много-много кода. . .
  jz label   ; Если результат предыдущего вычисления равен 0, перейти на метку label
  dec eax    ; Уменьшить на единицу содержимое регистра eax
label:
  call function1   ; Вызов функции function1
  . . .много-много кода. . .

Предположим, мы ставим breakpoint на строке dec eax, и используем при этом двухбайтную конструкцию CD 03. dec eax — это команда с однобайтным кодом операции 0x48. Вместо неё мы впихиваем двухбайтный код операции, затирая часть следующей инструкции (вызов функции с помощью команды call).

Предположим теперь, что во время тестового прогона программы результат вычисления оказался равным нулю, и команда jz label перебросила нас на метку label. Breakpoint не сработал. Но следующая инструкция, которая должна была бы выполняться, затёрта куском нашего breakpoint`а, и вместо кода операции FF, соответствующего команде call, там сейчас код операции 03, соответствующий команде add. Вместо вызова функции программа выполнит сложение. Результат? А чёрт его знает, но явно не тот, который нужен.

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

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