3.35->2.75, 15 years - 未名空间MITBBS历史存档

3.35->2.75, 15 years# Living

s*s2012-11-06 08:11

1 楼

先谢版主done推荐，虽然已跪了。
onsite见了5人，现在只记得部分：
1. 求用元素周期表中的每个元素代号，能评出的最长单词。
比如：T = { Si, C , K }. 结果为 sick.
(大小写无关，每个元素可用几次，怎么判断单词/已给字典， ... 这些前提假定都
要与面试官讨论)
2. 两棵二叉树，判断是否存在公共结点。
只想到了O(M*N). 最多也就能用hash表处理一颗树，优化到O(1) * O(N). 空间换时间
，空间是O(M). 不知道有什么好的办法？？？
3. 一堆色子，每面随意染色，判断是否能叠成一个立方柱，4面都同色。
当时现场有些懵（最后一轮），主要没想清楚多少种状态（色子可以旋转）。
面试官提示后，又说我多算了几种。他认为是3种就行，我说的6种中，有2种重复了。
回来后仔细想了想，其实一样的。他说的3种中，每种可以双向旋转，所以一共 3 * 8
= 24.
而我一开始想的6种，每种如果规定只能按右手螺旋法则旋转，也就是 6 * 4 = 24. 其
实是一样的。
这题没见过，一共只给了25分钟左右想，感觉时间挺紧的。

e*d2012-11-06 08:11

2 楼

second refinance. Agent said no cost. Is it worth refinancing?
thanks

l*b2012-11-06 08:11

3 楼

第一道题目我也被面了。不算难啊。
第3题能说清楚一些不？不太理解题目的意思。

b*d2012-11-06 08:11

4 楼

如果是no cost,当然值得做.

【在 e**d 的大作中提到】

: second refinance. Agent said no cost. Is it worth refinancing?
: thanks

y*o2012-11-06 08:11

5 楼

认认真真读完了签名

p*y2012-11-06 08:11

6 楼

当然值得啦，no cost么。

p*42012-11-06 08:11

7 楼

楼主真是好心人。。请问一轮大概多长时间？需要做几道题呢？中午吃饭时间还会面
试吗？是在黑板上写还是在纸上写提？谢谢！！

【在 s**s 的大作中提到】

: 先谢版主done推荐，虽然已跪了。
: onsite见了5人，现在只记得部分：
: 1. 求用元素周期表中的每个元素代号，能评出的最长单词。
: 比如：T = { Si, C , K }. 结果为 sick.
: (大小写无关，每个元素可用几次，怎么判断单词/已给字典， ... 这些前提假定都
: 要与面试官讨论)
: 2. 两棵二叉树，判断是否存在公共结点。
: 只想到了O(M*N). 最多也就能用hash表处理一颗树，优化到O(1) * O(N). 空间换时间
: ，空间是O(M). 不知道有什么好的办法？？？
: 3. 一堆色子，每面随意染色，判断是否能叠成一个立方柱，4面都同色。

h*u2012-11-06 08:11

8 楼

还是应该算一下，比如做或不做refinance，到还完都需要还多少钱。

b*g2012-11-06 08:11

9 楼

请问第三题是什么意思，没看懂

【在 s**s 的大作中提到】

: 先谢版主done推荐，虽然已跪了。
: onsite见了5人，现在只记得部分：
: 1. 求用元素周期表中的每个元素代号，能评出的最长单词。
: 比如：T = { Si, C , K }. 结果为 sick.
: (大小写无关，每个元素可用几次，怎么判断单词/已给字典， ... 这些前提假定都
: 要与面试官讨论)
: 2. 两棵二叉树，判断是否存在公共结点。
: 只想到了O(M*N). 最多也就能用hash表处理一颗树，优化到O(1) * O(N). 空间换时间
: ，空间是O(M). 不知道有什么好的办法？？？
: 3. 一堆色子，每面随意染色，判断是否能叠成一个立方柱，4面都同色。

b*d2012-11-06 08:11

10 楼

只要是利率低了,一定是省钱的.

【在 h***u 的大作中提到】

: 还是应该算一下，比如做或不做refinance，到还完都需要还多少钱。

p*22012-11-06 08:11

11 楼

貌似done的组面试比A的平均水平难一些呀。

p*22012-11-06 08:11

12 楼

第二题dfs应该可以。

s*s2012-11-06 08:11

13 楼

解释一下第三题。比如某个色子，他的颜色（上，下，左，右，前，后）可能为：
(1,2,3,4,2,3)。
另外有一个色子，颜色为 (3,3,2,3,4,3)
这样，我们把第一个色子放在第二个色子上面，第一个色子的4个面（前右后左）为
2433
第二个为 4332. 那么把他旋转90度，就可以变成 2433. 这样落在一起组成的高度为2的
立方柱，4面都同色。
现在我们有一堆色子，他们的颜色可以是任意的值。判断是否能组成这样的柱子。

【在 s**s 的大作中提到】

: 先谢版主done推荐，虽然已跪了。
: onsite见了5人，现在只记得部分：
: 1. 求用元素周期表中的每个元素代号，能评出的最长单词。
: 比如：T = { Si, C , K }. 结果为 sick.
: (大小写无关，每个元素可用几次，怎么判断单词/已给字典， ... 这些前提假定都
: 要与面试官讨论)
: 2. 两棵二叉树，判断是否存在公共结点。
: 只想到了O(M*N). 最多也就能用hash表处理一颗树，优化到O(1) * O(N). 空间换时间
: ，空间是O(M). 不知道有什么好的办法？？？
: 3. 一堆色子，每面随意染色，判断是否能叠成一个立方柱，4面都同色。

p*22012-11-06 08:11

14 楼

第一题你是怎么做的？dfs＋trie？

【在 l**b 的大作中提到】

: 第一道题目我也被面了。不算难啊。
: 第3题能说清楚一些不？不太理解题目的意思。

f*e2012-11-06 08:11

15 楼

第2题，用标号法，先给一棵树标号，再给另一棵树标号，如果碰到已经标号的就说明
有公共
节点。

【在 s**s 的大作中提到】

: 解释一下第三题。比如某个色子，他的颜色（上，下，左，右，前，后）可能为：
: (1,2,3,4,2,3)。
: 另外有一个色子，颜色为 (3,3,2,3,4,3)
: 这样，我们把第一个色子放在第二个色子上面，第一个色子的4个面（前右后左）为
: 2433
: 第二个为 4332. 那么把他旋转90度，就可以变成 2433. 这样落在一起组成的高度为2的
: 立方柱，4面都同色。
: 现在我们有一堆色子，他们的颜色可以是任意的值。判断是否能组成这样的柱子。

s*s2012-11-06 08:11

16 楼

二爷给个第二题的解法吧。想了半天没想到，除了用hash处理一下，还能怎么优化？

【在 p*****2 的大作中提到】

:
: 第一题你是怎么做的？dfs＋trie？

p*22012-11-06 08:11

17 楼

我好像看错题目了。再看一下。

【在 s**s 的大作中提到】

: 二爷给个第二题的解法吧。想了半天没想到，除了用hash处理一下，还能怎么优化？

e*s2012-11-06 08:11

18 楼

意思是不是node 有一个类似flag 的property呢？
如果没有，那用HashSet O(N + M) 也能完成，就是空间也是O(N + M)

【在 f*****e 的大作中提到】

: 第2题，用标号法，先给一棵树标号，再给另一棵树标号，如果碰到已经标号的就说明
: 有公共
: 节点。

p*22012-11-06 08:11

19 楼

：
2的
嗯。应该是一样的。

【在 s**s 的大作中提到】

: 解释一下第三题。比如某个色子，他的颜色（上，下，左，右，前，后）可能为：
: (1,2,3,4,2,3)。
: 另外有一个色子，颜色为 (3,3,2,3,4,3)
: 这样，我们把第一个色子放在第二个色子上面，第一个色子的4个面（前右后左）为
: 2433
: 第二个为 4332. 那么把他旋转90度，就可以变成 2433. 这样落在一起组成的高度为2的
: 立方柱，4面都同色。
: 现在我们有一堆色子，他们的颜色可以是任意的值。判断是否能组成这样的柱子。

p*22012-11-06 08:11

20 楼

HashSet应该N or M吧？

【在 e***s 的大作中提到】

: 意思是不是node 有一个类似flag 的property呢？
: 如果没有，那用HashSet O(N + M) 也能完成，就是空间也是O(N + M)

e*s2012-11-06 08:11

21 楼

二爷，你对！！

【在 p*****2 的大作中提到】

:
: HashSet应该N or M吧？

s*s2012-11-06 08:11

22 楼

第1题是不是可以反过来想？
从最长word开始，看能不能segment成string set/元素周期表

r*h2012-11-06 08:11

23 楼

关于第二题
公共节点指的是key相等的节点吗？
如果这两棵树不是BST，那还真没什么好办法，只有一个个找了
或者就是记下第一棵树里面出现的所有节点，然后第二棵树的节点一个个去比对

【在 s**s 的大作中提到】

: 先谢版主done推荐，虽然已跪了。
: onsite见了5人，现在只记得部分：
: 1. 求用元素周期表中的每个元素代号，能评出的最长单词。
: 比如：T = { Si, C , K }. 结果为 sick.
: (大小写无关，每个元素可用几次，怎么判断单词/已给字典， ... 这些前提假定都
: 要与面试官讨论)
: 2. 两棵二叉树，判断是否存在公共结点。
: 只想到了O(M*N). 最多也就能用hash表处理一颗树，优化到O(1) * O(N). 空间换时间
: ，空间是O(M). 不知道有什么好的办法？？？
: 3. 一堆色子，每面随意染色，判断是否能叠成一个立方柱，4面都同色。

l*b2012-11-06 08:11

24 楼

第一题应该有DP的解法，我当时给了recursive的。面试官提示了symbol是有长度限制
的，这样可以效率更好一点。

e*s2012-11-06 08:11

25 楼

能给个思路看看吗？是不是像上面所说的，从字典最长的字开始看能不能分成元素名？

【在 l**b 的大作中提到】

: 第一题应该有DP的解法，我当时给了recursive的。面试官提示了symbol是有长度限制
: 的，这样可以效率更好一点。

F*n2012-11-06 08:11

26 楼

public void compare(TreeNode n1, TreeNode n2, ListcommonValues) {
if (n1 == null || n2 == null) return;
if (n1.val == n2.val) {
commonValues.add(n1.val);
compare(n1.left, n2.left, commonValues);
compare(n1.right, n2.right, commonValues);
}
else if (n1.val < n2.val) {
compare(n1, n2.left, commonValues);
compare(n1.right, n2, commonValues);
}
else {
compare(n1.left, n2, commonValues);
compare(n1, n2.right, commonValues);
}
}

【在 s**s 的大作中提到】

: 二爷给个第二题的解法吧。想了半天没想到，除了用hash处理一下，还能怎么优化？

s*s2012-11-06 08:11

27 楼

是的，不是BST，就是找key相等的。
so far我能想到的也只是这样子，用hash记录一个，再去另一个里面遍历。

【在 r**h 的大作中提到】

: 关于第二题
: 公共节点指的是key相等的节点吗？
: 如果这两棵树不是BST，那还真没什么好办法，只有一个个找了
: 或者就是记下第一棵树里面出现的所有节点，然后第二棵树的节点一个个去比对

s*s2012-11-06 08:11

28 楼

我也期待看一眼怎么用DP解。
上面那个说反过来从字典里来分解的做法，是最后面试官给的正解。
理由：全部英文字典，最多1M条（或者还多一些）
元素表中，全部100多个元素组合，至少在100!以上的。
这个解空间比全部单词大得多。所以反过来做合适。
这题一开始我也是在想怎么DP解，入手点偏了后，后面就不容易钻出来了。

【在 e***s 的大作中提到】

: 能给个思路看看吗？是不是像上面所说的，从字典最长的字开始看能不能分成元素名？

s*s2012-11-06 08:11

29 楼

看来最近看题有进步。
给定word和100多个元素,对word做DFS search.返回第一条到底的path或空。
如果元素是1或2个letters.worst search space好像是fibonacci(len(word)).

【在 s**s 的大作中提到】

: 我也期待看一眼怎么用DP解。
: 上面那个说反过来从字典里来分解的做法，是最后面试官给的正解。
: 理由：全部英文字典，最多1M条（或者还多一些）
: 元素表中，全部100多个元素组合，至少在100!以上的。
: 这个解空间比全部单词大得多。所以反过来做合适。
: 这题一开始我也是在想怎么DP解，入手点偏了后，后面就不容易钻出来了。

b*a2012-11-06 08:11

30 楼

O(N+M)的意思就是线性吧，哪个大算哪个。

【在 p*****2 的大作中提到】

:
: HashSet应该N or M吧？

l*b2012-11-06 08:11

31 楼

没有，就普通的recursive就过去了。最后在他的提示下优化了一下，就说没什么问题
了。因为一开始聊天聊了很久。介绍自己的工作什么的。所以写完下一个interviewer
已经在门口等很久了（hm），所以也没怎么说。不过他当时的反馈是肯定写对了，让我
别继续想了。等一下贴一下code。

【在 p*****2 的大作中提到】

:
: HashSet应该N or M吧？

l*b2012-11-06 08:11

32 楼

我当时和你一样，也讨论了100！的方法，说不行，太慢了。还是从string那里入手比
较好。
这个是我当时写的。DP那个方法刚刚写的，实在是很弱，所以如果错了，请轻拍。其他
的基本应该和面试的时候一样。反正写完他就让我把原来for loop是用string的length
做end point的，改成了用symbol最长的length。然后就说没问题了。
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Set;
public class SymbolWord {
// Here is the max length of any symbol
public static final int MAX_SYMBOL_LENGTH = 2;
public String findLongestSymbolWord(List dict, Set
symbols) {
Collections.sort(dict, new Comparator() {
@Override
public int compare(String a, String b) {
if (a.length() == b.length()) {
return 0;
} else if (a.length() < b.length()) {
return 1;
} else {
return -1;
}
}
});
for (String str : dict) {
if (isSymbolWord(str, symbols)) {
return str;
}
}
return null;
}
public boolean isSymbolWord(String str, Set symbols) {
for (int i = 1; i <= MAX_SYMBOL_LENGTH && i < str.length(); i++) {
if (symbols.contains(str.substring(0, i)) && isSymbolWord(str.
substring(i, str.length()), symbols)) {
return true;
}
}
return false;
}
public boolean isSymbolWordDp(String str, Set symbols) {
boolean dp[] = new boolean[str.length() + 1];
dp[0] = true;
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j <= MAX_SYMBOL_LENGTH && i - j >= 0; j++) {
int index = i - j;
if (dp[index] && symbols.contains(str.substring(index, i))) {
dp[i] = true;
}
}
}
return dp[str.length()];
}
}

【在 s**s 的大作中提到】

: 我也期待看一眼怎么用DP解。
: 上面那个说反过来从字典里来分解的做法，是最后面试官给的正解。
: 理由：全部英文字典，最多1M条（或者还多一些）
: 元素表中，全部100多个元素组合，至少在100!以上的。
: 这个解空间比全部单词大得多。所以反过来做合适。
: 这题一开始我也是在想怎么DP解，入手点偏了后，后面就不容易钻出来了。

c*a2012-11-06 08:11

33 楼

第一题是cc150原题啊

r*h2012-11-06 08:11

34 楼

虽然理论上所有可能的解有100！规模
但是如果字典的储存形式是Trie的话，做DFS很容易能剪枝掉绝大部分的搜索（因为很
多情况下两个元素就拼不成词了，没有必要去继续搜索后面98个排列组合）
另外单词长度还有限制，一般单词最多不会超过15个字符，也就8个元素（按照两个字
符一个算）

【在 s**s 的大作中提到】

: 我也期待看一眼怎么用DP解。
: 上面那个说反过来从字典里来分解的做法，是最后面试官给的正解。
: 理由：全部英文字典，最多1M条（或者还多一些）
: 元素表中，全部100多个元素组合，至少在100!以上的。
: 这个解空间比全部单词大得多。所以反过来做合适。
: 这题一开始我也是在想怎么DP解，入手点偏了后，后面就不容易钻出来了。

d*e2012-11-06 08:11

35 楼

这是哪一位？

【在 s**s 的大作中提到】

: 先谢版主done推荐，虽然已跪了。
: onsite见了5人，现在只记得部分：
: 1. 求用元素周期表中的每个元素代号，能评出的最长单词。
: 比如：T = { Si, C , K }. 结果为 sick.
: (大小写无关，每个元素可用几次，怎么判断单词/已给字典， ... 这些前提假定都
: 要与面试官讨论)
: 2. 两棵二叉树，判断是否存在公共结点。
: 只想到了O(M*N). 最多也就能用hash表处理一颗树，优化到O(1) * O(N). 空间换时间
: ，空间是O(M). 不知道有什么好的办法？？？
: 3. 一堆色子，每面随意染色，判断是否能叠成一个立方柱，4面都同色。

d*e2012-11-06 08:11

36 楼

有这种事情？

【在 p*****2 的大作中提到】

: 貌似done的组面试比A的平均水平难一些呀。

r*92012-11-06 08:11

37 楼

第三题是brainteaser还是要编程实现？

【在 s**s 的大作中提到】

: 先谢版主done推荐，虽然已跪了。
: onsite见了5人，现在只记得部分：
: 1. 求用元素周期表中的每个元素代号，能评出的最长单词。
: 比如：T = { Si, C , K }. 结果为 sick.
: (大小写无关，每个元素可用几次，怎么判断单词/已给字典， ... 这些前提假定都
: 要与面试官讨论)
: 2. 两棵二叉树，判断是否存在公共结点。
: 只想到了O(M*N). 最多也就能用hash表处理一颗树，优化到O(1) * O(N). 空间换时间
: ，空间是O(M). 不知道有什么好的办法？？？
: 3. 一堆色子，每面随意染色，判断是否能叠成一个立方柱，4面都同色。

d*e2012-11-06 08:11

38 楼

用heap怎么会是O(1)空间呢？

h*y2012-11-06 08:11

39 楼

我想的是可以变找边删，distructive的，如果input不能动的话，那等于是弄了个copy
就不是O(1)了

【在 d**e 的大作中提到】

: 用heap怎么会是O(1)空间呢？

g*e2012-11-06 08:11

40 楼

你们组的题很难，我面就直接挂了

【在 d**e 的大作中提到】

: 用heap怎么会是O(1)空间呢？

d*e2012-11-06 08:11

41 楼

你别闹了，我看你出的题都比我们的难。。。
我现在只是在庆幸当年我不是直接面我们的组。。。

【在 g**e 的大作中提到】

: 你们组的题很难，我面就直接挂了

d*e2012-11-06 08:11

42 楼

有copy就不是O(1)了。
我觉得面试官是不期待大家动input的，所以可能开额外空间是必要的。

copy

【在 h****y 的大作中提到】

: 我想的是可以变找边删，distructive的，如果input不能动的话，那等于是弄了个copy
: 就不是O(1)了

p*22012-11-06 08:11

43 楼

interviewer
recursive的话，你怎么停止？假设最大长度？

【在 l**b 的大作中提到】

: 没有，就普通的recursive就过去了。最后在他的提示下优化了一下，就说没什么问题
: 了。因为一开始聊天聊了很久。介绍自己的工作什么的。所以写完下一个interviewer
: 已经在门口等很久了（hm），所以也没怎么说。不过他当时的反馈是肯定写对了，让我
: 别继续想了。等一下贴一下code。

p*22012-11-06 08:11

44 楼

是呀。所以我觉得dfs＋trie挺好

【在 r**h 的大作中提到】

: 虽然理论上所有可能的解有100！规模
: 但是如果字典的储存形式是Trie的话，做DFS很容易能剪枝掉绝大部分的搜索（因为很
: 多情况下两个元素就拼不成词了，没有必要去继续搜索后面98个排列组合）
: 另外单词长度还有限制，一般单词最多不会超过15个字符，也就8个元素（按照两个字
: 符一个算）