Facebook 电面

电面1
1. Determine is a tree is a binary search tree. Follow up: What if you can't

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

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

it without instantiating too many HashSet?

第一题，用Morris traversal 中序遍历即可

电面1-1，对于follow up，我的解法是用inorder去valid

1. class Solution {
   
2.     private Stack<Integer> stack = new Stack();
   
3.     private void inOrder(TreeNode root) {
   
4.         if (root==null) return;
   
5.         inOrder(root.left);
   
6.         stack.add(root.val);
   
7.         inOrder(root.right);
   
8.     }
   
9.     public boolean isValidBST(TreeNode root) {
   
10.         if (root==null) return true;
    
11.         inOrder(root);
    
12.         int end = stack.pop();
    
13.         while(!stack.isEmpty()) {
    
14.             int left = stack.pop();
    
15.             if (end<=left) return false;
    
16.             end = left;
    
17.         }
    
18.         return true;
    
19.     }
    
20. }

复制代码

jigsaw_Becky 发表于 2017-9-14 04:05
没有理解二面How to do it without instantiating too many HashSet?
哪里有需要用很多歌hashset么？用一 ...

这题还有点难度，abc，abc，bca被group在一起，但是两个abc必须删除一个，目标是让你少用hash去查重。

楼主怎么两次电面，这是找实习的电面吗？

1. 求问楼主如果不用recursion该怎么做啊？
2. 第二题不就是用了一个HashSet吗？“不能用太多hashset是什么意思啊”？

1，用iteration的方式进行inorder遍历，时间复杂度O(N),空间复杂度O(h)
2，一个HashMap, 以sorted(word)作为key，不知道对不对

ws775901 发表于 2017-9-10 18:34
第一题，用Morris traversal 中序遍历即可

空间复杂度O(1)

第二题感觉同一个key的字符串可以形成一个Trie树，每次加入一个字符串时检查下Trie树里是否有，这样就可以不用Hashset了

ws775901 发表于 2017-9-10 18:42
第二题感觉同一个key的字符串可以形成一个Trie树，每次加入一个字符串时检查下Trie树里是否有，这样就可以 ...

但是如果“ABC”出现了两次，还是要用hashset去重一下

没有理解二面How to do it without instantiating too many HashSet?
哪里有需要用很多歌hashset么？用一个就够了吧？