一亩三分地论坛

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

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

zenefits oa 做完,回报版友

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

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

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

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

x
前几天做完了zenefits的OA3, 题目没有变,就不贴了。网上也很多答案。
说一下我的方法
第一题 word chain跟版上别人的思路差不多,就是先按大小分类,从最长的. visit 1point3acres.com for more.
开始做,dfs + recursion。算过的词就删掉。注意一些细节,比如有可能
某一长度的词没有,或者比某单词长度短1的也没有,就可以直接跳过。
. from: 1point3acres.com/bbs 长度如果达到了当前单词能达到的最长时就不用往下做了。

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

我把4个test的题目都做过,貌似superstack很多人有疑问,我说下我的思路。. From 1point 3acres bbs
我的做法类似sort interval。把每个increase操作都保存下来放到一个Max heap中
increase 操作我建了一个数据结构,里面有start, end, inc。 start其实是它最大
影响到的位置,end初始化都是0。每当有新的increase推入heap中时,要更新heap中
top的end值,就是看看top下一个值的start是多少,那么top的end就是多少。
Stack就是用普通stack来做,只不过加了一个head,来看看目前长度,省的每次
都取大小。 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的更新有些细节. Waral 鍗氬鏈夋洿澶氭枃绔,
需要把握,比如有可能所有的increase都到a,那么heap更新完就只有一个值,其余
都合并了等。这个方法更新heap是最难的,其余都很简单。

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

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

. 鍥磋鎴戜滑@1point 3 acres

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-3-28 18:34

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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