湾区某职业社交网络公司电话一面# JobHunting - 待字闺中
r*d
1 楼
很简单，上来先介绍了下自己，做的项目，用什么技术等等
然后在网上做题，
1：判断一个输入的字符串是否是合法数字。
2：给定二叉树，按层次打印，写完后解释下逻辑。
对他们有什么问题
整个过程45分钟，两题大概只用了20多分钟
然后在网上做题，
1：判断一个输入的字符串是否是合法数字。
2：给定二叉树，按层次打印，写完后解释下逻辑。
对他们有什么问题
整个过程45分钟，两题大概只用了20多分钟
q*y
2 楼
多谢分享。
P*F
3 楼
感谢分享。
【在 r**d 的大作中提到】
: 很简单，上来先介绍了下自己，做的项目，用什么技术等等
: 然后在网上做题，
: 1：判断一个输入的字符串是否是合法数字。
: 2：给定二叉树，按层次打印，写完后解释下逻辑。
: 对他们有什么问题
: 整个过程45分钟，两题大概只用了20多分钟
【在 r**d 的大作中提到】
: 很简单，上来先介绍了下自己，做的项目，用什么技术等等
: 然后在网上做题，
: 1：判断一个输入的字符串是否是合法数字。
: 2：给定二叉树，按层次打印，写完后解释下逻辑。
: 对他们有什么问题
: 整个过程45分钟，两题大概只用了20多分钟
p*2
4 楼
20分钟写完也不错了。
i*0
5 楼
好像和我的面世官一个人
r*d
6 楼
第二面
仅一题
有一排房子，每幢可以油漆成3种颜色之一，每个房子漆成各种颜色的价钱各不相同，
存放在一个[n][3]的二维数组中，另外要求相邻的两幢房子颜色不同，求最少需要多少
钱。
给定了函数的定义，输入参数为数组，返回一个值。
感觉考官还是挺仁慈的，但自己表现一般，先给了一个直观上的指数级别的算法，并编
程。解释之。后来总算想出快速的办法，结果时间差不多了，刚来得及给出伪代码，好
歹让考官理解了思路。
听天由命了。
【在 r**d 的大作中提到】
: 很简单，上来先介绍了下自己，做的项目，用什么技术等等
: 然后在网上做题，
: 1：判断一个输入的字符串是否是合法数字。
: 2：给定二叉树，按层次打印，写完后解释下逻辑。
: 对他们有什么问题
: 整个过程45分钟，两题大概只用了20多分钟
仅一题
有一排房子，每幢可以油漆成3种颜色之一，每个房子漆成各种颜色的价钱各不相同，
存放在一个[n][3]的二维数组中，另外要求相邻的两幢房子颜色不同，求最少需要多少
钱。
给定了函数的定义，输入参数为数组，返回一个值。
感觉考官还是挺仁慈的，但自己表现一般，先给了一个直观上的指数级别的算法，并编
程。解释之。后来总算想出快速的办法，结果时间差不多了，刚来得及给出伪代码，好
歹让考官理解了思路。
听天由命了。
【在 r**d 的大作中提到】
: 很简单，上来先介绍了下自己，做的项目，用什么技术等等
: 然后在网上做题，
: 1：判断一个输入的字符串是否是合法数字。
: 2：给定二叉树，按层次打印，写完后解释下逻辑。
: 对他们有什么问题
: 整个过程45分钟，两题大概只用了20多分钟
w*x
7 楼
第三题很明显的DP,几个int就够用了
l*a
8 楼
bull
最佩服那些会dp的了
【在 w****x 的大作中提到】
: 第三题很明显的DP,几个int就够用了
最佩服那些会dp的了
【在 w****x 的大作中提到】
: 第三题很明显的DP,几个int就够用了
d*a
9 楼
你贴个程序看看, DP该怎么写。
【在 w****x 的大作中提到】
: 第三题很明显的DP,几个int就够用了
【在 w****x 的大作中提到】
: 第三题很明显的DP,几个int就够用了
j*e
10 楼
DP吧，用个size为3的数组A，记录从1到第K个房子，并且第K个房子用
第i种颜色(i=0,1,2)的最小价格。
K=1时，A[i] = B[0][i] (B是价格矩阵).
K>1时，更新 A[i] = min(B[K][i] + A[j]), j!=i and j in (0,1,2)
【在 r**d 的大作中提到】
: 第二面
: 仅一题
: 有一排房子，每幢可以油漆成3种颜色之一，每个房子漆成各种颜色的价钱各不相同，
: 存放在一个[n][3]的二维数组中，另外要求相邻的两幢房子颜色不同，求最少需要多少
: 钱。
: 给定了函数的定义，输入参数为数组，返回一个值。
: 感觉考官还是挺仁慈的，但自己表现一般，先给了一个直观上的指数级别的算法，并编
: 程。解释之。后来总算想出快速的办法，结果时间差不多了，刚来得及给出伪代码，好
: 歹让考官理解了思路。
: 听天由命了。
第i种颜色(i=0,1,2)的最小价格。
K=1时，A[i] = B[0][i] (B是价格矩阵).
K>1时，更新 A[i] = min(B[K][i] + A[j]), j!=i and j in (0,1,2)
【在 r**d 的大作中提到】
: 第二面
: 仅一题
: 有一排房子，每幢可以油漆成3种颜色之一，每个房子漆成各种颜色的价钱各不相同，
: 存放在一个[n][3]的二维数组中，另外要求相邻的两幢房子颜色不同，求最少需要多少
: 钱。
: 给定了函数的定义，输入参数为数组，返回一个值。
: 感觉考官还是挺仁慈的，但自己表现一般，先给了一个直观上的指数级别的算法，并编
: 程。解释之。后来总算想出快速的办法，结果时间差不多了，刚来得及给出伪代码，好
: 歹让考官理解了思路。
: 听天由命了。
i*e
11 楼
1判断一个输入的字符串是否是合法数字. 请问lz能不能帖个代码？ 感觉这个题不容易
写。谢谢
写。谢谢
r*d
12 楼
正解
【在 j********e 的大作中提到】
: DP吧，用个size为3的数组A，记录从1到第K个房子，并且第K个房子用
: 第i种颜色(i=0,1,2)的最小价格。
: K=1时，A[i] = B[0][i] (B是价格矩阵).
: K>1时，更新 A[i] = min(B[K][i] + A[j]), j!=i and j in (0,1,2)
【在 j********e 的大作中提到】
: DP吧，用个size为3的数组A，记录从1到第K个房子，并且第K个房子用
: 第i种颜色(i=0,1,2)的最小价格。
: K=1时，A[i] = B[0][i] (B是价格矩阵).
: K>1时，更新 A[i] = min(B[K][i] + A[j]), j!=i and j in (0,1,2)
r*d
13 楼
此题很多地方有答案，不过这次考官并未要求一次写出完美代码，而是从无符号整数开
始，并且也没追究到太深的地步。
【在 i***e 的大作中提到】
: 1判断一个输入的字符串是否是合法数字. 请问lz能不能帖个代码？ 感觉这个题不容易
: 写。谢谢
始，并且也没追究到太深的地步。
【在 i***e 的大作中提到】
: 1判断一个输入的字符串是否是合法数字. 请问lz能不能帖个代码？ 感觉这个题不容易
: 写。谢谢
y*n
14 楼
可以用Regular Expression 来回答第一个题目吗?
n*w
15 楼
试试这个？
价格矩阵
color
1 2 3
K
1 3 4 5
2 2 3 4
3 11 15 3
第一反应是，第K个房子颜色选定之后，对K+1颜色有影响。所以子问题对于前一个
choice有dependency，不能这么DP。
【在 j********e 的大作中提到】
: DP吧，用个size为3的数组A，记录从1到第K个房子，并且第K个房子用
: 第i种颜色(i=0,1,2)的最小价格。
: K=1时，A[i] = B[0][i] (B是价格矩阵).
: K>1时，更新 A[i] = min(B[K][i] + A[j]), j!=i and j in (0,1,2)
价格矩阵
color
1 2 3
K
1 3 4 5
2 2 3 4
3 11 15 3
第一反应是，第K个房子颜色选定之后，对K+1颜色有影响。所以子问题对于前一个
choice有dependency，不能这么DP。
【在 j********e 的大作中提到】
: DP吧，用个size为3的数组A，记录从1到第K个房子，并且第K个房子用
: 第i种颜色(i=0,1,2)的最小价格。
: K=1时，A[i] = B[0][i] (B是价格矩阵).
: K>1时，更新 A[i] = min(B[K][i] + A[j]), j!=i and j in (0,1,2)
s*k
16 楼
要是没影响就是greedy
【在 n*******w 的大作中提到】
: 试试这个？
: 价格矩阵
: color
: 1 2 3
: K
: 1 3 4 5
: 2 2 3 4
: 3 11 15 3
: 第一反应是，第K个房子颜色选定之后，对K+1颜色有影响。所以子问题对于前一个
: choice有dependency，不能这么DP。
【在 n*******w 的大作中提到】
: 试试这个？
: 价格矩阵
: color
: 1 2 3
: K
: 1 3 4 5
: 2 2 3 4
: 3 11 15 3
: 第一反应是，第K个房子颜色选定之后，对K+1颜色有影响。所以子问题对于前一个
: choice有dependency，不能这么DP。
j*e
17 楼
K = 1, A = { 3, 4, 5}
K = 2, A = { 6, 6, 7}
K = 3, A = { 17, 21, 9}
所以答案是9啦。
【在 n*******w 的大作中提到】
: 试试这个？
: 价格矩阵
: color
: 1 2 3
: K
: 1 3 4 5
: 2 2 3 4
: 3 11 15 3
: 第一反应是，第K个房子颜色选定之后，对K+1颜色有影响。所以子问题对于前一个
: choice有dependency，不能这么DP。
K = 2, A = { 6, 6, 7}
K = 3, A = { 17, 21, 9}
所以答案是9啦。
【在 n*******w 的大作中提到】
: 试试这个？
: 价格矩阵
: color
: 1 2 3
: K
: 1 3 4 5
: 2 2 3 4
: 3 11 15 3
: 第一反应是，第K个房子颜色选定之后，对K+1颜色有影响。所以子问题对于前一个
: choice有dependency，不能这么DP。
n*w
18 楼
对的。这个方法没问题。
问题在，这种解法并不是DP。我也被DP这个词误导了。
【在 j********e 的大作中提到】
: K = 1, A = { 3, 4, 5}
: K = 2, A = { 6, 6, 7}
: K = 3, A = { 17, 21, 9}
: 所以答案是9啦。
问题在，这种解法并不是DP。我也被DP这个词误导了。
【在 j********e 的大作中提到】
: K = 1, A = { 3, 4, 5}
: K = 2, A = { 6, 6, 7}
: K = 3, A = { 17, 21, 9}
: 所以答案是9啦。
n*w
19 楼
greedy跟dp都要求没dependency。我搞过算法证明。
区别在于greedy的choice有greedy原则，dp的choice要try各种possibilities。
【在 s******k 的大作中提到】
: 要是没影响就是greedy
区别在于greedy的choice有greedy原则，dp的choice要try各种possibilities。
【在 s******k 的大作中提到】
: 要是没影响就是greedy
t*e
20 楼
Use 2 D table for DP, first dimension is index, second dimension is color.
color is c0, c1, c2. Formula is
A[i][c2] = (min {A[i-1][c0], A[i-1][c1]}) + n[i][c2];
A[i][c1] = ...
A[i][c0] = ...
color is c0, c1, c2. Formula is
A[i][c2] = (min {A[i-1][c0], A[i-1][c1]}) + n[i][c2];
A[i][c1] = ...
A[i][c0] = ...
j*e
21 楼
yammer？
j*e
22 楼
yammer？
相关阅读
Google 面题问道算法题下周traveler店面，求blessF1期间H1B申请通过了能出国么？ (转载)纯理科PHD第四第五年找个公司实习急求建议，关于 OPT CAP GAP已经安排了onsite不去是不是不好解禁了，先发个Epic Skill Assessment的面经Job opening: Materials Analyst (in semiconductor area)如果申请opt extension被拒后怎么办?教汉语咋样？知道的人说说网上编程做题的那个网址是啥来着我司在米国的阿三真是多说好两周通知结果但啥都没有就是默据了吧这两个如何选择呢？准备申请CS master,该选C++还是JavaProcess MTS 是什么职位我到底算不算是statistician啊？ (转载)大家帮忙看看我的情况，感激涕零！！！贡献一个朋友在Google的面题一枚。