Facebook背靠背实习挂经

周二背靠背两轮电面，
一面：口音是华人小姐姐，感觉人挺nice。一共两道题，第一题是高频的remove invalid parenthesis, 要求输出一个答案就好；第二题是给你一个未排序的数组，构建BST，面经没见过，之前刷题也没刷到，比较懵，用dfs写的，感觉

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

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

大家之前发的和总结的面经帖。



补充内容 (2018-11-15 13:17):
一面的第二题应该是蠡口 蠡口思思就的变种

二面也是leetcode上fb tag的高频题啊，好像叫什么least latest used存储器还是啥的。标准做法就是用一个hashmap和一个双链表，这题刷过一遍的话就容易多了

依我来看，给出的应该不是一随意的乱序，而是一个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))

复制代码

鱼淼淼 发表于 2018-11-15 13:56
多问一下，这题如果按照构建BT的code写可以吗？面试官有说针对BST,需要什么优化吗？
以及，问下二面.... ...

肯定不行啊，要满足BST的结构的，左边比root小，后边比root大。需要用hashmap存val的prev node和next node，remove的时候找到val，把prev node的next指向next node

请问第二道是离口上的题吗....

鱼淼淼 发表于 2018-11-15 13:03
请问第二道是离口上的题吗....

谢谢提醒，第二题是 蠡口思思就 的变种

一面的第二题应该是蠡口 蠡口思思就的变种

lanyexiaosa369 发表于 2018-11-15 13:13
一面的第二题应该是蠡口 蠡口思思就的变种

多问一下，这题如果按照构建BT的code写可以吗？面试官有说针对BST,需要什么优化吗？
以及，问下二面......怎么优化到的o（1）啊...

lanyexiaosa369 发表于 2018-11-16 05:54
肯定不行啊，要满足BST的结构的，左边比root小，后边比root大。需要用hashmap存val的prev node和next nod ...

第二题是给你一个未排序的数组，构建BST，面经没见过 <= 想过用stack 但是好像还是不太好做 有要求要o(n) 的solution 吗?.

say543 发表于 2018-11-16 13:17
第二题是给你一个未排序的数组，构建BST，面经没见过

对的，要求是O(n)的，蠡口貌似有人做出来了

多谢lz的分享～所以lz面完第二天就出回复了？？？怎么感觉有的等回复等了十几天，lz这么快呢～