在国外一跟老外吵架口语立刻就不够用了

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 6302|回复: 30
收起左侧

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

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

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

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

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

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


example tree

      a
     / \
    b   c. Waral 博客有更多文章,
   / \   \
  d   g   z
   \     /
    e   i.1point3acres网
       /
      q
     /
    x
   /
  x1
/
x2
. Waral 博客有更多文章,

sample output-google 1point3acres
. From 1point 3acres bbs
x2
d x1
b e x
a g q
c i


我想的是先traverse一遍,然后把nodes存进相应的vector里面去,
void store(TreeNode* root, vector<vector<TreeNode*> > &h, int key)
{. Waral 博客有更多文章,
    if(!root)
        return;
    h[key].push(root);
    store(root->left, h, key--);
    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):
因为他要求的只是打印出来,不需要有data structure可以存所有的nodes.. 这样可以达到题目要求,可是总觉得不是很好,有点投机取巧,求大大们解释

评分

4

查看全部评分

本帖被以下淘专辑推荐:

  • · fb|主题: 33, 订阅: 16
Neal_kks 发表于 2014-11-25 14:50:14 | 显示全部楼层
这个题在做雅虎笔试的时候遇到过,我当时看成求层序遍历了,以为好简单。。用preorder递归应该是不行的,举个反例,假设第一个左孩子的右子树往右延伸了很长,那么在bfs他们都会在跟的右子树之前被加入到hash表,这是不对的。用层序遍历其实也不复杂,用个pair把他再水平方向的偏移量记录一下即可。贴一下我的实现,例子是楼主给出的那个。大家看看有没有bug。
  1. #include <iostream>
  2. #include <map>
  3. #include <string>
  4. #include <queue>
  5. #include <vector>
  6. using namespace std;
  7. . 围观我们@1point 3 acres
  8. struct tree{ 来源一亩.三分地论坛.
  9.     string key;
  10.     tree *left, *right;
  11.     tree(string mkey):key(mkey), left(NULL), right(NULL){}
  12. };

  13. typedef pair<tree*, int> pti;

  14. map<int, vector<tree*> > dict; 来源一亩.三分地论坛.

  15. void build(tree *root){
  16.     if(root == NULL){
  17.         return;
  18.     }. 1point 3acres 论坛
  19.     queue<pti> que;
  20.     que.push(pti(root, 0));. 围观我们@1point 3 acres
  21.     while(!que.empty()){
  22.         pti cur = que.front();
  23.         que.pop();
  24.         dict[cur.second].push_back(cur.first);
  25.         if(cur.first->left){.留学论坛-一亩-三分地
  26.             que.push(pti(cur.first->left, cur.second-1));
  27.         }
  28.         if(cur.first->right){
  29.             que.push(pti(cur.first->right, cur.second+1));
  30.         }
  31.     }
  32. }. from: 1point3acres

  33. void solve(tree *root){
  34.     if(root == NULL){. Waral 博客有更多文章,
  35.         return;
  36.     }
  37.     build(root);
  38.     map<int, vector<tree*> >::const_iterator it = dict.begin();
  39.     while(it != dict.end()){
  40.         vector<tree*>::const_iterator itt = it->second.begin();
  41.         while(itt != it->second.end()){ 来源一亩.三分地论坛.
  42.             cout<<(*itt)->key<<"\t";
  43.             ++itt;
  44.         }
  45.         cout<<endl;-google 1point3acres
  46.         ++it;
  47.     }. more info on 1point3acres
  48. }

  49. int main(){
  50.     tree *t1 = new tree("a");
  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");
  58.     tree *t9 = new tree("q");
  59.     tree *t10 = new tree("x");
  60.     tree *t11 = new tree("x1");
  61.     tree *t12 = new tree("x2");
  62.     t1->left = t2;
  63.     t1->right = t3;
  64.     t2->left = t4;
  65.     t2->right = t6;
  66.     t4->right = t5;
  67.     t3->right = t7;
  68.     t7->left = t8;. 留学申请论坛-一亩三分地
  69.     t8->left = t9;
  70.     t9->left = t10;
  71.     t10->left = t11;
  72.     t11->left = t12;
  73.     solve(t1);
  74. }
  75. . 1point3acres
  76. /*
  77.       a
  78.      / \. 留学申请论坛-一亩三分地
  79.     b   c
  80.    / \   \
  81.   d   g   z.留学论坛-一亩-三分地
  82.    \     /
  83.     e   i
  84.        /
  85.       q
  86.      /
  87.     x. 1point 3acres 论坛
  88.    /
  89.   x1
  90. /
  91. x2.1point3acres网
  92. */. From 1point 3acres bbs
  93. .留学论坛-一亩-三分地
复制代码
回复 支持 2 反对 1

使用道具 举报

当年也正派 发表于 2014-3-4 09:45:21 | 显示全部楼层
我的想法是用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!-google 1point3acres

x2       
d        x1       
b        e        x       
a        g        q       
c        i       
z       
回复 支持 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.     void verticalPrint(TreeNode root) {
  3.         if (root == null) return;
  4.         map = new TreeMap<Integer, TreeMap<Integer, Integer>>(); 来源一亩.三分地论坛.

  5.         populateMap(root, 1, 0);
  6.         printMap(map);
  7.     }

  8.     void populateMap(TreeNode root, int level, int indent) {.1point3acres网
  9.         if (!map.containsKey(indent)) map.put(indent, new TreeMap<Integer, Integer>());
  10.         map.get(indent).put(level, root.val);
  11. . 1point 3acres 论坛
  12.         if (root.left != null) {
  13.             populateMap(root.left, level+1, indent-1);
  14.         }
  15.         if (root.right != null) {
  16.             populateMap(root.right, level+1, indent+1);
  17.         }
  18.     }

  19.     void printMap(TreeMap<Integer, TreeMap<Integer, Integer>> map) {. 一亩-三分-地,独家发布
  20.         for (Integer indent : map.keySet()) {
  21.             for (Integer level : map.get(indent).keySet()) {
  22.                 System.out.print(map.get(indent).get(level) + " ");
  23.             }. 留学申请论坛-一亩三分地
  24.             System.out.println();
  25.         }
  26.     }
复制代码

补充内容 (2014-11-24 08:46):
时间复杂度O(NloglogN),因为两层TreeMap所以两个log(大家觉得对么?),空间复杂度O(N)

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

austurela 发表于 2014-3-4 07:07:44 | 显示全部楼层
How is this?
  1. import java.util.ArrayList;

  2. public class PrintByColumn<T> {
  3.        
  4.         public void Print(TreeNode<T> root){-google 1point3acres
  5.                 ArrayList<ArrayList<T>> right = new ArrayList<ArrayList<T>>();
  6.                 ArrayList<ArrayList<T>> left = new ArrayList<ArrayList<T>>();
  7.                 printHelper(0, root, left, right);
  8.                 // Print result
  9.                 for(int i = left.size() - 1; i > 0; i--){
  10.                         System.out.println(left.get(i));
  11.                 }
  12.                 for(int i = 0; i < right.size(); i++){
  13.                         System.out.println(right.get(i));
  14.                 }
  15.         } 来源一亩.三分地论坛.
  16.        
  17.         private void printHelper(int index, TreeNode<T> root, ArrayList<ArrayList<T>> left, ArrayList<ArrayList<T>> right){
  18.                 // Base case
  19.                 if(root == null)        return;. 一亩-三分-地,独家发布
  20.                 // Normal case
  21.                 if(index >= 0){
  22.                         while(right.size() <= index){
  23.                                 right.add(new ArrayList<T>());. more info on 1point3acres
  24.                         }. 1point 3acres 论坛
  25.                         right.get(index).add(root.data);
  26.                 }
  27.                 else{
  28.                         while(left.size() <= -index){
  29.                                 left.add(new ArrayList<T>());-google 1point3acres
  30.                         }
  31.                         left.get(-index).add(root.data);
  32.                 }
  33.                 // Recurse
  34.                 printHelper(index - 1, root.left, left, right);
  35.                 printHelper(index + 1, root.right, left, right);
  36.         }
  37. }
复制代码
Testing:. more info on 1point3acres
  1. import java.util.*;

  2. class TreeNode<T>{
  3.         TreeNode<T> left;
  4.         TreeNode<T> right;
  5.         T data;
  6.        
    .本文原创自1point3acres论坛
  7.         TreeNode(T data){
  8.                 this.data = data;
  9.         }
  10. }
  11. . 1point3acres
  12. public class Test {
  13.         public static void main(String[] args){
  14.                 TreeNode<String> root = new TreeNode<String>("a");
  15.                 root.left = new TreeNode<String>("b");
  16.                 root.right = new TreeNode<String>("c");
  17.                
  18.                 root.left.left = new TreeNode<String>("d");
  19.                 root.left.right = new TreeNode<String>("g");
    . 一亩-三分-地,独家发布
  20.                 . more info on 1point3acres
  21.                 root.right.right = new TreeNode<String>("z");
  22.                 root.right.right.left = new TreeNode<String>("i");
  23.                 root.right.right.left.left = new TreeNode<String>("q");. 一亩-三分-地,独家发布
  24.                 root.right.right.left.left.left = new TreeNode<String>("x");
  25.                 root.right.right.left.left.left.left = new TreeNode<String>("x1");
  26.                 root.right.right.left.left.left.left.left = new TreeNode<String>("x2");
  27.                
  28.                 root.left.left.right = new TreeNode<String>("e");
  29.                
  30.                 PrintByColumn<String> test = new PrintByColumn<String>();
  31.                 test.Print(root);
  32.         }
  33. }
复制代码




补充内容 (2014-3-4 07:08):
. From 1point 3acres bbsOutput:
[x2]
[d, x1]
[b, e, x]
[a, g, q]
[c, i]
[z]
. 牛人云集,一亩三分地

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

lhn9021 发表于 2014-3-4 09:25:32 | 显示全部楼层
跟求bs的最大深度一样 用recursion求完深度以后加到深度的arraylist即可
来源一亩.三分地论坛.
补充内容 (2014-3-4 09:32):
貌似不对 还得想想

补充内容 (2014-3-4 09:45):
我的做法跟lz 一样 左面key减1右面key加1 然后用hashmap 保存 key linkedlist 和最大最小值 然后iterate
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

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. 1point3acres
用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 | 显示全部楼层

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

使用道具 举报

byrlhb 发表于 2014-10-29 01:23:35 | 显示全部楼层
austurela 发表于 2014-3-4 07:07
How is this?
. 留学申请论坛-一亩三分地Testing:

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

使用道具 举报

gsm107 发表于 2014-10-29 13:21:27 | 显示全部楼层
.1point3acres网
层主我问下,你是怎么判断节点在一条线上呢,就比如说root.left.right和root.right.left,因为按图上画的,root.left.right就跟root在一条垂直线上了,这时候root.right.left有节点的话,位置不就跟那个root.left.right重合了么?
回复 支持 反对

使用道具 举报

gsm107 发表于 2014-10-29 13:21:40 | 显示全部楼层

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

使用道具 举报

gsm107 发表于 2014-10-29 13:22:02 | 显示全部楼层

层主我问下,你是怎么判断节点在一条线上呢,就比如说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,往右加一。. 1point3acres
用两个变量记录min_vertical_index, max_vertical_index .
打印时从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-》 保证顺序,即越靠近根的在队列前面
然后map.
其中,根的vertical_index是0,往左减1,往右加一。-google 1point3acres
...

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

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-23 11:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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