《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 4513|回复: 23
收起左侧

Google电面面经

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

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

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

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

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

就一个编程题,n个borad,两个颜色,相邻的三个board不能相同颜色,求一共能有多少可能的涂法。. Waral 鍗氬鏈夋洿澶氭枃绔,
. 鍥磋鎴戜滑@1point 3 acres
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;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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++ {. 鍥磋鎴戜滑@1point 3 acres
  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]
  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;. visit 1point3acres.com for more.
  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):
  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. def good(x): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  7.     n = len(x). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  8.     for i in xrange(3,n+1):-google 1point3acres
  9.         if x[i-3:i]=='111' or x[i-3:i]=='000': return False
  10.     return True

  11. 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 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

smallshrimp 发表于 2015-10-22 03:32:52 | 显示全部楼层
        public static int waysofcolor(int n) {
               
                int[] dp1 = new int[n];
                int[] dp2 = new int[n];
                dp1[0] = 2;-google 1point3acres
               
                dp1[1] = 4;
                dp2[1] = 2;
                . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                if ( n <= 2 ) return dp1[n];
               
                for (int i = 2; i < n; i ++) {. From 1point 3acres bbs
                           dp1[i] = dp1[i - 1] * 2 - dp2[i - 1];. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                           dp2[i] = dp1[i - 1] - dp2[i - 1];
                }
                return dp1[n - 1];
        }
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-11-24 21:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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