新鲜狗家阳谷昂赛

3月1号周五新鲜昂赛，应该是挂了。
1. 看起来不是很senior的中国小哥，lz一开始去错building了所以到了面试的会议室就没有寒暄直接开始。 找到tree 里面一个node的K th ancestor。 记得是蠡口原题但是不记得题号了。限制用O(K) space. Backtraking。 感觉面试官全程不是很nice，不知道是不是我一开始走错的原因

2. 中国大叔：

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

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

总之最后一轮和第一轮感觉不太行，找工作第一个onsite就是狗家，不太顺利也正常，继续加油吧，要的米不多，希望更多人看到。

求加米!

第六题用递归好做一些哈

第六题用树吗？比如a{b, c{d, e}}这个就是a 是根，b 还有 c{d, e}是a的children，然后d， e是c的children, dfs找所有从根到叶的路径？Parse的时候递归成树？

第六题用递归的方式写了一下

1. def process(str, start, end, parenthesisMatch):
   
2.     # Separate the string by commas on the same level
   
3.     i, j = start, start
   
4.     list = []
   
5.     while j <= end:
   
6.         if str[j] == ',':
   
7.             list.append((i, j))
   
8.             i = j + 1
   
9.         elif str[j] == '{':
   
10.             j = parenthesisMatch[j]
    
11.         j += 1
    
12.     if i<j:
    
13.         list.append((i, j))
    
14.    
    
15.     # Parse each separated string (recursive)
    
16.     res = []
    
17.     for i, j in list:
    
18.         if str[i:j].isalpha():
    
19.             res.append(str[i:j])
    
20.         else:
    
21.             ii, jj = i, i
    
22.             super = [""]
    
23.             while jj<j:
    
24.                 if str[jj] == '{':
    
25.                     res_before = process(str, ii, jj-1, parenthesisMatch)
    
26.                     res_in_paren = process(str, jj+1, parenthesisMatch[jj]-1, parenthesisMatch)
    
27.                     if res_before:
    
28.                         for k in range(len(res_in_paren)):
    
29.                             res_in_paren[k] = res_before[0] + res_in_paren[k]
    
30.                     super_new = []
    
31.                     for s in super:
    
32.                         for t in res_in_paren:
    
33.                             super_new.append(s+t)
    
34.                     super = super_new
    
35.                     jj = parenthesisMatch[jj]
    
36.                     ii = jj + 1
    
37.                 jj += 1
    
38.             if ii<jj:
    
39.                 for k in range(len(super)):
    
40.                     super[k] += str[ii:jj]
    
41.             res.extend(super)
    
42.     return res
    
43. 
    
44. def interpret(str):
    
45.     parenthesisMatch = {} # Key: index of left parenthesis, value: index of right parenthesis
    
46.     stack = []
    
47.     for i, c in enumerate(str):
    
48.         if c == '{':
    
49.             stack.append(i)
    
50.         elif c == '}':
    
51.             parenthesisMatch[stack.pop()] = i
    
52.     return process(str, 0, len(str) - 1, parenthesisMatch)
    
53.    
    
54. print(interpret('{a,b}x{c,d}y{e,f{g,h}{i,j}k}'))

复制代码

lz好人啊 能说一下ring和cycle的区别么？

douch 发表于 2019-3-3 10:55
lz好人啊 能说一下ring和cycle的区别么？

ring啊 想想戒指什么形状呢。就是所有Node生成一个环。 cycle 指若干个node形成环，不一定要所有的node

请问第2轮的题意是判断图中是否只有一个环对吗? 图中如果有多个环就return false?
follow up validate input 可以解释一下是validate 什么吗?

iq136man 发表于 2019-3-3 11:14
ring啊 想想戒指什么形状呢。就是所有Node生成一个环。 cycle 指若干个node形成环，不一定要所有的node

请教 所有Node生成一个环不就是linkedlist了么，和graph啥关系。。

漫漫人生路 发表于 2019-3-3 11:51
请问第2轮的题意是判断图中是否只有一个环对吗? 图中如果有多个环就return false?
follow up validate inp ...

比如给的input是{0:[1,2]},这就不valid，因为0连到了1，2,但是1，2 没连回来

iq136man 发表于 2019-3-3 11:14
ring啊 想想戒指什么形状呢。就是所有Node生成一个环。 cycle 指若干个node形成环，不一定要所有的node

对的就这个意思，说起来当时面试官当场把手上的戒指拿来给我看。。。。。

谢谢分享！

qiweiwang89 发表于 2019-3-4 10:42
比如给的input是{0:[1,2]},这就不valid，因为0连到了1，2,但是1，2 没连回来

好的,谢谢解答~

QAQ妈呀 思考第六轮感觉耗尽脑力
一个queue一个stack感觉也没做出来。。。有没有大神给讲解一下！