2026/05/28 17:28
1994年のマイクロソフトインターン面接（2023年再訪）の4つのプログラミング問題について
RSS: https://news.ycombinator.com/rss
要約▶
Japanese Translation:
この五部シリーズは、著者が1993年～1994年のマイクロソフト夏のインターンシップで受けた古典的なプログラミング課題を解く体験を記しています。4名の別々の審査員がそれぞれ即興で1問ずつ提示し、中心となるテーマは当時のデスクトップグラフィックアプリケーションでは浮動小数点演算が速すぎて使えなかったため、整数演算のみを使用して高水準なアルゴリズム思考を習得することです。読者は、ビデオバッファのコピー、4色CGAモードにおけるパックされた2ビットピクセル色の操作、現代のSIMDまたは浮動小数点支援なしで円のような幾何形状を描画する、そしてヌル終端文字列のコピーといった課題を探求します。特に問3は、その当時にボーランドを上回る性能を謳ったマイクロソフト製品のフローディールアルゴリズムに着想を与えました。著者はその場でこれを解くことはできなかったものの、実際のSIMD命令を使わないSIMDスタイルのプログラミングという性質から、これこそが大好きな課題としています。問4では、著者が以前見たことのない新しい円描画アルゴリズムが提示されました。この物語は、ビットパッキングや整数論理といった核心的なコンピュータサイエンスの概念が、これらの歴史的課題によって検証され、現在も関連性を持っていることを強調します。困難さは一貫していないと感じられます（問2は後に続く複雑なビット操作問題よりも単純に思えた）ものの、このシーケンスは最適化前のアルゴリズム設計への貴重な洞察を提供します。本シリーズはこの週で終了し、その後は通常の講義が再開されます。読者には、以下の投稿で提供される解答を見る前に、これらの課題を自分で解いてみることを勧めます。
本文
1994 年マイクロソフト・サマーインターンシップ面接：古き良きプログラミング課題の全貌
今週は「パフォーマンスを意識したプログラミング」に関するレッスンが設けられません。Computer Enhance において、1994 年のサマーインターンシップ週間のためです。通常通りのご紹介は来週から再開いたします。
背景：懐かしい面接の思い出
古く、そして遥か昔の話——おそらく 1993〜1994 年頃のことでありましたが、マイクロソフトのサマーインターンポジション向けの面接を受けました。当時は以下の状況がありました。
- 若き日: 私がまだ高校生だった時期です。
- 未知の体験: インターネットが未発達で、「マイクロソフト流のプログラミング問題」自体が新しい試みでした。
- 形式化された面接: 計 4 名の担当者に個別に面接を受け、それぞれが典型的な採用テストの問題を出題しました。
私はその経験を通じて、当時「正解」とされていただけでありながら、今では見直されるべき古典的なアルゴリズム課題を共有します。今週、順次その問題と解答（当時の答え・現代の応用）について解説いたします。
課題一覧と詳細解説
面接で提示された問題は、難易度が一日進むにつれて上がる傾向がありましたが、今回のケースでは順序が少し異なる構成でした。以下に 4 つの主要課題をご紹介します。
1. バッファ間での長方形領域コピー（Problem 1）
最も簡単な問題で、C 言語におけるポインタ操作と長方形領域の概念を理解しているかを確認するものです。
- 課題内容: バッファ A からバッファ B へ、指定された長方形領域（ピクセル単位）をコピーするコードを書く。
- 要件:
- 要素サイズは 8 ビット（当時の標準）。
- パフォーマンス要件は特に課されず、「処理の理解度」が問われた。
- 与えられたシグネチャ例:
void CopyRect(char *BufferA, int PitchA, char *BufferB, int PitchB, int FromMinX, int FromMinY, int FromMaxX, int FromMaxY, int ToMinX, int ToMinY) { /* ここに実装を記述 */ }
- 評価: ポインタ操作に不慣れな人にとっては少し難解ですが、概念自体は直感的です。
2. ASCII ゼロ終止文字列のコピー（Problem 2）
長方形コピーを理解すれば自然に解けるが、あえて文字列を対象にした理由は不明です。
- 課題内容: 「ASCII-Z」方式（1 バイト要素、ゼロ終止型）の文字列をコピーする関数を記述。
- 与えられたシグネチャ例:
void CopyString(char *From, char *To) { /* ここに実装を記述 */ }
- 特徴的なエピソード:
- コードが完了した後、面接官から**「いくつか修正を加えてください」**という追加課題が出されました。
- これこそが、面接官の専門性について少し疑念を持たせた事例です。
3. 4 色対応 CGA モードでのフールフィル判定（Problem 3）
最も興味深く、難易度も高い問題です。当時の私には即席での解答が不可能でしたが、現代の視点では素晴らしい課題です。
- 背景: マイクロソフト製品用に実装していた「絵の具バケツツール」に相当する処理。
- 課題内容: 特定のバイト値が特定の色と一致するかを検出するコードを実装（
）。ContainsColor - 重要な制約:
- CGA モード (4 色): ピクセルは 2 ビットで表現され、1 バイトに4 つのピクセルがパックされている。
- SIMD なし:当時の環境では SIMD 命令が存在しなかったため、単純な等号比較では不十分。
- 課題の本質: 「1 バイト内の 4 つのピクセルのうち、与えられた色が含まれているかどうかを最も効率的に判定する方法」を考えさせる。
int ContainsColor(char unsigned Pixel, char unsigned Color) { /* ここに真（非ゼロ）か偽（ゼロ）かを判定する計算を実装 */ }
- 戦略的自由: 色
の表現形式については自由であり、事前計算結果を組み込むことも可。Color - 評価: この問題は「SIMD 命令を用いない SIMD 風プログラミング」の古典的な例として非常に好きです。
4. 円周の描画アルゴリズム（Problem 4）
少しばかげている側面もありますが、「経験値」と「読書量」を試すための問いでした。
- 課題内容:
関数を使って、円周上の各ピクセルを一度だけ描画するPlot(X, Y)
を実装。OutlineCircle - 与えられたシグネチャ例:
void Plot(int X, int Y); /* これは既に存在すると仮定 */ void OutlineCircle(int Cx, int Cy, int R) { /* ここにコードを実装し、円周上の各ピクセルについて一度だけ Plot を呼び出してください */ }
- 制約と理由:
- すべて整数型: 1994 年当時、デスクトップコンピュータでの浮動小数点演算は十分高速ではなく、グラフィックス処理でも整数が主流でした。
- 既存知識の試み: アルゴリズム自体が発見されたばかりであり、現場ですぐに発明する機会はなかったため、「以前読んだ本や知識があるか」を試す目的がありました。
- 結果: ホワイトボード上でコードを書けましたが、面接官が手取り足取り手伝ってくれました。
今週のスケジュール
来週以降、それぞれの課題に対する「当時の答え」と「現代の答え」について、4 つの記事に分けてご紹介します。
- Problem 1: バッファコピーの最適化
- Problem 2: 文字列コピーの拡張と修正
- Problem 3: ビット操作による高速フールフィル判定
- Problem 4: アルゴリズムの再考と整数演算の意義
ご自身でもぜひ挑戦してみてください。経験豊富なプログラマーであれば既にご存知かもしれませんし、私のような初学者にとってはゼロから導出するプロセスがまた楽しい体験になるはずです。
詳細は、Computer Enhance の購読者特典として無料で配信しております。