查看: 11259|回复: 71

[我这里要招人] 长期提供Rocket Fuel内推——实习和全职

[复制链接] |试试Instant~ |关注本帖
cpcs 发表于 2014-11-13 13:23:46 | 显示全部楼层 |阅读模式

2015(10-12月)-[13]CS博士+fresh grad 无实习/全职 - 内推| 码农类全职@Rocket Fuel


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

本帖最后由 北美农民 于 2014-12-3 18:35 编辑

. from: 1point3acres.com/bbs 因为码农比较多……sde的相关职位描述可以通过这个这个链接里"Apply now"申请。包括:(1) 校招 new grad
(2) 社招 senior
(3) 暑期实习 intern
如果需要其他职位招聘,例如PM、Operation等,欢迎站内联系或者给我发email, 我email: 529929033@qq.com. 1point3acres.com/bbs

补充内容 (2014-11-13 13:35):. from: 1point3acres.com/bbs

补充内容 (2014-11-13 23:15):
(1) GPA不是硬性指标 可以不用理
(2) 欢迎给我发邮件 我可以把某些职位的内推链接发到您邮箱
(3) 申请后我在系统能看到,欢迎写一个第三人称推荐理由发给我,我可以在系统内部add comments as the reference

. Waral 鍗氬鏈夋洿澶氭枃绔,
分享一个得到positive feedback的解题思路,代码就不贴了,因为邮件里面说rocket
fuel的engineer会code review

题目网上有,这个链接里面的第3题:http://get-that-job-at-google.bl ... -at-iit-bombay.html

首先题目里面给了一个提示:把所有的输入,按照start time均分为K个区间去处理. 1point3acres.com/bbs
. Waral 鍗氬鏈夋洿澶氭枃绔,
我的思路用sample input解释一下:.鏈枃鍘熷垱鑷1point3acres璁哄潧
2 100 200
3 110 190
4 105 145
1 90 150
5 102 198

1,所有的开始时间和结束时间没有重复的,对输入得到三元组<time, racer_id,

idx  time  r_id type   value/ret
0    90    1    start  0      +1
1    100   2    start  0                  +1
2    102   5    start  0              +1
3    105   4    start  0  +1
4    110   3    start  0          +1
5    145   4    end    0  *0.鐣欏璁哄潧-涓浜-涓夊垎鍦
6    150   1    end    0      *1
7    190   3    end    0          *0
8    198   5    end    0              *2
9    200   2    end    0                  *3

上图中+1表示value, *x表示ret

   2.1 当碰到标记为start的item时,记录racer_id对应的idx是多少:
       比如{"1":"0", "2":"1", "5":"3", "4":"3", "3":"4"}
   2.2 当碰到标记为end的item时,比如racer_id=4这一行,当前end_idx=5,做2件事
       找到racer_id=4对应start time的start_idx=3
       2.2.1 value[start_idx]++,也就是value[3]++. Waral 鍗氬鏈夋洿澶氭枃绔,
       2.2.2 对[start_idx + 1, end_idx]这个区间的value求和,就是racer_id=4的

3,对所有的结果按照题目要求排序即可. From 1point 3acres bbs

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴型的数据结构是线段树:http://en.wikipedia.org/wiki/Segment_tree 线段树比较好写,本质上就是个二叉树。


下周安排了skype interview,求rp!

http://www.meetqun.com/forum.php ... 2240&fromuid=12

Suppose you are a fan of auto-racing and want to figure out which drivers are likely to perform well in an upcoming race. Luckily you have access to a log of the times that each racer started and finished their test race the day before.
The particular rating algorithm you have chosen is to assign each racer R a score that equals the number of other racers who both started after R started and also finished before R finished.
Note that a lower score generally suggests that the racer is faster, and this rating algorithm keeps from penalizing fast racers who have slow times simply because they are stuck behind a crash or slow racer. Additionally, this rating algorithm does not reward fast racers who pass tons of slow racers in comparison to fast racers who race when there are not many slow racers on the track to pass (compare this with rating a racer based on the net number of passes).

More formally, you want to write a program that will read the test race log from standard input. The first line of the log contains a single integer n from 0 to 70,000 that represents the number of racers in the log. The next n lines of the test race log have the following format:

racerId startTime endTime-google 1point3acres
. from: 1point3acres.com/bbs
where racerId is an integer in the range [0,10^9] and startTime and endTime are both integers such that 0 <= startTime < endTime <= 10^18. Each racerId will be distinct. Also, the collection of all start and end times will not contain any duplicate elements.
-google 1point3acres
Given such an input, you should print output in the following format:

racerId score

where score is the score as defined above for racer racerId. The output lines should be sorted in ascending order ofscore with ties broken by sorting by racerId, also in ascending order. This can be accomplished with a simple sort at the end.

Please code this problem in Java, C, or C++. Your solution should run in less than O(N^2) on all inputs.. from: 1point3acres.com/bbs
Hint: The naive brute force solution is too slow to run within the time limit. You will need to think of a faster solution. Specifically, we are looking for a solution that is guaranteed to be less than O(N^2) on all inputs. One possible way to accomplish this (there are several other acceptable methods) is to use a data structure with K buckets (e.g., K = 300), each of which is initially empty and is defined by two times. Each bucket  will eventually contain racers whose start time falls between the two times. The bucket boundaries should be chosen such that they ultimately will contain the same number of racers. Then iterate through the racers in end time order and, as you iterate over each racer, build up this bucketed data structure in such a way that you can use it to quickly count the number of racers that finished before him but started after him.

What We Are Looking For:
For this problem, we simply want to see that you can implement the algorithm correctly, without particular regard to principles of object orientation or modularity.  Do give us at least minimal documentation to help us understand what you are trying to accomplish in certain key places of the algorithm.

Sample Testcases
input:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
2 100 200
3 110 190
4 105 145
1 90 150
5 102 198
output:. 1point3acres.com/bbs
3 0. 1point 3acres 璁哄潧
4 0
1 1
5 2
2 3

Note in the above example that racer 3 has a score of 0 because no one starts after racer 3 (a drawback to this scoring system is the last racer always has a score of 0). Racer 4 also has a score of 0 because the only racer who starts after racer 4's start time (racer 3) has a later finish time. Racer 3 is listed ahead of racer 4 despite having a slower time because racer 3's id is lower. At the other end, racer 2 has a score of 3 because racers 3, 4, and 5 start after racer 2 and finish before racer 2 finishes


简单的说就是每个车有一个[开始时间,结束时间] ,要计算对每辆车,有多少车比这辆车的开始时间晚,并且结束时间早。即,对每辆车算出这么一个数。题目还告诉我们所有时间都不相等。首先很容易想到按照开始时间逆序排序,我们按照开始时间的逆序一个一个考虑车。这样,已经考虑的车的开始时间全都比当前这个车晚,我们只看结束时间就行了。所以现在是按开始时间递减的顺序分别考虑每辆车的结束时间。

.1point3acres缃还有另外一招——叫做离散化。因为题目给的时间范围高达10^18,真的有必要那么大么?因为只有n个数,我们考虑的是这n个数的大小——或者说画在数轴上的位置关系,所以我们可以把这n个数排好顺序,最小的变为0,次小的变为1,。。。最大的变为(n - 1)……这样数据范围小多了。。。当然这步应该要先做,因为我们需要按照开始时间递减的顺序考虑问题。.1point3acres缃

(1) 离散化,先按照结束时间递增的顺序排序,然后把排好顺序的结束时间分别变为0,1,2...n - 1
(2) 再按照开始时间递减的顺序牌好顺序。

下面来按顺序考虑每辆车。 我们需要一种结构,实现如下操作:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
(1) 给定x,查找结构里有多少个数< x。
(2) 插入x。


如何实现这样的结构? 显然用数组n^2是不可以的(n=70000),即使你可以二分查找,那么插入怎么处理?要移动很多元素……

其实实现上述操作的经典数据结构叫做线段树(区间树 , segment tree),算法导论上也有讲,玩过acm的人都熟知的基础东东…… 它需要O(n)的空间,和O(n)的时间建树 (很多人认为建树是nlogn,但应该不对。。。),O(logn)查询。 因为它要O(n)的空间,这就是我们前面离散化的意义所在了——不然10^18太大了。 比线段树稍微好写一点的结构叫做点树(pointTree),这是一种简化的结构,好像也有用树状数组的……思想简单写,大体含义是要比某个数小的个数,需要二进制表示里某个位是1的地方变位0,所以它插入x的时候,要把每个x二进制表示的“前缀”都加1,查找小于x的个数时,也是同时考虑每个前缀,如果最低位时1,就变位0,并且把个数累加起来。 总之,这些结构是非常经典而常用的结构。我在最初做这个题的时候,自然而然地用了线段树。 注意 这些结构都是跟数的范围(而不是个数)相关的,所以离散化很重要,在这个题里面,个数和范围统一了。

其实有一个更简单的方法,题目里有提示,我们不需要复杂的数据结构。这种方法就是分桶…… 之前O(n^2)的方法之所以不行,就是因为复杂度太高。我们能不能简化一些操作?可以的,例如,我们把数据分成sqrt(n)个桶,每个桶最多存sqrt(n)个数。. more info on 1point3acres.com
比如n = 100, 我们0号桶只存[0..9]的值,1号桶值存[10..19]的值,。。。。9号桶只存[90..99]的值。
桶用什么实现? 数组,或者vector<int>就可以,当然链表也可以,集合也可以……比如我们就用vector<int> bucket[10]来存10个桶。
如何找到x对应的桶编号? 显然[x / 10] (取整) 就是x应该放入的桶。

(1)给定x,查找结构里有多少个数< x。
我们知道 所有编号小于[x / 10]的桶里的数全都小于x,那么我们干脆循环从0..[x / 10] - 1把bucket的size()相加即可(每个桶需要记录已经插入了多少个数,vector list等自带这个size,用数组的话,自己要记录个数)。 那么[x / 10]的桶里有些数小于x,有些数大于x,怎么办? 同样循环遍历该桶所有数,看一下有多少个数小于x…… 看起来还是很暴力的。. 鍥磋鎴戜滑@1point 3 acres
(2) 插入x。很简单,直接把x放入对应的桶就号了。bucket[x / 10].push_back(x)

复杂度分析: 显然插入时O(1)的。查找的复杂度由两部分组成,第一个时查找所有编号小于[x / 10]的桶。那么我们至多时把所有桶-1都循环了一次,桶的个数是sqrt(n) - 1,对[x / 10]这同一个桶里的数,我们也要一个一个遍历,所以最多循环也是sqrt(n) - 1次。所以时间复杂度是O(sqrt(n)),这个比之前的O(n)好多了。 n次查询之后,总复杂度其实是O(n^1.5),比O(n^2)快很多,虽然线段树是O(nlogn),但是n = 70000这个数量级来讲O(n^1.5)也是可接受的……

之所以取桶的size是sqrt(n),其实是个trade-off,因为我们可能要遍历所有的桶和其中一个桶里所有的数,桶的个数和每个桶里的数都不能太多…… 这就是简单粗暴的“根号n大法“,实际做的是后其实取一个附近的值就好,比如我们可以强制桶的大小是270左右即可。。。。
. Waral 鍗氬鏈夋洿澶氭枃绔,
输出还是简单的排序 不是重点。

http://www.meetqun.com/thread-2248-1-1.html?x=12. visit 1point3acres.com for more.

滑动窗口最大(小)值问题。 简单的说就是一个窗口沿着数组(或者流式输入)走,窗口只能保留最近的k个值,不断查询滑动窗口内最大(小)值。
这是一个陈年旧题了……不知道为啥最近又有重现的趋势。。。。一般人会想到用堆。。。插入删除logk ,走n次 nlogk...
这题经典的方法是O(n)的…… 就是用双端队列。队列里最多存k个值。从队头到队尾的值从旧到新。 设想,一个值比较旧,来了比它大的新值之后,它永远不会是窗口内最大值了,这种没前途的值就没必要存了……

所以当来一个新值的时候,我们把队尾这端的不大于它(小于或等于)的值都踢出去,再把这个值入队。 当然,窗口滑动一下的时候,队头那个值如果失效了,也要踢出去。所以队列里实际上保存了一个值和一个时间戳,(每次滑动可能把对头踢出去,可能不踢)。进一步,如果原来的值是数组而不是流的话,队列里可以只存下标,这样就不用存时间戳了…… 这都是常数的空间优化。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.


(简单说从队尾踢出值,是因为旧值不够大,没有存在的必要。而从队头踢出值是因为旧值失效了而“不得不“出队,虽然它是最大的,但窗口滑动了). visit 1point3acres.com for more.
. 1point3acres.com/bbs

http://www.meetqun.com/thread-1340-1-1.html?x=12. visit 1point3acres.com for more.


1. Given 2D array, find the local minimum in constant time
2. Given a binary file and a txt file which contains parameters for this binary file.-google 1point3acres
exp: 1 2 3
        3 4 5
        4 5 6

use map reduce method to launch a bunch of binary files with different parameters that could run in parallel
how the split works?
override the split method to make one line of parameter -> one mapper.1point3acres缃
. 1point 3acres 璁哄潧
3. Given a base file name and a size. For exp. file.txt, 106668
Also given a logger interface and a loggable class, implements a log class that implements logger interface to save the input to a local disk file which has the given base name. When the file is full, you should rotate this file.
.1point3acres缃Example: when file.txt is full, copy all content of file.txt to file.txt.1 and clear file.txt and continue writing to file.txt

4. Remove duplicated number from sorted array

5. Remove duplicated number from unsorted array

6. Given an array of integers A, for example [2, 3,1, 1, 4, 2, 1], integers could be 0 or negative as well.
return Array of Integers that contains the multiplications of all elements in the array A except for the element in the same position. B = [ 24, 16, 48, 48, 12, 24, 48]
(1) use constant time and space
(2) what if in the system, division costs expensively while multiplication and adding could be done efficiently, write a solution with constant time and space again. (Array A and an empty array B are both given).1point3acres缃

http://www.meetqun.com/forum.php ... 2629&fromuid=12

Phone Interview。遇到很nice的同胞~也不知道放水了没有,总之感谢内推的亲和面我的面试官。欢迎指正 ~~  ^ ^
1. BST, given a min and a max, can you trim the tree so that the remaining nodes are within the range of (min, max)?
Node* trim(Node *root,int min,int max)
    Node *left,*right;
         return NULL;
         left = trim(root->left,min,max);
         right = trim(root->right,min,max);
         root->left = left,root->right = right;. more info on 1point3acres.com
         return root;
   }else if(root->value>=max)
         left = trim(root->left,min,max);
         return left;
   }else. From 1point 3acres bbs
   {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
         right = trim(root->right,min,max);
         return right;
2. Given a matrix, it’s sorted by column and by row, can you design an algorithm to find the target
.1point3acres缃boolean check(vector< vector<int> > &matrix, int &target) {
    int row,col;.鐣欏璁哄潧-涓浜-涓夊垎鍦
    row = matrix.size();
    if(row==0) return false;
    col = matrix[0].size();
    if(col==0) return false;
    int rowIndex,colIndex;
    rowIndex = 0,colIndex = col-1;
        //find target. From 1point 3acres bbs
            return true;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        else if(matrix[rowIndex][colIndex]<target)
        {//target is smaller
        {//target is bigger
    return false;

. visit 1point3acres.com for more.

补充内容 (2015-9-19 05:13):
. 鍥磋鎴戜滑@1point 3 acres我已经跳槽到Google了。。。




windream1991 发表于 2014-12-6 04:28:23 | 显示全部楼层
cpcs 发表于 2014-12-4 03:02

回复 支持 1 反对 0

使用道具 举报

rengokantai 发表于 2014-11-13 13:33:13 | 显示全部楼层
职位挺多。要求gpa 3.6  以上。
回复 支持 反对

使用道具 举报

 楼主| cpcs 发表于 2014-11-13 13:35:19 | 显示全部楼层
rengokantai 发表于 2014-11-13 13:33
职位挺多。要求gpa 3.6  以上。
. From 1point 3acres bbs
GPA不是硬系 i 功能指标。。。。

补充内容 (2014-11-13 13:35):
不是硬性指标 。。。

补充内容 (2014-11-14 23:18):
. 鍥磋鎴戜滑@1point 3 acres貌似多了一个sde职位infrastructure的。。。
回复 支持 反对

使用道具 举报

 楼主| cpcs 发表于 2014-11-14 23:20:34 | 显示全部楼层
回复 支持 反对

使用道具 举报

 楼主| cpcs 发表于 2014-11-16 02:06:43 | 显示全部楼层
回复 支持 反对

使用道具 举报

ekco 发表于 2014-11-18 01:33:42 | 显示全部楼层
回复 支持 反对

使用道具 举报

 楼主| cpcs 发表于 2014-11-18 14:20:23 | 显示全部楼层
ekco 发表于 2014-11-18 01:33

OK 祝好运
回复 支持 反对

使用道具 举报

zhaobaoxue 发表于 2014-11-18 22:29:30 | 显示全部楼层
楼主你好,SDE的是通过https://hire.jobvite.com/Jobvite/jobvite.aspx?b=nNFr0pwN 这个链接来填写吗?还是将简历发送到你的邮箱?谢谢!
回复 支持 反对

使用道具 举报

 楼主| cpcs 发表于 2014-11-20 12:41:36 | 显示全部楼层
zhaobaoxue 发表于 2014-11-18 22:29
楼主你好,SDE的是通过https://hire.jobvite.com/Jobvite/jobvite.aspx?b=nNFr0pwN 这个链接来填写吗?还是 ...

可以通过帖子里的链接直接申请(内推链接) 也可以给我发邮件要一个内推链接 都一样的。。。。. visit 1point3acres.com for more.

补充内容 (2014-11-20 12:41):
回复 支持 反对

使用道具 举报

 楼主| cpcs 发表于 2014-11-20 12:42:15 | 显示全部楼层
目前148个职位 内推 (含实习). Waral 鍗氬鏈夋洿澶氭枃绔,
回复 支持 反对

使用道具 举报

 楼主| cpcs 发表于 2014-11-23 00:29:49 | 显示全部楼层
回复 支持 反对

使用道具 举报

金妮韦崽 发表于 2014-11-24 09:25:58 | 显示全部楼层
问一下,gpa和ruby and rails是硬指标吗?我想申web applications但是gpa略低而且也没用过ruby,如果申请的话会不会直接过滤到垃圾箱。。。?谢谢啦!
回复 支持 反对

使用道具 举报

金妮韦崽 发表于 2014-11-24 09:26:08 | 显示全部楼层
问一下,gpa和ruby and rails是硬指标吗?我想申web applications但是gpa略低而且也没用过ruby,如果申请的话会不会直接过滤到垃圾箱。。。?谢谢啦!
回复 支持 反对

使用道具 举报

 楼主| cpcs 发表于 2014-11-24 14:58:45 | 显示全部楼层
金妮韦崽 发表于 2014-11-24 09:26
问一下,gpa和ruby and rails是硬指标吗?我想申web applications但是gpa略低而且也没用过ruby,如果申请的 ...

gpa不是硬指标。。。。ruby and rails应该是。。。
回复 支持 反对

使用道具 举报

 楼主| cpcs 发表于 2014-11-24 14:59:10 | 显示全部楼层
回复 支持 反对

使用道具 举报

金妮韦崽 发表于 2014-11-25 11:20:17 | 显示全部楼层
cpcs 发表于 2014-11-24 01:58
gpa不是硬指标。。。。ruby and rails应该是。。。

回复 支持 反对

使用道具 举报

 楼主| cpcs 发表于 2014-11-25 14:21:28 | 显示全部楼层
cpcs 发表于 2014-11-24 14:58
gpa不是硬指标。。。。ruby and rails应该是。。。

回复 支持 反对

使用道具 举报

zgymcycok 发表于 2014-11-26 05:11:13 | 显示全部楼层
回复 支持 反对

使用道具 举报

zgymcycok 发表于 2014-11-26 05:13:50 | 显示全部楼层
对了我是申new graduate
回复 支持 反对

使用道具 举报

 楼主| cpcs 发表于 2014-11-26 05:47:03 | 显示全部楼层
zgymcycok 发表于 2014-11-26 05:13-google 1point3acres
对了我是申new graduate

回复 支持 反对

使用道具 举报



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


custom counter

GMT+8, 2017-6-29 13:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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