Citadel 店面

Citadel他家非常喜欢招C++做infra, 但是我选的是Java，而且我工作也用的是Java。
是猎头联系的电面，
一上来直接做题：




We have an array representation of a tree,  where each index represents a node, and the va

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

间的解法。我花了很久想，想出来的时间复杂度都太高，
，最后还是没能给出O(1) 空间 O(N)时间的解法。面试完后想了一下，其实还真的有O(1) 空间， O(N)时间的解法，基本上就是Union Find set的路径压缩的变种。大家可以试试。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

所以citadel也可以用java去面吗？还是面的职位是用到java的？

O(1)space的话不要用recursion用iteration 找所有祖先点就行。union and find的话，rank要O(n)space,而且find是recursion,最差情况栈就要O(n).

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

jsgq 发表于 2019-12-17 17:25
感觉只需要简单的recursive就可以了啊.
public static void printSubTree(int[] a, int idx){
    Syste ...

没看明白这是啥意思，可以解释下么？

jsgq 发表于 2019-12-17 17:25
感觉只需要简单的recursive就可以了啊.
public static void printSubTree(int[] a, int idx){
    Syste ...

没看懂诶。。还麻烦解释一下，这个left right是啥意思。。

recursive o(n)+o(n)的确实几分钟就能完事，o(1)空间的咋整。。

1. l = [-1, 0, 0, 1, 1, 4]
   
2. target = 1
   
3. 
   
4. def find(num, l, target):
   
5.         while num != target and num != -1:
   
6.                 num = l[num]
   
7.         return num               
   
8.        
   
9. res = set([])
   
10. for i, parent in enumerate(l):
    
11.        
    
12.         root_parent = find(parent, l, target)
    
13.         l[i] = root_parent
    
14.         l[parent] = root_parent
    
15.         if root_parent == target:
    
16.                 res.add(i)
    
17.                 res.add(parent)
    
18. print(res)

复制代码

Hope this would help.