facebook 电面 3.2

Facebook 电面第一轮，报面经攒人品求onsite。找人内推的。第二天hr就联系我了。约了电面。
电面打电话过来的是一个美国人，听口音。开始问了最近在坐得project，然后开始写代码

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

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

ce，excellent。其实我觉得我第二题有向图修改的代码不一定对。

1. INPUT: "xyzabcxyaaxyd"
   
2. OUTPUT: "xyzabcd"
   
3. 
   
4. class Solution{
   
5.     public String removeD(String s){
   
6.         if(s==null || s.length()==0) return s;
   
7.         HashMap<Character, Boolean> hs = new HashMap<>();
   
8.         StringBuilder result = new StringBuilder();
   
9.         for(int i = 0; i<s.length(); i++){
   
10.             if(!hs.constainsKey(s.charAt(i)){
    
11.                 hs.put(s.charAt(i), true);
    
12.                 result.append(s.charAt(i));
    
13.             }
    
14.         }
    
15.         return new String(result);
    
16.     }
    
17. }
    
18. 
    
19. 
    
20.          A
    
21.         / \
    
22.        B   C
    
23.       /   / \
    
24.      D   E   F
    
25.      
    
26. Output:
    
27. ABD
    
28. ACE
    
29. ACF
    
30. 
    
31. class TreeNode{
    
32.     int val;
    
33.     ArrayList<TreeNode> child;
    
34.     boolean isVisited = false;
    
35.     public TreeNode(int x){
    
36.         val = x;
    
37.         child = null;
    
38.     }
    
39. }
    
40. 
    
41. class Soulution{
    
42.     public void printPath(TreeNode root, ArrayList<TreeNode> list){
    
43.         if(root == null || root.isVistied==true) return;
    
44.         if(root.child==null){
    
45.             list.add(root);
    
46.             print(list);
    
47.             list.remove(list.size()-1);
    
48.             return;
    
49.         }
    
50.         list.add(root);
    
51.         list.isVisited = true;
    
52.         for(TreeNode e : root.child){
    
53.             printPath(e, list);
    
54.         }
    
55.         //printPath(root.left, list);
    
56.         //printPath(root.right,list);
    
57.         list.remove(list.size()-1);
    
58.     }
    
59.    
    
60.     public void print(ArrayList<TreeNode> list){
    
61.         for(TreeNode e: list){
    
62.             System.out.print(e.val);
    
63.         }
    
64.         System.out.println();
    
65.     }
    
66. }
    
67. 
    
68. 
    
69. 
    
70.     A
    
71.    / \
    
72.   B   C
    
73.    \ /
    
74.     D
    
75.    / \
    
76.   E   F
    
77.    \ /
    
78.     G

复制代码

应该还可以吧。
卤煮改成图的代码也上了？

houqingniao 发表于 2015-3-3 08:28
应该还可以吧。
卤煮改成图的代码也上了？

第二题的代码就是修改以后的代码

此题应该不需要isVisited这个boolean吧，有的点还是会被重复访问的，比如最后那个图

deanmax 发表于 2015-3-4 09:05
此题应该不需要isVisited这个boolean吧，有的点还是会被重复访问的，比如最后那个图

我也觉得不用啊。。如果只是从根输出到叶子，DFS就ok。follow up是不是问如果有环要判断并中断啊？那就设定一个visit 如果第二次处于某种状况又遇到了 直接return -1？？这个意思么。

DFS对undirected和directed有区别吗？不都要记录visited吗？
当然如果是tree，就默认没cycle，就不需要用visited了

第一题不用hashMap吧，用hashSet是不是就可以了

第一题不用hashMap吧，用hashSet是不是就可以了

pandafolk 发表于 2015-3-5 01:00
我也觉得不用啊。。如果只是从根输出到叶子，DFS就ok。follow up是不是问如果有环要判断并中断啊？那就设 ...

同疑问，为什么visit过了就不输出了？
LZ贴的第二个图输出应该是什么？