palantir 电面合集

原帖地址:一亩三分地

http://www.mitbbs.com/article_t/JobHunting/32674339.htmlPhone:求两个List的交集,假设每个list中的interval都是disjoint的。
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
4)猜字游戏,有一个board和dictionary,从一个字符出发,你被允许走8个方向。如果已经有了以下method,isWord(String str)和isPrefix(String str)。你怎么把所有的词打印出来。你可以假设解法唯一。Hint: BFS
http://www.mitbbs.com/article_t/JobHunting/32672247.html
有一个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),不符合要求~
谢谢大家指教!http://www.mitbbs.com/article_t/Recommend/31369185.html
1.(a) 一个大的脚本文件里有很多测试的时间戳(可能是混乱的),怎么设计算法和数据结构返回测试用的时间。比如:
2011-01-01 13:49:12 Test started2011-01-01 13:50:33 Test ended
返回 myData.timeTaken(“Test”) => 81
(b) 在(a)的基础上,如果有多套测试,怎么设计。比如:
2011-01-01 13:49:12 MyTests.SimpleTests.TestA started2011-01-01 13:51:33 MyTests.SimpleTests.TestA ended2011-01-01 13:51:36 MyTests.SimpleTests.TestB started2011-01-01 13:51:45 MyTests.SimpleTests.TestB ended2011-01-01 13:52:00 MyTests.QuickTests.Test1 started2011-01-01 13:52:03 MyTests.QuickTests.Test1 ended
应该返回
myData.timeTaken(“SimpleTests”) => 141 + 9 => 150myData.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,回头上面经。http://www.mitbbs.com/article_t/Recommend/31366829.htmlhttp://www.mitbbs.com/article_t/JobHunting/31963843.html finbonaci number,是前三个数的和而不是两个;写代码;改进;logn算法 range sum query,array,给[i,j]算区间内元素和,给出不同的space/time complexity组合,在提示下给出一个n^1/2 space/time complexity的算法 同上,现在的数组是2维,给出一个O(n^2) time/space complexity的预处理方法,然后是一个O(1)的query 最后一个设计题,一个目录下面有别的目录和source file,要把所有的source file的一个name替换,考regular expression,然后修改的时候要备份所有文件 Give traversal of a treemerge intervalshttp://ace-interview-questions.com/Palantir+Technologies/interview+questionshttp://www.quora.com/What-is-the-interview-process-like-at-Palantirhttps://www.quora.com/What-are-good-questions-to-ask-a-Palantir-interviewerhttp://ace-interview-questions.com/Palantir+Technologies/interview+questions