AirBnb面经【挂了】

楼主，最近面了下airbnb
第一题：

You need to implement a simplified `tree` command line tool.
1. You will get some paths like '/aaa/bcd/c.txt' which split by '/' and consisted with several characters, every path starts with '/'
2. All the characters are in `[a-zA-Z0-9./]`
3. You need to output files/sub-folders in the same folder in dictionary order
4. You need to output the hierarchical path tree as following:
sample input:

[
"/bin/usr/bash",
"/var/test/.ssh",
"/var/log/wifi.log",
"/opt",
"/xyz"
]

sample output:

+-- bin
|   +-- usr
|       +-- bash
+-- opt
+-- var
|   +-- log
|   |   +-- wifi.log
|   +-- test
|       +-- .ssh
+-- xyz

the indent should be 4 blanks
* new node starts with `+-- `
* the siblings are linked by '|'
Note: How to handle the input/output is not important. You can even hard code the input as a string array in the code.

我的代码:

1. 
   
2. import java.util.*;
   
3. 
   
4. public class Main {
   
5.     public static class Tree {
   
6.         String val;
   
7. 
   
8.         Tree() {
   
9.         };
   
10. 
    
11.         Tree(String val) {
    
12.             this.val = val;
    
13.         }
    
14. 
    
15.         ArrayList<Tree> children = new ArrayList<>();
    
16.     }
    
17. 
    
18.     public static void main(String[] args) {
    
19. 
    
20. 
    
21.         String[] arr = {"/bin/usr/bash",
    
22.                 "/var/test/.ssh",
    
23.                 "/var/log/wifi.log",
    
24.                 "/opt",
    
25.                 "/xyz"
    
26.                         };
    
27.         Arrays.sort(arr);
    
28.         Tree head = new Tree("/");
    
29.         Tree t = head;
    
30.         for (String s : arr) {
    
31.             String[] tmp = s.split("\\/");
    
32.             t = head;
    
33.             for (String a : tmp) {
    
34.                 if (a.equals("")) {
    
35.                     continue;
    
36.                 }
    
37.                 boolean flag = false;
    
38.                 for (Tree tree : t.children
    
39.                 ) {
    
40.                     if (a.equals(tree.val)) {
    
41.                         t = tree;
    
42.                         flag = true;
    
43.                         break;
    
44.                     }
    
45.                 }
    
46.                 if (!flag) {
    
47.                     Tree tree = new Tree(a);
    
48.                     t.children.add(tree);
    
49.                     t = tree;
    
50.                 }
    
51.             }
    
52.         }
    
53.         //
    
54. 
    
55.         dfs(head, 0, "",false);
    
56. 
    
57.       //  System.out.println("1234");
    
58.         return;
    . Waral dи,
59. 
    
60.     }
    
61. 
    
62.     public static void dfs(Tree t, int i, String s,Boolean hasFloor) {
    
63.         System.out.println(s + t.val);
    
64.         if (t.children.isEmpty()) {
    
65.             return;
    
66.         }
    
67. 
    
68.         int num = t.children.size();
    
69.         for (int j = 0; j < num; ++j) {
    
70.             Tree tree = t.children.get(j);
    
71.             StringBuffer sb = new StringBuffer(s);
    
72.             if ( i == 0){
    
73.                 sb.append("+-- ");
    . From 1point 3acres bbs
74.             }
    
75.             if (i > 0 ) {
    
76.                 if (hasFloor) {
    
77.                     sb.insert(sb.length() - 4, "|   ");
    
78.                 } else {
    
79.                     sb.insert(sb.length() - 4, "    ");
    
80.                 }
    
81.             }
    
82.             if(j == num-1) {
    
83.                 hasFloor = false;
    
84.             }else {
    
85.                 hasFloor = true;
    
86.             }
    
87.             dfs(tree, i + 1, sb.toString(),hasFloor);
    
88.         }
    
89. 
    
90.     }
    
91. 
    
92. }

复制代码

第二题:
Problem statement
Given a nonnegative number set (can have duplicates), divide it into two sets so that the sum of the variances of these two sets is minimized. You can shuffle set order. The values of two sets cannot overlap. All number in the original set must appear in one of the two sets.
Finally return the value of the sum. The result include one decimal place.
The definition of variance: S^2= ∑ (X-a) ^2 / (n-1), where X is the average, a is every number in the set, and n is the size of the set.
For example: There is a set [1,3,1] . We can divide it into [1,1] and [3], Then return the result:0.0
Please simply proof the correctness of your solution.
Follow up: What if we want to divide the set into three subsets?

1. //CASE 1:
   
2. // Input
   
3. // [4,3,2,1]
   
4. // Output
   
5. // 1.0
   
6. import java.util.*;
   
7. public class Main {
   
8.     public static void main(String[] args) {
   
9.         //Scanner in = new Scanner(System.in);
   
10.         //int a = in.nextInt();
    
11.         //System.out.println(a);
    
12.         System.out.println("Hello World!");
    
13.         
    
14.         // n 知道 sum 知道 min ((sumA/a -ai)/a-1 + ((sum-aumA)/n-a - bi)/n-a-1)
    
15.         // sum 可以分成 a+b个数  (sumA/a-ai)^2/ a-1 + sumB/b
    
16.         int []arr = {4,3,2,1};
    
17.         //int[]arr = {1,3,1};
    
18.         Arrays.sort(arr);
    
19.         int len = arr.length; // 数组长度
    
20.         // 如果数组小于 2 则直接返回 0
    
21.         if( len  < 2 ) {
    
22.             System.out.println(0);
    
23.             return ;
    
24.         }
    
25.         int sum = 0; // 前缀求和
    
26.         double ans = 10000;  // 存储最小的结果
    
27.         int sum2 = 0;
    
28.         for( int i = 0; i < len; ++i ) {
    
29.             sum += arr[i];
    
30.             sum2 += arr[i]*arr[i];
    
31.         }
    
32.         // 选择分割点
    
33.         int pre = 0; //前缀和
    
34.         int pre2 = 0; // 前缀平方和
    
35.         for ( int i = 0; i < len-1; ++i ) {
    . From 1point 3acres bbs
36.             pre += arr[i];
    
37.             pre2 += arr[i]*arr[i];
    
38.             int ave = pre/(i+1);
    
39.             int x =(i+1)*ave*ave;
    
40.             int mid = 2*ave*pre;
    
41.             int y = pre2;
    
42.                 // 长度为0 则直接为0
    
43.             double a = 0;
    
44.             double b = 0;
    
45.             if(i > 0) {
    
46.               a = (double)(x-mid+y)/i;   
    
47.            }else{
    
48.              a = 0;
    
49.            }
    
50.             //System.out.println("a:"+a);
    
51.             int ave2 = (sum-pre)/(len-i-1);
    
52.            // System.out.println("ave2:"+ave2);
    
53.             int x2 = (len-i-1)*ave2*ave2;
    
54.             //System.out.println("x2:"+x2);
    
55.             int mid2 = 2*ave2*(sum-pre);
    
56.             //System.out.println("mid2:"+mid2);
    
57.             int y2 = sum2-pre2;
    
58.             //System.out.println("y2:"+y2);
    
59.                 if(len-i-1>1) {
    
60.                     b = (double)(x2-mid2+y2)/(len-i-1-1);
    
61.                 }else{
    
62.                     b = 0;
    
63.                 }
    
64.             //System.out.println("b:"+b);
    
65.             ans= Math.min(a+b,ans);
    
66.             
    
67.         }
    
68.         System.out.println(ans);
    
69.         
    
70.     }
    
71.    
    
72.   
    
73. }

复制代码

第二题面试的时候有个变量ave2没有写2 导致答案一直不对，时间来不及 面试官就说到这吧。。自己太菜了 虽然挂了 求点大米安慰下～～

skyshuaiboy 发表于 2022-5-2 02:01
｜这个符号 你可以理解为 关联同级目录的  因为.ssh的上一级目录没有同级目录了 所以不需要加 ｜

还是不理解  .ssh 上级是/test/么， /test/不是有同级目录 /log/么 而且log字典顺序再test前面

Felix1218 发表于 2022-4-27 00:07
已加米 请问楼主怎么获得Airbnb面试机会呢 谢谢

投简历 然后oa做题 过了就可以面试了

楼主这是电面吗?

已加米 请问楼主怎么获得Airbnb面试机会呢 谢谢

einApfel 发表于 2022-4-26 23:52
楼主这是电面吗?

算ov吧 你说的是电面是OA么？就是做题？

为什么 同为 第三级directory    |       +-- .ssh 和   |       +-- bash 只有一个  |   
而 |   |   +-- wifi.log 这个有两个|

jeanne_17 发表于 2022-5-2 08:25
为什么 同为 第三级directory    |       +-- .ssh 和   |       ...

｜这个符号 你可以理解为 关联同级目录的  因为.ssh的上一级目录没有同级目录了 所以不需要加 ｜

感謝分享
這是onsite嗎？

mikemike0 发表于 2022-5-3 16:23
感謝分享
這是onsite嗎？

嗯 是的 感谢加米～