一亩三分地论坛

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

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

半小时前Facebook电面

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

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

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

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

x


第一题:

     3
   /
1         
   \ . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    2
一棵树,返回一个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这个结点。
follow up如何不先获得序列,直接在traverse的时候获得结果。follow up没回答出来。. Waral 鍗氬鏈夋洿澶氭枃绔,

第二题
         A.1point3acres缃
       /  \ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
     B    C     
    /     / \. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
   D    E  F. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

打印所有path
ABD
ACE
ACF
. 鍥磋鎴戜滑@1point 3 acres
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;
  5.     DoubleLinkedListNode dummy(0);
  6.     stack<TreeNode*> s;
  7.     s.push(root);
  8.     DoubleLinkedListNode *prev = &dummy;. visit 1point3acres.com for more.
  9.     TreeNode *cur = nullptr;
  10.     while(!s.empty() || cur) {
  11.         if(cur) {
  12.             s.push(cur);
  13.             cur = cur->left;. Waral 鍗氬鏈夋洿澶氭枃绔,
  14.         }
  15.         else {
  16.             TreeNode *top = s.top();
  17.             s.pop();. more info on 1point3acres.com
  18.             DoubleLinkedListNode *next = new DoubleLinkedListNode(top->val);
  19.             next->prev = prev;
  20.             prev->next = next;
  21.             prev = next;
  22.             cur = top->right;
  23.         }
  24.     }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  25.     prev->next = dummy.next;
  26.     return dummy.next; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  27. }
复制代码
回复 支持 反对

使用道具 举报

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

using namespace std;

struct TreeNode {
         int val;
         TreeNode *left;
         TreeNode *right;. 1point 3acres 璁哄潧
         TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     };

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);
}-google 1point3acres

int main()
{
    TreeNode* dummy=new TreeNode(0);
    TreeNode* pre=dummy;
    TreeNode* a1=new TreeNode(3);
    a1->left =new TreeNode(1);. visit 1point3acres.com for more.
    a1->left->right =new TreeNode(2);
    gen(a1,pre);
    dummy->left=pre->right;
    dummy->right->left=pre;. more info on 1point3acres.com
    return 0;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
}
回复 支持 反对

使用道具 举报

 楼主| zwj1991 发表于 2016-6-5 01:07:02 | 显示全部楼层
第一题中序遍历的时候顺便把结点的结构改了就好,面完才想出来的,这样Space就是O(1). 鍥磋鎴戜滑@1point 3 acres
private TreeNode listRootNode = null;
private TreeNode tmp = null;
        public TreeNode convert(TreeNode root) {
        inOrderList(root);
        TreeNode tail = listRootNode;
        while(tail.right != null)
                tail = tail.right;
        tail.right = listRootNode;
        listRootNode.left = tail;
        return listRootNode;
        }
       
        private void inOrderList(TreeNode root){. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                if(root == null)
                        return;
                inOrderList(root.left);
                if(listRootNode == null). 鍥磋鎴戜滑@1point 3 acres
                        listRootNode = root;
. 1point 3acres 璁哄潧                if(tmp == null)
                        tmp = root;. Waral 鍗氬鏈夋洿澶氭枃绔,
                if(tmp != root){
                        tmp.right = root;. visit 1point3acres.com for more.
                        root.left = tmp;
                        tmp = tmp.right;
                }. visit 1point3acres.com for more.
                inOrderList(root.right);               
        }
回复 支持 反对

使用道具 举报

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);
    a1->right->right->left =new TreeNode(6); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    a1->left->left =new TreeNode(0);
    a1->left->left->left =new TreeNode(-1);
   
    gen(a1,pre);
    dummy->left=pre->right;.1point3acres缃
    dummy->right->left=pre;. Waral 鍗氬鏈夋洿澶氭枃绔,
    . more info on 1point3acres.com
    TreeNode* head=dummy->right;
    while(head)
    {.鐣欏璁哄潧-涓浜-涓夊垎鍦
        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!

想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 反对

使用道具 举报

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

void pp(TreeNode* root, string s)
{.1point3acres缃
    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);
    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就好了
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 17:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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