帮朋友发google onsite面经

bobzhang2004 发表于 2016-2-4 11:43
不太懂c++ code，这个countMap对应的是java中的hashmap? 那vector是array, 如果这样的话这key有点奇怪啊

Java版，楼主的算法，比楼主的长很多，因为JAVA的数组的相等不是比值，

        public int count(int n) {
                Map<List<Integer>, Integer> countMap = new HashMap<>();
                countMap.put(new ArrayList<>(), 1);
                for (int i = 0; i < n * n; i++) {
                        Map<List<Integer>, Integer> newCountMap = new HashMap<>();
                        for (Map.Entry<List<Integer>, Integer> entry : countMap.entrySet()) {
                                List<Integer> currList = entry.getKey();
                                int currCount = entry.getValue();
                                for (int j = 0; j < currList.size(); j++) {
                                        if ((j == 0 || currList.get(j) < currList.get(j - 1)) && currList.get(j) < n) {
                                                List<Integer> newList = new ArrayList<>(currList);
                                                newList.set(j, newList.get(j) + 1);
                                                addToNewMap(newCountMap, currCount, newList);
                                        }
                                }
                                if (currList.size() < n) {
                                        List<Integer> newList = new ArrayList<>(currList);
                                        newList.add(1);
                                        addToNewMap(newCountMap, currCount, newList);
                                }
                        }
                        countMap = newCountMap;
                }
                return countMap.entrySet().iterator().next().getValue();
        }

        private void addToNewMap(Map<List<Integer>, Integer> newCountMap, int currCount, List<Integer> newList) {
                if (newCountMap.containsKey(newList)) {
                        newCountMap.put(newList, newCountMap.get(newList) + currCount);
                } else {
                        newCountMap.put(newList, currCount);
                }
        }

补充内容 (2016-4-30 11:19):
不是楼主， 是163

The following is my JAVA solution, similar to 163'.

1. 
   
2. import java.util.*;
   
3. class Solution{
   
4.     static long solve(int n){
   
5.         Map<List<Integer>,Long> map=new HashMap<>(), alt=new HashMap<>(), temp;
   
6.         List<Integer> stat=new ArrayList<>();
   
7.         for(int i=0; i<n; i++) stat.add(0);
   
8.         map.put(stat,1l);
   
9.         for(int j=1; j<=n*n; j++){
   
10.             alt.clear();
    
11.             for(Map.Entry<List<Integer>,Long> entry:map.entrySet()){
    
12.                 stat=entry.getKey();
    
13.                 long count=entry.getValue();
    
14.                 for(int i=0; i<n; i++){
    
15.                     if((i==0 && stat.get(i)<n) || (i>0 && stat.get(i)<stat.get(i-1))){
    
16.                         List<Integer> newStat=new ArrayList<>(stat);
    
17.                         newStat.set(i,stat.get(i)+1);
    
18.                         Long newC=alt.get(newStat);
    
19.                         if(newC==null)
    
20.                             alt.put(newStat,count);
    
21.                         else
    
22.                             alt.put(newStat,newC+count);
    
23.                     }
    
24.                 }
    
25.             }
    
26.             temp=alt; alt=map; map=temp;
    
27.         }
    
28.         System.out.println(map);
    
29.         return 1;
    
30.     }
    
31.     public static void main(String[] args){
    
32.         System.out.format("%d: %d\n", 5, solve(5));
    
33. 
    
34.     }
    
35. }
    

复制代码

第一题follow up是不是最小费用流？

每个点拆成i->i'，流量1（起点流量为2），费用为格子数值的负数
相邻的格子连边i'->j，流量1，费用为0
源点就是左上角的点，汇点就是最右下角的点
答案就是: abs(最小费用) - 原点格子的值 - 终点格子的值（后两个算了两遍，所以要减掉）

基于163给个python解法 存的tuple为key
def waysToFillMatrix(n):
        # store current state and number of ways to get to current state
        # number of filled cells in each row
        dic = {(0,) * n:1}
        for i in range(n * n):
                newDic = {}
                for state in dic:
                        for j in range(n):
                                # row j-1 must have more cells filled than row j
                                if (j == 0 or state[j - 1] > state[j]) and state[j] < n:
                                        newState = state[:j] + (state[j] + 1,) + state[j + 1:]
                                        newDic[newState] = newDic.get(newState, 0) + dic[state]
                dic = newDic
        return dic[dic.keys()[0]]

print waysToFillMatrix(1)
print waysToFillMatrix(2)
print waysToFillMatrix(3)
print waysToFillMatrix(4)
print waysToFillMatrix(5)
print waysToFillMatrix(6)

163的记录状态方法好好用 也写了两个人走grid的那题

def twoPeoplePath(grid):
        m, n = len(grid), len(grid[0])
        # positions of two people and max gain
        dic = {(0, 0): grid[0][0]}
        for i in range(m + n - 2):
                newDic = {}
                for state in dic:
                        a, b = state
                        x1, y1 = a / n, a % n
                        x2, y2 = b / n, b % n
                        for i1, j1 in (x1 + 1, y1), (x1, y1 + 1):
                                if -1 < i1 < m and -1 < j1 < n:
                                        for i2, j2 in (x2 + 1, y2), (x2, y2 + 1):
                                                if -1 < i2 < m and -1 < j2 < n:
                                                        newState = (i1 * n + j1, i2 * n + j2)
                                                        total = dic[state] + grid[i1][j1] + (0 if i1 == i2 and j1 == j2 else grid[i2][j2])
                                                        if newState not in newDic:
                                                                newDic[newState] = total
                                                        else:
                                                                if newDic[newState] < total:
                                                                        newDic[newState] = total
                dic = newDic
        return dic[dic.keys()[0]]

163 发表于 2016-1-11 01:51
我觉得我的这个dp应该是work了，结果有701149020种（7亿种，确实很多）。不过是秒出的结果。所以应该是work ...

有点不太明白，  开始一个没填 [0,0,0,0,0] , count =1,
第一行填一个数， 只能填1（最小）， [1,0,0,0,0], count=1 也可以理解，
下一个循环， [2,0,0,0,0] [1,1,0,0,0] count 为啥也是 1 啊， 有很多种填法呀。

lvvvvv 发表于 2016-8-28 10:24
有点不太明白，  开始一个没填 [0,0,0,0,0] , count =1,
第一行填一个数， 只能填1（最小）， [1,0,0,0 ...

每个hash里的value指的是到当前状态的填法，一个都不填的填法是1
i-1排填的数量必须大于等于i排，你试着手填一下就发现了

pushazhiniao 发表于 2016-8-29 01:41
每个hash里的value指的是到当前状态的填法，一个都不填的填法是1
i-1排填的数量必须大于等于i排，你试着 ...

我明白了， i 是当前要往里填的数。

谢谢

第一题是双调欧几里得回路。
当做两个人同时往下走就好了，状态很好推。状态划分是斜线。

南慕伦 发表于 2016-8-30 07:02
第一题是双调欧几里得回路。
当做两个人同时往下走就好了，状态很好推。状态划分是斜线。

能不能给稍微详细一点的解法呢？多谢！