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;
}

我注意到我可能有一个循环并运行一个 stackoverflow 错误，因为我没有检查我是否已经通过了一个“节点”。然后我很难我应该有另一个数据结构（如用于处理键/值的哈希图）来处理临时列表以进行比较。

4

3 回答 3

2

如果您正在处理一个真正的“树”结构，那么您不必担心循环。

你已经有了基本的想法，但是你需要考虑递归调用的实际返回值。如果我们假设对象的总大小 ( objectSize()) 等于其子对象的大小之和加上它自己的大小 ( sizeOf())，那么您只需要确保将所有子树大小相加。

这是您可以做到的一种方法：

public Long objectSize(Object object) {
    List<Object> objectList = getRefs(object);
    long sum = sizeOf(object);

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

    return Long.valueOf(sum);
}

您缺少的是递归objectSize调用返回了一个值，并且该值需要包含（在本例中是通过添加）到您的返回值中。

于 2013-05-15T13:49:38.350 回答
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 来初始化堆栈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 回答