12
返回列表 发新帖
楼主: lwt1104
跳转到指定楼层
上一主题 下一主题
收起左侧

Palantir onsite面经

🔗
 楼主| lwt1104 2015-3-15 10:58:08 | 只看该作者
全局:
zhuang1992 发表于 2015-3-15 04:40
跟我想的一样。。只需要记录三个数字应该可以算是Constant了吧。

如果只记住三个数字确实是constant,可是调整数字的时候要查前面读入的数字,我觉得可能就不太算了吧。
你觉得呢? 欢迎讨论哈。
回复

使用道具 举报

🔗
zhuang1992 2015-3-15 11:32:47 | 只看该作者
全局:
lwt1104 发表于 2015-3-15 10:58
如果只记住三个数字确实是constant,可是调整数字的时候要查前面读入的数字,我觉得可能就不太算了吧。
...

嗯也有道理。如果是个输入流的话,要记住之前的数字还是需要额外空间的。
但是我之前看到的题稍微有点不同,它给的是一个数组,让计算从头到第i个数的median,这样就不需要额外空间了。
还有除了要考虑比较与上个median的大小,还需要考虑目前已经有了奇数个还是偶数个数字。
我在这里贴了代码。欢迎讨论。
http://www.1point3acres.com/bbs/ ... p;page=1#pid1753652
回复

使用道具 举报

🔗
shawlin 2015-3-15 11:35:40 | 只看该作者
全局:
lwt1104 发表于 2015-3-14 21:56
第三题我觉得你说的是对的。当时我想到的方法是记住三个数(median, median 左边和右边的数),那个人没 ...

如果是NXM的board,复杂度就是O(MN), 对每一个位置,交换周围neighbor(最多4个),check有木有三连?
面试官是不是要想优化下,比如一行都没有两个相同的,那这一行怎么换都换不出三联了
回复

使用道具 举报

🔗
 楼主| lwt1104 2015-3-15 22:27:34 | 只看该作者
全局:
shawlin 发表于 2015-3-15 11:35
如果是NXM的board,复杂度就是O(MN), 对每一个位置,交换周围neighbor(最多4个),check有木有三连?
面 ...

是啊,应该是有 更好的办法的。我当时的优化就只给出了一个交换相同颜色棋子就不用check了这一项。
回复

使用道具 举报

🔗
大饭团 2015-3-16 11:21:52 | 只看该作者
全局:
lwt1104 发表于 2015-3-15 10:56
第三题我觉得你说的是对的。当时我想到的方法是记住三个数(median, median 左边和右边的数),那个人没 ...

想请问下楼主,这个第一题是求的所有能交换得到三个一样的坐标集,是每个交换事件是相互独立的吗?
我想了想好像做下来的O(N^2)啊,要优化貌似感觉也是在nested loop内部优化了。楼主有啥子优化的方法不。
回复

使用道具 举报

🔗
 楼主| lwt1104 2015-3-16 12:24:46 | 只看该作者
全局:
大饭团 发表于 2015-3-16 11:21
想请问下楼主,这个第一题是求的所有能交换得到三个一样的坐标集,是每个交换事件是相互独立的吗?
我想 ...

交换事件是相互独立的,要求返回所有的坐标pair(两个点进行交换)
我感觉这个题本质是o(n2)是改不了的。可能有高手可以写的时间系数小一点把。
我当时没有给出什么特别的优化,因为时间有限嘛。就写了个如果两个交换的棋子是一样的值,就不用check了。
回复

使用道具 举报

🔗
大饭团 2015-3-16 20:48:55 | 只看该作者
全局:
lwt1104 发表于 2015-3-16 12:24
交换事件是相互独立的,要求返回所有的坐标pair(两个点进行交换)
我感觉这个题本质是o(n2)是改不了的 ...

多谢楼主啦!表示楼主还是很牛的!!
回复

使用道具 举报

🔗
mayijie88 2015-6-7 06:25:26 | 只看该作者
全局:
感觉第三题为什么要keep 3个参数呢?感觉记住当前median就可以做了?
如果知道了当前的median,那么如果新增一个元素,假如当前数组长度为奇数,意味着median平分当前数组,如果新增的数大于median,那么median不变,因为偶数长度的话默认median把数组分成右边比左边多一个的情况。如果新增的数小于median,意味着按照当前median的分法,左边会比右边多一个,则搜索数组,得到比median小的最大值作为新的median.

假如当前数组长度为偶数,意味着median将数组分成右边比左边多一个的情况,如果新增的数大于median,那么搜索数组,把比median大的数的最小值作为新的median,如果新增数小于median,则median不变。
回复

使用道具 举报

🔗
yuruofeifei 2015-6-8 05:41:31 | 只看该作者
全局:
多谢楼主!祝楼主早日拿到offer!!
回复

使用道具 举报

🔗
 楼主| lwt1104 2015-11-7 23:05:33 | 只看该作者
全局:
mayijie88 发表于 2015-6-7 06:25
感觉第三题为什么要keep 3个参数呢?感觉记住当前median就可以做了?
如果知道了当前的median,那么如果新 ...

好久没来了,我同意你的观点。反正都是O(n)。我现在想想,如果记录三个参数,小于median和大于median的那两个参数offline调整,这样时间复杂度算不算变相的O(1)了。就是说每新来一个数,先把median返回了,再offline的调整另外两个参数。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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