Airbnb 北京onsite

北京Airbnb onsite 已跪，分享两道onsite题
第一题打印图形



实现一个 print(int n) 的函数打印图形


第二题  x-or tree

给定树的顶点个数  n
和多叉树的多条边
2 1  //2为子节点、1为父节点
3 1
4 5
7 5
5 3
6 2
9 6
8 9
10 9

给定初始化数组表示每个节点的值
1 0 0 1 0 1 0 1 0

目标数组，每个节点的值
1 1 0 1 0 1 1 1 0

每个节点的值修改时，他的孙子节点（递归下去，孙子节点的孙子节点）对应值需要反转（0-》1，1-》0）

求重初始化数组到目标数组最少需要修改几个节点，需要修改的节点是什么

第一题是打印一个分形（fractal），分形具有递归结构，当前n的某个坐标上的字符可以由n - 1子分形的某个对应字符平移（复杂的还可以旋转拉伸——也就是affine transform）得到。

写了一份参考代码：

1. #include <iostream>
   
2. #include <memory>
   
3. 
   
4. class Shape {
   
5. public:
   
6.   virtual ~Shape() {}
   
7.   virtual int GetNumRows() const = 0;
   
8.   virtual int GetNumCols() const = 0;
   
9.   virtual char GetCell(int row, int col) const = 0;
   
10. 
    
11.   static std::unique_ptr<Shape> Create(int degree);
    
12. };
    
13. 
    
14. // 最基础的三角形
    
15. class BaseTriangle : public Shape {
    
16. public:
    
17.   int GetNumRows() const override { return 2; }
    
18.   int GetNumCols() const override { return 4; }
    
19. 
    
20.   char GetCell(int row, int col) const override {
    
21.     constexpr char kShape[2][4] = {
    
22.         {' ', '/', '\\', ' ' }, {'/', '_', '_', '\\' }};
    
23.     return kShape[row][col];
    
24.   }
    
25. };
    
26. 
    
27. // 否则是一个递归分形，某个位置的字符可以依靠平移坐标再通过子分形计算
    
28. class TriangleFractal : public Shape {
    
29. public:
    
30.   TriangleFractal(int degree)
    
31.       : sub_fractal_(Shape::Create(degree - 1)),
    
32.         half_num_rows_(sub_fractal_->GetNumRows()),
    
33.         half_num_cols_(sub_fractal_->GetNumCols()),
    
34.         half_half_num_cols_(half_num_cols_ / 2),
    
35.         num_rows_(half_num_rows_ * 2),
    
36.         num_cols_(half_num_cols_ * 2) {}
    
37. 
    
38.   int GetNumRows() const override { return num_rows_; }
    
39.   int GetNumCols() const override { return num_cols_; }
    
40. 
    
41.   char GetCell(int row, int col) const override {
    
42.     // 上面部分
    
43.     if (row < half_num_rows_) {
    
44.       if (col >= half_half_num_cols_ &&
    
45.           col < half_num_cols_ + half_half_num_cols_) {
    
46.         return sub_fractal_->GetCell(row, col - half_half_num_cols_);
    
47.       }
    
48.       return ' ';
    
49.     }
    
50.     // 左下部分
    
51.     if (col < half_num_cols_) {
    
52.       return sub_fractal_->GetCell(row - half_num_rows_, col);
    
53.     }
    
54.     // 右下部分
    
55.     return sub_fractal_->GetCell(row - half_num_rows_, col - half_num_cols_);
    
56.   }
    
57. 
    
58. private:
    
59.   const std::unique_ptr<Shape> sub_fractal_;
    
60.   const int half_num_rows_;
    
61.   const int half_num_cols_;
    
62.   const int half_half_num_cols_;
    
63.   const int num_rows_;
    
64.   const int num_cols_;
    
65. };
    
66. 
    
67. std::unique_ptr<Shape> Shape::Create(int degree) {
    
68.   // 要求degree大于等于1，这里就不做check了
    
69.   if (degree == 1) {
    
70.     return std::make_unique<BaseTriangle>();
    
71.   }
    
72.   return std::make_unique<TriangleFractal>(degree);
    
73. }
    
74. 
    
75. void PrintShape(int degree) {
    
76.   std::unique_ptr<Shape> shape = Shape::Create(degree);
    
77.   for (int i = 0; i < shape->GetNumRows(); ++i) {
    
78.     for (int j = 0; j < shape->GetNumCols(); ++j) {
    
79.       std::cout << shape->GetCell(i, j);
    
80.     }
    
81.     std::cout << "\n";
    
82.   }
    
83. }
    
84. 
    
85. int main(int argc, char* argv[]) {
    
86.   for (int n = 1; n < 5; ++n) {
    
87.     std::cout << "n = " << n << "\n";
    
88.     PrintShape(n);
    
89.     std::cout << "\n";
    
90.   }
    
91.   return 0;
    
92. }
    

复制代码

谢谢楼主分享！

crazycodyman 发表于 2019-6-18 11:15
这比地里的面经难多了，是不是外企在国内自动提高bar啊

跟airbnb的朋友聊了聊，18年底之前的面试题还和地理的面经相似度很大，19年这半年已经换了不少题了，如果去面地理的题还是要准备，但出现原题的概率也就50%吧

北京的面试题库 和地理面的还是有较大不同的。

有大佬知道怎么做吗？楼主面的mobile还是backend？

crazycodyman 发表于 2019-6-17 23:19
有大佬知道怎么做吗？楼主面的mobile还是backend？

第一题，没啥思路，后来想了想，可能要动态计算这个二位数组的坐标
第二题，bfs，但是在处理孙子节点的翻转时也很麻烦

Ht1990 发表于 2019-6-18 10:22
第一题，没啥思路，后来想了想，可能要动态计算这个二位数组的坐标
第二题，bfs，但是在处理孙子节点的 ...

这比地里的面经难多了，是不是外企在国内自动提高bar啊

http://www.voidcn.com/article/p-srkptnpu-bnt.html
贴一个链接，是各种分型打印的问题

在想是不是去刷一下poj了。

赞详细的解答