苏州微软sde实习一面

三月底内推，四月初约面试，已经约了就去面了
上来先自我介绍，让介绍了一个项目然后开始做题

第一题：
encode algo: abcde -> c, abde -> cb, ade -> cbd, ae -> cbda, e-> cbdae，相当于每次取剩余字符串的中间字符append
give encode string like cbdae , return raw data string like abcde.
给了deque的解法，问能不能不用dq，然后又换了个方法做

第二题：
compressed string, 2[abc] -> abcabc, 2[a2[b2[c]]] -> 2[a2[bcc]]-> 2[abccbcc] -> abcbccabcbcc
输入 2[a2[b2[c]]]，输出 abcbccabcbcc，lc应该有原题

chinkaimu 发表于 2020-4-18 17:09
题目一样？求问在哪里，我感觉也刷了很多面经，但没看到一样的？？

https://www.1point3acres.com/bbs/thread-615864-1-1.html
类似这套，这个时间段发的几个帖子，都是这类型题目，感觉挺难。。。

qiaofengmarco 发表于 2020-4-15 15:02
第一题可以直接找规律吧？
从中间开始，每次步长+1，然后换方向跳

可以的，但是需要区分原来string长度的奇偶性。
当然了，还个办法是从后往前复原，这样的话可以忽略这个问题。

小君君啊啊 发表于 2020/04/14 12:29:54
记得lz有 L 家offer了啊 为啥还要面国内的～

前一段时间担心实习被取消投的国内，前几天L才确定remote，但是面试已经约了就还是去面了

记得lz有 L 家offer了啊 为啥还要面国内的～

请问楼主第一题不用dq该用什么方法做呢
以及第二题该怎么做呀

connor123 发表于 2020-4-15 04:22
请问楼主第一题不用dq该用什么方法做呢
以及第二题该怎么做呀

第一题可以先初始化个数组然后用index一个一个往里面填

第二题就是用递归去做，这是我当时写的代码

1. def helper(s):
   
2.     if '[' not in s:
   
3.         return s
   
4.     lidx = s.find('[')
   
5.     ridx = -1
   
6.     l = 0
   
7.     for i in range(lidx, len(s)):
   
8.         if s[i] == '[':
   
9.             l += 1
   
10.         elif s[i] == ']':
    
11.             l -= 1
    
12.         if l == 0:
    
13.             ridx = i
    
14.             break
    
15.     nidx = lidx - 1
    
16.     while nidx >= 0 and s[nidx].isdigit():
    
17.         nidx -= 1
    
18.     number = int(s[nidx + 1 : lidx])
    
19.     return s[:nidx+1] + number * helper(s[lidx+1:ridx]) + helper(s[ridx+1:])

复制代码

第一题想到两种做法，但是都有缺点：

1. class Solution:
   
2.     # 缺点：空间复杂度较高
   
3.     def getdata(self, s):
   
4.         if len(s) < 2: return s
   
5.         def helper(x):
   
6.             if not x: return
   
7.             # 分割原列表，如"abcde"，mid="c", x1="ab", x2="de"
   
8.             x1 = x[:(len(x)-1)//2]
   
9.             x2 = x[(len(x)-1)//2+1:]
   
10.             mid = x[(len(x)-1)//2]
    
11.             res.append(mid)
    
12.             print(x1, x2, mid)
    
13.             helper(x1+x2)
    
14.         
    
15.         s = list(s)
    
16.         res = []
    
17.         helper(s)
    
18.         return ''.join(res)
    
19. 
    
20.     # 缺点：列表中 del 复杂度较高
    
21.     def getdata2(self, s):
    .--
22.         if len(s) < 2: return s
    
23.         s = list(s)
    
24.         res = []
    
25.         while s:
    
26.             mid = (len(s)-1) // 2
    
27.             res.append(s[mid])
    
28.             del s[mid]
    
29.         return ''.join(res)

复制代码

第二题是原题

微软面试题这么友好吗？sde实习有多大的包？

kuboy 发表于 2020-4-15 14:25
第一题想到两种做法，但是都有缺点：[mw_shl_code=python,true]class Solution:
    # 缺点：空间复杂度较 ...

第一题可以直接找规律吧？
从中间开始，每次步长+1，然后换方向跳

村里的一哥 发表于 2020-4-15 15:25
可以的，但是需要区分原来string长度的奇偶性。
当然了，还个办法是从后往前复原，这样的话可以忽略这个 ...

感谢！你这个方法更好一点