狗家SETI昂赛MTV

sean72kimo 发表于 2019-4-22 09:26
不清楚，但我上次去面，硬體/韌體轉專業(做了五六年)，還是問我backend design... 我也只能用網上自修的 ...

因为你是5年以上了吧，虽然说exp为0，但是基本知识还是要懂的吧

是喜欢问基本的array题目啊

请问第三轮这个题有lc原题吗

yayafuture 发表于 2019/04/30 00:00:34
请问第三轮这个题有lc原题吗

没有吧。。。

请问一下第五轮第一题
“没有nested的括号，但是可以里面的字符有括号。”  是啥意思

a{ b, c, d{mn}xy }ef

整个d{mn}xy  看成一个整体  这样？

Wyf2222 发表于 2019-5-31 02:32
请问一下第五轮第一题
“没有nested的括号，但是可以里面的字符有括号。”  是啥意思

是的，字数字数字数

锋之舞 发表于 2019-5-31 02:33
是的，字数字数字数

thanks。

第四轮第二题 请问能具体讲讲你的做法和复杂度吗

我觉得直接扫一遍On 就能得到结果了把。
这题worse case的话，如果每个index的值都不一样，没法比On更快了把

当然average case，从第一个开始，二分找下一个不一样的，然后index跳过去，可能比On快一点。但是这样做worse case就成了nlogn

just my two cents ：）

Wyf2222 发表于 2019-5-31 02:48
thanks。

第四轮第二题 请问能具体讲讲你的做法和复杂度吗

worst case是On, 一般情况是m(logw+1), w是平均版本变动的间隔,m是版本变动的次数。worst case就是m=n,w=1

第五轮第一问用递归的方式写了下，遇到括号时对括号里的substring调用递归函数处理

1. def bracketMatch(s): # Key: left bracket, value: right bracket
   
2.     stack = []
   
3.     dic = {}
   
4.     for i,c in enumerate(s):
   
5.         if c == '{':
   
6.             stack.append(i)
   
7.         elif c == '}':
   
8.             dic[stack.pop()] = i
   
9.     return dic
   
10. 
    
11. def process(s, start, end, bracketDic):
    
12.     res = []
    
13.     i, j = start, start
    
14.     while j <= end+1:
    
15.         if j == end+1 or s[j] == ',':
    
16.             if '{' not in s[i:j]:
    
17.                 res.append(s[i:j])
    
18.             else:
    
19.                 bracketInd = i
    
20.                 while s[bracketInd] != '{':
    
21.                     bracketInd += 1
    
22.                 before = s[i:bracketInd]
    
23.                 after = s[(bracketDic[bracketInd]+1):j]
    
24.                 mid = process(s, bracketInd+1, bracketDic[bracketInd]-1, bracketDic)
    
25.                 for i in range(len(mid)):
    
26.                     mid[i] = before+mid[i]+after
    
27.                 res.extend(mid)
    
28.             i = j+1
    
29.         elif s[j] == '{':
    
30.             j = bracketDic[j]
    
31.         j +=1
    
32.     return res
    
33.    
    
34. s = "a{b,c,de{{1,222,3}8,x,y}h}f"
    
35. bracketDic = bracketMatch(s)
    
36. res = process(s, 0, len(s)-1, bracketDic)
    
37. print(res)

复制代码

原来 5 年之内都可以不问 system design 啊