私が好きなソフトウェアエンジニアリング面接の質問：中央値の計算

 (krisshamloo.com)
1 ポイント 投稿者 GN⁺ 4 시간 전 | 1件のコメント | WhatsAppで共有
  • 技術面接の小さな実装問題はパズルより効果的なことがあり、中央値の計算は基本的なコーディング能力と設計センスを同時に示す
  • ソートが必要な問題なので、関数が直接ソートするのか、呼び出し側がソートするのか、元の配列を変更してもよいのかといったAPIの議論へ自然につながる
  • 奇数長と偶数長を分ける分岐、インデックス計算、off-by-oneミスは、候補者のデバッグ過程を観察するのに適している
  • 中央値と平均値の違い、テストの書きやすさ、Pythonのstatistics標準ライブラリの知識まで、短い問題の中で確認できる
  • サンプル実装は空リストでValueErrorを投げ、sorted()でコピーをソートしたうえで、偶数長では中央の2つの値の平均、奇数長では中央の値を返す

中央値の問題が面接に適している理由

  • 良い技術面接の質問は、パズルのようにひねった問題ではなく、直感的な実装の中からより深いテーマを引き出せるものであるべき
  • 「数値の配列を受け取り中央値を返す関数を書け」という質問は、候補者が実際にプログラミングできるかを確認するFizz Buzz系のシグナルとして使いやすい
  • 配列の値を1つの結果に集約する作業は基本能力にあたり、問題自体も十分に小さいため、会話とデバッグを一緒に見やすい

実装過程で表れる判断ポイント

  • 中央値の計算にはまずソートが必要
    • 関数が直接ソートするのか、呼び出し側がソート済み配列を渡すべきなのかを決める必要がある
    • 配列が参照で渡される場合、元の配列を変更してよいかどうかもAPI契約に含まれる
    • こうした選択は性能に関する議論にもつながる
  • インデックス計算にはoff-by-oneの落とし穴がある
    • ミスの有無よりも、小さな問題をどうデバッグするかを観察できる
  • 配列の長さによって返し方が変わる
    • 偶数長では中央の2つの値の平均を返す
    • 奇数長では中央の値を返す

短い問題から広がる会話

  • 中央値は平均値と比べて、ほとんどの場合になぜより良い選択になり得るのかといった統計の議論につなげられる
  • 入力と期待値が単純でテストしやすく、候補者がテストの感覚を示しやすい
  • Pythonではstatistics標準ライブラリの知識を示す機会にもなる

サンプルPython実装での選択

  • 空リストではValueError("median called with empty list")を発生させる
  • sorted(numbers)を使い、numbers.sort()とは異なり入力リストを直接ソートしない
  • 長さはlen(numbers)で求め、中央のインデックスはmid = length // 2で計算する
  • 偶数長では(numbers[mid - 1] + numbers[mid]) / 2.0を返し、奇数長ではnumbers[mid]を返す

関連記事

1件のコメント

 
GN⁺ 4 시간 전
Lobste.rs のコメント

  • この記事はよく理解できない。筆者は中央値は O(n) で計算できることを知らないように見える。参考: https://rcoh.me/posts/linear-time-median-finding/
    だから「最初から数値はソートされていなければならない」という話は間違っている。この理由から、よい面接問題でもないと思う。最適解は複雑なアルゴリズムなので、暗記して知っている場合でもなければその場で期待するのは難しく、暗記しているかどうかも候補者評価にはあまり役立たない。
    むしろ候補者に、配列をライブラリ関数でソートしてから中央の値を返すナイーブな解法を出してもらうことはできる

    • この問題に n*log(n) の解法を出して電話面接で落とされた記憶があるので、腹が立ちかけた
      後でアルゴリズムの授業で quickselect を学び、「まさかその場でこれを思いつくことを期待していたわけじゃないよな」と思った。まあ、その職務に合っていなかったのかもしれない
    • 筆者です。候補者が quickselect に言及したら、かなり印象的だと思う。それでも、これが悪い質問だとは思わない。直感的なアルゴリズムだけでも話せることは多い
      「配列をライブラリ関数でソートしてから中央の値を返すナイーブな解法」を期待できるという話については、候補者に python standard library より優れたコードを期待しているわけではない

  • おまけに、誰かがアルゴリズムを勉強したか、少なくとも面接対策をしたかがすぐ分かる。quickselect を使おうと提案するはずだから: https://en.wikipedia.org/wiki/Quickselect

    • それが言及されていなくて驚いた。この質問を受けて C++ を使うなら、nth_element を使うと思う
      そして quickselect を一から自分で書く必要があるなら、それもできる。基本的には分割 + 二分探索に近い
    • 実際にはそうではないと思う。この質問は基本的な「本当にプログラミングできるのか？」、つまり「スクリーナーが自分の仕事をきちんとしたのか？」を見る問題のように見える。quickselect を頭の中でスラスラ説明できたとしても、完璧にはできない気がするし、面接官の時間を無駄にしないためにナイーブな解法を選ぶだろう
    • 配列長が偶数の場合が興味深い。中央の2つのインデックスに対して一般的な quickselect を2回走らせるか、作業に合わせて quickselect を調整する形になる。両者は実質的に同じことになる場合もある
    • リストは必ずソートされていなければならないという要件があって混乱した。直感的にも、必ずそうである必要はない
    • LLM から得た答えがこれで、必要なら選べるイミュータブルな変形までおまけで付いていた

  • Python の int 型にはオーバーフローがないが、C や C++ や Go を使うなら、偶数長配列の分岐で加算オーバーフローも心配すべきではないか？

    • その加算は int ではなく float で起きる。それでもオーバーフローして inf になる可能性はある。配列の2つの要素がどちらも sys.float_info.max なら答えも sys.float_info.max であるべきだが、加算結果は inf になり、それを2で割っても依然として inf のままだ
      加算について2で割る操作を分配して直そうとすることはできるが、そうすると非正規化数では誤った答えになる。多くの場合、プログラムにこの問題が起きるほど大きな数は出てこないと仮定しているようだ。numpy もここでは警告とともに inf を出す: 
      >>> import sys  
>>> import numpy  
>>> numpy.median([sys.float_info.max, sys.float_info.max])  
.../venv/lib64/python3.11/site-packages/numpy/_core/_methods.py:132: RuntimeWarning: overflow encountered in reduce  
  ret = umr_sum(arr, axis, dtype, out, keepdims, where=where)  
np.float64(inf)

  • 実際、中央値そのものを選ぶ方法もいくつかある。線形補間をするのか、上側を使うのか、下側を使うのかといった選択がある
    そして分位数に進むと、何時間でも話せる。1つだけ選ぶ場合と複数を一度に選ぶ場合では、アプローチを変えるべきだ

  • 元記事のような面接問題は使わない。私はなめらかさを求めていて、問題を解く難易度が候補者の能力と経験に応じて滑らかに変化すべきだという意味だ。特にライブラリ関数や quickselect、基数ソートのようなアルゴリズムの存在を知っているかどうかで結果が急激に変わるなら、測定用としてよい問題ではない
    候補者の経験と能力を測るのではなく、特定の魔法のアイテムを知っているかを試しているようなものだ。フォローアップ質問で補うことはできるが、最初からもっとなめらかな問題を出すほうがよい

    • 共有できるなら、そういうなめらかな問題の具体例がとても気になる