当前在线人数8598
首页 - 分类讨论区 - 海外生活 - 待字闺中版 - 同主题阅读文章

此篇文章共收到打赏
0

  • 10
  • 20
  • 50
  • 100
您目前伪币余额:0
未名交友
[更多]
[更多]
问道G的onsite题
[版面:待字闺中][首篇作者:austurela] , 2015年09月19日02:48:26 ,6248次阅读,42次回复
来APP回复,赚取更多伪币 关注本站公众号:
[首页] [上页][下页][末页] [分页:1 2 ]
austurela
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 1 ]

发信人: austurela (austurela), 信区: JobHunting
标  题: 问道G的onsite题
发信站: BBS 未名空间站 (Sat Sep 19 02:48:26 2015, 美东)

在别处看到别的公司也考,突然想起来我G onsite貌似挂在这题上了。想请教请教各位
大牛怎么做

“给你一棵树,不是binary的,每个节点会有任意个children,然后这棵树是存在一个
数组里的,数组的每个元素就是一个节点,节点包含了它的index以及它的parent的
index,而不是children的index哦,所以这棵树是从child指向parent的。最后是给我
这个数组和一个节点的index,让我删除这个index以及它的子树,只能用O(n)的空间复
杂度,而且大小是确定好的”
数组里各个node是打乱的,不是topologically sorted的

update:
举个例子:
[3,1,4,1,5,7,2,6]
删index 1
得到
[x,x,4,x,5,7,2,6] (x代表被删除)
最终输出
[1,2,4,0,3]

我觉得主要难点在找到哪些index要删,最后往前挪补空缺的步骤比较trivial
--
※ 修改:·austurela 於 Sep 19 03:42:49 2015 修改本文·[FROM: 98.]
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 98.]

 
tiswen
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 2 ]

发信人: tiswen (Finally), 信区: JobHunting
标  题: Re: 问道G的onsite题
发信站: BBS 未名空间站 (Sat Sep 19 03:03:26 2015, 美东)

建个数组of (位置,是否删除)。walk一遍拿到位置。再walk一遍同时search是否应
该删除。O(n)的时间和空间复杂度。总共连写code,最多10-15分钟应该搞定。
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 69.]

 
ThinkU
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 3 ]

发信人: ThinkU (每天想你多一丝), 信区: JobHunting
标  题: Re: 问道G的onsite题
发信站: BBS 未名空间站 (Sat Sep 19 03:07:23 2015, 美东)

请定义一下删除。
一般来说子树到父节点链接去掉就是删除了,那这里把这个节点指向parent的链接清掉
就行了。
【 在 austurela (austurela) 的大作中提到: 】
: 在别处看到别的公司也考,突然想起来我G onsite貌似挂在这题上了。想请教请教各位
: 大牛怎么做
: “给你一棵树,不是binary的,每个节点会有任意个children,然后这棵树是存在一个
: 数组里的,数组的每个元素就是一个节点,节点包含了它的index以及它的parent的
: index,而不是children的index哦,所以这棵树是从child指向parent的。最后是给我
: 这个数组和一个节点的index,让我删除这个index以及它的子树,只能用O(n)的空间复
: 杂度,而且大小是确定好的”
: 数组里各个node是打乱的,不是topologically sorted的



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 70.]

 
kjbl
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 4 ]

发信人: kjbl (看家本领), 信区: JobHunting
标  题: Re: 问道G的onsite题
发信站: BBS 未名空间站 (Sat Sep 19 03:10:46 2015, 美东)

一两遍不行吧,走一遍发现这个节点的几个孩子,再走一遍又发现前面还有漏掉的孙子
,再走一遍重孙子。。。直到九族全灭
【 在 tiswen (Finally) 的大作中提到: 】
: 建个数组of (位置,是否删除)。walk一遍拿到位置。再walk一遍同时search是否应
: 该删除。O(n)的时间和空间复杂度。总共连写code,最多10-15分钟应该搞定。



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 50.]

 
tiswen
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 5 ]

发信人: tiswen (Finally), 信区: JobHunting
标  题: Re: 问道G的onsite题
发信站: BBS 未名空间站 (Sat Sep 19 03:16:01 2015, 美东)

可以,walk的同时循环找parent,一直到r碰到一个已知被删除或保留的的节点。mark
所有的parent和grand。。。
结果还是线性的复杂度

【 在 kjbl (看家本领) 的大作中提到: 】
: 一两遍不行吧,走一遍发现这个节点的几个孩子,再走一遍又发现前面还有漏掉的孙子
: ,再走一遍重孙子。。。直到九族全灭

--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 69.]

 
austurela
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 6 ]

发信人: austurela (austurela), 信区: JobHunting
标  题: Re: 问道G的onsite题
发信站: BBS 未名空间站 (Sat Sep 19 03:26:29 2015, 美东)

就是最后输出一个把该删除的都删除掉了的新的数组
比如1,2,3是5的children,要删5,那么最后输出的数组里面,index 1,2,3,5都
被删
除掉了,其他
的往前挪,填空出来的位置
【 在 ThinkU (每天想你多一丝) 的大作中提到: 】
: 请定义一下删除。
: 一般来说子树到父节点链接去掉就是删除了,那这里把这个节点指向parent的链接清掉
: 就行了。






--
※ 修改:·austurela 於 Sep 19 03:28:49 2015 修改本文·[FROM: 98.]
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 98.]

 
austurela
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 7 ]

发信人: austurela (austurela), 信区: JobHunting
标  题: Re: 问道G的onsite题
发信站: BBS 未名空间站 (Sat Sep 19 03:34:05 2015, 美东)

你每search一个index是不是该删除,都要从它一直追溯到它的老祖宗,which is logn
in average,O(n) in the worst case,如何做到总共O(n)时间
【 在 tiswen (Finally) 的大作中提到: 】
: 建个数组of (位置,是否删除)。walk一遍拿到位置。再walk一遍同时search是否应
: 该删除。O(n)的时间和空间复杂度。总共连写code,最多10-15分钟应该搞定。



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 98.]

 
austurela
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 8 ]

发信人: austurela (austurela), 信区: JobHunting
标  题: Re: 问道G的onsite题
发信站: BBS 未名空间站 (Sat Sep 19 03:43:04 2015, 美东)

I have updated an example above
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 98.]

 
gorilazz
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 9 ]

发信人: gorilazz (gorilazz), 信区: JobHunting
标  题: Re: 问道G的onsite题
发信站: BBS 未名空间站 (Sat Sep 19 03:51:59 2015, 美东)

但是在这logn步的追溯过程中,可以有logn个节点被确定是否被删除,等搜到他们的时
候就不用再追溯了,相当于确定每一个节点是否被删除只需要常数复杂度,所以应该是
O(n)没错的
【 在 austurela (austurela) 的大作中提到: 】
: 你每search一个index是不是该删除,都要从它一直追溯到它的老祖宗,which is
logn
:  in average,O(n) in the worst case,如何做到总共O(n)时间



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 24.]

 
tiswen
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 10 ]

发信人: tiswen (Finally), 信区: JobHunting
标  题: Re: 问道G的onsite题
发信站: BBS 未名空间站 (Sat Sep 19 03:52:49 2015, 美东)

不需要每一个都到root,到一个已知的就结束了。第二次walk每个节点on average
touch最多两次。所以是线性的


【 在 austurela (austurela) 的大作中提到: 】
: 你每search一个index是不是该删除,都要从它一直追溯到它的老祖宗,which is
logn
:  in average,O(n) in the worst case,如何做到总共O(n)时间

--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 69.]

 
tiswen
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 11 ]

发信人: tiswen (Finally), 信区: JobHunting
标  题: Re: 问道G的onsite题
发信站: BBS 未名空间站 (Sat Sep 19 03:55:03 2015, 美东)

嗯,你的表达能力比我好,优势大大的


【 在 gorilazz (gorilazz) 的大作中提到: 】
: 但是在这logn步的追溯过程中,可以有logn个节点被确定是否被删除,等搜到他们的时
: 候就不用再追溯了,相当于确定每一个节点是否被删除只需要常数复杂度,所以应该是
: O(n)没错的
: logn

--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 69.]

 
kjbl
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 12 ]

发信人: kjbl (看家本领), 信区: JobHunting
标  题: Re: 问道G的onsite题
发信站: BBS 未名空间站 (Sat Sep 19 04:00:04 2015, 美东)

我给你举个例子,要删除的节点logn-1代单传,
你n-logn个节点都得上述到根节点才能确定不删
【 在 gorilazz (gorilazz) 的大作中提到: 】
: 但是在这logn步的追溯过程中,可以有logn个节点被确定是否被删除,等搜到他们的时
: 候就不用再追溯了,相当于确定每一个节点是否被删除只需要常数复杂度,所以应该是
: O(n)没错的
: logn



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 50.]

 
austurela
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 13 ]

发信人: austurela (austurela), 信区: JobHunting
标  题: Re: 问道G的onsite题
发信站: BBS 未名空间站 (Sat Sep 19 04:00:07 2015, 美东)

大牛第一遍walk拿位置指的是拿什么位置?
【 在 tiswen (Finally) 的大作中提到: 】
: 不需要每一个都到root,到一个已知的就结束了。第二次walk每个节点on average
: touch最多两次。所以是线性的
: logn



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 98.]

 
tiswen
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 14 ]

发信人: tiswen (Finally), 信区: JobHunting
标  题: Re: 问道G的onsite题
发信站: BBS 未名空间站 (Sat Sep 19 04:04:19 2015, 美东)

拿的是在input数组中的位置。目的是得到一个index to position的map。方便第二次
search parent


【 在 austurela (austurela) 的大作中提到: 】
: 大牛第一遍walk拿位置指的是拿什么位置?

--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 69.]

 
austurela
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 15 ]

发信人: austurela (austurela), 信区: JobHunting
标  题: Re: 问道G的onsite题
发信站: BBS 未名空间站 (Sat Sep 19 04:05:32 2015, 美东)

想了想,恩你说的对,谢谢大牛
【 在 gorilazz (gorilazz) 的大作中提到: 】
: 但是在这logn步的追溯过程中,可以有logn个节点被确定是否被删除,等搜到他们的时
: 候就不用再追溯了,相当于确定每一个节点是否被删除只需要常数复杂度,所以应该是
: O(n)没错的
: logn



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 98.]

 
tiswen
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 16 ]

发信人: tiswen (Finally), 信区: JobHunting
标  题: Re: 问道G的onsite题
发信站: BBS 未名空间站 (Sat Sep 19 04:08:05 2015, 美东)

懒得写了,你仔细想想,不删也是可以拿来short circuit 子孙的search的


【 在 kjbl (看家本领) 的大作中提到: 】
: 我给你举个例子,要删除的节点logn-1代单传,
: 你n-logn个节点都得上述到根节点才能确定不删

--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 69.]

 
austurela
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 17 ]

发信人: austurela (austurela), 信区: JobHunting
标  题: Re: 问道G的onsite题
发信站: BBS 未名空间站 (Sat Sep 19 04:10:15 2015, 美东)

大牛你说的对,谢谢。
你想的很周全,完全符合题意
其实题也没那么复杂
比如input【3,1,4,1,5,7,2,6】
拿index 0 来说,他的index就是0,他的parent是index 3,他的index就是数组中的
index,所以没必要拿位置。
你的意思我理解,如果他的index不是数组中index,就要按你说的做
大牛确实厉害。。。
【 在 tiswen (Finally) 的大作中提到: 】
: 拿的是在input数组中的位置。目的是得到一个index to position的map。方便第二次
: search parent



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 98.]

 
austurela
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 18 ]

发信人: austurela (austurela), 信区: JobHunting
标  题: Re: 问道G的onsite题
发信站: BBS 未名空间站 (Sat Sep 19 04:13:46 2015, 美东)

你自己画两个例子。。。最开始由于没有记录要找到祖宗,但是每找到一次祖宗(或要
删得node),你都可以把这条路径记录下来,哪些删哪些不删,下次碰到直接用结果就好
【 在 kjbl (看家本领) 的大作中提到: 】
: 我给你举个例子,要删除的节点logn-1代单传,
: 你n-logn个节点都得上述到根节点才能确定不删



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 98.]

 
kjbl
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 19 ]

发信人: kjbl (看家本领), 信区: JobHunting
标  题: Re: 问道G的onsite题
发信站: BBS 未名空间站 (Sat Sep 19 04:27:56 2015, 美东)

第一遍是n*logn,以后就不用再找了

anyway, 这个确实比我说的那个多次遍历好多了
【 在 austurela (austurela) 的大作中提到: 】
: 你自己画两个例子。。。最开始由于没有记录要找到祖宗,但是每找到一次祖宗(或要
: 删得node),你都可以把这条路径记录下来,哪些删哪些不删,下次碰到直接用结果
就好



--
※ 修改:·kjbl 於 Sep 19 04:38:43 2015 修改本文·[FROM: 50.]
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 50.]

 
edison2012
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 20 ]

发信人: edison2012 (jimmy), 信区: JobHunting
标  题: Re: 问道G的onsite题
发信站: BBS 未名空间站 (Sat Sep 19 05:36:27 2015, 美东)

1)

for( int i : nums ){

    find path p : i --> to the root;

    if(p contains Integer.MAX_VALUE or node to be deleted somewhere)

          then set the nodes between i (inclusive) and Integer.MAX_VALUE to
Integer.MAX_VALUE;

}

2)

compact the pierced array:

Say, exchange i and Integer.MAX_VALUE at j:

     nums[j] = nums[i]

     nums[i] = - j - 1;


3)

for( j in those not change position with Integer.MAX_VALUE){

     if(nums[nums[j]] < 0)

        nums[j] = - nums[nums[j]] - 1;


}   



【 在 austurela (austurela) 的大作中提到: 】
: 在别处看到别的公司也考,突然想起来我G onsite貌似挂在这题上了。想请教请教各位
: 大牛怎么做
: “给你一棵树,不是binary的,每个节点会有任意个children,然后这棵树是存在一个
: 数组里的,数组的每个元素就是一个节点,节点包含了它的index以及它的parent的
: index,而不是children的index哦,所以这棵树是从child指向parent的。最后是给我
: 这个数组和一个节点的index,让我删除这个index以及它的子树,只能用O(n)的空间复
: 杂度,而且大小是确定好的”
: 数组里各个node是打乱的,不是topologically sorted的
: update:
: 举个例子:
: ...................


--

※ 来源:·BBS 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 73.]

[首页] [上页][下页][末页] [分页:1 2 ]
[快速返回] [ 进入待字闺中讨论区] [返回顶部]
回复文章
标题:
内 容:

未名交友
将您的链接放在这儿

友情链接


 

Site Map - Contact Us - Terms and Conditions - Privacy Policy

版权所有,未名空间(mitbbs.com),since 1996