一亩三分地论坛

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

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

palantir 电面合集

[复制链接] |试试Instant~ |关注本帖
mm豆 发表于 2015-6-2 09:34:32 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Palantir - 网上海投 - 技术电面 |Failfresh grad应届毕业生

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

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

x
http://www.mitbbs.com/article_t/JobHunting/32674339.html
Phone:
求两个List<Interval>的交集,假设每个list中的interval都是disjoint的。
. From 1point 3acres bbs
onsite:
1)给你一个list的字符串,找出一个list的prefix,从而可以uniquely identify每个
字符串。
Hint:此题可以用trie来解决

2)给你一棵树,implement一个iterator,可以是BFS或者DFS。要求用iterative
method来实现。
Hint:选择DFS
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
3)压缩算法。用树的变形来表示一个string,比如 B->left = A, B->right = A, 此
种情况我们可以把B的left, right同时指向A。
问题1)对于一个有n个节点的树,可以表示的最长string的长度
问题2)implement get(Tree t, int position),返回这个字符串在position的字符。
Hint:exponential + binary search
. visit 1point3acres.com for more.
4)猜字游戏,有一个board和dictionary,从一个字符出发,你被允许走8个方向。如果
已经有了以下method,
isWord(String str)和isPrefix(String str)。你怎么把所有的词打印出来。你可以假
设解法唯一。
Hint: BFS


有一个binary directed acyclic graph, 每个node存有一个字符,有一个左节点和一
个右节点。
(node定义如下:
Node {   
Node L;
Node R;
char ch;
}

这样如果in-order traverse这个DAG,就会得到一个string。例子如下:假设一个DAG
只有两个node,分别装着A和B这两个字符。假设Node A的左右两条边都指向Node B:
A (root node)
||
B
那么这个存储的string就是BAB

现在假设已经有了一个这样的DAG, 请写一个函数,返回这个string的第k个字符。要求
复杂度不能是exponential的。。。

我先写了个in order 的遍历。面试官就问我如果n个node,string最长可以是多少
我觉得是2^n-1
面试官说,那么traverse的话最坏情况复杂度就是O(2^n),不符合要求~

谢谢大家指教!

1.(a) 一个大的脚本文件里有很多测试的时间戳(可能是混乱的),怎么设计算法和数
据结构返回测试用的时间。比如:

2011-01-01 13:49:12 Test started
2011-01-01 13:50:33 Test ended
.鏈枃鍘熷垱鑷1point3acres璁哄潧
返回 myData.timeTaken("Test") => 81

(b) 在(a)的基础上,如果有多套测试,怎么设计。比如:

2011-01-01 13:49:12 MyTests.SimpleTests.TestA started
2011-01-01 13:51:33 MyTests.SimpleTests.TestA ended
2011-01-01 13:51:36 MyTests.SimpleTests.TestB started
2011-01-01 13:51:45 MyTests.SimpleTests.TestB ended
2011-01-01 13:52:00 MyTests.QuickTests.Test1 started
2011-01-01 13:52:03 MyTests.QuickTests.Test1 ended
. Waral 鍗氬鏈夋洿澶氭枃绔,
应该返回

myData.timeTaken("SimpleTests") => 141 + 9 => 150
myData.timeTaken("MyTests") => 141 + 9 + 3 => 153

2. 设计排序算法:sort a list of n numbers where each number is at most k
indices away, where k << n

就面了一轮电面,几天后收到email要求onsite,这里也求一下bless,回头上面经。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
finbonaci number,是前三个数的和而不是两个;写代码;改进;logn算法

range sum query,array,给[i,j]算区间内元素和,给出不同的
space/time
complexity组合,在提示下给出一个n^1/2 space/time complexity的算
. more info on 1point3acres.com
同上,现在的数组是2维,给出一个O(n^2) time/space complexity的预
处理方法,然
后是一个O(1)的query

最后一个设计题,一个目录下面有别的目录和source file,要把所有的
source file的
一个name替换,考regular expression,然后修改的时候要备份所有文件

Give traversal of a tree
merge intervals



. Waral 鍗氬鏈夋洿澶氭枃绔,

评分

4

查看全部评分

 楼主| mm豆 发表于 2015-6-2 22:33:01 | 显示全部楼层
完全版本,直接贴有字数限制

pal.pdf

103.09 KB, 下载次数: 101, 下载积分: 大米 -1 升

回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 07:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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