May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 3994|回复: 29
收起左侧

[找工就业] Palantir onsite被虐记

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
今天去NYC的office面试,中午先一起和他们吃饭,一个白人小哥接待我。小哥貌似不善言谈,me too,所以略微尴尬,问了一堆问题,然后他没事还老盯着我。。。。实在是。。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
四轮面试,每轮一个小时。
第一轮,求一个string list的每个string对应的unique prefix,返回也是一个list。我用Trie解决,建Trie、查找写了半个大黑板。面试官觉得很好。
第二轮,简单来说就是求2个数组的交集,然后follow up,变形的奇奇怪怪,现在都不知道他要干什么,很麻烦,弄了半天没怎么弄懂,然后时间到了。. From 1point 3acres bbs
第三轮,求数组都最长等差数列(要求连续),follow up 可以不连续,这里答得不太好,直接暴力做了- -
第四轮,求一些区间的相交次数最多的任意一点。因为一开始是区间是int类型,我直接开了个数组,每读取一个区间就++,然后求数组最大的点就行了。follow up区间是float类型,之前方法明显不行,后来先按区间的start排序,然后每次比较end,好麻烦感觉,弄了半天没符合他的要求。
. Waral 鍗氬鏈夋洿澶氭枃绔,
半个小时后接到电话说跪了,4-6个月后再投。。

Palantir的NYC做的主要都是些数据可视化,演示demo的时候看了下感觉就是个网页版的word,能够满足不同的数据显示的要求。
工作环境很好,很轻松,午饭也不错,吃喝免费。. 鍥磋鎴戜滑@1point 3 acres
找实习差不多了,从了Amazon。。也祝大家好运:)

评分

5

查看全部评分

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

使用道具 举报

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

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

使用道具 举报

zlxwd 发表于 2015-3-24 12:46:57 | 显示全部楼层
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之前的思路。
回复 支持 反对

使用道具 举报

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

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

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

CASES:

8.1point3acres缃
1 3 5 2 3 5 7 8
8
1 5 4 3 2 1 0 2
8. from: 1point3acres.com/bbs
9 4 12 15 3 2 1 8
8
1 2 4 3 6 8 9 10 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
8. Waral 鍗氬鏈夋洿澶氭枃绔,
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. #ifdef ONLINE_JUDGE
  3. #define FINPUT(file) 0
  4. #define FOUTPUT(file) 0. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  5. #else
  6. #define FINPUT(file) freopen(file,"r",stdin)
  7. #define FOUTPUT(file) freopen(file,"w",stdout)
  8. #endif-google 1point3acres

  9. #include <iostream>. visit 1point3acres.com for more.
  10. #include <cstdio>
  11. #include <cstring>. Waral 鍗氬鏈夋洿澶氭枃绔,
  12. #include <cstdlib>. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  13. #include <cmath>-google 1point3acres
  14. #include <ctime>
  15. #include <set>
  16. #include <stack>
  17. #include <string>
  18. #include <map>. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  19. #include <vector>
  20. #include <queue>
  21. #include <algorithm>.鐣欏璁哄潧-涓浜-涓夊垎鍦
  22. #include <functional>
  23. #include <bitset>

  24. typedef long long ll;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  25. typedef long double ld;
  26. static const int N = 110;
  27. static const int M = 2010;
  28. static const int LEN = 50;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  29. static const int MAX = 0x7fffffff;. Waral 鍗氬鏈夋洿澶氭枃绔,
  30. static const int GMAX = 0x3f3f3f3f;
  31. static const ll LGMAX = 0x3f3f3f3f3f3f3f3f;
  32. static const int MIN = ~MAX;. more info on 1point3acres.com
  33. static const double EPS = 1e-9;
  34. static const ll BASE = 1000000007;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  35. static const int CH = 258;

  36. int arr[N];
  37. int dp[N][M];. 鍥磋鎴戜滑@1point 3 acres

  38. void solve(int n). more info on 1point3acres.com
  39. {
  40.     int ans = -1;. more info on 1point3acres.com
  41.     for (int i = 0; i < n; ++i) {
  42.         for (int j = 0; j < i; ++j) {
  43.             dp[i][arr[i] - arr[j] + 1000] = std::max(dp[i][arr[i] - arr[j] + 1000],
  44.                                               dp[j][arr[i] - arr[j] + 1000] + 1);
  45.             ans = std::max(ans,dp[i][arr[i] - arr[j] + 1000]);
  46.         }
  47. .1point3acres缃
  48.     }
  49.     printf("%d\n", ans + 1);

  50.     memset(dp, 0, sizeof(dp));
  51. }

  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]);. more info on 1point3acres.com
  60.         }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

  61.         solve(n);
  62.     }

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

使用道具 举报

robinho364 发表于 2015-3-24 14:24:30 | 显示全部楼层
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。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我整理一下思路:. 1point 3acres 璁哄潧

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

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

这里还有一篇Jeff的分析:. from: 1point3acres.com/bbs

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]为最后两个数字 ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
抱歉哈,之前理解错你的意思了,O(n^2)的解法在上面的链接帖子里哈。
回复 支持 反对

使用道具 举报

zlxwd 发表于 2015-3-24 22:34:51 | 显示全部楼层
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;
    .鏈枃鍘熷垱鑷1point3acres璁哄潧

  3. public class Test { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

  4.     private static int maxLen;

  5.     private static void update(Map<Integer, Integer> dp, int diff, int len) {
  6.         if (!dp.containsKey(diff) || dp.get(diff) < len) {
  7.             dp.put(diff, len);.1point3acres缃
  8.             maxLen = Math.max(maxLen, len);
  9.         }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  10.     }

  11.     private static int solve(int[] input) {
  12.         if (input == null) {
  13.             return 0;
  14.         } else if (input.length <= 2) {
  15.             return input.length;
  16.         }
  17. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  18.         maxLen = 0;

  19.         int N = input.length;
  20.         Map<Integer, Map<Integer, Integer>> dp = new HashMap<Integer, Map<Integer, Integer>>();
  21.         for (int i = 0; i < N; ++i) {
  22.             dp.put(i, new HashMap<Integer, Integer>());
  23.         }. 1point3acres.com/bbs
  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);. Waral 鍗氬鏈夋洿澶氭枃绔,
  31.                 }
  32.             }
  33.         }-google 1point3acres

  34.         return maxLen;
  35.     }. 1point3acres.com/bbs

  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)的解法在上面的链接帖子里哈。
. more info on 1point3acres.com
能否说一下第三题的思路呢?
回复 支持 反对

使用道具 举报

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
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,我似乎找到一个讨论贴:
. more info on 1point3acres.com
https://www.ocf.berkeley.edu/~ww ... play;num=1247162214 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

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

我整理一下思路:.鐣欏璁哄潧-涓浜-涓夊垎鍦

这题本意上是要求我们找到任意的indices,要求i0<i1<ik。
如果不局限于i0<i1...<ik,那也可以用TenaliRaman的方法,但是用我的方法就不对了。我的方法本质上等同于miletus的方法。
.1point3acres缃
因此,我们在不局限于i0<i1...<ik,可以用TenaliRaman的dynamic programming方法达到O(n^2)的复杂度,并且没有存储空间的限制。

这里还有一篇Jeff的分析:. 1point3acres.com/bbs

http://web.engr.illinois.edu/~jeffe/pubs/pdf/arith.pdf
-google 1point3acres

就是说这题有两种形式,一种是在序列里找等差数列——不可以打乱顺序,一种是在集合里找等差数列——可以打乱顺序。两者都是不连续的。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
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。

补充内容 (2015-3-25 10:23):. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
貌似打不出来二维的……
dp[k] = dp [j] + 1,其中dp[k] ,代表这个等差数列的前两个数字分别为index k和index i。

补充内容 (2015-3-25 10:23):
醉了. more info on 1point3acres.com
dp[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
没理解啊,能不能细说下?

我的理解:

给出n个区间,求被共享最多的子区间。. Waral 鍗氬鏈夋洿澶氭枃绔,

按照lz的例子:

[1,7]、[2,8]、[0, 3]. from: 1point3acres.com/bbs

   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),直接数数的方法一样没法做。.1point3acres缃

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

补充内容 (2015-3-25 21:08):
代码估计有点长,如果需要的话我给你个链接呗。
回复 支持 反对

使用道具 举报

shawlin 发表于 2015-3-25 23:36:22 | 显示全部楼层
robinho364 发表于 2015-3-24 21:19
思路在之前的帖子里哈。
. more info on 1point3acres.com
谢谢啦,看懂了,很tricky的DP, 等差序列的性质还给中学老师啦 哈哈
回复 支持 反对

使用道具 举报

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

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

建一个interval search tree? 再次感谢,求个代码链接
我的思路是 每一个interval 对应一个字符 比如
[0, 3] : A  [1, 7] : B, [2, 8] : C
给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
建一个interval search tree? 再次感谢,求个代码链接
我的思路是 每一个interval 对应一个字符 比如
[ ...

http://ideone.com/kqntG3. from: 1point3acres.com/bbs

您好。

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

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-25 13:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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