一亩三分地论坛

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

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

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

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

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

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

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

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

因为码农比较多……sde的相关职位描述可以通过这个这个链接里"Apply now"申请。包括:(1) 校招 new grad.鐣欏璁哄潧-涓浜-涓夊垎鍦
(2) 社招 senior
(3) 暑期实习 intern
总共13个
如果需要其他职位招聘,例如PM、Operation等,欢迎站内联系或者给我发email, 我email: 529929033@qq.com
祝大家好运。

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

补充内容:
http://www.mitbbs.com/article_t/JobHunting/32573375.html

分享一个得到positive feedback的解题思路,代码就不贴了,因为邮件里面说rocket
fuel的engineer会code review

题目网上有,这个链接里面的第3题:http://get-that-job-at-google.bl ... -at-iit-bombay.html
. visit 1point3acres.com for more.
首先题目里面给了一个提示:把所有的输入,按照start time均分为K个区间去处理 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

我的思路用sample input解释一下:
5
2 100 200
3 110 190. 鍥磋鎴戜滑@1point 3 acres
4 105 145
1 90 150
5 102 198

1,所有的开始时间和结束时间没有重复的,对输入得到三元组<time, racer_id,
start|end>,然后根据time排序得到:

idx  time  r_id type   value/ret. 鍥磋鎴戜滑@1point 3 acres
--------------------------------------------. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
0    90    1    start  0      +1
1    100   2    start  0                  +1
2    102   5    start  0              +1. From 1point 3acres bbs
3    105   4    start  0  +1. 1point3acres.com/bbs
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. 鍥磋鎴戜滑@1point 3 acres
9    200   2    end    0                  *3. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

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

2,对排好序的数组从前往后扫描: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
   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]++
       2.2.2 对[start_idx + 1, end_idx]这个区间的value求和,就是racer_id=4的
最终结果,ret=0. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
       上面图中以列为时间轴,大致把过程模拟了一遍

3,对所有的结果按照题目要求排序即可

=====分割线:以上是本题的解法,以下是本题用到的数据结构=====
抽象以上过程,有个数组,不断的修改其中某个位置的值,不断要求某个区间的和。典.鏈枃鍘熷垱鑷1point3acres璁哄潧
型的数据结构是线段树:http://en.wikipedia.org/wiki/Segment_tree 线段树比较好写,本质上就是个二叉树。

最后这个解法的整体时间复杂度是O(nlogn)的,写起来也比较容易,比hint的解法要上
流一点。

下周安排了skype interview,求rp!



http://www.meetqun.com/forum.php ... 2240&fromuid=12
. visit 1point3acres.com for more.
题目:
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

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.

Given such an input, you should print output in the following format:
. visit 1point3acres.com for more.
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.

Directions:
Please code this problem in Java, C, or C++. Your solution should run in less than O(N^2) on all inputs.
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:
5. more info on 1point3acres.com
2 100 200
3 110 190. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
4 105 145
1 90 150
5 102 198. Waral 鍗氬鏈夋洿澶氭枃绔,
output:
3 0. more info on 1point3acres.com
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
复制代码
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
这种题目的风格就是acm的题型,只是简单很多……有明确的输入输出格式和数据范围。

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


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

说了这么多,简单地说就是两步
(1) 离散化,先按照结束时间递增的顺序排序,然后把排好顺序的结束时间分别变为0,1,2...n - 1
(2) 再按照开始时间递减的顺序牌好顺序。

下面来按顺序考虑每辆车。 我们需要一种结构,实现如下操作:
(1) 给定x,查找结构里有多少个数< x。
(2) 插入x。

假设我们有这样的结构,考虑一个车的时候,看一下有多少车比它结束早(因为按开始时间递减顺序考虑的,结构里的车是开始时间比它晚的全部车)就可以了,再把该车的结束时间插入到结构里。

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

. 1point3acres.com/bbs其实实现上述操作的经典数据结构叫做线段树(区间树 , 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)个数。
举个例子更好一些:. 1point 3acres 璁哄潧
比如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…… 看起来还是很暴力的。
(2) 插入x。很简单,直接把x放入对应的桶就号了。bucket[x / 10].push_back(x). from: 1point3acres.com/bbs

复杂度分析: 显然插入时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左右即可。。。。

输出还是简单的排序 不是重点。



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

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

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

这样保存的队列是单调的,从队尾到队头,值是严格递减的,时间上是从旧到新的,队列里最旧的值是最大的。

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

时间复杂度上,因为每个数最多入队出队一次,所以时间复杂度是O(n)。


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

. 鍥磋鎴戜滑@1point 3 acres
面了4个45分钟,全是三哥。
. 1point3acres.com/bbs
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.
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
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
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.
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.. From 1point 3acres bbs
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)


http://www.meetqun.com/forum.php ... 2629&fromuid=12. Waral 鍗氬鏈夋洿澶氭枃绔,

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)?. Waral 鍗氬鏈夋洿澶氭枃绔,
Node* trim(Node *root,int min,int max)
{
    Node *left,*right;
    if(NULL==root)
         return NULL;. Waral 鍗氬鏈夋洿澶氭枃绔,
    if(root->value>min&&root->value<max)
    {
         left = trim(root->left,min,max);
         right = trim(root->right,min,max); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
         root->left = left,root->right = right;. from: 1point3acres.com/bbs
         return root;
   }else if(root->value>=max)
   {. 1point3acres.com/bbs
         left = trim(root->left,min,max);
         return left;-google 1point3acres
   }else
   {
         right = trim(root->right,min,max);
         return right;
   }
}. 1point 3acres 璁哄潧
2. Given a matrix, it’s sorted by column and by row, can you design an algorithm to find the target
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;
    while(rowIndex<=row-1&&colIndex>=0). from: 1point3acres.com/bbs
    {
        //find target
        if(maxtrix[rowIndex][colIndex]==target)
            return true;. 鍥磋鎴戜滑@1point 3 acres
        else if(matrix[rowIndex][colIndex]<target)
        {//target is smaller. 1point 3acres 璁哄潧
           colIndex--;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        }else
        {//target is bigger
            rowIndex++;
        }
    }
    return false;
}

. Waral 鍗氬鏈夋洿澶氭枃绔,

补充内容 (2015-9-19 05:13):
我已经跳槽到Google了。。。

评分

9

查看全部评分

windream1991 发表于 2014-12-6 04:28:23 | 显示全部楼层
cpcs 发表于 2014-12-4 03:02
刚刚结束的RF电面
http://www.meetqun.com/forum.php?mod=viewthread&tid=2629&fromuid=12

能发到地里吗……米群没有权限……
回复 支持 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  以上。

GPA不是硬系 i 功能指标。。。。

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

补充内容 (2014-11-14 23:18):
貌似多了一个sde职位infrastructure的。。。
回复 支持 反对

使用道具 举报

 楼主| cpcs 发表于 2014-11-14 23:20:34 | 显示全部楼层
内推之后将收到系统确认邮件……
回复 支持 反对

使用道具 举报

 楼主| cpcs 发表于 2014-11-16 02:06:43 | 显示全部楼层
有些邮箱肯跟收不到邮件。。请换邮箱
回复 支持 反对

使用道具 举报

ekco 发表于 2014-11-18 01:33:42 | 显示全部楼层
谢谢lz,简历发lz邮箱了,请查收
回复 支持 反对

使用道具 举报

 楼主| cpcs 发表于 2014-11-18 14:20:23 | 显示全部楼层
ekco 发表于 2014-11-18 01:33
谢谢lz,简历发lz邮箱了,请查收

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 这个链接来填写吗?还是 ...

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

补充内容 (2014-11-20 12:41):-google 1point3acres
申请后最好给我发个第三人称的推荐理由来。。。。
回复 支持 反对

使用道具 举报

 楼主| cpcs 发表于 2014-11-20 12:42:15 | 显示全部楼层
目前148个职位 内推 (含实习)-google 1point3acres
http://jobvite.com/m?3pTnQgwg
回复 支持 反对

使用道具 举报

 楼主| 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. 1point 3acres 璁哄潧
对了我是申new graduate

er...不知道是不是您。。。邮件好简单。。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 11:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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