Facebook背靠背实习挂经

lanyexiaosa369 发表于 2018-11-16 13:23
对的，要求是O(n)的，蠡口貌似有人做出来了

思思就   只要生成任意一个valid bst tree 就行了吗 ?

balla2011 发表于 2018-11-17 07:54
多谢lz的分享～所以lz面完第二天就出回复了？？？怎么感觉有的等回复等了十几天，lz这么快呢～

看不同的HR吧，我这个感觉还挺responsive的

say543 发表于 2018-11-17 08:01
思思就   只要生成任意一个valid bst tree 就行了吗 ?

和面试官讨论的，确定是挨个遍历就行了，这个方法生成的是unique的，没有说要高度最小

lanyexiaosa369 发表于 2018-11-17 08:12
和面试官讨论的，确定是挨个遍历就行了，这个方法生成的是unique的，没有说要高度最小

if input 是[3,5,2] 你要怎么挨个遍寻? o(n) 怎么做到?

求问下第二题怎么体现order的 对于java是不是就是treeset这种数据结构

zjd005 发表于 2018-11-24 13:43
求问下第二题怎么体现order的 对于java是不是就是treeset这种数据结构

差不多的

想问下lz，hr直接跟你说要个时间背靠背么？我是master实习，不知道能不能背靠背

按449做好像会有点问题，应该可以直接按 bst 插入元素来做？就是直接build一个bst那样？

如果O(N)可做的话，那么inorder traverse BSTtree得到排好序的列表 （O(N)复杂度），也就是说我们可以O(N)排序一个无序的列表？

依我来看，给出的应该不是一随意的乱序，而是一个BST的先根序遍历。所以还是照搬449的做法。

1. class TreeNode(object):
   
2.     def __init__(self, x):
   
3.         self.val = x
   
4.         self.left = None
   
5.         self.right = None
   
6. 
   
7. class Codec:
   
8. 
   
9.     def serialize(self, root):
   
10.         """Encodes a tree to a single string.
    
11. 
    
12.         :type root: TreeNode
    
13.         :rtype: str
    
14.         """
    
15.         R = []
    
16.         L = [root]
    
17. 
    
18.         def DFS(node):
    
19.             if node:
    
20.                 R.append(node.val)
    
21.                 DFS(node.left)
    
22.                 DFS(node.right)
    
23. 
    
24.         DFS(root)
    
25.         return R
    
26. 
    
27.     def deserialize(self, data):
    
28.         """Decodes your encoded data to tree.
    
29. 
    
30.         :type data: str
    
31.         :rtype: TreeNode
    
32.         """
    
33. 
    
34.         def BuildTree(start, end):
    
35.             if start >= end:
    
36.                 return None
    
37.             i = start + 1
    
38.             while i < end and data[i] < data[start]:
    
39.                 i += 1
    
40.             root = TreeNode(data[start])
    
41.             root.left = BuildTree(start + 1, i)
    
42.             root.right = BuildTree(i, end)
    
43.             return root
    
44. 
    
45.         return BuildTree(0, len(data))

复制代码