一亩三分地论坛

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

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

FB面试被碾压,求思路

[复制链接] |试试Instant~ |关注本帖
kevinkaizhou 发表于 2015-10-21 11:45:45 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 实习@Facebook - 校园招聘会 - 校园招聘会 |Otherfresh grad应届毕业生

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

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

x
上来先寒暄了下,毕竟也是前两天reception见了面的。然后我看到我简历上最近的那段工作经历被划了个红圈。果然,他从这段经历开始问,第一个问题是,问我不喜欢angular哪一点,然后又问了个问题我没很听清,然后我只能找了几个关键字扯了扯,感觉他表情很异样,感觉是我答不对题,不过他还是说OKOKlet’s move on solving problems.
第一个题上来就懵了,是一个binary tree,要求用BFS不能用DFS来打印从head到所有leaf的路。我想不出来好的办法,就用了暴力破解了。存一个listlist,用一个queue遍历,不断往里面插入,实现得也有问题被它找了出来。我居然在一个list上重复操作了,现在想想犯这个错误真是弱智,当时真是懵了。在写代码的时候一直在想有没有更好的解决结果代码也没写好。
第二题算是做出来了,有一个字符串sentense比如bedbebinary,还有个哈希表words存了所有可能的字符,比如{bed, be,binary ….} 现在要判断这个字符串能不能拆分成word的集合。我用了递归的方法,几分钟写了几行就出来了,总算松了口气。结果他发现了终结条件的bug,我看了好长时间没发现,心里越来越慌,后来他告诉我了哪里错了。(这个是leetcode上的word break题,可以用PD做,可是还没有刷到。。)
哎,感觉肯定过不了,就当涨涨姿势,积累经验。一是口语听力太渣,表述不清。二是刷题太少,都是当场想方法肯定写不好代码啊。
归根到底,多刷题!

另求第一题的思路。。。



补充内容 (2015-10-21 11:49):
PD --> DP 打快了
nothingtrouble 发表于 2015-10-24 01:53:38 | 显示全部楼层
类似于union find。用hashmap保存parent


public List<String> binaryTreePaths(TreeNode root) {
        List<String> ret = new ArrayList<String>();
        if(null==root) return ret;
        Queue<TreeNode> q = new LinkedList<TreeNode>();.鏈枃鍘熷垱鑷1point3acres璁哄潧
        HashMap<TreeNode, TreeNode> parent = new HashMap<TreeNode, TreeNode>();
        q.add(root);

        while(!q.isEmpty()){-google 1point3acres
                TreeNode n = q.poll();
                if(null==n.left && null==n.right){
                        ret.add(printPath(parent, n));
                } else {
                        if(null!=n.left){. 1point3acres.com/bbs
                                parent.put(n.left, n);.鏈枃鍘熷垱鑷1point3acres璁哄潧
                                q.add(n.left);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                        }
                        if(null!=n.right) {
                                parent.put(n.right, n);
                                q.add(n.right);
                        }
                }
        }. 1point 3acres 璁哄潧
        return ret;
}

public String printPath(HashMap<TreeNode, TreeNode> parent, TreeNode node){
        String ret = Integer.toString(node.val);
        while(parent.containsKey(node)){
                node = parent.get(node);
                ret = Integer.toString(node.val) + "->" + ret;
        }
        return ret;.鐣欏璁哄潧-涓浜-涓夊垎鍦
}
回复 支持 1 反对 0

使用道具 举报

神罗天征 发表于 2015-10-21 12:14:51 | 显示全部楼层
请问你的面试官是个什么样的人呀?
回复 支持 反对

使用道具 举报

clfhaha1234 发表于 2015-10-21 12:20:01 | 显示全部楼层
第一题lz的做法应该足够通过了,一定要优化的话每个queue里的结点只需要记录它的父结点,然后每个叶子遍历回去输出路径就行。
回复 支持 反对

使用道具 举报

hpplayer 发表于 2015-10-21 12:24:46 | 显示全部楼层
第一题BFS那个,自己新建个NODE, 里面记录PARENT NODE怎么样? 然后用HASH表存对应关系,这样每一个叶子节点都可以用PARENT NODE返回到HEAD的路径
回复 支持 反对

使用道具 举报

神罗天征 发表于 2015-10-21 12:27:12 | 显示全部楼层
能告诉我名字吗
回复 支持 反对

使用道具 举报

 楼主| kevinkaizhou 发表于 2015-10-21 14:23:17 | 显示全部楼层

Peter……
回复 支持 反对

使用道具 举报

jy_121 发表于 2015-10-21 15:19:45 | 显示全部楼层
第一题有什么要求吗?觉得用一个hash保存自身的父节点,遍历到根节点时反向查找输出。
回复 支持 反对

使用道具 举报

majiamajia 发表于 2015-10-21 15:37:44 | 显示全部楼层
对BFS那个,新开个NODE,存目前的TREENODE和他的PARENT,然后走到底了之后往上traceback就好。BFS时候QUEUE里面存的是这个新开的NODE。
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-10-21 16:33:14 | 显示全部楼层
第一题, morris algorithm. 您是面金看的少

补充内容 (2015-10-23 13:47):. 鍥磋鎴戜滑@1point 3 acres
看错题了。。。
回复 支持 反对

使用道具 举报

xuchen1m3fd 发表于 2015-10-23 12:43:14 | 显示全部楼层
第一题我的思路是,其实还是bfs只不过Q里面存的东西变成了path,每次只要看path的最后一个元素,如果有子节点,就加进path然后重新enqueue,如果没有,就打印。. more info on 1point3acres.com
public void BFSPrintPaths(TreeNode root) {
  if (root == null) return;
  Queue<List<TreeNode>> queue = new LinkedList<>();
  List<TreeNode> rootPath = new LinkedList<>();
  rootPath.add(root);
  path.add(rootPath);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  while (!queue.isEmpty()) {
    int size = queue.size();
    for (int i = 0;i < size; i++) {. From 1point 3acres bbs
      List<TreeNode> list = queue.poll();.鐣欏璁哄潧-涓浜-涓夊垎鍦
      TreeNode lastNode = list.get(list.size() - 1);. From 1point 3acres bbs
      if (lastNode.left == null && lastNode.right == null) {
        printPath(list);
      }
      if (lastNode.left != null) {
        List<TreeNode> leftPath = new LinkedList<>();
        leftPath.addAll(list);
        leftPath.add(lastNode.left);
        queue.offer(leftPath);
      }
      if (lastNode.right != null) {
        List<TreeNode> rightPath = new LinkedList<>();
        rightPath.addAll(list);
        rightPath.add(lastNode.right);. Waral 鍗氬鏈夋洿澶氭枃绔,
        queue.offer(rightPath);. Waral 鍗氬鏈夋洿澶氭枃绔,
      }
    } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  }
}
.鏈枃鍘熷垱鑷1point3acres璁哄潧
public void printPath(List<TreeNode> path) {
  for (TreeNode n: path) {
    System.out.print(n.val + " ");
  }
  System.out.println();
}
回复 支持 反对

使用道具 举报

soysenioritasue 发表于 2015-10-23 16:00:25 | 显示全部楼层
第一题要用stack,第二题递归leetcode上会超时,只能DP

补充内容 (2015-10-23 16:02):
我也看错第一题了,第一题不好做啊
回复 支持 反对

使用道具 举报

xiaoying10101 发表于 2015-10-23 18:34:24 | 显示全部楼层
楼主怎么拿到面试的,今年new grad不是都招满了吗?
回复 支持 反对

使用道具 举报

comicrudy 发表于 2015-10-23 21:04:09 | 显示全部楼层
第一题用queue存vector,逐层遍历的时候直接往里加,没有child了就存进return不行么?
回复 支持 反对

使用道具 举报

akluffy 发表于 2015-10-26 10:30:41 | 显示全部楼层
  1.     vector<string> binaryTreePaths(TreeNode* root) {
  2.         vector<string> result;
  3.         if(!root) return result;. more info on 1point3acres.com
  4.         queue<vector<TreeNode*>> Q;
  5.         Q.push(vector<TreeNode*>(1, root));
  6.         while(!Q.empty()) {
  7.             vector<TreeNode *> path = Q.front();. more info on 1point3acres.com
  8.             Q.pop();
  9.             TreeNode *lastNode = path.back();
  10.             if(lastNode->left || lastNode->right) {
  11.                 if(lastNode->left) {. 1point 3acres 璁哄潧
  12.                     vector<TreeNode*> copyPath(path);. from: 1point3acres.com/bbs
  13.                     copyPath.push_back(lastNode->left);
  14.                     Q.push(copyPath);
  15.                 }
  16.                 if(lastNode->right) {
  17.                     vector<TreeNode*> copyPath(path);
  18.                     copyPath.push_back(lastNode->right);
  19.                     Q.push(copyPath);
  20.                 }-google 1point3acres
  21.             } else {
  22.                 string sub;
  23.                 for(auto p : path) {
  24.                     sub = sub + to_string(p->val) + "->";
  25.                 }
  26.                 sub.resize(sub.size() - 2);
  27.                 result.push_back(sub);
  28.             }
  29.         }
  30.         
  31.         return result;
  32.     }
复制代码
回复 支持 反对

使用道具 举报

akluffy 发表于 2015-10-26 10:38:29 | 显示全部楼层
  1.     vector<string> binaryTreePaths(TreeNode* root) {
  2.         vector<string> result;
  3.         if(!root) return result;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  4.         queue<vector<TreeNode*>> Q;
  5.         Q.push(vector<TreeNode*>(1, root));
  6.         while(!Q.empty()) {
  7.             vector<TreeNode *> path = Q.front();
  8.             Q.pop();
  9.             TreeNode *lastNode = path.back();-google 1point3acres
  10.             if(lastNode->left || lastNode->right) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  11.                 if(lastNode->left) {
  12.                     vector<TreeNode*> copyPath(path);
  13.                     copyPath.push_back(lastNode->left);. more info on 1point3acres.com
  14.                     Q.push(copyPath);
  15.                 }
  16.                 if(lastNode->right) {
  17.                     vector<TreeNode*> copyPath(path);.1point3acres缃
  18.                     copyPath.push_back(lastNode->right);
  19.                     Q.push(copyPath);
  20.                 }
  21.             } else {
  22.                 string sub;
  23.                 for(auto p : path) {
  24.                     sub = sub + to_string(p->val) + "->";
  25.                 }
  26.                 sub.resize(sub.size() - 2);
  27.                 result.push_back(sub);
  28.             }
  29.         }
  30.         
  31.         return result;. visit 1point3acres.com for more.
  32.     }
复制代码
回复 支持 反对

使用道具 举报

joseph5wu 发表于 2016-2-6 15:35:52 | 显示全部楼层
  1. class Solution {
  2.     public List<String> getPath(TreeNode root) {
  3.         List<String> results = new ArrayList<>();
  4.         if(root == null) {
  5.             return results;
  6.         }
  7.          鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  8.         Queue<TreeNode> queue = new LinkedList<>();
  9.         Queue<StringBuilder> sbQueue = new LinkedList<>();. 1point3acres.com/bbs
  10.         queue.add(root);. 1point3acres.com/bbs
  11.         StringBuilder sb = new StringBuilder();
  12.         sb.append(root.val);
  13.         sbQueue.add(sb);
  14.         TreeNode node;
  15.         StringBuilder temp;. Waral 鍗氬鏈夋洿澶氭枃绔,
  16.         while(!queue.isEmpty()) {
  17.             int size = queue.size();
  18.             for(int i = 0; i < size; i++) {
  19.                 node = queue.poll();
  20.                 temp = sbQueue.poll();
  21.                 if(node.left == null && node.right == null) {
  22.                     results.add(temp.toString());
  23.                 }. 鍥磋鎴戜滑@1point 3 acres
  24.                
  25.                 if(node.left != null) {.1point3acres缃
  26.                     queue.add(node.left);
  27.                     StringBuilder newSb = new StringBuilder(temp);. more info on 1point3acres.com
  28.                     newSb.append("->").append(node.left.val);
  29.                     sbQueue.add(newSb);. 鍥磋鎴戜滑@1point 3 acres
  30.                 }
  31.                
  32.                 if(node.right != null) {
  33.                     queue.add(node.right);
  34.                     StringBuilder newSb = new StringBuilder(temp);
  35.                     newSb.append("->").append(node.right.val);
  36.                     sbQueue.add(newSb);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  37.                 }
  38.             }
  39.         }
  40.         
  41.         return results;
  42.     }
  43.    
  44.     public static void main(String[] args) {
  45.         TreeNode root = new TreeNode(1);
  46.         TreeNode node2 = new TreeNode(2);
  47.         TreeNode node3 = new TreeNode(3);. visit 1point3acres.com for more.
  48.         TreeNode node4 = new TreeNode(4);
  49.         TreeNode node5 = new TreeNode(5);
  50.         root.left = node2;
  51.         root.right = node3;
  52.         node3.left = node4;
  53.         node3.right = node5;
  54.         
  55.         Solution sol = new Solution();
  56.         List<String> results = sol.getPath(root);
  57.         for(String result : results) {
  58.             System.out.println(result);
  59.         }
  60.     }
  61.    
  62. }. 鍥磋鎴戜滑@1point 3 acres

  63. class TreeNode {
  64.     int val;
  65.     TreeNode left;
  66.     TreeNode right;
  67.    
  68.     TreeNode(int val) {
  69.         this.val = val;
  70.     }
  71. }
复制代码
回复 支持 反对

使用道具 举报

xiaohui5319 发表于 2016-3-30 04:35:58 | 显示全部楼层
class Solution { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        // Write your code here
        vector<string> res;
        if (root == NULL) return res;.鐣欏璁哄潧-涓浜-涓夊垎鍦
        queue<pair<string, TreeNode*>> Q;
        Q.push({to_string(root->val), root});

        while (!Q.empty()) {
            string curStr = Q.front().first;
            TreeNode* curNode = Q.front().second;
            Q.pop();

            if (curNode->left == NULL && curNode->right == NULL) {
                res.push_back(curStr);
            } else {.1point3acres缃
                if (curNode->left != NULL)
                    Q.push({curStr + "->" + to_string(curNode->left->val), curNode->left});
. visit 1point3acres.com for more.                if (curNode->right != NULL). 鍥磋鎴戜滑@1point 3 acres
                    Q.push({curStr + "->" + to_string(curNode->right->val), curNode->right});
            }
        }
. more info on 1point3acres.com
        return res;
    }
};
回复 支持 反对

使用道具 举报

sealove999 发表于 2016-4-4 04:21:22 | 显示全部楼层
第一题看题目要返回什么,。
. 1point 3acres 璁哄潧
补充内容 (2016-4-4 04:21):
看题目的意思是打印,不要返回,所以用parent hashmap是比较省的。. Waral 鍗氬鏈夋洿澶氭枃绔,
如果是要返回所有path的list,那么就可以直接在bfs的queue里面放以往的path

补充内容 (2016-4-4 04:22):
第二题也是看要返回什么,. 1point 3acres 璁哄潧
如果是要返回boolean,那么dp
如果是要返回list list word,那么dfs
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 19:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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