San Jose各个房价 <1.5m 区域买房总结

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 3534|回复: 12
收起左侧

半小时前Facebook电面

[复制链接] |试试Instant~ |关注本帖
zwj1991 发表于 2016-6-4 05:24:37 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类General 硕士 全职@Facebook - 内推 - 技术电面  | Other | fresh grad应届毕业生

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

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

x


第一题:

     3
   /
1         . 1point3acres
   \
    2. From 1point 3acres bbs
一棵树,返回一个list的头结点:
1《——》2《——》3(一三相连)
意思是返回一个递增list,1的right是2,left是3, 2的left是1,right是3,3的left是2,right是 1.
我用inorder获得递增序列然后设置left与right的node。返回1这个结点。. 1point3acres
follow up如何不先获得序列,直接在traverse的时候获得结果。follow up没回答出来。
.本文原创自1point3acres论坛
第二题. From 1point 3acres bbs
         A
       /  \
     B    C     
    /     / \
   D    E  F

打印所有path
ABD
ACE
ACF

dfs可以,第一次用了一个list获得所有path输出,后来修改成直接输出。
follow up时间,空间复杂度。。没回答好。。。
准备有点不充分,求人品~~~~~~~~~~~~~~~~

评分

2

查看全部评分

blackrose 发表于 2016-6-4 05:39:24 | 显示全部楼层
第一题是BST 转成double linked list吧。。。。。
回复 支持 反对

使用道具 举报

yfang0663 发表于 2016-6-4 23:54:07 | 显示全部楼层
第二题time O(2^h) space O(h) 是吗
回复 支持 反对

使用道具 举报

laonawuli 发表于 2016-6-5 00:06:14 | 显示全部楼层
yfang0663 发表于 2016-6-4 07:54
第二题time O(2^h) space O(h) 是吗

我觉得time就是 O(n),n是node的个数;space我同意你的。
回复 支持 反对

使用道具 举报

yfang0663 发表于 2016-6-5 00:14:52 | 显示全部楼层
laonawuli 发表于 2016-6-5 00:06
我觉得time就是 O(n),n是node的个数;space我同意你的。

dfs要back tracking 非leaf node肯定会被push到不同的path中 怎么会是O(n)?
回复 支持 反对

使用道具 举报

yfang0663 发表于 2016-6-5 00:20:10 | 显示全部楼层
第一题是类似这样写吗
  1.                
  2. DoubleLinkedListNode* FlatBST(TreeNode* root) {
  3.     if(!root)
  4.         return nullptr;. 围观我们@1point 3 acres
  5.     DoubleLinkedListNode dummy(0);. 留学申请论坛-一亩三分地
  6.     stack<TreeNode*> s;
  7.     s.push(root);
  8.     DoubleLinkedListNode *prev = &dummy;
    .留学论坛-一亩-三分地
  9.     TreeNode *cur = nullptr;
  10.     while(!s.empty() || cur) {
  11.         if(cur) {
  12.             s.push(cur);
  13.             cur = cur->left;
  14.         }
  15.         else {
  16.             TreeNode *top = s.top();
  17.             s.pop();
  18.             DoubleLinkedListNode *next = new DoubleLinkedListNode(top->val);
  19.             next->prev = prev;
  20.             prev->next = next;. From 1point 3acres bbs
  21.             prev = next;
  22.             cur = top->right;
  23.         }. 围观我们@1point 3 acres
  24.     }
  25.     prev->next = dummy.next;
  26.     return dummy.next;
  27. }
复制代码
回复 支持 反对

使用道具 举报

dong882205 发表于 2016-6-5 00:57:30 | 显示全部楼层
第一题用递归好像能做? 写了一下, 可直接编译运行,望指教!

using namespace std;. from: 1point3acres
. more info on 1point3acres
struct TreeNode {
         int val;
         TreeNode *left;
         TreeNode *right;
         TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     };. 1point3acres

void gen(TreeNode* root, TreeNode* &pre)
{
    if(!root) return;
    if(root->left) gen(root->left, pre);
    pre->right=root;. 一亩-三分-地,独家发布
    root->left=pre;
    pre=pre->right;
    if(root->right) gen(root->right,pre);
}
. 牛人云集,一亩三分地
int main(). 围观我们@1point 3 acres
{. 留学申请论坛-一亩三分地
    TreeNode* dummy=new TreeNode(0);. 1point 3acres 论坛
    TreeNode* pre=dummy;
    TreeNode* a1=new TreeNode(3);
    a1->left =new TreeNode(1);. 1point3acres
    a1->left->right =new TreeNode(2);.1point3acres网
    gen(a1,pre);
    dummy->left=pre->right;. visit 1point3acres for more.
    dummy->right->left=pre;
    return 0;
}
回复 支持 反对

使用道具 举报

 楼主| zwj1991 发表于 2016-6-5 01:07:02 | 显示全部楼层
第一题中序遍历的时候顺便把结点的结构改了就好,面完才想出来的,这样Space就是O(1)
private TreeNode listRootNode = null;
private TreeNode tmp = null;
        public TreeNode convert(TreeNode root) {. Waral 博客有更多文章,
        inOrderList(root);. 留学申请论坛-一亩三分地
        TreeNode tail = listRootNode;
        while(tail.right != null). more info on 1point3acres
                tail = tail.right;
. 围观我们@1point 3 acres        tail.right = listRootNode;.本文原创自1point3acres论坛
        listRootNode.left = tail;
        return listRootNode;
        }. From 1point 3acres bbs
       
        private void inOrderList(TreeNode root){
                if(root == null)
                        return;
                inOrderList(root.left);
                if(listRootNode == null)
                        listRootNode = root;.留学论坛-一亩-三分地
                if(tmp == null)
                        tmp = root;
                if(tmp != root){
                        tmp.right = root;
                        root.left = tmp;
                        tmp = tmp.right;. 牛人云集,一亩三分地
                }
                inOrderList(root.right);               
        }
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

dong882205 发表于 2016-6-5 01:07:26 | 显示全部楼层
写了个复杂点的树结构, 看来是没问题了, 输出是-1,0,1,2,3,4,5,6,7
int main()
{
    TreeNode* dummy=new TreeNode(0);
    TreeNode* pre=dummy;
   
    TreeNode* a1=new TreeNode(3);
    a1->left =new TreeNode(1);. 留学申请论坛-一亩三分地
    a1->left->right =new TreeNode(2);
    a1->right =new TreeNode(5);
    a1->right->left =new TreeNode(4);
    a1->right->right =new TreeNode(7);. 1point 3acres 论坛
    a1->right->right->left =new TreeNode(6);
    a1->left->left =new TreeNode(0);
    a1->left->left->left =new TreeNode(-1);. visit 1point3acres for more.
   
    gen(a1,pre);
    dummy->left=pre->right; 来源一亩.三分地论坛.
    dummy->right->left=pre;
    . 1point3acres
    TreeNode* head=dummy->right;.1point3acres网
    while(head)
    {. visit 1point3acres for more.
        cout<<head->val<<endl;
        head=head->right;
    }
    return 0;
}
回复 支持 反对

使用道具 举报

 楼主| zwj1991 发表于 2016-6-5 01:10:41 | 显示全部楼层
yfang0663 发表于 2016-6-5 00:14
dfs要back tracking 非leaf node肯定会被push到不同的path中 怎么会是O(n)?

第二题时间复杂度是O(n),空间复杂度也是O(n)....我不太确定空间复杂度,听面试官说好像是O(n).
其实不需要记录当前的path,只要dfs到叶子结点的时候就输出path就好了,但是递归占用stack,所以还是有空间复杂度。
private void dfs(TreeNode root, String str) ----方法大概是这样
回复 支持 反对

使用道具 举报

dong882205 发表于 2016-6-5 01:18:36 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!
. From 1point 3acres bbs
想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 反对

使用道具 举报

dong882205 发表于 2016-6-5 01:24:09 | 显示全部楼层
刚发的不见了- -! 变成了默认文字...
第二题好像不难
空间的话, 求指点: 最多同时会有深度H的recurrence在堆栈中, 每个最多存了O(N)长的string, 所以是O(N^2)??

void pp(TreeNode* root, string s)
{. visit 1point3acres for more.
    if(!root) return;
    s+=to_string(root->val);
    if(!root->left && !root->right)
        cout<<s<<endl;
    pp(root->left,s);
    pp(root->right,s);
}

int main()
{. 牛人云集,一亩三分地
    TreeNode* a1=new TreeNode(3);
    a1->left =new TreeNode(1);
    a1->left->right =new TreeNode(2);
    a1->right =new TreeNode(5);
    a1->right->left =new TreeNode(4);. 围观我们@1point 3 acres
    a1->right->right =new TreeNode(7);
    a1->right->right->left =new TreeNode(6);
    a1->left->left =new TreeNode(0);
    a1->left->left->left =new TreeNode(-1);
   
    pp(a1,"");

    return 0;
}
回复 支持 反对

使用道具 举报

yfang0663 发表于 2016-6-5 02:50:57 | 显示全部楼层
dong882205 发表于 2016-6-5 01:24
刚发的不见了- -! 变成了默认文字...
第二题好像不难
空间的话, 求指点: 最多同时会有深度H的recurrence ...

pass string by reference就好了
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-26 18:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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