一亩三分地论坛

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

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

[找工就业] Palantir onsite被虐记

[复制链接] |试试Instant~ |关注本帖
cjqhenry 发表于 2015-3-24 09:33:56 | 显示全部楼层 |阅读模式

2015(7-9月)-[14]CS硕士+fresh grad 无实习/全职 - 内推| 码农类实习@fresh grad应届毕业生

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

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

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

四轮面试,每轮一个小时。
第一轮,求一个string list的每个string对应的unique prefix,返回也是一个list。我用Trie解决,建Trie、查找写了半个大黑板。面试官觉得很好。
第二轮,简单来说就是求2个数组的交集,然后follow up,变形的奇奇怪怪,现在都不知道他要干什么,很麻烦,弄了半天没怎么弄懂,然后时间到了。.鏈枃鍘熷垱鑷1point3acres璁哄潧
第三轮,求数组都最长等差数列(要求连续),follow up 可以不连续,这里答得不太好,直接暴力做了- -
第四轮,求一些区间的相交次数最多的任意一点。因为一开始是区间是int类型,我直接开了个数组,每读取一个区间就++,然后求数组最大的点就行了。follow up区间是float类型,之前方法明显不行,后来先按区间的start排序,然后每次比较end,好麻烦感觉,弄了半天没符合他的要求。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
半个小时后接到电话说跪了,4-6个月后再投。。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
Palantir的NYC做的主要都是些数据可视化,演示demo的时候看了下感觉就是个网页版的word,能够满足不同的数据显示的要求。
工作环境很好,很轻松,午饭也不错,吃喝免费。
找实习差不多了,从了amazon。。也祝大家好运:)

评分

5

查看全部评分

旋转时空 发表于 2015-3-24 09:47:54 | 显示全部楼层
我也是今天去面的!
.1point3acres缃看好多会议室里都是面试。。。说不定擦肩而过啊~~~
都没给我show demo。。。直接问我拿product能做什么也是跪了。。。
不知道是不是ft的原因,非Dev的流程貌似更麻烦。。HR说我即使通过这个onsite起码还有两轮QAQ
回复 支持 反对

使用道具 举报

 楼主| cjqhenry 发表于 2015-3-24 09:51:19 | 显示全部楼层
旋转时空 发表于 2015-3-24 09:47
我也是今天去面的!
看好多会议室里都是面试。。。说不定擦肩而过啊~~~
都没给我show demo。 ...

确实面试的挺多,你还有机会,good luck
回复 支持 反对

使用道具 举报

zlxwd 发表于 2015-3-24 12:46:57 | 显示全部楼层
3(1) 记录前两个数字的差,以及到上一个数字为止的最长等差数列。单遍扫描。. visit 1point3acres.com for more.
(2) DP, dp[i][j]为最后两个数字为X(i)和X(j)的等差数列最大长度,O(N^3),不知道能不能优化到N^2?
. 鍥磋鎴戜滑@1point 3 acres4. float类型可以对所有端点排序,然后把float值按照大小转为整数1,2,3,4...,然后套用follow up之前的思路。
回复 支持 反对

使用道具 举报

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

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

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

CASES:. 鍥磋鎴戜滑@1point 3 acres

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.1point3acres缃
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. -google 1point3acres
  3. #ifdef ONLINE_JUDGE
  4. #define FINPUT(file) 0
  5. #define FOUTPUT(file) 0.鏈枃鍘熷垱鑷1point3acres璁哄潧
  6. #else
  7. #define FINPUT(file) freopen(file,"r",stdin)
  8. #define FOUTPUT(file) freopen(file,"w",stdout)
  9. #endif

  10. #include <iostream>
    . Waral 鍗氬鏈夋洿澶氭枃绔,
  11. #include <cstdio>
  12. #include <cstring>
  13. #include <cstdlib>
  14. #include <cmath>. 鍥磋鎴戜滑@1point 3 acres
  15. #include <ctime>
  16. #include <set>
  17. #include <stack>
  18. #include <string>
  19. #include <map>
  20. #include <vector>
  21. #include <queue>
  22. #include <algorithm>
  23. #include <functional>
  24. #include <bitset>

  25. typedef long long ll;
  26. typedef long double ld;
  27. static const int N = 110;
  28. static const int M = 2010;.1point3acres缃
  29. static const int LEN = 50;
    . 1point 3acres 璁哄潧
  30. static const int MAX = 0x7fffffff;
  31. static const int GMAX = 0x3f3f3f3f;
  32. static const ll LGMAX = 0x3f3f3f3f3f3f3f3f;
  33. static const int MIN = ~MAX;
  34. static const double EPS = 1e-9;
  35. static const ll BASE = 1000000007;
  36. static const int CH = 258;

  37. int arr[N];
  38. int dp[N][M];. 1point3acres.com/bbs

  39. void solve(int n)
  40. {
  41.     int ans = -1;. visit 1point3acres.com for more.
  42.     for (int i = 0; i < n; ++i) {
  43.         for (int j = 0; j < i; ++j) {
  44.             dp[i][arr[i] - arr[j] + 1000] = std::max(dp[i][arr[i] - arr[j] + 1000],.鐣欏璁哄潧-涓浜-涓夊垎鍦
  45.                                               dp[j][arr[i] - arr[j] + 1000] + 1);. more info on 1point3acres.com
  46.             ans = std::max(ans,dp[i][arr[i] - arr[j] + 1000]);
  47.         }

  48.     }.1point3acres缃
  49.     printf("%d\n", ans + 1);

  50.     memset(dp, 0, sizeof(dp));
  51. }-google 1point3acres

  52. int main()
  53. {
  54.     FINPUT("in.txt");. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  55.     FOUTPUT("out.txt");

  56.     int n;
  57.     while (scanf("%d", &n) != EOF) {
  58.         for (int i = 0; i < n; ++i) {
  59.             scanf("%d", &arr[i]);
  60.         }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  61. . 鍥磋鎴戜滑@1point 3 acres
  62.         solve(n);
  63.     }

  64.     return 0;
  65. }
复制代码
回复 支持 反对

使用道具 举报

robinho364 发表于 2015-3-24 14:24:30 | 显示全部楼层
zlxwd 发表于 2015-3-24 12:46. From 1point 3acres bbs
3(1) 记录前两个数字的差,以及到上一个数字为止的最长等差数列。单遍扫描。
(2) DP, dp[j]为最后两个数字 ...

Hi,我似乎找到一个讨论贴:

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

我的方法有局限性,如果两个数字之差太大,就会有问题,等于是要hash。帖子里TenaliRaman的方法不会有问题,因为他只是不断的找a+b = 2b里的b。
. From 1point 3acres bbs
我整理一下思路:

这题本意上是要求我们找到任意的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
回复 支持 反对

使用道具 举报

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

抱歉哈,之前理解错你的意思了,O(n^2)的解法在上面的链接帖子里哈。
回复 支持 反对

使用道具 举报

zlxwd 发表于 2015-3-24 22:34:51 | 显示全部楼层
robinho364 发表于 2015-3-24 14:24
Hi,我似乎找到一个讨论贴:-google 1point3acres

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. . 鍥磋鎴戜滑@1point 3 acres
  4. public class Test {

  5.     private static int maxLen;

  6.     private static void update(Map<Integer, Integer> dp, int diff, int len) {
  7.         if (!dp.containsKey(diff) || dp.get(diff) < len) {
  8.             dp.put(diff, len);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  9.             maxLen = Math.max(maxLen, len);. From 1point 3acres bbs
  10.         }
  11.     }

  12.     private static int solve(int[] input) {
  13.         if (input == null) {
  14.             return 0;. 1point3acres.com/bbs
  15.         } else if (input.length <= 2) {
  16.             return input.length;
  17.         }

  18.         maxLen = 0;

  19.         int N = input.length;
  20.         Map<Integer, Map<Integer, Integer>> dp = new HashMap<Integer, Map<Integer, Integer>>();-google 1point3acres
  21.         for (int i = 0; i < N; ++i) {
  22.             dp.put(i, new HashMap<Integer, Integer>());
  23.         }
  24.         for (int i = 1; i < N; ++i) {
  25.             for (int j = 0; j < i; ++j) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  26.                 int diff = input[i] - input[j];
  27.                 if (dp.get(j).containsKey(diff)) {
  28.                     update(dp.get(i), diff, dp.get(j).get(diff) + 1);
  29.                 } else {
  30.                     update(dp.get(i), diff, 2);. 1point 3acres 璁哄潧
  31.                 }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  32.             }
  33.         }

  34.         return maxLen;
  35.     }

  36.     public static void main(String[] args) {
  37.         int[] arr = new int[] { 1, 3, 5, 10, 10, 7, 2, 4, 1, -2 };
  38.         System.out.println(solve(arr));.鐣欏璁哄潧-涓浜-涓夊垎鍦
  39.     }
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
  40. }
复制代码
回复 支持 反对

使用道具 举报

giddens9527 发表于 2015-3-25 04:30:20 | 显示全部楼层
我是上周四面的 到现在都没收到结果。。。
回复 支持 反对

使用道具 举报

shawlin 发表于 2015-3-25 04:55:16 | 显示全部楼层
robinho364 发表于 2015-3-24 01:26
抱歉哈,之前理解错你的意思了,O(n^2)的解法在上面的链接帖子里哈。

能否说一下第三题的思路呢?
回复 支持 反对

使用道具 举报

shawlin 发表于 2015-3-25 04:56:56 | 显示全部楼层
LZ能不能说下第四题,没读懂题呢?感觉像 merge interval / insert interval 变种?
回复 支持 反对

使用道具 举报

 楼主| cjqhenry 发表于 2015-3-25 05:39:42 | 显示全部楼层
shawlin 发表于 2015-3-25 04:56-google 1point3acres
LZ能不能说下第四题,没读懂题呢?感觉像 merge interval / insert interval 变种?

就是[1,7]、[2,8]、[0, 3]这个三个区间,[2,3]重合的次数最多。
回复 支持 反对

使用道具 举报

GTmac 发表于 2015-3-25 09:49:32 | 显示全部楼层
第四个interval start就+1,interval end就-1,然后对所有端点排序就行了
回复 支持 反对

使用道具 举报

robinho364 发表于 2015-3-25 10:19:41 | 显示全部楼层
shawlin 发表于 2015-3-25 04:55
能否说一下第三题的思路呢?

思路在之前的帖子里哈。

Hi,我似乎找到一个讨论贴:
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
https://www.ocf.berkeley.edu/~ww ... play;num=1247162214

我的方法有局限性,如果两个数字之差太大,就会有问题,等于是要hash。帖子里TenaliRaman的方法不会有问题,因为他只是不断的找a+b = 2b里的b。
. more info on 1point3acres.com
我整理一下思路:

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

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

这里还有一篇Jeff的分析:
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
http://web.engr.illinois.edu/~jeffe/pubs/pdf/arith.pdf


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

hash的方法。也就是我的方法,前面那位同学也是hash的方法。也就是说用dp[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] = dp[j] + 1,其中dp[k],代表这个等差数列的前两个数字分别为index k和index i。总的来说这种解法还是非常巧妙的,里面有一些细节。

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

补充内容 (2015-3-25 10:22):
公式被吞了。
dp[k] = dp[j] + 1,其中dp[k],代表这个等差数列的前两个数字分别为index k和index i。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
.1point3acres缃
补充内容 (2015-3-25 10:23):
貌似打不出来二维的……
dp[k] = dp [j] + 1,其中dp[k] ,代表这个等差数列的前两个数字分别为index k和index i。.1point3acres缃

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

使用道具 举报

 楼主| cjqhenry 发表于 2015-3-25 10:20:15 | 显示全部楼层
GTmac 发表于 2015-3-25 09:49. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第四个interval start就+1,interval end就-1,然后对所有端点排序就行了

拍完序选个中位数是不是就行了?
回复 支持 反对

使用道具 举报

shawlin 发表于 2015-3-25 10:39:57 | 显示全部楼层
GTmac 发表于 2015-3-24 20:49
第四个interval start就+1,interval end就-1,然后对所有端点排序就行了

没理解啊,能不能细说下?
回复 支持 反对

使用道具 举报

robinho364 发表于 2015-3-25 21:04:39 | 显示全部楼层
shawlin 发表于 2015-3-25 10:39
没理解啊,能不能细说下?

我的理解:.鏈枃鍘熷垱鑷1point3acres璁哄潧

给出n个区间,求被共享最多的子区间。

按照lz的例子:
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
[1,7]、[2,8]、[0, 3].1point3acres缃

. 1point 3acres 璁哄潧   1 2 3 4 5 6 7 8 9
      2 3 4 5 6 7 8
0  1 2 3

重叠最多的就是[2, 3]。

其实第二小问浮点数和第一小问本质上是一样的,考的都是离散化的思想。因为实际上如果区间的端点值太大([a, b],a = 0, b = IntegerMax),直接数数的方法一样没法做。

除了离散化以外,如果要求复杂度较低。还需要建一颗线段树(带lazy tag,每次更新时将对应区间的值+1,其实可以理解为将多个点的值+1),这样每次插入的复杂度是logn。每次查询也是logn。

补充内容 (2015-3-25 21:08):.鐣欏璁哄潧-涓浜-涓夊垎鍦
代码估计有点长,如果需要的话我给你个链接呗。
回复 支持 反对

使用道具 举报

shawlin 发表于 2015-3-25 23:36:22 | 显示全部楼层
robinho364 发表于 2015-3-24 21:19
思路在之前的帖子里哈。

谢谢啦,看懂了,很tricky的DP, 等差序列的性质还给中学老师啦 哈哈
回复 支持 反对

使用道具 举报

shawlin 发表于 2015-3-25 23:52:58 | 显示全部楼层
robinho364 发表于 2015-3-25 08:04
我的理解:

给出n个区间,求被共享最多的子区间。

建一个interval search tree? 再次感谢,求个代码链接-google 1point3acres
我的思路是 每一个interval 对应一个字符 比如. more info on 1point3acres.com
[0, 3] : A  [1, 7] : B, [2, 8] : C . From 1point 3acres bbs
给interval排序
然后用leetcode  merge interval的思路, merge的结果为
[0, 1] : A
[1, 2] : AB
[2, 3] : ABC
[3, 7] : BC
[7, 8] : B
选出一个对应最长字符串的interval?就是[2,3] 不知道行不行哈,欢迎讨论. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
回复 支持 反对

使用道具 举报

robinho364 发表于 2015-3-26 00:26:36 | 显示全部楼层
shawlin 发表于 2015-3-25 23:52. from: 1point3acres.com/bbs
建一个interval search tree? 再次感谢,求个代码链接
我的思路是 每一个interval 对应一个字符 比如. visit 1point3acres.com for more.
[ ...

http://ideone.com/kqntG3
.1point3acres缃
您好。. from: 1point3acres.com/bbs

我没有刷过leetcode,所以这种题一般都是惯性思维了。

能不能给个链接呢?看起来很精妙的样子。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 08:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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