一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 5572|回复: 31
收起左侧

帮朋友发google onsite面经

[复制链接] |试试Instant~ |关注本帖
cjlm007 发表于 2016-1-9 13:01:25 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 本科 全职@Google - 内推 - Onsite |Other在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
1. from: 1point3acres.com/bbs
lc 66, 原题 Plus One

2
1)
Unique Paths 变体
m * n的矩阵, 每一格有一个数字
求从左上角到右下角,和最大的路径
followup: 如果两个人一起从左上角走, 每个人到了一个格子之后会把该格子的数清零。 求两个人走的路径和的最大值
2)
给一个5*5的矩阵, 把数字1到25填进不同的格子, 要求相同行相同列的数字递增
求有多少种放法

3
给一个字符串s和整数k
求包含k个不同字符的滑动窗的最大长度
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
4
lc 212. Word Search II (print)

一共四轮,有一轮半是工作经验,自我介绍,项目和behavior。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

. From 1point 3acres bbs

评分

1

查看全部评分

本帖被以下淘专辑推荐:

163 发表于 2016-1-11 01:51:25 | 显示全部楼层
我觉得我的这个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++) {. 1point 3acres 璁哄潧
                if ((j == 0 || curVec[j] < curVec[j - 1]) && curVec[j] < n) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                    curVec[j]++;
                    newCountMap[curVec] += curCount;
                    curVec[j]--;.1point3acres缃
                }
            }
        }
        countMap = newCountMap;
    }
    return countMap.begin()->second;-google 1point3acres
}. 1point3acres.com/bbs
.鐣欏璁哄潧-涓浜-涓夊垎鍦
解释一下:这里是逐个填入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))处理,所以整体的时间比最终的结果数小很多。

评分

1

查看全部评分

回复 支持 3 反对 0

使用道具 举报

xiaobao9 发表于 2016-1-9 14:39:10 | 显示全部楼层
请问LZ, "给一个5*5的矩阵, 把数字1到25填进不同的格子, 要求相同行相同列的数字递增"有什么解法?
回复 支持 反对

使用道具 举报

ninacc 发表于 2016-1-10 13:55:22 | 显示全部楼层
同问第二题的5*5 矩阵的方法,谢谢 ~~~
回复 支持 反对

使用道具 举报

tltzhsajsdr 发表于 2016-1-10 14:49:36 | 显示全部楼层
刚开始以为第二题是个递归题和八皇后差不多
写了一个递归dfs的,跑了不到10分钟跑出30多万个解,完全吓尿了。。
这题一定有dp解,但我还没想出来
回复 支持 反对

使用道具 举报

ninacc 发表于 2016-1-10 14:59:16 | 显示全部楼层
tltzhsajsdr 发表于 2016-1-10 01:49
刚开始以为第二题是个递归题和八皇后差不多.1point3acres缃
写了一个递归dfs的,跑了不到10分钟跑出30多万个解,完全吓尿 ...

艾玛 dfs+backtracking 结果7亿多个解法。。。。醉了
回复 支持 反对

使用道具 举报

redkaras 发表于 2016-1-10 16:09:12 | 显示全部楼层
这个题暴力dfs的话不可行, 需要剪枝。
dfs满足两个条件
1、 1到25逐个填入值
2、 当前行的个数不能大于上一行

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

fatalme 发表于 2016-1-10 22:35:12 | 显示全部楼层
我怎么觉得他的onsite怎么这么难呢?
回复 支持 反对

使用道具 举报

163 发表于 2016-1-11 00:53:08 | 显示全部楼层
redkaras 发表于 2016-1-10 16:09. 1point 3acres 璁哄潧
这个题暴力dfs的话不可行, 需要剪枝。
dfs满足两个条件
1、 1到25逐个填入值

问题是,如果解法本身就有几十万种甚至几亿种,那你再怎么剪枝也没用啊。
回复 支持 反对

使用道具 举报

163 发表于 2016-1-11 00:57:08 | 显示全部楼层
我好像想到一个dp的解法,等下试试看work不。
回复 支持 反对

使用道具 举报

163 发表于 2016-1-11 01:01:54 | 显示全部楼层
第一题的follow up 怎么做?.1point3acres缃
有假定说每个格子里的数字都是非负的吗?
回复 支持 反对

使用道具 举报

sonicgu 发表于 2016-1-11 01:29:12 | 显示全部楼层
可以根据杨氏矩阵的性质进行剪枝
回复 支持 反对

使用道具 举报

163 发表于 2016-1-11 01:57:22 | 显示全部楼层
另外,如上code使用了map,略微拖慢了运行速度(虽然算5x5的基本看不出来什么区别)。
可以换成一个5x5x5x5x5的数组+queue做bfs,来处理是否访问过的问题。这样会把复杂度扔掉一个log factor

我还做了些其他测试,事实发现这个东西随n增大(这里n=5),那个count数涨的非常快。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
n=1: 1
n=2: 2. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
n=3: 42
n=4: 24024
n=5: 701149020. 1point 3acres 璁哄潧
n=6: 1671643033734960 (已经超出 int的范围了,是用long 算的)

我的code可以跑n=10,大概要3秒左右。复杂度基本是 n! 量级,当然n=10的结果肯定就是错的了,这个count随n增大会迅速变成天文数字。
回复 支持 反对

使用道具 举报

ninacc 发表于 2016-1-11 02:15:59 | 显示全部楼层
163 发表于 2016-1-10 12:51
我觉得我的这个dp应该是work了,结果有701149020种(7亿种,确实很多)。不过是秒出的结果。所以应该是work ...

好厉害!!!DFS+backtracing用了剪枝40+秒,是应该用DP做更好,厉害!
回复 支持 反对

使用道具 举报

2Young2Simple 发表于 2016-1-11 06:28:34 | 显示全部楼层
Uique Path的follow up 楼主是怎么解决的啊?
回复 支持 反对

使用道具 举报

say543 发表于 2016-1-11 15:28:39 | 显示全部楼层
想知道unique path follow -up 怎么解的?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-2-4 11:43:31 | 显示全部楼层
163 发表于 2016-1-11 01:51
我觉得我的这个dp应该是work了,结果有701149020种(7亿种,确实很多)。不过是秒出的结果。所以应该是work ...

不太懂c++ code,这个countMap对应的是java中的hashmap? 那vector<int>是array, 如果这样的话这key有点奇怪啊
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-2-4 12:27:41 | 显示全部楼层
两个人一起走那个能先用dp算一个人的 同时刷新矩阵 再用dp算第二个人的 求和。不知道对不对
回复 支持 反对

使用道具 举报

kittycerry 发表于 2016-4-13 03:01:10 | 显示全部楼层
kinggarden2001 发表于 2016-2-4 12:27
两个人一起走那个能先用dp算一个人的 同时刷新矩阵 再用dp算第二个人的 求和。不知道对不对

应该走一遍就可以。。。每次取最好的两个
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-4-25 06:40:44 | 显示全部楼层
同想问路径和的follow应该怎么考虑
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 06:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表