Redian新闻
>
Palantir 电面面经求指教
avatar
Palantir 电面面经求指教# JobHunting - 待字闺中
l*4
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),不符合要求~
谢谢大家指教!
avatar
l*s
2
为什么不能遍历,遍历的复杂度又不是O(2^n)
avatar
s*j
3
没懂。。。这不就是一个in order traversal么?
只不过因为是dag所以你要一个hash set来keep track 哪个是visited
avatar
l*4
4
因为面试官说如果有n个node,字符最长可以是2^n-1
遍历的话最坏情况就是O(2^n)了。。。

【在 l********s 的大作中提到】
: 为什么不能遍历,遍历的复杂度又不是O(2^n)
avatar
l*4
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

avatar
e*u
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。所以

avatar
k*s
7
被面试官问的套进去了吧
>> traverse的话最坏情况复杂度就是O(2^n)
traverse树是O(n), 枚举每个字符才是O(2^n).
traverse树的时候,记住左孩子的count就可以,右孩子相同的话,直接加count,不用
一个字符一个字符生成就不是O(2^n).
avatar
s*7
8
有点意思, 最坏 A=B=C=D, 确实字符串长度是 2^n
不过,这个跟fibonachi数列一样,你可以用dp保存sub的str,遇到=就copy一下就可以
了,所以还是O(n)就可以了
avatar
k*s
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;
}
avatar
l*m
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

avatar
G*n
11
请问DAG的in order traversal 什么是停止条件?比如树的inorder 遇到叶结点(左右
child都是null)就可以返回当前recursion
那图的呢?
avatar
r*y
12
我怎么感觉复杂度应该是O(2*n)=O(n)呢?一个节点两条边,看题意最多就走完这两次
吧应该?不知道哪里理解的不对
avatar
l*1
13
lz这个题里的树都是这种结构的a=b=c还是正常的binary tree和这种结构混杂的?就
是说有可能一个node左右ponter指向不同node么?如果都是这种结构的a=b=c,还有O
(n)的方法,不是感觉就没了
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。