高分求教Oracle公司笔试答案

Question

1、please realize the defined function to get the height of BinaryTree predifined tree structure
java:
   public interface Tree{
             public object getValue();
             public Tree getLchild();
              public Tree getRchild();
} The Function which you need to realize 
long getTreeHeight(Tree t);
2 There are 50 persons standing in a circle for a team, those who count the number 3 or multiple of 3 should leave from the circle, who is the last one in the circle? Please implement a class to get the persons original position in the circle...

Answer 1

http://steven-hong.javaeye.com/blog/491982注意我的头像！

Answer 2

long getTreeHeight(Tree t){
long rHight = getTreeHeight(t.getRchild());
long lHight = getTreeHeight(t.getLchild());

long max = rHight > lHight ? rHight : lHight;
return max + 1;
}

Answer 3

第二题给你一个成品吧....public class TestRound {
public static void print(int number,int count) {
ArrayList list = new ArrayList();
for (int i = 1; i <=number; i++) {
list.add(i);
}
for (int i = 1; list.size() > 1; i++) {
if (i % count == 0) {
System.out.println(list.remove(0) + "-->");
} else {
list.add(list.remove(0));
}
}
System.out.println("最后一位："+list.get(0));
}
public static void main(String[] args) {
print(50,3);
}
}输出结果：
3-->
6-->
9-->
12-->
15-->
18-->
21-->
24-->
27-->
30-->
33-->
36-->
39-->
42-->
45-->
48-->
1-->
5-->
10-->
14-->
19-->
23-->
28-->
32-->
37-->
41-->
46-->
50-->
7-->
13-->
20-->
26-->
34-->
40-->
47-->
4-->
16-->
25-->
35-->
44-->
8-->
22-->
38-->
2-->
29-->
49-->
31-->
17-->
43-->
最后一位：11

Answer 4

第一个题 
int sum = 0; 记录二叉树最大层数sum 
int count; 记录叶节点的层数
使用深度优先周游二叉树算法，递归得到每一个叶节点
while(叶节点有父节点){
count++;
} 
if(count>sum){
count = sum;
}
递归完后得到每一个叶节点的层数的最大值sum，sum+1就是二叉树的高度，我的基本思路是这样的
第二题是约瑟夫环问题 
百度搜索约瑟夫换就可以得到详细解答

Answer 5

第2题package com.keeya.saved;public class Josephus {
  /**
   * 自己的编号
   */
  private final int number;   /**
   * 链表指针
   */
  private Josephus previous;   /**
   * 链表指针
   */
  private Josephus next;   /**
   * 创建一个新的<code>Josephus</code>对象。
   * 
   * @param number
   *          自己的编号
   */
  public Josephus(int number) {
    this.number = number;
  }   
  /**
   * 返回 <code>number</code> 的当前值。
   *
   * @return <code>number</code> 的当前值
   */
  public int getNumber() {
    return number;
  }   /**
   * 返回 <code>previous</code> 的当前值。
   * 
   * @return <code>previous</code> 的当前值
   */
  public Josephus getPrevious() {
    return previous;
  }   /**
   * 设置 <code>previous</code> 的当前值。
   * 
   * @param previous
   *          <code>previous</code> 的当前值
   */
  public void setPrevious(Josephus previous) {
    this.previous = previous;
  }   /**
   * 返回 <code>next</code> 的当前值。
   * 
   * @return <code>next</code> 的当前值
   */
  public Josephus getNext() {
    return next;
  }   /**
   * 设置 <code>next</code> 的当前值。
   * 
   * @param next
   *          <code>next</code> 的当前值
   */
  public void setNext(Josephus next) {
    this.next = next;
  }   /**
   * 从自己开始报数，报到的人被踢走。
   * 
   * @param n
   *          报的数字
   * @return 被踢走的人
   */
  public Josephus startCountingOut(int n) {
    Josephus current = this;
    for (int i = 1; i < n; i++) {
      current = current.getNext();
    }
    return current.countOut();
  }   /**
   * 从自己开始报3个数，报到的人被踢走。
   * 
   * @return 被踢走的人
   */
  public Josephus startCountingOut() {
    return startCountingOut(3);
  }   /**
   * 被报到，而被踢走
   * 
   * @return 被踢走的人
   */
  private Josephus countOut() {
    previous.setNext(next);
    next.setPrevious(previous);
    return this;
  }
  
  @Override
  public String toString() {
    StringBuilder buff = new StringBuilder(64);
    buff.append("Josephus");
    buff.append("\nNum:  ").append(number);
    buff.append("\nPrev: ").append(previous.getNumber());
    buff.append("\nNext: ").append(next.getNumber());
    return buff.toString();
  }
     public static Josephus init(int n) {
    Josephus[] arrays = new Josephus[n];
    for (int i = 0; i < arrays.length; i++) {
      arrays[i] = new Josephus(i);
    }
    for (int i = 0; i < arrays.length; i++) {
      arrays[i].setNext(arrays[(i + 1) % n]);
      arrays[i].setPrevious(arrays[(i + n - 1) % n]);
    }
    return arrays[0];
  }   public static void main(String[] args) {
    Josephus j = init(50);
    do {
      System.out.println("报数的人:");
      System.out.println(j);
      j = j.startCountingOut();
      System.out.println("被踢走的人:");
      System.out.println(j);
      // 移交给下一个人
      j = j.getNext();
    } while ((j.getNext()) != j); // 就他一个了
    System.out.println("最后的幸存者:");
    System.out.println(j);
  }
}