美團筆試題目淺析

在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次，還是很耗性能的。