Palantir onsite被虐记

今天去NYC的office面试，中午先一起和他们吃饭，一个白人小哥接待我。小哥貌似不善言谈，me too，所以略微尴尬，问了一堆问题，然后他没事还老盯着我。。。。实在是。。

四轮面试，每轮一个小时。
第一轮，求一个string list的每个string对应的unique

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

demo的时候看了下感觉就是个网页版的word，能够满足不同的数据显示的要求。
工作环境很好，很轻松，午饭也不错，吃喝免费。
找实习差不多了，从了amazon。。也祝大家好运：）

robinho364 发表于 2015-3-24 14:24
Hi，我似乎找到一个讨论贴：

https://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddle ...

昨天想复杂了，在不改变顺序的前提下也可以达到N^2。

1. import java.util.HashMap;
   
2. import java.util.Map;
   
3. 
   
4. public class Test {
   
5. 
   
6.     private static int maxLen;
   
7. 
   
8.     private static void update(Map<Integer, Integer> dp, int diff, int len) {
   
9.         if (!dp.containsKey(diff) || dp.get(diff) < len) {
   
10.             dp.put(diff, len);
    
11.             maxLen = Math.max(maxLen, len);
    
12.         }
    
13.     }
    
14. 
    
15.     private static int solve(int[] input) {
    
16.         if (input == null) {
    
17.             return 0;
    
18.         } else if (input.length <= 2) {
    
19.             return input.length;
    
20.         }
    
21. 
    
22.         maxLen = 0;
    
23. 
    
24.         int N = input.length;
    
25.         Map<Integer, Map<Integer, Integer>> dp = new HashMap<Integer, Map<Integer, Integer>>();
    
26.         for (int i = 0; i < N; ++i) {
    
27.             dp.put(i, new HashMap<Integer, Integer>());
    
28.         }
    
29.         for (int i = 1; i < N; ++i) {
    
30.             for (int j = 0; j < i; ++j) {
    
31.                 int diff = input[i] - input[j];
    
32.                 if (dp.get(j).containsKey(diff)) {
    
33.                     update(dp.get(i), diff, dp.get(j).get(diff) + 1);
    
34.                 } else {
    
35.                     update(dp.get(i), diff, 2);
    
36.                 }
    
37.             }
    
38.         }
    
39. 
    
40.         return maxLen;
    
41.     }
    
42. 
    
43.     public static void main(String[] args) {
    
44.         int[] arr = new int[] { 1, 3, 5, 10, 10, 7, 2, 4, 1, -2 };
    
45.         System.out.println(solve(arr));
    
46.     }
    
47. }
    

复制代码

zlxwd 发表于 2015-3-24 12:46
3(1) 记录前两个数字的差，以及到上一个数字为止的最长等差数列。单遍扫描。
(2) DP, dp[j]为最后两个数字 ...

为什么要记录最后两个数字呢？

我只要记录两个数字的差不就可以了吗？

CASES:

8
1 3 5 2 3 5 7 8
8
1 5 4 3 2 1 0 2
8
9 4 12 15 3 2 1 8
8
1 2 4 3 6 8 9 10
8
1 1 1 1 1 1 1 1
15
1 3 5 3 17 2 38 310 3 4 3 5 6 2 3

1. #define _USE_MATH_DEFINES
   
2. 
   
3. #ifdef ONLINE_JUDGE
   
4. #define FINPUT(file) 0
   
5. #define FOUTPUT(file) 0
   
6. #else
   
7. #define FINPUT(file) freopen(file,"r",stdin)
   
8. #define FOUTPUT(file) freopen(file,"w",stdout)
   
9. #endif
   
10. 
    
11. #include <iostream>
    
12. #include <cstdio>
    
13. #include <cstring>
    
14. #include <cstdlib>
    
15. #include <cmath>
    
16. #include <ctime>
    
17. #include <set>
    
18. #include <stack>
    
19. #include <string>
    
20. #include <map>
    
21. #include <vector>
    
22. #include <queue>
    
23. #include <algorithm>
    
24. #include <functional>
    
25. #include <bitset>
    
26. 
    
27. typedef long long ll;
    
28. typedef long double ld;
    
29. static const int N = 110;
    
30. static const int M = 2010;
    
31. static const int LEN = 50;
    
32. static const int MAX = 0x7fffffff;
    
33. static const int GMAX = 0x3f3f3f3f;
    
34. static const ll LGMAX = 0x3f3f3f3f3f3f3f3f;
    
35. static const int MIN = ~MAX;
    
36. static const double EPS = 1e-9;
    
37. static const ll BASE = 1000000007;
    
38. static const int CH = 258;
    
39. 
    
40. int arr[N];
    
41. int dp[N][M];
    
42. 
    
43. void solve(int n)
    
44. {
    
45.     int ans = -1;
    
46.     for (int i = 0; i < n; ++i) {
    
47.         for (int j = 0; j < i; ++j) {
    
48.             dp[i][arr[i] - arr[j] + 1000] = std::max(dp[i][arr[i] - arr[j] + 1000],
    
49.                                               dp[j][arr[i] - arr[j] + 1000] + 1);
    
50.             ans = std::max(ans,dp[i][arr[i] - arr[j] + 1000]);
    
51.         }
    
52. 
    
53.     }
    
54.     printf("%d\n", ans + 1);
    
55. 
    
56.     memset(dp, 0, sizeof(dp));
    
57. }
    
58. 
    
59. int main()
    
60. {
    
61.     FINPUT("in.txt");
    
62.     FOUTPUT("out.txt");
    
63. 
    
64.     int n;
    
65.     while (scanf("%d", &n) != EOF) {
    
66.         for (int i = 0; i < n; ++i) {
    
67.             scanf("%d", &arr[i]);
    
68.         }
    
69. 
    
70.         solve(n);
    
71.     }
    
72. 
    
73.     return 0;
    
74. }
    

复制代码

shawlin 发表于 2015-3-25 04:55
能否说一下第三题的思路呢？

思路在之前的帖子里哈。

Hi，我似乎找到一个讨论贴：

https://www.ocf.berkeley.edu/~ww ... play;num=1247162214

我的方法有局限性，如果两个数字之差太大，就会有问题，等于是要hash。帖子里TenaliRaman的方法不会有问题，因为他只是不断的找a+b = 2b里的b。

我整理一下思路：

这题本意上是要求我们找到任意的indices，要求i0<i1<ik。
如果不局限于i0<i1...<ik，那也可以用TenaliRaman的方法，但是用我的方法就不对了。我的方法本质上等同于miletus的方法。

因此，我们在不局限于i0<i1...<ik，可以用TenaliRaman的dynamic programming方法达到O(n^2)的复杂度，并且没有存储空间的限制。

这里还有一篇Jeff的分析：

http://web.engr.illinois.edu/~jeffe/pubs/pdf/arith.pdf

就是说这题有两种形式，一种是在序列里找等差数列——不可以打乱顺序，一种是在集合里找等差数列——可以打乱顺序。两者都是不连续的。

hash的方法。也就是我的方法，前面那位同学也是hash的方法。也就是说用dp[i][j]，代表第i位的时候，相差为j的数的最长个数。

但是hash的限制就是两个数可能相差太大，数字可能很多。所以这题其实可以不用hash。在jeff的论文里详细阐明了这个思想。等差数列a_i+a_j=2b一定是个固定数字，那么我们从这个性质出发，可以找最长的序列。首先排序，每次假设a_i=b，如果a_(i) - a_(k)> a_(j) - a_(i)，那么需要将index j增大；反过来将index k减小。如果是=，那么正好找到一组对称，dp[k][i] = dp[i][j] + 1，其中dp[k][i]，代表这个等差数列的前两个数字分别为index k和index i。总的来说这种解法还是非常巧妙的，里面有一些细节。

具体的证明可以仔细参考jeff的论文。

补充内容 (2015-3-25 10:22):
公式被吞了。
dp[k][i] = dp[i][j] + 1，其中dp[k][i]，代表这个等差数列的前两个数字分别为index k和index i。

补充内容 (2015-3-25 10:23):
貌似打不出来二维的……
dp[k] [i] = dp[i] [j] + 1，其中dp[k] [i]，代表这个等差数列的前两个数字分别为index k和index i。

补充内容 (2015-3-25 10:23):
醉了
dp[k, i] = dp [i, j] + 1，其中dp[k, i] ，代表这个等差数列的前两个数字分别为index k和index i。

我也是今天去面的！
看好多会议室里都是面试。。。说不定擦肩而过啊～～～
都没给我ｓｈｏｗ　ｄｅｍｏ。。。直接问我拿ｐｒｏｄｕｃｔ能做什么也是跪了。。。
不知道是不是ｆｔ的原因，非Ｄｅｖ的流程貌似更麻烦。。ＨＲ说我即使通过这个ｏｎｓｉｔｅ起码还有两轮ＱＡＱ

旋转时空 发表于 2015-3-24 09:47
我也是今天去面的！
看好多会议室里都是面试。。。说不定擦肩而过啊～～～
都没给我ｓｈｏｗ　ｄｅｍｏ。 ...

确实面试的挺多，你还有机会，good luck

3(1) 记录前两个数字的差，以及到上一个数字为止的最长等差数列。单遍扫描。
(2) DP, dp[i][j]为最后两个数字为X(i)和X(j)的等差数列最大长度，O(N^3)，不知道能不能优化到N^2？
4. float类型可以对所有端点排序，然后把float值按照大小转为整数1，2，3，4...，然后套用follow up之前的思路。

zlxwd 发表于 2015-3-24 12:46
3(1) 记录前两个数字的差，以及到上一个数字为止的最长等差数列。单遍扫描。
(2) DP, dp[j]为最后两个数字 ...

Hi，我似乎找到一个讨论贴：

https://www.ocf.berkeley.edu/~ww ... play;num=1247162214

我的方法有局限性，如果两个数字之差太大，就会有问题，等于是要hash。帖子里TenaliRaman的方法不会有问题，因为他只是不断的找a+b = 2b里的b。

我整理一下思路：

这题本意上是要求我们找到任意的indices，要求i0<i1<ik。
如果不局限于i0<i1...<ik，那也可以用TenaliRaman的方法，但是用我的方法就不对了。我的方法本质上等同于miletus的方法。

因此，我们在不局限于i0<i1...<ik，可以用TenaliRaman的dynamic programming方法达到O(n^2)的复杂度，并且没有存储空间的限制。

这里还有一篇Jeff的分析：

http://web.engr.illinois.edu/~jeffe/pubs/pdf/arith.pdf

zlxwd 发表于 2015-3-24 12:46
3(1) 记录前两个数字的差，以及到上一个数字为止的最长等差数列。单遍扫描。
(2) DP, dp[j]为最后两个数字 ...

抱歉哈，之前理解错你的意思了，O(n^2)的解法在上面的链接帖子里哈。

我是上周四面的 到现在都没收到结果。。。

robinho364 发表于 2015-3-24 01:26
抱歉哈，之前理解错你的意思了，O(n^2)的解法在上面的链接帖子里哈。

能否说一下第三题的思路呢？