設計問題では、それぞれにコストの目標がある複数の操作を持つ小さなクラスを作るよう求められます。要点は、どの操作も安く済むようにどんな状態を保持するかを決め、変更のたびにその状態を正しく保つことです。
まず操作とその目標コストを書き出してください。操作がO(1)でなければならないなら走査はできないので、答えはすでにどこかに保存されている必要があります。ポップしても最小値が失われないようにするには、各要素と一緒に最小値を保存します。タイマーを使わないレート制限とは、リクエストが届いたときに遅延的に補充することです。コピーなしでバージョンごとの読み取りを行うには、変更だけを保存してそれを探索します。
これらの練習問題では、チェッカーがテストできるようにクラスを操作のリストで再生しますが、面接ではクラスとして説明してください:フィールドを挙げ、各メソッドのコストを示し、どのメソッドもどの不変条件を保つかを述べます。続けて、エッジケースを声に出してテストしてください:空の構造、重複する値、最初と最後のバージョンです。