帮朋友发google onsite面经

1
lc 66, 原题 Plus One

2
1）
Unique Paths 变体
m * n的矩阵， 每一格有一个数字
求从左上角到右下角，和最大的路径

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

（print）

一共四轮，有一轮半是工作经验，自我介绍，项目和behavior。

我觉得我的这个dp应该是work了，结果有701149020种（7亿种，确实很多）。不过是秒出的结果。所以应该是work了
code如下：

int count(int n) {
    map<vector<int>, int> countMap;
    countMap[vector<int>(n, 0)] = 1;
    for (int i = 1; i <= n * n; i++) {
        map<vector<int>, int> newCountMap;
        for (auto cur : countMap) {
            vector<int> curVec = cur.first;
            int curCount = cur.second;
            for (int j = 0; j < n; j++) {
                if ((j == 0 || curVec[j] < curVec[j - 1]) && curVec[j] < n) {
                    curVec[j]++;
                    newCountMap[curVec] += curCount;
                    curVec[j]--;
                }
            }
        }
        countMap = newCountMap;
    }
    return countMap.begin()->second;
}

解释一下：这里是逐个填入1到25的，dp是用在了 “只考虑count，不记录结果” 这一点上面。其中countMap是一个把vector映到int的map，vector就表示当前的选取方法，而int是选取方法对应的count数，
比如vector是 [4,3,2,1,1] 就表示第一行填了前4个，第二行填了前三个这样这样。（因为4+3+2+1+1=11，所以当前一定是在处理i=11这个数）每次一个大循环的loop结束后，newCount里面就存了填入第i个数后，所有的填法以及每个填法对应的count。所有可能的状态数大概是 5! 种（也就是非严格单减序列的个数，比 5!稍多，不过差不太多，）每个状态数会用常数时间（严格来说是 O(5)）处理，所以整体的时间比最终的结果数小很多。

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

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]]

请问LZ, "给一个5*5的矩阵， 把数字1到25填进不同的格子， 要求相同行相同列的数字递增"有什么解法？

同问第二题的5*5 矩阵的方法，谢谢 ~~~

刚开始以为第二题是个递归题和八皇后差不多
写了一个递归dfs的，跑了不到10分钟跑出30多万个解，完全吓尿了。。
这题一定有dp解，但我还没想出来

tltzhsajsdr 发表于 2016-1-10 01:49
刚开始以为第二题是个递归题和八皇后差不多
写了一个递归dfs的，跑了不到10分钟跑出30多万个解，完全吓尿 ...

艾玛 dfs+backtracking 结果7亿多个解法。。。。醉了

这个题暴力dfs的话不可行， 需要剪枝。
dfs满足两个条件
1、 1到25逐个填入值
2、 当前行的个数不能大于上一行

我怎么觉得他的onsite怎么这么难呢？

redkaras 发表于 2016-1-10 16:09
这个题暴力dfs的话不可行， 需要剪枝。
dfs满足两个条件
1、 1到25逐个填入值

问题是，如果解法本身就有几十万种甚至几亿种，那你再怎么剪枝也没用啊。

我好像想到一个dp的解法，等下试试看work不。

第一题的follow up 怎么做？
有假定说每个格子里的数字都是非负的吗？