保持する必要がある結果からデータ構造を選び、その不変条件を述べてください。この練習セットでは、トライ木、ヒープ、区間、木、連結リスト、単調な走査にわたる新しい課題を使います。業務の設定は変わりますが、正しさを決めるのはやはり比較と境界のルールです。
各問題について、コードを書く前にアプローチと想定される計算量を説明してください。空または最小の入力のテストを1つと、同値、答えがない場合、端点の境界のいずれかのテストを1つ書いてください。その後、面接で使う予定の言語で解答を実装してください。最初の案がすべてを並べ替えるものなら、小さいヒープや二分探索木の直接の探索で処理を減らせないか検討してください。判定は正しい実装ならどれでも受け付けるので、選んだアプローチのコストを説明してください。
いくつかの課題は順序付きのリストを返しますが、保持する状態はそれぞれ異なります。フォルダーの候補表示には、文字の接頭辞による所属判定と辞書順の走査が必要です。最も近い乗車地点には、座標が同じ場合の扱いを明示した順位付けのキーが必要なので、上限付きヒープはそのキー全体の逆順を使って候補を捨てます。両方の後続部分はすでに並べ替え済みなので、連結されたレーンをマージするときは、現在の2つの先頭を比べるだけで済みます。構造を選ぶ前に、入力が何を保証し、出力が何を求めているかを確認してください。区間の端点、木の高さ、リストの末尾は、それぞれ異なる情報を要約しており、間違った要約を持ち回ると、もっともらしく見えても不変条件が成り立たないアルゴリズムになります。