一亩三分地论坛

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

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

Google电面面经

[复制链接] |试试Instant~ |关注本帖
三低励志 发表于 2015-10-21 07:16:09 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Google - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
刚刚google电面面完,听说发到这里会有大米什么的?

就一个编程题,n个borad,两个颜色,相邻的三个board不能相同颜色,求一共能有多少可能的涂法。

LZ一开始想求出所有可能的涂法然后再去判断,然后面试官姐姐说只用求个数,不需要具体的涂法,lz就想到用dp,想了半天还是没想出递归式,面试官姐姐就说还是回到第一个方法上去吧,然后就用递归做了,在提示下做了一点优化,每加一个就和前两个颜色做比较,lz用的是list存储的,勉强写完。之后又问有没有可能优化,list那里能不能用别的数据结构,lz之后才想到可以用size3的queue做...
. 鍥磋鎴戜滑@1point 3 acres
不知道有没有更好的解法。坐等大神现身,另外求个onsite,拿不到offer去蹭个饭也不错。

bless~~~. 1point3acres.com/bbs

评分

3

查看全部评分

本帖被以下淘专辑推荐:

Linzertorte 发表于 2015-10-21 07:43:00 | 显示全部楼层
  1. def f(n):
  2.     if n==1: return 2;
  3.     dp[2][0][1] = dp[2][0][0] = dp[2][1][0] = dp[2][1][2] = 1
  4.     for i=3;i<=n;i++ {
  5.       dp[i][0][1] = dp[i-1][1][0] + dp[i-1][0][0]
  6.       dp[i][0][0] = dp[i-1][1][0]
  7.       dp[i][1][0] = dp[i-1][0][1]+dp[i-1][1][1]. from: 1point3acres.com/bbs
  8.       dp[i][1][1] = dp[i-1][0][1]
  9.     }
  10.     return dp[n][0][0]+dp[n][0][1]+dp[n][1][0]+dp[n][1][1]
复制代码
回复 支持 1 反对 0

使用道具 举报

DK_BurNing 发表于 2015-10-21 07:20:29 | 显示全部楼层
是LC上Paint Fence这道题?
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-10-21 07:36:11 | 显示全部楼层
dp(i,x,y) 表示 前i个屋子已经涂了,第i个涂的颜色为y,第i-1涂的颜色为x的方法数。
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-10-21 07:44:41 | 显示全部楼层
这题简直是矩阵乘法的例题
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-10-21 07:50:30 | 显示全部楼层
  1. A=[0,0,1,0;
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  2.       1,0,1,0;
  3.       0,1,0,1;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  4.       0,1,0,0]
  5. if n==1: return 2;. from: 1point3acres.com/bbs
  6. else  return sum(A^(n-1))
复制代码

补充内容 (2015-10-21 08:04):
return sum(A^(n-2))
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-10-21 07:55:05 | 显示全部楼层
DP关系式应该是  res [ i ] = 2 * res [ i - 3 ] + res [ i - 1 ] 吧?
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-10-21 07:55:35 | 显示全部楼层
宝贝忆彼岸 发表于 2015-10-21 07:55
DP关系式应该是  res [ i ] = 2 * res [ i - 3 ] + res [ i - 1 ] 吧?

res [ i ] 表示前 i 个房子一共有多少种涂法
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-10-21 08:04:45 | 显示全部楼层
宝贝忆彼岸 发表于 2015-10-21 07:55
res [ i ] 表示前 i 个房子一共有多少种涂法

n=10的时候,结果是几?
回复 支持 反对

使用道具 举报

姐姐不吃糖 发表于 2015-10-21 08:10:16 | 显示全部楼层
应该是dp[i] = 2 x dp[i-1] - dp[i-3] 吧
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-10-21 08:18:12 | 显示全部楼层
Linzertorte 发表于 2015-10-21 08:04
n=10的时候,结果是几?

我的方法算出来是246,我也不知道对不对
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-10-21 08:22:17 | 显示全部楼层
参考n=10 , return 178
1.png
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-10-21 08:27:44 | 显示全部楼层
  1. def dfs(i):. from: 1point3acres.com/bbs
  2.     if i==0: return ['']
  3.     return [p+x for p in dfs(i-1) for x in '01']

  4. all = dfs(10)
  5. print len(all)
  6. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  7. def good(x):
  8.     n = len(x). more info on 1point3acres.com
  9.     for i in xrange(3,n+1):
  10.         if x[i-3:i]=='111' or x[i-3:i]=='000': return False
  11.     return True

  12. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  13. print len(filter(good,all))
复制代码
这个暴力枚举的程序表明n=10 的时候 ,是178
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-10-21 08:33:14 | 显示全部楼层

对,应该是178,我错了,改了一下
res [ i ] = res [ i - 1 ] + res [ i - 2 ];
回复 支持 反对

使用道具 举报

姐姐不吃糖 发表于 2015-10-21 08:36:31 | 显示全部楼层
不知道178对不对 至少我的算出来也是178
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-10-21 08:37:28 | 显示全部楼层
姐姐不吃糖 发表于 2015-10-21 08:36
不知道178对不对 至少我的算出来也是178

当然对啦。。暴力求解的能用错?
回复 支持 反对

使用道具 举报

marthew777 发表于 2015-10-21 09:02:08 | 显示全部楼层
感谢LZ分享! 不过楼主你笔误了把?题目是给了3个颜色,不是2个把。。要不然怎么做到相邻3个board颜色不同。
回复 支持 反对

使用道具 举报

bunnyNova 发表于 2015-10-21 09:10:38 | 显示全部楼层
leetcode paint fence
回复 支持 反对

使用道具 举报

lll_2013 发表于 2015-10-21 10:03:18 | 显示全部楼层
不知道可不可以这样啊。。。same[1] = 2, diff[1] = 2; same[i] = diff [ i - 1]; diff[i] =same[i - 1] + diff[i - 1]; return diff[n -1] + same [n - 1] ,请大家指正,谢谢啦
回复 支持 反对

使用道具 举报

smallshrimp 发表于 2015-10-22 03:32:52 | 显示全部楼层
        public static int waysofcolor(int n) {
                .鏈枃鍘熷垱鑷1point3acres璁哄潧
                int[] dp1 = new int[n];
                int[] dp2 = new int[n];
                dp1[0] = 2;
               
                dp1[1] = 4;
                dp2[1] = 2;
                . Waral 鍗氬鏈夋洿澶氭枃绔,
                if ( n <= 2 ) return dp1[n];
               
                for (int i = 2; i < n; i ++) {
                           dp1[i] = dp1[i - 1] * 2 - dp2[i - 1];
                           dp2[i] = dp1[i - 1] - dp2[i - 1];
                }
                return dp1[n - 1];
        }
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 01:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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