4

面接の演習で提起された問題を解決しようとしています。面接では解決できなかったので、教えていただけると助かります。

問題は：

整数を取り、最後の 10 分間に呼び出されたメソッドの最大値である整数を返すメソッドを持つクラスを作成します。

私が理解していることから、メソッドが最後の 10 分間に呼び出されたすべての値を保存する必要があります。このメソッドは 1 秒間に数回呼び出される可能性があるため、値は効率的なデータ構造に格納する必要があります。

このためにどのデータ構造がより効率的であるべきかについて何か提案はありますか? また、これはタイム ローリング ウィンドウであるため、期限切れになった値をクリーンアップするにはどうすればよいですか?

使用されるデータ構造に応じて、最大値を取得する最良の方法は何ですか?

私はいくつかの基本コードを持っています:

    private final static ScheduledExecutorService EXECUTOR_SERVICE = Executors.newSingleThreadScheduledExecutor(); 

    private static List<Integer> values = new ArrayList<Integer>();


    public int method(final int value){
        values.add(value);

         // Task to remove the key-value pair     
        Runnable task = new Runnable() {     
            @Override     
            public void run() {     
                values.remove(value);
            }     
        };     

        // Schedule the task to run after the delay  
        EXECUTOR_SERVICE.schedule(task, 60, TimeUnit.SECONDS);  


        //TODO get the max value
        return 1;
    }
4

4 に答える 4

2

これは実際には、償却された定数時間で実行できます。

values := deque of timestamped values

function prune()
    while values.front is older than 10 minutes
        values.pop_front()

function add(v)
    while values is not empty and v is greater than values.back
        values.pop_back()
    values.push_back(v)

function getMax()
    prune()
    return values.front()

値は、新しい値を取得すると、小さい古い値を忘れる可能性があるという観測を使用して、降順で格納されます。

于 2013-05-17T11:40:18.747 に答える