Palantir 电面面经求指教 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

Palantir 电面面经求指教

Palantir 电面面经求指教# JobHunting - 待字闺中

l*42014-04-15 07:04

1 楼

有一个binary directed acyclic graph，每个node存有一个字符，有一个左节点和一
个右节点。
（node定义如下：
Node {
Node L;
Node R;
char ch;
}
）
这样如果in-order traverse这个DAG，就会得到一个string。例子如下：假设一个DAG
只有两个node，分别装着A和B这两个字符。假设Node A的左右两条边都指向Node B:
A (root node)
||
B
那么这个存储的string就是BAB
现在假设已经有了一个这样的DAG, 请写一个函数，返回这个string的第k个字符。要求
复杂度不能是exponential的。。。
我先写了个in order 的遍历。面试官就问我如果n个node,string最长可以是多少
我觉得是2^n-1
面试官说，那么traverse的话最坏情况复杂度就是O(2^n)，不符合要求～
谢谢大家指教！

l*s2014-04-15 07:04

2 楼

为什么不能遍历，遍历的复杂度又不是O(2^n)

s*j2014-04-15 07:04

3 楼

没懂。。。这不就是一个in order traversal么？
只不过因为是dag所以你要一个hash set来keep track 哪个是visited

l*42014-04-15 07:04

4 楼

因为面试官说如果有n个node，字符最长可以是2^n-1
遍历的话最坏情况就是O(2^n)了。。。

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

: 为什么不能遍历，遍历的复杂度又不是O(2^n)

l*42014-04-15 07:04

5 楼

面试官先问我如果n个node,string最长可以是多少
我觉得是2^n-1
于是面试官说，traverse的话最坏情况复杂度就是O(2^n)啦，不符合要求。于是我就无
语凝噎了。。。
另外，遍历时访问过的node是可以再次访问的。比如那个两个节点的例子
A
||
B
A是root
in order 先访问B，再访问A,可是A的right edge指向的还是B，于是要再访问B。所以
这两个node的图表示的string是BAB

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

: 没懂。。。这不就是一个in order traversal么？
: 只不过因为是dag所以你要一个hash set来keep track 哪个是visited

e*u2014-04-15 07:04

6 楼

太难了，要是我直接放弃了

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

: 面试官先问我如果n个node,string最长可以是多少
: 我觉得是2^n-1
: 于是面试官说，traverse的话最坏情况复杂度就是O(2^n)啦，不符合要求。于是我就无
: 语凝噎了。。。
: 另外，遍历时访问过的node是可以再次访问的。比如那个两个节点的例子
: A
: ||
: B
: A是root
: in order 先访问B，再访问A,可是A的right edge指向的还是B，于是要再访问B。所以

k*s2014-04-15 07:04

7 楼

被面试官问的套进去了吧
>> traverse的话最坏情况复杂度就是O(2^n)
traverse树是O(n), 枚举每个字符才是O(2^n).
traverse树的时候，记住左孩子的count就可以，右孩子相同的话，直接加count，不用
一个字符一个字符生成就不是O(2^n).

s*72014-04-15 07:04

8 楼

有点意思，最坏 A=B=C=D, 确实字符串长度是 2^n
不过，这个跟fibonachi数列一样，你可以用dp保存sub的str,遇到=就copy一下就可以
了，所以还是O(n)就可以了

k*s2014-04-15 07:04

9 楼

感觉应该是O(n)。以当前节点为inorder node的字符串长为left + 1 + right, 其中
left和right都可以只算一次然后用map存起来。
伪代码如下，感觉写得有点恶...
Character c;
Map map;
private int count(Node node, int rank) {
if (rank <= 0) {
return 0;
} else if (node == null) {
return 0;
} else if (map.containsKey(node)) {
return map.get(node);
}
int count = 1;
int leftCount = count(node.left, rank);
if (leftCount == -1) {
return -1;
} else if ((count += leftCount) == rank) {
c = node.ch;
return -1;
}
int rightCount += count(node.right, rank - count);
if (rightCount == -1) {
return -1;
} else if ((count += rightCount) == rank) {
c = node.ch;
return -1;
}
map.put(node, count);
return count;
}
public Character find(Node node, int rank) {
c = null;
map = new HashMap();
count(node, rank);
return c;
}

l*m2014-04-15 07:04

10 楼

很有趣的一个题
产生exp复杂度的原因是当Node L ＝＝ Node R的时候，只要一个input node却导致节
点数＊2了
所以可以给每个节点存储以当前节点为根的字符串的长度LEN(root)
LEN(root) = LEN(L) + LEN(R)
就像楼上说的用map把节点的count存起来，这样L＝＝R的时候R就直接拿结果就好了
因为没有环，O（n）就能遍历这个树，得到每个节点的LEN
要找第K个字符，root的位置是r＝LEN(L) + 1，比K小那就找R里的K － r，比K大就找L
里的K，不然返回就好。复杂度是树的高度。

DAG

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

: 有一个binary directed acyclic graph，每个node存有一个字符，有一个左节点和一
: 个右节点。
: （node定义如下：
: Node {
: Node L;
: Node R;
: char ch;
: }
: ）
: 这样如果in-order traverse这个DAG，就会得到一个string。例子如下：假设一个DAG

G*n2014-04-15 07:04

11 楼

请问DAG的in order traversal 什么是停止条件？比如树的inorder 遇到叶结点(左右
child都是null)就可以返回当前recursion
那图的呢？

r*y2014-04-15 07:04

12 楼

我怎么感觉复杂度应该是O(2*n)=O(n)呢？一个节点两条边，看题意最多就走完这两次
吧应该？不知道哪里理解的不对

l*12014-04-15 07:04

13 楼

lz这个题里的树都是这种结构的a＝b＝c还是正常的binary tree和这种结构混杂的？就
是说有可能一个node左右ponter指向不同node么？如果都是这种结构的a＝b＝c，还有O
（n）的方法，不是感觉就没了