📣 VIP通行证夏日特惠 限时立减$68
回复: 36
跳转到指定楼层
上一主题 下一主题
收起左侧

Facebook第一轮电面

全局:

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

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
很传统:先介绍简历 + 做题 + 问问题。
题目1:求二叉树所有从根开始到叶子的所有路径和。
题目2:不能用递归,完成以上题目。
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
终”。。。写总收到感觉很损人品啊。。。。。。哪有总。。。求签证过了吧。。

评分

参与人数 1大米 +5 收起 理由
zach + 5

查看全部评分


上一篇:高盛电面
下一篇:amazon 电面
推荐
yanguango 2015-5-1 03:54:15 | 只看该作者
全局:
Recursive的话就是典型的 DFS,中间结果的 sum 都当做一个参数传到下一层递归。
如果要 Iterative 的话就是把 DFS 写成 Non-recursive的,也就是用 stack 实现。这时需要保存中间结果的 sum,用另一个 stack 可以解决,楼上所说的用一个 int 保存中间结果,我没有想出来怎么实现,因为在遇到叶子节点的时候,不知道要在 sum 里减掉多少回退到上一层,可能回退的层数不是1。

粗略写的代码如下:
#include <iostream>
#include <stack>
using namespace std;

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int v) : val(v), left(NULL), right(NULL) {}
};

void pathSumRecHelper(TreeNode *root, int sum, int &res) {
  if (root->left == NULL && root->right == NULL) {
    sum += root->val;
    res += sum;
    return;
  }

  if (root->left != NULL) pathSumRecHelper(root->left, sum + root->val, res);
  if (root->right != NULL) pathSumRecHelper(root->right, sum + root->val, res);
}

int pathSumRec(TreeNode *root) {
  if (root == NULL) return 0;
  int res = 0;
  pathSumRecHelper(root, 0, res);
  return res;
}

int pathSumItr(TreeNode *root) {
  if (root == NULL) return 0;
  stack<TreeNode *> node_stack;
  stack<int> sum_stack;
  int res = 0;

  node_stack.push(root);
  sum_stack.push(root->val);

  while (!node_stack.empty()) {
    TreeNode *node = node_stack.top();
    int sum = sum_stack.top();
    node_stack.pop();
    sum_stack.pop();
    if (node->left == NULL && node->right == NULL) {
      res += sum;
    }

    if (node->left != NULL) {
      node_stack.push(node->left);
      sum_stack.push(sum + node->left->val);
    }

    if (node->right != NULL) {
      node_stack.push(node->right);
      sum_stack.push(sum + node->right->val);
    }
  }

  return res;
}

int main(int argc, char const *argv[]) {
  TreeNode *root = new TreeNode(1);
  TreeNode *n1 = new TreeNode(2);
  TreeNode *n2 = new TreeNode(5);
  TreeNode *n3 = new TreeNode(3);
  TreeNode *n4 = new TreeNode(4);

  root->left = n1;
  root->right = n2;
  n1->left = n3;
  n1->right = n4;

  int sum = pathSumItr(root);
  cout << sum << endl;
}
回复

使用道具 举报

推荐
sanguine 2015-3-16 05:58:21 | 只看该作者
全局:
为什么我觉得non-recursive的方法更好想。。。我感觉我被绕进去了,我写的recursive方法是先得到所有的path在加起来==特别冗余
求指导如何简单的就直接得到sum……
  1. public static List<List<Integer>> getAllPathSum(TreeNode root) {
  2.         List<List<Integer>> rst = new ArrayList<List<Integer>>();

  3.         helper(rst, new ArrayList<Integer>(), root);
  4.         return rst;
  5.     }

  6.     public static void helper(List<List<Integer>> rst, ArrayList<Integer> list,
  7.                        TreeNode root) {
  8.         if (root == null) {
  9.             return;
  10.         }
  11.         list.add(root.val);
  12.         if (root.left == null && root.right == null) {
  13.             rst.add(new ArrayList<Integer>(list));
  14.         }
  15.         helper(rst, list, root.left);
  16.         helper(rst, list, root.right);
  17.         list.remove(list.size() - 1);
  18.     }
复制代码
回复

使用道具 举报

推荐
 楼主| pandafolk 2015-3-23 01:50:11 | 只看该作者
全局:
sanguine 发表于 2015-3-15 16:58
为什么我觉得non-recursive的方法更好想。。。我感觉我被绕进去了,我写的recursive方法是先得到所有的path ...

额,你这么写的话确实。。
可以这样呀~
  1. public class Solution {
  2.     public int sumNumbers(TreeNode root) {
  3.         return dfs(root, 0);
  4.     }
  5.    
  6.     private int dfs(TreeNode root, int prev) {
  7.         if (root == null) {
  8.             return 0;
  9.         }
  10.         
  11.         int sum = prev + root.val;
  12.         if (root.left == null && root.right == null) {
  13.             return sum;
  14.         }
  15.         
  16.         return dfs(root.right, sum) + dfs(root.left, sum);
  17.     }
  18. }
复制代码
回复

使用道具 举报

🔗
 楼主| pandafolk 2015-3-12 04:26:12 | 只看该作者
全局:
有不明白的大家请猛烈问我啊~~~
另外隔了四天才收到通过。。。可能是自己太水了
回复

使用道具 举报

🔗
lsycody 2015-3-12 05:06:57 | 只看该作者
全局:
楼主通过了是指要去onsite了吗?恭喜啊!

请问follow up的第二问怎么实现呢?
回复

使用道具 举报

🔗
 楼主| pandafolk 2015-3-12 05:21:40 | 只看该作者
全局:
lsycody 发表于 2015-3-11 16:06
楼主通过了是指要去onsite了吗?恭喜啊!

请问follow up的第二问怎么实现呢?

用两个stack实现呀~~
一个存储结点,另一存储和
比如
       1
    2     5
3     4
第一次,root入stack
node【1,
sum【1,
然后pop栈顶元素,push其儿子,我这里习惯先push右边的,这样输出就是先输出左边的~:
node【5,2
sum【6,3
然后取出结点2,和它的sum,再push儿子
node【5,4,3
sum【6,7,6
然后到3了,发现是叶子,那么pop出来直接输出:6
node【5,4
sum【6,7
然后到4了。发现又是叶子,那么再次pop出来直接输出咯:7
node【5
sum【6
终于到5了,还是叶子,那么就输出咯:6
完毕~~~~

评分

参与人数 1大米 +3 收起 理由
peace + 3 话说这解释真是太详尽了

查看全部评分

回复

使用道具 举报

🔗
 楼主| pandafolk 2015-3-12 05:24:21 | 只看该作者
全局:
最后输出一个int = 6 + 7 + 6 = 19~~~~
回复

使用道具 举报

🔗
lsycody 2015-3-12 05:29:57 | 只看该作者
全局:
恩~~祝你onsite顺利!
回复

使用道具 举报

🔗
anastasia22 2015-3-12 05:53:49 | 只看该作者
全局:
不知道题目是不是我理解错的 leetcode上有个类似题目 也是求和
回复

使用道具 举报

🔗
anastasia22 2015-3-12 05:54:31 | 只看该作者
全局:
比如root是1 两个儿子是2和3 那么就输出12+13=25
回复

使用道具 举报

🔗
 楼主| pandafolk 2015-3-12 06:15:13 | 只看该作者
全局:
ryuichist 发表于 2015-3-11 16:54
比如root是1 两个儿子是2和3 那么就输出12+13=25

不一定出原题啊。。。另外是哪个题目啊 求链接~~
回复

使用道具 举报

🔗
sonicgu 2015-3-12 08:46:12 | 只看该作者
全局:
第二问用后续或者level order 都可以解
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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