美团笔试题目浅析

在Iteye招聘贴上看到美团的crm后端笔试的题目http://www.iteye.com/topic/1134016，姑且称为笔试吧，感觉还蛮有趣的，

就试着想一想吧

1），二维数组（N*N），沿对角线方向，从右上角打印到左下角如N=4：

4*4二维数组

Java代码  收藏代码

{ 1 2 3 4 } 

{ 5 6 7 8 } 

{ 9 10 11 12 } 

{13 14 15 16 } 

打印顺序

Java代码  收藏代码

4 

3 8 

2 7 12 

1 6 11 16 

5 10 15 

9 14 

13 

这应该很简单的，两个循环就可以搞定了，好吧，我用了递归的，感觉递归实现起来比较省事。

public static int solve(int[][] a)
  { 
	  int N=a.length;
	  if(N==0)
		 return -1; 
	  dfs(a,0,N-1,N);
	    return 1;
  }
  public static void dfs(int [][]arr,int row,int col,int N)
  {
	  if(row<N-1&&col==N-1)
	  {
		  System.out.println(arr[row][col]);
		  dfs(arr,0,N-row-2,N);
		  return ;
	  }
	  if(row==N-1&&col==N-1)
	  {
		  System.out.println(arr[row][col]);
		  dfs(arr,1,0,N);
		  return ;
	  }
	  if(row==N-1&&col<N-1&&col>0)
	  {
		  System.out.println(arr[row][col]);
		  dfs(arr,N-col,0,N);
		  return ;
	  }
	  if(row==N-1&&col==0)
	  {
		  System.out.println(arr[row][col]);
		  return;
	  }
	   System.out.print(arr[row][col]);
	   System.out.print(" ");
	   dfs(arr,row+1,col+1,N);
	   return ;
  }
           

2）java hashmap，如果确定只装载100个元素，new HashMap(?)多少是最佳的，why？

论坛上有人说是100 个，这也不一定啊，题目并没有说可以设定loadFactor为1，如果是1的话

我们可以说是100个，但是没有说的，我们假设就是hashmap的loadFactor为默认值0.75了，但是我们就可以说new HashMap的最佳值为100/0.75=134吗？答案是否定的，好吧用代码解释

测试代码：

HashMap<String,String> has=newHashMap<String,String>(134);
      for(inti=0;i<100;i++)
           has.put("str"+i, "str"+i);
           

debug的时候发现：

所以可以看到其实hashMap 还是容量在256，这是为什么呢？

其实看JDK源码就可以知道：

在HashMap的源代码可以发现

// Find a power of 2 >= initialCapacity
        int capacity = 1;
        while (capacity < initialCapacity)
           capacity <<= 1;
           

所以说capaccity会设置成大于且最接近initialCapacity 的2的幂，如上述的话还是256，那这样的话其实如果129至255其实都是可以的，因为容量会被HashMap 重设，然后说一下为什么要这样估算容量？主要是为了防止HashMap 发生扩容，扩容三部曲：

1）HashMap以两倍扩容

void addEntry(int hash, K key, V value,int bucketIndex) {
    Entry<K,V>e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >=threshold)
            resize(2 * table.length);
    }
           

2）在resize调用transfer将就得HashMap 转移新的hashmap上

void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity ==MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
 
        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable);
        table = newTable;
        threshold = (int)(newCapacity *loadFactor);
}
           

3）这一步是比较好性能的，因为他是把旧的HashMap中的每一个元素都经过新的hash算法定位到新的HashMap的位置上，在插入到新的hashmap上的

void transfer(Entry[] newTable) {
        Entry[] src = table;
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) {
            Entry<K,V> e = src[j];
            if (e !=null) {
                src[j] = null;
                do {
                    Entry<K,V> next = e.next;
                    int i =indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e !=null);
            }
        }
   }
           

总体上来说的话，如果你不事先制定容量的话，只使用HashMap的16*0.75，这要扩容4次，还是很耗性能的。