4 
Class Diagnostic {

//Get the size in bytes of an object
static long sizeOf(Object object);

//Get the references for an object (leafs)
static List<Object> getRefs(Object object);

//Implement this with those above
public Long objectSize(Object object);
}

オブジェクトのサイズをバイト単位で返すには、objectSize をどのように実装しますか?

メソッド objectSize は、結合されたすべての子ノード (ツリー上のすべてのノード) のサイズをバイト単位で返します。

例： 

               Object A (19 bytes)
                      /    \
                     /      \
                   B(20)    C(37)
                   /
                  /
                C(15)

答え: 19+20+37+15 = 91

インタビュー中にこの質問がありましたが、他の人の答えを知りたいです。以来、ツリートラバーサルアルゴリズムについてはあまり知りませんでした。

私はこれを思いつきました...（私はそれが悪いかどうかを知っています;）、ただ学ぼうとしています）

    public Long objectSize(Object object) {
    List<Object> objectList = new ArrayList<Object>();

    Long sum = sizeOf(object);
    objectList = getRefs(object);

    for(Object object : objectList){
           sum += objectSize(object);
    }

return sum;
}

すでに「ノード」を通過したかどうかを確認していなかったため、サイクルが発生してスタックオーバーフロー エラーが発生する可能性があることに気付きました。次に、比較用の一時リストを処理するために、別のデータ構造 (キー/値を処理するためのハッシュマップなど) を用意する必要があります。

4

3 に答える 3

0

私はそれをテストしませんでしたが、この単純な BFS 検索アルゴリズムはそれを行うはずです。

public Long objectSize(Object object) {
   long sum=sizeOf(object);

   Queue<Object> q= new LinkedList<Object>();
   for (Object o : getRefs(object)) {
      q.add(o);
   }
   while (q.peek() != null) {
      Object child= q.poll();
      sum+= sizeOf(child);
      fore (Object o : getRefs(child)) {
         q.add(o);
      }
   }
   return sum;   
}
于 2013-05-15T13:49:55.927 に答える
0

これが私がすることです：

調査が残っているノードを含むスタックを構築し、それをwhileループで処理します。私のJavaスキルは頭のどこかで失われているので、実装は提供しませんが、プロセスを説明します:

入力:ツリーT
出力:ノード オブジェクトの合計サイズ

  1. T.root (ルートノード) をプッシュしてスタックSを初期化します。
  2. 合計サイズsizeを 0 に初期化: size = 0
  3. Sが空でない場合 :
    1. NをSの先頭とすると、Sをポップします。N = pop ( S )
    2. N.leftChildとN.rightChildが存在する場合はSにプッシュします。
    3. サイズの更新: size = size + N.size
  4. 返品サイズ
于 2013-05-15T14:10:19.850 に答える