狗家昂赛跪经

昨天面了狗家的昂赛，目测应该是凉凉了。。

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

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

感觉第一次白板还是有点不太习惯，而且代码有时候写着写着发现有问题的地方就直接问能不能在原有代码上加，导致白板上很难看。。。可是擦掉重写也来不及。。。经验不足吧，move on。。。

非常感谢给我内推的大哥，准备了也挺长时间吧，希望能给大家带来点帮助，顺便也给下周的面试攒攒人品，加油！

第二轮感觉可以把node的value排个序，然后从值小的开始进行union，到某个值，起点终点在一个union里面之后，这个值就是bound

smallmikko 发表于 2018-12-13 00:41
请问lz，第四题第一轮什么意思？有没有具体例子，谢谢！

就比如abcdafgb，最大的substring就是bcdafgb而不是abcda，所以应该是7

第二轮写了个dfs+pruning

1. def findMinMaxPath(self, start_node, end_node, graph):
   
2.         self.global_min = float('inf')
   
3.         self.global_path = []
   
4. 
   
5.         def dfs(cur_max, cur_path, cur_node):
   
6.                 if not cur_node:
   
7.                         return
   
8.                 if cur_node == end_node:
   
9.                         cur_max = max(cur_max, cur_node.val)
   
10.                         cur_path.append(cur_node)
    
11.                         if cur_max < self.global_min:
    
12.                                 self.global_path = cur_path
    
13.                                 self.global_min = cur_max
    
14.                         return
    
15.                        
    
16. 
    
17.                 for neighbour in graph[cur_node]:
    
18.                         if neighbour.val > cur_max:
    
19.                                 cur_max = neighbour.val
    
20.                         # when max value in current path exceeds global_min, no need to search further
    
21.                         if cur_max > self.global_min:
    
22.                                 continue
    
23.                         cur_path.append(neighbour.val)
    
24.                         dfs(cur_max, cur_path, neighbour)
    
25. 
    
26.         dfs(-float('inf'), [], start_node)
    
27.         return self.global_path
    

复制代码

能麻烦楼主稍微具体讲一下第一题的解法吗？我现在能想到的就是对每个节点bfs搜一遍，memo要怎么用呢？已加米！

wzy602867832 发表于 2018-11-9 23:06
能麻烦楼主稍微具体讲一下第一题的解法吗？我现在能想到的就是对每个节点bfs搜一遍，memo要怎么用呢？已加 ...

就是把所有的1的位置+step=0全放到队列里面，然后bfs，用一个数组记录哪些点被访问过，就可以了。

wzy602867832 发表于 2018/11/09 23:06:37
能麻烦楼主稍微具体讲一下第一题的解法吗？我现在能想到的就是对每个节点bfs搜一遍，memo要怎么用呢？已加米！

这题就是典型的终点源bfs找起点

楼主   第三题const是啥意思阿.  two pointer只是移动指针 并没有动input呀

zhangzitong001 发表于 2018-11-9 23:43
楼主   第三题const是啥意思阿.  two pointer只是移动指针 并没有动input呀

因为我的做法是比如abc#，我在原来的这个string上进行改动，然后原来的input就变成了ab，但是现在const的话，就是要求不能改动这个原来的string。。。

zhangzitong001 发表于 2018-11-9 23:43
楼主   第三题const是啥意思阿.  two pointer只是移动指针 并没有动input呀

我后来想了想，应该是从后往前推，记录#的数量，这样来对比两个string是否相等，当时反正没想到= =

tigerhuhu16 发表于 2018/11/10 00:08:42


我后来想了想，应该是从后往前推，记录#的数量，这样来对比两个string是否相等，当时反正没想到= =

对哈..  机智

说实话我在白板练习的时候也遇到相同问题不知道咋办.  感觉要预留一些空间为了方便之后加代码

那个#号的，好像标准解法就是从后往前，遇到#就记一下，跳过相应数目的非#字符