一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

一亩三分地官方iOS手机应用下载
查看: 5351|回复: 30
收起左侧

fb intern面经,面对奇葩问题膝盖碎了

[复制链接] |试试Instant~ |关注本帖
gu0001hi 发表于 2014-3-4 05:53:14 | 显示全部楼层 |阅读模式

2014(1-3月) 码农类 硕士 实习@Facebook - 校园招聘会 - 技术电面 |Fail

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
已跪,45分钟面了道很奇葩的问题,面试是个三哥,有气无力地听着,最后也装模作样回答一些问题.. 跪了
问题:
Print arbitrary binary tree by vertical levels / columns from left to right
.鏈枃鍘熷垱鑷1point3acres璁哄潧

example tree.鐣欏璁哄潧-涓浜-涓夊垎鍦

      a
     / \
    b   c.鏈枃鍘熷垱鑷1point3acres璁哄潧
   / \   \
  d   g   z
   \     /
    e   i
       /-google 1point3acres
      q
     /
    x
   /
  x1-google 1point3acres
/
x2


sample output. 1point 3acres 璁哄潧
. 鍥磋鎴戜滑@1point 3 acres
x2. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
d x1
b e x
a g q
c i
. from: 1point3acres.com/bbs
. From 1point 3acres bbs
我想的是先traverse一遍,然后把nodes存进相应的vector里面去,
void store(TreeNode* root, vector<vector<TreeNode*> > &h, int key)
{. 鍥磋鎴戜滑@1point 3 acres
    if(!root)
        return;
    h[key].push(root);
    store(root->left, h, key--);. 1point3acres.com/bbs
    store(root->right, h, key++);
}
然后print出来,最后有点问题,因为那个level的index如果root是0的话,左边的就都是负数了,不知道怎么存进相应的vector里面去,就gg了



补充内容 (2014-3-4 06:01):
在用vector之前我还想到用hash,然后preorder traversal一下把所有的nodes按照<key, value>这样存进去,但是我当时想法是key必须是unique,所以这个办法被我否决了.. 后来发现是不是可以把<key, string>这样存

补充内容 (2014-3-4 06:02):. 1point 3acres 璁哄潧
因为他要求的只是打印出来,不需要有data structure可以存所有的nodes.. 这样可以达到题目要求,可是总觉得不是很好,有点投机取巧,求大大们解释

评分

4

查看全部评分

本帖被以下淘专辑推荐:

  • · fb|主题: 33, 订阅: 15
Neal_kks 发表于 2014-11-25 14:50:14 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
这个题在做雅虎笔试的时候遇到过,我当时看成求层序遍历了,以为好简单。。用preorder递归应该是不行的,举个反例,假设第一个左孩子的右子树往右延伸了很长,那么在bfs他们都会在跟的右子树之前被加入到hash表,这是不对的。用层序遍历其实也不复杂,用个pair把他再水平方向的偏移量记录一下即可。贴一下我的实现,例子是楼主给出的那个。大家看看有没有bug。
  1. #include <iostream>
  2. #include <map>
  3. #include <string>
  4. #include <queue>
  5. #include <vector>. 1point 3acres 璁哄潧
  6. using namespace std;. 鍥磋鎴戜滑@1point 3 acres

  7. struct tree{
  8.     string key;
  9.     tree *left, *right;
  10.     tree(string mkey):key(mkey), left(NULL), right(NULL){}
  11. };

  12. typedef pair<tree*, int> pti;. visit 1point3acres.com for more.

  13. map<int, vector<tree*> > dict;.鐣欏璁哄潧-涓浜-涓夊垎鍦

  14. void build(tree *root){. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  15.     if(root == NULL){-google 1point3acres
  16.         return;
  17.     }
  18.     queue<pti> que;. 1point 3acres 璁哄潧
  19.     que.push(pti(root, 0));
  20.     while(!que.empty()){. 1point 3acres 璁哄潧
  21.         pti cur = que.front();
  22.         que.pop();
  23.         dict[cur.second].push_back(cur.first);
  24.         if(cur.first->left){
  25.             que.push(pti(cur.first->left, cur.second-1));
  26.         }
  27.         if(cur.first->right){
  28.             que.push(pti(cur.first->right, cur.second+1));
  29.         }. more info on 1point3acres.com
  30.     }
  31. }

  32. void solve(tree *root){
  33.     if(root == NULL){
  34.         return;
  35.     }
  36.     build(root);
  37.     map<int, vector<tree*> >::const_iterator it = dict.begin();. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  38.     while(it != dict.end()){. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  39.         vector<tree*>::const_iterator itt = it->second.begin();
  40.         while(itt != it->second.end()){.鐣欏璁哄潧-涓浜-涓夊垎鍦
  41.             cout<<(*itt)->key<<"\t";. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  42.             ++itt;
  43.         }
  44.         cout<<endl;
  45.         ++it;. From 1point 3acres bbs
  46.     }
  47. }

  48. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  49. int main(){. 鍥磋鎴戜滑@1point 3 acres
  50.     tree *t1 = new tree("a");. more info on 1point3acres.com
  51.     tree *t2 = new tree("b");
  52.     tree *t3 = new tree("c");
  53.     tree *t4 = new tree("d");
  54.     tree *t5 = new tree("e");
  55.     tree *t6 = new tree("g");
  56.     tree *t7 = new tree("z");
  57.     tree *t8 = new tree("i");
    -google 1point3acres
  58.     tree *t9 = new tree("q");
  59.     tree *t10 = new tree("x");
  60.     tree *t11 = new tree("x1");. 1point3acres.com/bbs
  61.     tree *t12 = new tree("x2");
  62.     t1->left = t2;
  63.     t1->right = t3;
  64.     t2->left = t4;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  65.     t2->right = t6;
  66.     t4->right = t5;
  67.     t3->right = t7;
  68.     t7->left = t8;
  69.     t8->left = t9;
  70.     t9->left = t10;. 1point 3acres 璁哄潧
  71.     t10->left = t11;. 鍥磋鎴戜滑@1point 3 acres
  72.     t11->left = t12;
  73.     solve(t1);
  74. }

  75. /*.鐣欏璁哄潧-涓浜-涓夊垎鍦
  76.       a
  77.      / \
  78.     b   c
  79.    / \   \-google 1point3acres
  80.   d   g   z
  81.    \     /
  82.     e   i
  83.        /
    -google 1point3acres
  84.       q
  85.      /
  86.     x
  87.    /
  88.   x1
  89. /. from: 1point3acres.com/bbs
  90. x2
  91. */

复制代码
回复 支持 2 反对 1

使用道具 举报

当年也正派 发表于 2014-3-4 09:45:21 | 显示全部楼层
关注一亩三分地微博:
Warald
我的想法是用hashmap, key是列的偏移,设定root偏移为0,然后向左走偏移-1,向右偏移+1,value是一个String的arraylist。然后应该和lz想法就差不多了,preorder遍历,每个node的值append到对应的偏移的arraylist后面
回复 支持 1 反对 0

使用道具 举报

CrossTheWall 发表于 2015-2-9 20:54:22 | 显示全部楼层
这题虽然略蛋疼但还比较容易,preorder traversal tree,用unordered_map<int,  vector<TreeNode*> >来保存每个key相同的结点集合,根的key是0,左树加1, 右树减1。 key是正是负都无所谓
回复 支持 0 反对 1

使用道具 举报

尚佳蕾 发表于 2015-2-5 21:42:56 | 显示全部楼层
your output is like this omg!

x2       
d        x1       
b        e        x       
a        g        q       
c        i       
z       
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 0 反对 1

使用道具 举报

kongweihan 发表于 2014-11-24 08:44:12 | 显示全部楼层
我觉得可以用TreeMap,随时保证index按顺序排列,TreeMap<Integer, TreeMap<Integer, Integer>> map;
递归DFS,每次调用传入level以及横向的index,左孩子-1,右孩子+1
  1. TreeMap<Integer, TreeMap<Integer, Integer>> map;
  2. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  3.     void verticalPrint(TreeNode root) {
  4.         if (root == null) return;
  5.         map = new TreeMap<Integer, TreeMap<Integer, Integer>>();

  6.         populateMap(root, 1, 0);
  7.         printMap(map);
  8.     }
  9. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  10.     void populateMap(TreeNode root, int level, int indent) {
  11.         if (!map.containsKey(indent)) map.put(indent, new TreeMap<Integer, Integer>());.鐣欏璁哄潧-涓浜-涓夊垎鍦
  12.         map.get(indent).put(level, root.val);

  13.         if (root.left != null) {
  14.             populateMap(root.left, level+1, indent-1);
    . from: 1point3acres.com/bbs
  15.         }
  16.         if (root.right != null) {
  17.             populateMap(root.right, level+1, indent+1);
  18.         }
  19.     }

  20.     void printMap(TreeMap<Integer, TreeMap<Integer, Integer>> map) {. visit 1point3acres.com for more.
  21.         for (Integer indent : map.keySet()) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  22.             for (Integer level : map.get(indent).keySet()) {
  23.                 System.out.print(map.get(indent).get(level) + " ");
  24.             }
  25.             System.out.println();
  26.         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  27.     }
复制代码
. visit 1point3acres.com for more.
补充内容 (2014-11-24 08:46):
时间复杂度O(NloglogN),因为两层TreeMap所以两个log(大家觉得对么?),空间复杂度O(N)

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

austurela 发表于 2014-3-4 07:07:44 | 显示全部楼层
How is this?. From 1point 3acres bbs
  1. import java.util.ArrayList;
  2. . 1point 3acres 璁哄潧
  3. public class PrintByColumn<T> {
  4.        
  5.         public void Print(TreeNode<T> root){.1point3acres缃
  6.                 ArrayList<ArrayList<T>> right = new ArrayList<ArrayList<T>>();
  7.                 ArrayList<ArrayList<T>> left = new ArrayList<ArrayList<T>>();
  8.                 printHelper(0, root, left, right);
  9.                 // Print result
  10.                 for(int i = left.size() - 1; i > 0; i--){
  11.                         System.out.println(left.get(i));
  12.                 }
  13.                 for(int i = 0; i < right.size(); i++){
  14.                         System.out.println(right.get(i));
  15.                 }. visit 1point3acres.com for more.
  16.         }
  17.        
  18.         private void printHelper(int index, TreeNode<T> root, ArrayList<ArrayList<T>> left, ArrayList<ArrayList<T>> right){
  19.                 // Base case
  20.                 if(root == null)        return;
  21.                 // Normal case
  22.                 if(index >= 0){
  23.                         while(right.size() <= index){
  24.                                 right.add(new ArrayList<T>());
  25.                         }
  26.                         right.get(index).add(root.data);
  27.                 }
  28.                 else{. visit 1point3acres.com for more.
  29.                         while(left.size() <= -index){
  30.                                 left.add(new ArrayList<T>());. From 1point 3acres bbs
  31.                         }.1point3acres缃
  32.                         left.get(-index).add(root.data);
  33.                 }
  34.                 // Recurse. 1point3acres.com/bbs
  35.                 printHelper(index - 1, root.left, left, right);
  36.                 printHelper(index + 1, root.right, left, right);
  37.         }
  38. }
复制代码
Testing: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  1. import java.util.*;

  2. class TreeNode<T>{. From 1point 3acres bbs
  3.         TreeNode<T> left;
  4.         TreeNode<T> right;
    . 1point3acres.com/bbs
  5.         T data;
  6.        
  7.         TreeNode(T data){. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  8.                 this.data = data;
  9.         }
  10. }

  11. public class Test {
  12.         public static void main(String[] args){
  13.                 TreeNode<String> root = new TreeNode<String>("a");
  14.                 root.left = new TreeNode<String>("b");
  15.                 root.right = new TreeNode<String>("c");
  16.                 .鐣欏璁哄潧-涓浜-涓夊垎鍦
  17.                 root.left.left = new TreeNode<String>("d");
  18.                 root.left.right = new TreeNode<String>("g");
  19.                
  20.                 root.right.right = new TreeNode<String>("z");. more info on 1point3acres.com
  21.                 root.right.right.left = new TreeNode<String>("i");
  22.                 root.right.right.left.left = new TreeNode<String>("q");. From 1point 3acres bbs
  23.                 root.right.right.left.left.left = new TreeNode<String>("x");
  24.                 root.right.right.left.left.left.left = new TreeNode<String>("x1");. Waral 鍗氬鏈夋洿澶氭枃绔,
  25.                 root.right.right.left.left.left.left.left = new TreeNode<String>("x2");-google 1point3acres
  26.                
  27.                 root.left.left.right = new TreeNode<String>("e");
  28.                
  29.                 PrintByColumn<String> test = new PrintByColumn<String>();
  30.                 test.Print(root);
  31.         }
  32. }
复制代码



.1point3acres缃
补充内容 (2014-3-4 07:08):
Output:
[x2]
[d, x1]
[b, e, x]
[a, g, q]
[c, i]. 1point 3acres 璁哄潧
[z]

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

lhn9021 发表于 2014-3-4 09:25:32 | 显示全部楼层
跟求bs的最大深度一样 用recursion求完深度以后加到深度的arraylist即可

补充内容 (2014-3-4 09:32):.鏈枃鍘熷垱鑷1point3acres璁哄潧
貌似不对 还得想想. Waral 鍗氬鏈夋洿澶氭枃绔,
. 鍥磋鎴戜滑@1point 3 acres
补充内容 (2014-3-4 09:45):. 1point 3acres 璁哄潧
我的做法跟lz 一样 左面key减1右面key加1 然后用hashmap 保存 key linkedlist 和最大最小值 然后iterate
回复 支持 反对

使用道具 举报

lixiang.xjtu 发表于 2014-3-4 11:08:49 | 显示全部楼层
弄个链表不行吗。正的往右,负的往左。
或者弄俩数组,一个存正的,一个存负的。
回复 支持 反对

使用道具 举报

nothingtrouble 发表于 2014-3-5 02:10:25 | 显示全部楼层

我觉得也是,HashMap<Integer,ArrayList<TreeNode>>用来保存对应的key对应的节点,更新最小key value就行了。然后iterate hashmap,比如key的最小是-5,那么说明root左边有5层,那么key=-5 to key not in HashMap,依次print HashMap中的ArrayList
回复 支持 反对

使用道具 举报

WinterNight 发表于 2014-3-5 08:41:22 | 显示全部楼层
想法差不多,BFS。 HashMap<Integer, ArrayList<Integer>> , 存一下最大最小列数.鏈枃鍘熷垱鑷1point3acres璁哄潧
=========
key   value
0      a -> g -> q
-1      b -> e -> x 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
1      c -> i
-2      d -> x1
2      z. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
-3      x2
回复 支持 反对

使用道具 举报

lingeast 发表于 2014-3-5 11:50:25 | 显示全部楼层
用vector<vector<Node*>> tree_list 结构是可以存的。做一个pre-order traverse,把node放到相应的level中,因为是pre-order,所以tree_list.size()始终等于 depth 或 depth + 1。
回复 支持 反对

使用道具 举报

tyr034 发表于 2014-10-29 00:43:51 | 显示全部楼层
lingeast 发表于 2014-3-5 11:50
用vector tree_list 结构是可以存的。做一个pre-order traverse,把node放到相应的level中,因为是pre-orde ...

pre-ordery 应该不行把,因为会把level的顺序弄乱。
虽然题主给的case这题可以用Pre-order,但我觉得是特例。
得 Breadth first search。
回复 支持 反对

使用道具 举报

byrlhb 发表于 2014-10-29 01:18:50 | 显示全部楼层
austurela 发表于 2014-3-4 07:07
How is this?.鐣欏璁哄潧-涓浜-涓夊垎鍦
Testing:

好方法,不过我感觉插入left的时候的判断条件应该是-index > left.size(), 不要那个等于号,请指正了
回复 支持 反对

使用道具 举报

byrlhb 发表于 2014-10-29 01:23:35 | 显示全部楼层

楼主还有一个,就是每个节点的左孩子和右孩子一定是比它父亲大一或者小1,感觉其实在判断left和right是不是有这个点对应的index的时候只需要用if就可以了,如果能到达这个index,那么说明所有绝对值小于或等于这个index的点已经经历过了
回复 支持 反对

使用道具 举报

gsm107 发表于 2014-10-29 13:21:27 | 显示全部楼层
austurela 发表于 2014-3-4 07:07. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
How is this?
Testing:

层主我问下,你是怎么判断节点在一条线上呢,就比如说root.left.right和root.right.left,因为按图上画的,root.left.right就跟root在一条垂直线上了,这时候root.right.left有节点的话,位置不就跟那个root.left.right重合了么?
回复 支持 反对

使用道具 举报

gsm107 发表于 2014-10-29 13:21:40 | 显示全部楼层
austurela 发表于 2014-3-4 07:07. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
How is this?
Testing:

层主我问下,你是怎么判断节点在一条线上呢,就比如说root.left.right和root.right.left,因为按图上画的,root.left.right就跟root在一条垂直线上了,这时候root.right.left有节点的话,位置不就跟那个root.left.right重合了么?
回复 支持 反对

使用道具 举报

gsm107 发表于 2014-10-29 13:22:02 | 显示全部楼层
austurela 发表于 2014-3-4 07:07. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
How is this?
Testing:

层主我问下,你是怎么判断节点在一条线上呢,就比如说root.left.right和root.right.left,因为按图上画的,root.left.right就跟root在一条垂直线上了,这时候root.right.left有节点的话,位置不就跟那个root.left.right重合了么?
回复 支持 反对

使用道具 举报

pyemma 发表于 2014-10-30 09:54:52 | 显示全部楼层
我在疑惑这道题会不会有交叉的情况,如果有较差那就不知道要怎么做了,没有交叉的话那就很好说,中序遍历一下带着列数然后往hash里面存就好了
回复 支持 反对

使用道具 举报

valder 发表于 2014-10-30 10:13:49 | 显示全部楼层
用level-order遍历然后把相应的点加到arraylist里面去吧
回复 支持 反对

使用道具 举报

22691482 发表于 2014-11-4 13:03:48 | 显示全部楼层
BFS-》 保证顺序,即越靠近根的在队列前面
然后map<vertical_index, queue<node*>>.
其中,根的vertical_index是0,往左减1,往右加一。
用两个变量记录min_vertical_index, max_vertical_index .. 鍥磋鎴戜滑@1point 3 acres
打印时从map里,从min_vertical_index, 到 max_vertical_index
回复 支持 反对

使用道具 举报

adiggo 发表于 2014-11-5 07:30:50 | 显示全部楼层
这道貌似是高频题啊。
回复 支持 反对

使用道具 举报

kongweihan 发表于 2014-11-24 08:41:01 | 显示全部楼层
22691482 发表于 2014-11-4 13:03
BFS-》 保证顺序,即越靠近根的在队列前面. more info on 1point3acres.com
然后map.
其中,根的vertical_index是0,往左减1,往右加一。
...

请问BFS如何知道当前节点的vertical_index呢?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2017-3-27 16:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表