一亩三分地论坛

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

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

Palantir onsite面经

[复制链接] |试试Instant~ |关注本帖
lwt1104 发表于 2015-3-6 03:12:06 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 博士 实习@Palantir - 网上海投 - Onsite |Fail

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

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

x
在Palantir Onsite面了三个面试官, 题目如下:
1. 给你一个棋盘 int[][] board, 你可以交换任何一个棋子和它的邻居(横向或者竖向相邻的棋子),如果交换后,在横向或者竖向产生了大于等于三个连续的一样的棋子 e.g.  4 4 4   
5
5
5. from: 1point3acres.com/bbs
那么就算交换有效。(就是一个比较常见的游戏,忘记叫啥名字了)
请你写一个函数返回所有可以有效交换的棋子的坐标对。 比如  ((0, 0), (1, 0)) , ((3,2),(3,3))
.鐣欏璁哄潧-涓浜-涓夊垎鍦
2. 看code,debug, 然后写出争取的code,这个没啥说的。

3. a. Merge interval.鏈枃鍘熷垱鑷1point3acres璁哄潧
    b. 给你一个数组, 要求返回一个数组,数组的每个元素是是输入数组到此位置的subarray 的 median。如果subarray的size是偶数,那么用小的那个数做median.

        e.g. input [1 3 4  2 6]. visit 1point3acres.com for more.

        output [1, 1, 3, 2, 3]  

        因为 [1] median 1
-google 1point3acres
                [1 3] median 1
. From 1point 3acres bbs
                [1 3 4]  -- 3. 鍥磋鎴戜滑@1point 3 acres

                [1  3 4 2]  -- 2

                [1 3 4  2 6] -- 3

   这是道题目是两道题目:

   b1.要求越快要好
    b2. constant extra memory, 并且输入数组read-only(不能in place quick sort)时间复杂度要求可以低一些。

yuruofeifei 发表于 2015-6-8 05:41:31 | 显示全部楼层
多谢楼主!祝楼主早日拿到offer!!
回复 支持 1 反对 0

使用道具 举报

大饭团 发表于 2015-3-16 20:48:55 | 显示全部楼层
lwt1104 发表于 2015-3-16 12:24. 鍥磋鎴戜滑@1point 3 acres
交换事件是相互独立的,要求返回所有的坐标pair(两个点进行交换)
我感觉这个题本质是o(n2)是改不了的 ...

多谢楼主啦!表示楼主还是很牛的!!
回复 支持 1 反对 0

使用道具 举报

shuiguo 发表于 2015-3-7 08:50:41 | 显示全部楼层
lz这么快就知道面挂了?
回复 支持 反对

使用道具 举报

sevensevens 发表于 2015-3-7 14:11:19 | 显示全部楼层
请问楼主是在加州面的吗?   
回复 支持 反对

使用道具 举报

 楼主| lwt1104 发表于 2015-3-8 09:19:53 | 显示全部楼层
sevensevens 发表于 2015-3-7 14:11
请问楼主是在加州面的吗?

是的, Palo Alto
回复 支持 反对

使用道具 举报

 楼主| lwt1104 发表于 2015-3-8 09:20:29 | 显示全部楼层
shuiguo 发表于 2015-3-7 08:50
lz这么快就知道面挂了?

我等了10天知道的。
回复 支持 反对

使用道具 举报

cocaptainco 发表于 2015-3-8 09:46:02 | 显示全部楼层
请问楼主 第3题要求constant memory有什么解吗?
回复 支持 反对

使用道具 举报

 楼主| lwt1104 发表于 2015-3-12 09:46:34 | 显示全部楼层
cocaptainco 发表于 2015-3-8 09:46. more info on 1point3acres.com
请问楼主 第3题要求constant memory有什么解吗?

这个有点复杂,就在白板上比划了一下,没写代码。. 1point 3acres 璁哄潧
大概的方法是 记住三个数字: median, 小于median的最大的数字,大于median的最小的数字。 这样新的数字进来之后,相应的调整这三个数字。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

但是每次调整数字的时间还是O(n), 而且还是要记住之前有的数字。我觉得可能做不到真正的constant memory。
回复 支持 反对

使用道具 举报

shawlin 发表于 2015-3-15 04:14:16 | 显示全部楼层
LZ第一题能说说思路么?第三题follow up O(1) space也太变态了吧,如果可以改变原数组的话,可以用insertion-sort?
回复 支持 反对

使用道具 举报

zhuang1992 发表于 2015-3-15 04:40:56 | 显示全部楼层
lwt1104 发表于 2015-3-12 09:46
这个有点复杂,就在白板上比划了一下,没写代码。
大概的方法是 记住三个数字: median, 小于median的最 ...
. From 1point 3acres bbs
跟我想的一样。。只需要记录三个数字应该可以算是Constant了吧。
回复 支持 反对

使用道具 举报

 楼主| lwt1104 发表于 2015-3-15 10:56:40 | 显示全部楼层
shawlin 发表于 2015-3-15 04:14
LZ第一题能说说思路么?第三题follow up O(1) space也太变态了吧,如果可以改变原数组的话,可以用insertio ...

第三题我觉得你说的是对的。当时我想到的方法是记住三个数(median, median 左边和右边的数),那个人没让我写代码,算我作对了貌似。但是我现在想想当时做的不对,估计这是我挂的原因吧。
.1point3acres缃
第一题是这样,交换两个棋子会影响两个坐标,你可以分别检查这两个坐标有没有产生三连的数字。比如检查坐标(x, y) 有没有横三联
int val = board[x][y];. Waral 鍗氬鏈夋洿澶氭枃绔,
int len = 1;.鏈枃鍘熷垱鑷1point3acres璁哄潧
int index = y + 1;
while (index < board[0].length && board[x][index] == val) {
    len++;. more info on 1point3acres.com
    index++;
}
index = y - 1;
while (index >= 0 && board[x][index] == val) {
     len++;
     index--;
}

//len is the length of horizontal consecutive value of board[x][y]
这个题也有很多小的细节可以优化。.鐣欏璁哄潧-涓浜-涓夊垎鍦

回复 支持 反对

使用道具 举报

 楼主| 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
想请问下楼主,这个第一题是求的所有能交换得到三个一样的坐标集,是每个交换事件是相互独立的吗?. 1point3acres.com/bbs
我想 ...

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

使用道具 举报

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不变。
回复 支持 反对

使用道具 举报

 楼主| lwt1104 发表于 2015-11-7 23:05:33 | 显示全部楼层
mayijie88 发表于 2015-6-7 06:25
感觉第三题为什么要keep 3个参数呢?感觉记住当前median就可以做了?. Waral 鍗氬鏈夋洿澶氭枃绔,
如果知道了当前的median,那么如果新 ...

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 03:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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