近期论坛无法登录的解决方案


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 3176|回复: 12
收起左侧

半小时前Facebook电面

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

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

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

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

x


第一题:
.鐣欏璁哄潧-涓浜-涓夊垎鍦
     3
   / 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
1         . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
   \ .鏈枃鍘熷垱鑷1point3acres璁哄潧
    2. more info on 1point3acres.com
一棵树,返回一个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没回答出来。

第二题
         A. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
       /  \
     B    C     
    /     / \. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
   D    E  F

打印所有path
ABD. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
ACE. 1point 3acres 璁哄潧
ACF
. from: 1point3acres.com/bbs
dfs可以,第一次用了一个list获得所有path输出,后来修改成直接输出。
follow up时间,空间复杂度。。没回答好。。。
准备有点不充分,求人品~~~~~~~~~~~~~~~~

评分

2

查看全部评分

blackrose 发表于 2016-6-4 05:39:24 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
第一题是BST 转成double linked list吧。。。。。
回复 支持 反对

使用道具 举报

yfang0663 发表于 2016-6-4 23:54:07 | 显示全部楼层
关注一亩三分地微博:
Warald
第二题time O(2^h) space O(h) 是吗
回复 支持 反对

使用道具 举报

laonawuli 发表于 2016-6-5 00:06:14 | 显示全部楼层
yfang0663 发表于 2016-6-4 07:54. Waral 鍗氬鏈夋洿澶氭枃绔,
第二题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我同意你的。
.1point3acres缃
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;. from: 1point3acres.com/bbs
  9.     TreeNode *cur = nullptr;
  10.     while(!s.empty() || cur) {-google 1point3acres
  11.         if(cur) {
  12.             s.push(cur);
  13.             cur = cur->left;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  14.         }. more info on 1point3acres.com
  15.         else {
  16.             TreeNode *top = s.top();
  17.             s.pop();
  18.             DoubleLinkedListNode *next = new DoubleLinkedListNode(top->val);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  19.             next->prev = prev;
  20.             prev->next = next;
  21.             prev = next;
  22.             cur = top->right;
  23.         }
  24.     }. From 1point 3acres bbs
  25.     prev->next = dummy.next;
  26.     return dummy.next;
  27. }
复制代码
回复 支持 反对

使用道具 举报

dong882205 发表于 2016-6-5 00:57:30 | 显示全部楼层
第一题用递归好像能做? 写了一下, 可直接编译运行,望指教!
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
using namespace std;
. visit 1point3acres.com for more.
struct TreeNode {-google 1point3acres
         int val;
-google 1point3acres         TreeNode *left;
         TreeNode *right;
         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;. visit 1point3acres.com for more.
    pre=pre->right;
    if(root->right) gen(root->right,pre);
}

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);-google 1point3acres
    gen(a1,pre);
    dummy->left=pre->right;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    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) {
        inOrderList(root);
        TreeNode tail = listRootNode;
        while(tail.right != null)
                tail = tail.right;
        tail.right = listRootNode;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        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;
                }. From 1point 3acres bbs
                inOrderList(root.right);               
        }
回复 支持 反对

使用道具 举报

dong882205 发表于 2016-6-5 01:07:26 | 显示全部楼层
写了个复杂点的树结构, 看来是没问题了, 输出是-1,0,1,2,3,4,5,6,7
int main()
{.鏈枃鍘熷垱鑷1point3acres璁哄潧
    TreeNode* dummy=new TreeNode(0);
    TreeNode* pre=dummy;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
   
    TreeNode* a1=new TreeNode(3);
    a1->left =new TreeNode(1);. 1point3acres.com/bbs
    a1->left->right =new TreeNode(2);
    a1->right =new TreeNode(5);. 鍥磋鎴戜滑@1point 3 acres
    a1->right->left =new TreeNode(4);. visit 1point3acres.com for more.
    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;
    dummy->right->left=pre;. from: 1point3acres.com/bbs
   
    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).. 鍥磋鎴戜滑@1point 3 acres
其实不需要记录当前的path,只要dfs到叶子结点的时候就输出path就好了,但是递归占用stack,所以还是有空间复杂度。. 1point 3acres 璁哄潧
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)??
. 1point 3acres 璁哄潧
void pp(TreeNode* root, string s)
{
    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);
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
    pp(a1,"");

    return 0;
}
回复 支持 反对

使用道具 举报

yfang0663 发表于 2016-6-5 02:50:57 | 显示全部楼层
dong882205 发表于 2016-6-5 01:24
刚发的不见了- -! 变成了默认文字...
第二题好像不难
空间的话, 求指点: 最多同时会有深度H的recurrence ...
. from: 1point3acres.com/bbs
pass string by reference就好了
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-6-27 10:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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