一亩三分地论坛

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

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

Palantir 1.7 Onsite

[复制链接] |试试Instant~ |关注本帖
又见紫风铃 发表于 2016-1-8 10:13:32 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 实习@Palantir - 网上海投 - Onsite |Failfresh grad应届毕业生

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

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

x
面的Intern,水水地跪了一早上,写一下面经吧-google 1point3acres
早上先是一个demo,介绍palantir的,同一天面试的在一个会议室一起看,10个人左右,自我介绍的时候除了我我只听到了MIT stanford harvard这几个学校的名字。。觉得真是跟一群大神们在一起无地自容。。然后貌似就我一个中国人
面试前recruiter跟我说早上两轮coding一轮decomp(design)结果居然出现了UX Design我也是跪了。。
1. UX Design。 两个白人姐姐,一个面试一个围观,面试官问我面过UX Design没有,我说没有,她说totally fine,她也是第一次在P家遇到这种面试。大概就是design一个app来实现比如吃饭了有人付了款,然后用app算好每个人应该相互给多少之类的(类似splitwise,两周前出去玩刚用过)。把各个界面都画出来(有哪些input,button),然后形成一个使用的流程图之类的。然后被指出了一点设计上如果用户不按照规定输入时要怎么处理,这个一开始没注意到。这一轮只要求设计,给出app的输入到中间过程到输出结果,不要求任何具体的实现。回答完了两个姐姐表示很满意(不知道真的满意还是客气话。。。)
2. 这轮coding是肯定跪了,一个亚裔的哥哥。问题很具体,一个他们开发的产品,用于地震救援的,抽象出来最后就是地图上很多点,给一个矩形区域,最快地返回区域内的点。brute force就是O(n)一个个点看在不在区域内。然后优化的方法想用什么数据结构,最后讨论得出所有点建一个有四个child的树,每一个child的子树包含了以这个点为原点划分出的四个象限之一区域的所有点。然后从root开始DFS,每次判断当前点和输入矩形区域的位置关系,然后只search与矩形区域重合的象限的子节点,最后一直search到的叶子就是的。怎么比较位置关系讨论了好久,最后没时间了,code也没写完,明显能感觉出来面试官不满意,这轮肯定跪了。
3. 这轮是debug,地里有人报过。也是一个亚裔的哥哥
http://www.1point3acres.com/bbs/ ... adio%26sortid%3D311
这个的第一题
第一个client side(描述中intern写的)的bug主要有1)while判断条件可能一次都不执行,应该先执行一次再判断。 2)数组最后一个index写成了数组长度,应该减一。 3)下一次调用load_result_page时的timestamp应该是上次得到page里最后一个timestamp + 1。4)如果第一次读到page_list就是空的时候是不能通过index = len - 1得到最后一个page的,所以要先判断一下page_list是不是空
第二个server side的bug主要是filter掉了invisible的list会使得总数小于page_size,应该一直读到visible的list达到page_size(实际需要读到page_size加1来判断读到page_size后还有没有下一个)
因为有代码要读,所以只能尽量描述成这样了。之前那个帖子我面试前看到了也还是不知道是啥,面试还是现场肉眼debug的。。不过可以记得server side的code会导致client可以发现server side有隐藏page的安全漏洞。

中午吃个饭看个demo,然后就被一个姐姐领走了,说我的面试今天就到这里,我的recruiter有事不在,她会收集三个面试官的反馈再给我答复的,然而我都看到会议室上下午也给我assign了一场面试的,自然就是跪咯。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴逼格超高的公司也没指望我这个渣渣能进咯,抱着玩玩的态度去的。不过还是相当喜欢的,简直dream。onsite待遇也超好,Onsite了五六次了,第一次坐到了有食物有水有frozen yoghurt有靠垫眼罩耳塞牙膏牙刷靠近舱门出入方便的comfort+的航班,然后奔驰S级美女司机接送,500刀一晚的酒店住两晚也超赞,拿了件tshirt也算不虚此行了!

评分

2

查看全部评分

 楼主| 又见紫风铃 发表于 2016-1-8 10:20:50 | 显示全部楼层
163 发表于 2016-1-8 10:19
第二题那个点是固定的还是会随时间变化?

是固定的,不会变的
回复 支持 1 反对 0

使用道具 举报

163 发表于 2016-1-8 10:19:19 | 显示全部楼层
第二题那个点是固定的还是会随时间变化?
回复 支持 反对

使用道具 举报

yjfox 发表于 2016-1-8 11:48:10 | 显示全部楼层
palantir, 面过都说好
回复 支持 反对

使用道具 举报

163 发表于 2016-1-8 12:14:11 | 显示全部楼层
又见紫风铃 发表于 2016-1-8 10:20
是固定的,不会变的

那直接先把地图扫描一遍,用 O(n^2)的时间求出(0,0)到 (i1,i2)围成(左上角-右下角)的矩形内的点的个数,然后如果是计算 (j1,j2) 到(k1,k2)内的点的个数的话,用刚刚的数据加加减减 O(1)就算出来了。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

总的来说,有一个 O(n^2)的setup时间,setup好了以后,每个inquiry都是O(1)的,面试官是不是期待这种答案?
回复 支持 反对

使用道具 举报

163 发表于 2016-1-8 12:14:42 | 显示全部楼层
又见紫风铃 发表于 2016-1-8 10:20
是固定的,不会变的

参见leetcode 304. Range Sum Query 2D - Immutable
回复 支持 反对

使用道具 举报

 楼主| 又见紫风铃 发表于 2016-1-8 12:15:39 | 显示全部楼层
163 发表于 2016-1-8 12:14.鏈枃鍘熷垱鑷1point3acres璁哄潧
那直接先把地图扫描一遍,用 O(n^2)的时间求出(0,0)到 (i1,i2)围成(左上角-右下角)的矩形内的点的个数 ...

不是求点的个数,是直接返回区域内的点(Point Object)
回复 支持 反对

使用道具 举报

 楼主| 又见紫风铃 发表于 2016-1-8 12:18:27 | 显示全部楼层
163 发表于 2016-1-8 12:14
那直接先把地图扫描一遍,用 O(n^2)的时间求出(0,0)到 (i1,i2)围成(左上角-右下角)的矩形内的点的个数 ...

然后建一个4叉树是他提示下我说出来的,这些他还是表现得比较满意的应该是他想要的方法
回复 支持 反对

使用道具 举报

163 发表于 2016-1-8 12:21:58 | 显示全部楼层
又见紫风铃 发表于 2016-1-8 12:15
不是求点的个数,是直接返回区域内的点(Point Object)
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
噢。这样。

那是不是默认地图的像素比较多,而点相对稀疏一些?
回复 支持 反对

使用道具 举报

 楼主| 又见紫风铃 发表于 2016-1-8 12:25:31 | 显示全部楼层
163 发表于 2016-1-8 12:21
噢。这样。

那是不是默认地图的像素比较多,而点相对稀疏一些?

这个没有说,应该是的,稀疏是想用hash么?
回复 支持 反对

使用道具 举报

163 发表于 2016-1-8 12:47:26 | 显示全部楼层
又见紫风铃 发表于 2016-1-8 12:25
这个没有说,应该是的,稀疏是想用hash么?

hash也不够快,因为原问题的精髓应该是说,矩阵是 O(n^2)个像素,然而点的总个数k 远远小于 n^2,但同时你发起inquiry的矩阵内的点的个数又是远远小于k的。在这些前提下,希望最终的运算量能够和所求矩阵内点的个数相关,而不是和k线性相关或者和n线性相关(或者更糟糕)。

我想了一下,我不认为他说的那种一个大方块四个小方块的数据结构是最好的,一个极端的例子是,假设矩阵是 1024x1024的,然后我现在就问 1x1024这个长条内有多少个点。按照他那种数据结构,估计得大概~1024的运算量。

我认为处理这个题最好的方法是用一维线段树和自身的笛卡尔积。简单来说是这样的,比如你矩阵的size是16x16,然后呢他的方法是存了这些node:. 1point3acres.com/bbs
16x16, 4个 8x8, 16个4x4, 64个 2x2, 256个1x1
. From 1point 3acres bbs
这导致如果要计算某个16x1的长方形内的点的个数,就傻逼了

我认为需要存这些node:
(1个16,2个8,4个4,8个2,16个1)x(1个16,2个8,4个4,8个2,16个1)
中间那个x号就是笛卡尔积,这是什么意思呢?意思是:
. Waral 鍗氬鏈夋洿澶氭枃绔,存1个16x16
2个16x8
2个8x16
4个8x8
4个16x4
4个4x16
...

这样的话存储空间和初始化的计算复杂度会由O(n^2 log n) 上涨到 O(n^2 (log n)^2),不过归根结底也就是多了一个log factor而已,无所谓
好处是显而易见的,当你询问某些非常瘦或者非常扁的矩形的时候,新的这种结构会给你更快的结果。
回复 支持 反对

使用道具 举报

 楼主| 又见紫风铃 发表于 2016-1-8 13:18:31 | 显示全部楼层
163 发表于 2016-1-8 12:47
hash也不够快,因为原问题的精髓应该是说,矩阵是 O(n^2)个像素,然而点的总个数k 远远小于 n^2,但同时 ...

可能我没有解释清楚,16*16的矩阵并咩有存256个1*1,这个数据结构只存地图里的点,而不管矩阵的pixel。
比如root结点是坐标(x0, y0),那么它的四个子树里分别是
1. (x1, y1) for x1 < x0, y1 > y0,即该点的左上方的所有点(注意是地图里需要求的点,而不是矩阵的所有的pixel)
2. (x2, y2) for x2 > x0, y2 > y0,即该点右上方的所有点
3. ...该点左下方的所有点
4. ...该点右下方的所有点
回复 支持 反对

使用道具 举报

 楼主| 又见紫风铃 发表于 2016-1-8 13:19:26 | 显示全部楼层
163 发表于 2016-1-8 12:47-google 1point3acres
hash也不够快,因为原问题的精髓应该是说,矩阵是 O(n^2)个像素,然而点的总个数k 远远小于 n^2,但同时 ...

而我所说的n指的是地图上点的个数,而不是矩阵的边长pixel个数

补充内容 (2016-1-8 13:20):
也就是要以比O(n)快的方式(比遍历所有点快的方式)找出哪些点是在给定区域内的
回复 支持 反对

使用道具 举报

163 发表于 2016-1-8 13:34:11 | 显示全部楼层
又见紫风铃 发表于 2016-1-8 13:18
可能我没有解释清楚,16*16的矩阵并咩有存256个1*1,这个数据结构只存地图里的点,而不管矩阵的pixel。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
...

咱们就统一以n表示边长好了,否则一会整不好还要用sqrt(n)这种东西
. from: 1point3acres.com/bbs
现在就假设是1024x1024的,n=1024
然后点的坐标范围是 [1,1024] x [1,1024]
我就问,如果我问矩阵{1} x [1,1024]内有哪些点,你怎么求?
回复 支持 反对

使用道具 举报

163 发表于 2016-1-8 13:35:31 | 显示全部楼层
又见紫风铃 发表于 2016-1-8 13:19
而我所说的n指的是地图上点的个数,而不是矩阵的边长pixel个数

补充内容 (2016-1-8 13:20):

我的point是,现在矩阵有 n^2个位置,
那个人给你的面积树的方法的worst case是O(n)的,我感觉很一般
我有worst case 是 O( (log n)^2 + t)的算法,其中 t 是矩阵内点的个数 (这个因为要输出t个点,是不可避免的)
回复 支持 反对

使用道具 举报

Gianluigi 发表于 2016-1-9 03:11:15 | 显示全部楼层
应该用 2D segment tree 吧。每个节点存一个 vector,是它这个方块内所有点的集合。
回复 支持 反对

使用道具 举报

no.9 发表于 2016-1-14 16:21:42 | 显示全部楼层
楼主是refer的吗?一直想投这个公司但是不知道海投会不会有人理。
回复 支持 反对

使用道具 举报

 楼主| 又见紫风铃 发表于 2016-1-14 20:44:18 | 显示全部楼层
no.9 发表于 2016-1-14 16:21.鐣欏璁哄潧-涓浜-涓夊垎鍦
楼主是refer的吗?一直想投这个公司但是不知道海投会不会有人理。

我是网上海投的,第二天就被recruiter联系了,也是很神奇
回复 支持 反对

使用道具 举报

no.9 发表于 2016-1-15 02:28:07 | 显示全部楼层
又见紫风铃 发表于 2016-1-14 20:44.鐣欏璁哄潧-涓浜-涓夊垎鍦
我是网上海投的,第二天就被recruiter联系了,也是很神奇
. from: 1point3acres.com/bbs
嗯,Thx~
回复 支持 反对

使用道具 举报

2015fallcser 发表于 2016-1-24 08:33:55 | 显示全部楼层
这这这  怕怕的   
P家感觉就没见过谁去实习。。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 03:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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