一亩三分地论坛

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

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

zenefits oa 做完,回报版友

[复制链接] |试试Instant~ |关注本帖
uabenjamin 发表于 2016-2-13 05:01:32 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Zenefits - 内推 - 在线笔试 |Passfresh grad应届毕业生

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

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

x
前几天做完了zenefits的OA3, 题目没有变,就不贴了。网上也很多答案。
说一下我的方法
第一题 word chain跟版上别人的思路差不多,就是先按大小分类,从最长的
开始做,dfs + recursion。算过的词就删掉。注意一些细节,比如有可能
某一长度的词没有,或者比某单词长度短1的也没有,就可以直接跳过。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
长度如果达到了当前单词能达到的最长时就不用往下做了。

第二题 我自己想的方法,因为这个题目难度相对小多了,代码也短多了。
思路就是每个queen都对应一个长度为4的status list,里面初始化为0。
从第一行开始,检测每一个queen对角线方向,如果对角线方向上有威胁,
更新这两个queen的对应方向状态为1。4个位置对应四个方向。 对于每个queen,
其实只需要检测她下方的两个对角线,因为上面的已经被之前的queen检测
过了,所以没必要重复检测。每算完一个queen看看sum是不是4, 是的话
就直接结束。

我把4个test的题目都做过,貌似superstack很多人有疑问,我说下我的思路。
我的做法类似sort interval。把每个increase操作都保存下来放到一个Max heap中
increase 操作我建了一个数据结构,里面有start, end, inc。 start其实是它最大
影响到的位置,end初始化都是0。每当有新的increase推入heap中时,要更新heap中
top的end值,就是看看top下一个值的start是多少,那么top的end就是多少。
Stack就是用普通stack来做,只不过加了一个head,来看看目前长度,省的每次. 1point3acres.com/bbs
都取大小。 heap的top的start值永远不会比head值大,因为大了没有意义。
每次top操作,top出来的数都要加上heap里top的inc值。Pop后还得更新下heap,看看
是不是当前的top已经不再影响了,也就是end==head了,如果是的话,把top给pop掉, 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
新的top要加上刚刚pop出来的top的inc。而且新的top需要更新下end值。
有push操作就正常push,更改head。有increase就更新heap。heap的更新有些细节
需要把握,比如有可能所有的increase都到a,那么heap更新完就只有一个值,其余
都合并了等。这个方法更新heap是最难的,其余都很简单。

这个方法每次pop 和increase都会更新heap。 时间主要浪费在了heap的更新上,
而且heap也占空间。因为没看到原题,所以不清楚有多少increase操作,以及stack
的长度能到多少,所以也没法说这个方法到底能不能通过所有测试,只是把思路
分享给大家。

祝大家春节快乐!每人新年offer收不停!. more info on 1point3acres.com


本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 12:29

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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