Redian新闻
>
湾区某职业社交网络公司电话一面
avatar
湾区某职业社交网络公司电话一面# JobHunting - 待字闺中
r*d
1
很简单,上来先介绍了下自己,做的项目,用什么技术等等
然后在网上做题,
1:判断一个输入的字符串是否是合法数字。
2:给定二叉树,按层次打印,写完后解释下逻辑。
对他们有什么问题
整个过程45分钟,两题大概只用了20多分钟
avatar
q*y
2
多谢分享。
avatar
P*F
3
感谢分享。

【在 r**d 的大作中提到】
: 很简单,上来先介绍了下自己,做的项目,用什么技术等等
: 然后在网上做题,
: 1:判断一个输入的字符串是否是合法数字。
: 2:给定二叉树,按层次打印,写完后解释下逻辑。
: 对他们有什么问题
: 整个过程45分钟,两题大概只用了20多分钟

avatar
p*2
4
20分钟写完也不错了。
avatar
i*0
5
好像和我的面世官一个人
avatar
r*d
6
第二面
仅一题
有一排房子,每幢可以油漆成3种颜色之一,每个房子漆成各种颜色的价钱各不相同,
存放在一个[n][3]的二维数组中,另外要求相邻的两幢房子颜色不同,求最少需要多少
钱。
给定了函数的定义,输入参数为数组,返回一个值。
感觉考官还是挺仁慈的,但自己表现一般,先给了一个直观上的指数级别的算法,并编
程。解释之。后来总算想出快速的办法,结果时间差不多了,刚来得及给出伪代码,好
歹让考官理解了思路。
听天由命了。

【在 r**d 的大作中提到】
: 很简单,上来先介绍了下自己,做的项目,用什么技术等等
: 然后在网上做题,
: 1:判断一个输入的字符串是否是合法数字。
: 2:给定二叉树,按层次打印,写完后解释下逻辑。
: 对他们有什么问题
: 整个过程45分钟,两题大概只用了20多分钟

avatar
w*x
7
第三题很明显的DP,几个int就够用了
avatar
l*a
8
bull
最佩服那些会dp的了

【在 w****x 的大作中提到】
: 第三题很明显的DP,几个int就够用了
avatar
d*a
9
你贴个程序看看, DP该怎么写。

【在 w****x 的大作中提到】
: 第三题很明显的DP,几个int就够用了
avatar
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]的二维数组中,另外要求相邻的两幢房子颜色不同,求最少需要多少
: 钱。
: 给定了函数的定义,输入参数为数组,返回一个值。
: 感觉考官还是挺仁慈的,但自己表现一般,先给了一个直观上的指数级别的算法,并编
: 程。解释之。后来总算想出快速的办法,结果时间差不多了,刚来得及给出伪代码,好
: 歹让考官理解了思路。
: 听天由命了。

avatar
i*e
11
1判断一个输入的字符串是否是合法数字. 请问lz能不能帖个代码? 感觉这个题不容易
写。谢谢
avatar
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)

avatar
r*d
13
此题很多地方有答案,不过这次考官并未要求一次写出完美代码,而是从无符号整数开
始,并且也没追究到太深的地步。

【在 i***e 的大作中提到】
: 1判断一个输入的字符串是否是合法数字. 请问lz能不能帖个代码? 感觉这个题不容易
: 写。谢谢

avatar
y*n
14
可以用Regular Expression 来回答第一个题目吗?
avatar
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)

avatar
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。

avatar
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。

avatar
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啦。

avatar
n*w
19
greedy跟dp都要求没dependency。我搞过算法证明。
区别在于greedy的choice有greedy原则,dp的choice要try各种possibilities。

【在 s******k 的大作中提到】
: 要是没影响就是greedy
avatar
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] = ...
avatar
j*e
21
yammer?
avatar
j*e
22
yammer?
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。