湾区某职业社交网络公司电话一面# JobHunting - 待字闺中r*d2012-06-27 07:061 楼很简单,上来先介绍了下自己,做的项目,用什么技术等等然后在网上做题,1:判断一个输入的字符串是否是合法数字。2:给定二叉树,按层次打印,写完后解释下逻辑。对他们有什么问题整个过程45分钟,两题大概只用了20多分钟
P*F2012-06-27 07:063 楼感谢分享。【在 r**d 的大作中提到】: 很简单,上来先介绍了下自己,做的项目,用什么技术等等: 然后在网上做题,: 1:判断一个输入的字符串是否是合法数字。: 2:给定二叉树,按层次打印,写完后解释下逻辑。: 对他们有什么问题: 整个过程45分钟,两题大概只用了20多分钟
r*d2012-06-27 07:066 楼第二面仅一题有一排房子,每幢可以油漆成3种颜色之一,每个房子漆成各种颜色的价钱各不相同,存放在一个[n][3]的二维数组中,另外要求相邻的两幢房子颜色不同,求最少需要多少钱。给定了函数的定义,输入参数为数组,返回一个值。感觉考官还是挺仁慈的,但自己表现一般,先给了一个直观上的指数级别的算法,并编程。解释之。后来总算想出快速的办法,结果时间差不多了,刚来得及给出伪代码,好歹让考官理解了思路。听天由命了。【在 r**d 的大作中提到】: 很简单,上来先介绍了下自己,做的项目,用什么技术等等: 然后在网上做题,: 1:判断一个输入的字符串是否是合法数字。: 2:给定二叉树,按层次打印,写完后解释下逻辑。: 对他们有什么问题: 整个过程45分钟,两题大概只用了20多分钟
j*e2012-06-27 07:0610 楼 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]的二维数组中,另外要求相邻的两幢房子颜色不同,求最少需要多少: 钱。: 给定了函数的定义,输入参数为数组,返回一个值。: 感觉考官还是挺仁慈的,但自己表现一般,先给了一个直观上的指数级别的算法,并编: 程。解释之。后来总算想出快速的办法,结果时间差不多了,刚来得及给出伪代码,好: 歹让考官理解了思路。: 听天由命了。
r*d2012-06-27 07:0612 楼正解【在 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*d2012-06-27 07:0613 楼此题很多地方有答案,不过这次考官并未要求一次写出完美代码,而是从无符号整数开始,并且也没追究到太深的地步。【在 i***e 的大作中提到】: 1判断一个输入的字符串是否是合法数字. 请问lz能不能帖个代码? 感觉这个题不容易: 写。谢谢
n*w2012-06-27 07:0615 楼试试这个?价格矩阵color1 2 3K1 3 4 52 2 3 43 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*k2012-06-27 07:0616 楼要是没影响就是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。
j*e2012-06-27 07:0617 楼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。
n*w2012-06-27 07:0618 楼对的。这个方法没问题。问题在,这种解法并不是DP。我也被DP这个词误导了。【在 j********e 的大作中提到】: K = 1, A = { 3, 4, 5}: K = 2, A = { 6, 6, 7}: K = 3, A = { 17, 21, 9}: 所以答案是9啦。
n*w2012-06-27 07:0619 楼greedy跟dp都要求没dependency。我搞过算法证明。区别在于greedy的choice有greedy原则,dp的choice要try各种possibilities。【在 s******k 的大作中提到】: 要是没影响就是greedy
t*e2012-06-27 07:0620 楼Use 2 D table for DP, first dimension is index, second dimension is color.color is c0, c1, c2. Formula isA[i][c2] = (min {A[i-1][c0], A[i-1][c1]}) + n[i][c2];A[i][c1] = ...A[i][c0] = ...