一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 4781|回复: 30
收起左侧

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

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

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

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

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

x
已跪,45分钟面了道很奇葩的问题,面试是个三哥,有气无力地听着,最后也装模作样回答一些问题.. 跪了
问题:. From 1point 3acres bbs
Print arbitrary binary tree by vertical levels / columns from left to right. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷


example tree

      a
     / \. from: 1point3acres.com/bbs
    b   c
   / \   \
  d   g   z. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
   \     /. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    e   i
       /
      q
     /. 1point 3acres 璁哄潧
    x
   /. 鍥磋鎴戜滑@1point 3 acres
  x1. 1point 3acres 璁哄潧
/
x2


sample output. from: 1point3acres.com/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)
{
    if(!root)
        return;
    h[key].push(root);
    store(root->left, h, key--);-google 1point3acres
    store(root->right, h, key++);
}. 1point3acres.com/bbs
然后print出来,最后有点问题,因为那个level的index如果root是0的话,左边的就都是负数了,不知道怎么存进相应的vector里面去,就gg了


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

补充内容 (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. struct tree{
  8.     string key;
  9.     tree *left, *right;
  10.     tree(string mkey):key(mkey), left(NULL), right(NULL){}. from: 1point3acres.com/bbs
  11. };

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

  13. map<int, vector<tree*> > dict;

  14. void build(tree *root){. more info on 1point3acres.com
  15.     if(root == NULL){
  16.         return;
  17.     }
  18.     queue<pti> que;
  19.     que.push(pti(root, 0));
  20.     while(!que.empty()){
  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.         }
  30.     }
  31. }. Waral 鍗氬鏈夋洿澶氭枃绔,

  32. void solve(tree *root){
  33.     if(root == NULL){
  34.         return;
  35.     }
  36.     build(root);. 1point 3acres 璁哄潧
  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.         }.1point3acres缃
  44.         cout<<endl;
  45.         ++it;
  46.     }
  47. }

  48. int main(){
  49.     tree *t1 = new tree("a");
  50.     tree *t2 = new tree("b");
  51.     tree *t3 = new tree("c");
  52.     tree *t4 = new tree("d");
  53.     tree *t5 = new tree("e");
  54.     tree *t6 = new tree("g");
  55.     tree *t7 = new tree("z");
  56.     tree *t8 = new tree("i");
  57.     tree *t9 = new tree("q");
  58.     tree *t10 = new tree("x");
  59.     tree *t11 = new tree("x1");
  60.     tree *t12 = new tree("x2");
  61.     t1->left = t2;
  62.     t1->right = t3;
  63.     t2->left = t4;. Waral 鍗氬鏈夋洿澶氭枃绔,
  64.     t2->right = t6;
  65.     t4->right = t5;
  66.     t3->right = t7;
  67.     t7->left = t8;
  68.     t8->left = t9;
  69.     t9->left = t10;
  70.     t10->left = t11;
  71.     t11->left = t12;
  72.     solve(t1);
  73. }
  74. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  75. /*
  76.       a 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  77.      / \
  78.     b   c. From 1point 3acres bbs
  79.    / \   \
  80.   d   g   z
  81.    \     /. 1point3acres.com/bbs
  82.     e   i
  83.        /
  84.       q
  85.      /
  86.     x
  87.    /
  88.   x1. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  89. /
  90. x2
  91. */

复制代码
回复 支持 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!

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. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  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.     void populateMap(TreeNode root, int level, int indent) {. visit 1point3acres.com for more.
  10.         if (!map.containsKey(indent)) map.put(indent, new TreeMap<Integer, Integer>());
  11.         map.get(indent).put(level, root.val);

  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. . From 1point 3acres bbs
  20.     void printMap(TreeMap<Integer, TreeMap<Integer, Integer>> map) {
  21.         for (Integer indent : map.keySet()) {
  22.             for (Integer level : map.get(indent).keySet()) {
  23.                 System.out.print(map.get(indent).get(level) + " ");. From 1point 3acres bbs
  24.             }
  25.             System.out.println();
  26.         }. 1point3acres.com/bbs
  27.     }
复制代码
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
补充内容 (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;-google 1point3acres

  2. public class PrintByColumn<T> {
  3.        
  4.         public void Print(TreeNode<T> root){
  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++){.1point3acres缃
  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){
    . 1point3acres.com/bbs
  22.                         while(right.size() <= index){
  23.                                 right.add(new ArrayList<T>());
  24.                         }
  25.                         right.get(index).add(root.data);
  26.                 }
  27.                 else{ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  28.                         while(left.size() <= -index){
  29.                                 left.add(new ArrayList<T>());
  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:
  1. import java.util.*;
  2. . visit 1point3acres.com for more.
  3. class TreeNode<T>{
  4.         TreeNode<T> left;
    .1point3acres缃
  5.         TreeNode<T> right;
  6.         T data;. visit 1point3acres.com for more.
  7.         .鏈枃鍘熷垱鑷1point3acres璁哄潧
  8.         TreeNode(T data){
  9.                 this.data = data;
  10.         }
  11. }

  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");.1point3acres缃
  16.                 root.right = new TreeNode<String>("c");
  17.                
  18.                 root.left.left = new TreeNode<String>("d");.1point3acres缃
  19.                 root.left.right = new TreeNode<String>("g");. Waral 鍗氬鏈夋洿澶氭枃绔,
  20.                
  21.                 root.right.right = new TreeNode<String>("z");. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  22.                 root.right.right.left = new TreeNode<String>("i");.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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");.1point3acres缃
  26.                 root.right.right.left.left.left.left.left = new TreeNode<String>("x2");
  27.                
  28.                 root.left.left.right = new TreeNode<String>("e");
  29.                 . From 1point 3acres bbs
  30.                 PrintByColumn<String> test = new PrintByColumn<String>();
  31.                 test.Print(root);
  32.         }
  33. }
复制代码




补充内容 (2014-3-4 07:08):
Output:
[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即可-google 1point3acres
. Waral 鍗氬鏈夋洿澶氭枃绔,
补充内容 (2014-3-4 09:32):
貌似不对 还得想想

补充内容 (2014-3-4 09:45):
我的做法跟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>> , 存一下最大最小列数
=========
key   value
0      a -> g -> q
-1      b -> e -> x. 鍥磋鎴戜滑@1point 3 acres
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 | 显示全部楼层

好方法,不过我感觉插入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 | 显示全部楼层
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 | 显示全部楼层

层主我问下,你是怎么判断节点在一条线上呢,就比如说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,往右加一。. From 1point 3acres bbs
用两个变量记录min_vertical_index, max_vertical_index .
打印时从map里,从min_vertical_index, 到 max_vertical_index . 1point3acres.com/bbs
回复 支持 反对

使用道具 举报

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,往右加一。
...

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 22:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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