我是如何肉身翻墙,从国内直接来美国工作的?

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 1745|回复: 4
收起左侧

Rocket fuel OA以及店面

[复制链接] |试试Instant~ |关注本帖
我的人缘0
ki87uj 发表于 2015-1-12 05:42:33 | 显示全部楼层 |阅读模式
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】

2014(10-12月) 码农类General 硕士 全职@Rocket fuel - 校园招聘会 - 技术电面  | Fail |

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

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

x
先说OA,这个题目网上都有了。赛车手排序问题。我的做法第4个case过不去。但是还是拿到店面了。废话少说,直接上代码。我按照题目提示用buckets做的,buckets的大小会影响test case的通过率,我反复调也过不了第4个。.留学论坛-一亩-三分地
Mitbbs上还有大神用别的方法做的。


/* Enter your code here. Read input from STDIN. Print output to STDOUT */
import java.io.BufferedReader;. From 1point 3acres bbs
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;

class Racer {
        int ID;. From 1point 3acres bbs
        long start;. Waral 博客有更多文章,
        long end;
        int score;. 1point3acres
        public Racer(int id,long start,long end){
                this.ID = id;
                this.start = start;
                this.end = end;
    }
    public void setscore(int score){. visit 1point3acres for more.
                this.score = score;
        }
        public int getscore(){.本文原创自1point3acres论坛
                return this.score;
        }
}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));. 1point3acres
        String line = br.readLine();. 牛人云集,一亩三分地
        int n = Integer.parseInt(line);
        //arraylist save all racers records
        ArrayList<Racer> A = new ArrayList<Racer>();
        while ((line = br.readLine()) != null) {
           String[] k = line.split(" ");. 一亩-三分-地,独家发布
                   Racer r1 = new Racer(Integer.parseInt(k[0]),Long.parseLong(k[1]),Long.parseLong(k[2]));. From 1point 3acres bbs
                   A.add(r1);
        }
        //sort the A array by start time decending
        Collections.sort(A, new Comparator<Racer>(){
                        public int compare(Racer r1,Racer r2){
                                if(r1.start > r2.start)
                    return -1;
                else
                    return 1;
                        }
                });
        //System.out.println("A size is "+A.size());
        //System.out.println(A.get(0).ID +" "+A.get(0).start );
        //use buckets, split and save all racers' data into buckets, then record the start time range of each bucket
        //sort each bucket by endtime
        ArrayList<ArrayList<Racer>> Buckets = new ArrayList<ArrayList<Racer>>(); 来源一亩.三分地论坛.
        int buck_size = Math.max(1500,(int)Math.sqrt(n));
        HashMap<Integer,Long> map = new HashMap<Integer,Long>();. 留学申请论坛-一亩三分地
        int i = 0;. From 1point 3acres bbs
        while(i < A.size()){
            ArrayList<Racer> bucket = new ArrayList<Racer>();
            for(int j=0;j<buck_size&&i<A.size();j++){
                bucket.add(A.get(i)); 来源一亩.三分地论坛.
                i++;. 留学申请论坛-一亩三分地
            }
            map.put(Buckets.size(),bucket.get(bucket.size()-1).start);//record each bucket's earliest start time
            //System.out.println("map0123 is "+Buckets.size() + " " + map.get(Buckets.size()));
            //System.out.println("bucket size " + bucket.size());
            //sort this bucket by endtime 来源一亩.三分地论坛.
            Collections.sort(bucket, new Comparator<Racer>(){
                             public int compare(Racer r1,Racer r2){. more info on 1point3acres
                                 if(r1.end < r2.end)
                    return -1;
                 else
                    return 1;
                             }
                      });
            Buckets.add(new ArrayList<Racer>(bucket)); . from: 1point3acres
        }

        //travesal all racers and get score
        for(int k=0;k<A.size();k++){
            int score = getscore(A.get(k),Buckets,map); 来源一亩.三分地论坛.
            A.get(k).setscore(score);.1point3acres网
        }
        //sort A by score
        Collections.sort(A, new Comparator<Racer>(){
                        public int compare(Racer r1,Racer r2){
                                return r1.ID - r2.ID;
                        }. visit 1point3acres for more.
                });
        Collections.sort(A, new Comparator<Racer>(){
                        public int compare(Racer r1,Racer r2){-google 1point3acres
                                return r1.score - r2.score;
                        }
                });
        //output results.留学论坛-一亩-三分地
        for(Racer r : A){
            System.out.println(r.ID + " " + r.score);. 一亩-三分-地,独家发布
        }

    }

    public static int getscore(Racer r,ArrayList<ArrayList<Racer>> Buckets,HashMap<Integer,Long> map){
        int sum = 0,i = 0;
        for(i=0;i<Buckets.size();i++){
            if(map.get(i) <= r.start)
                break;
            sum += getnum(Buckets.get(i),r.end);
        }
        //process the last bucket
        int count = 0;
        for(Racer p : Buckets.get(i)){
            if(p.end < r.end && p.start > r.start)
                count++;
        }
        /*int q = getnum(Buckets.get(i),r.end);
        for(int u=0;u<q;u++){
            Racer p = Buckets.get(i).get(u);
            if(p.start > r.start)
                count++;
        }
        */
        return sum + count;
    }

    public static int getnum(ArrayList<Racer> bucket,long endtime){
        if(bucket.get(0).end >= endtime)
            return 0;
        if(bucket.get(bucket.size()-1).end < endtime)
            return bucket.size();
        int l=0,r=bucket.size()-1;
        //the bucket already sorted by endtime, so do BST. Waral 博客有更多文章,
        while(l<r){
            int m = (l+r)/2;
            if(bucket.get(m-1).end < endtime && bucket.get(m).end >= endtime)
                return m;
            if(bucket.get(m).end < endtime)
                l = m;
            else
                r = m;
        }. from: 1point3acres
        return 0;
    }.1point3acres网
}



店面,广告商问题
有百万个广告,反正很多很多.本文原创自1point3acres论坛
Millions of Ads [n]

比如下面五个,左边是id,右边是广告名字. Waral 博客有更多文章,
1 -> new york (y)
. 一亩-三分-地,独家发布2 -> new york city (n). From 1point 3acres bbs
3 -> new york police department (y)
4 -> new york york (y)
5 -> york new (y)
[k] = average number of words in an ad
-google 1point3acres
我们要设计一种查询,如果输入一个关键字,立刻能得到结果。比如我们输入:
query -> police department new york [m]
那么上面五个里面,应该返回1,3,4,5; 而2就不是。查询速度要求小于O(n)
queries should be fast

这种查询是,如果广告中的名字是我们输入的查询query的subset,那么就返回。比如上面的1,3,4,5的广告,都是我们输入的police department new york 的子集。但是2里面包含一个”city“,所以2不是输入police department new york 的子集。
valid(ad,query) = set of words in the ad is a subset of the words in the query


以下是我的解法,参考mitbbs一位大神的。

首先构造一个表,表的column是所有百万广告里面的出现过的单词。unique 单词应该不会太多,几千个吧
对每个广告,如果这个单词有,就写1,没有就0,这样为每条广告构造一个vector
.本文原创自1point3acres论坛
step1:   O(N)

table word count
        new  york   city  police  department
1        1    1     0
2        1    1     1    0....
3        1    1     0    1        1
4        1    2
5        1    1     0



HashMap  k=word  v =position

1  map.get(new) po =1 2  vector 1 1 0 0 ..
2

vector :  word1 w2 w3  ......    w1000 (1000 words in all M IDs)
. 留学申请论坛-一亩三分地
vector length =  unique words in all M IDs 来源一亩.三分地论坛.

step2:   O(1)
get vector from query. 一亩-三分-地,独家发布
  1 1 0 1 1

然后反过来构造一个vector 对应广告id的hashmap
step 3:  O(N)
hashmap2  <vector, set<ID>>  from step 1
1 1 0 ...     ID= {1, 5}

查询输入的时候,计算出查询的所有subsets,然后逐个去查hashmap。
step 4: O(query.wordscount)
Assumption: query is a not very long sentance. from: 1point3acres
get all subsets from query vector-google 1point3acres
ex:
   1 1 0 1 1
   的subsets包括
   1 0 0 0 0
   1 1 0 0 0
.....

   search in hashmap2  
. 牛人云集,一亩三分地

下面是代码,但是我没写完,比较乱,仅作参考
// process data, step 1. more info on 1point3acres
HashMap<String,Integer> map = new HashMap<String,Integer>();
int position = 0;
for(i : Ads) // i is single Ad, Ad.ID,  Ad.content
    for(k : i.content){
        if(!map.containsKey(k)){
            map.put(k,position);
            position++;. Waral 博客有更多文章,
        }
    }
}



HashMap<Integer,vector[]> map1 = new HashMap<Integer,vector[]>();. Waral 博客有更多文章,

for(i : Ads){
    int[] vector = new int[set.size()];
    for(k : i.content){. 围观我们@1point 3 acres
        vector[map.get(k)] = 1;
    }
    map1.put(i.ID,vector); //ID=1   vector= 1 1 0 0 ....
}

//step 2. visit 1point3acres for more.
int[] Q_vector = new int[set.size()];
for(i : query){. 一亩-三分-地,独家发布
    Q_vector[map.get(i)] = 1;. 留学申请论坛-一亩三分地
}

. Waral 博客有更多文章,
//step 3  build map <vector,List<ID>>

HashMap<vector[],ArrayList<Integer>> map2 = new HashMap<vector[],ArrayList<Integer>>;
for(i : map1.keyValue()){
    if(!map2.containsKey(map1.get(i)).1point3acres网
        map2.put(map1.get(i),new ArrayList. from: 1point3acres
}


最后挂了。   
. 1point 3acres 论坛

. Waral 博客有更多文章,


评分

1

查看全部评分


上一篇:Amazon Onsite面经
下一篇:EMC Software Dev 电话面试
我的人缘0
chenwoo 发表于 2015-1-12 13:14:45 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
sorry to hear that.   你好,请教个问题哈。最近看面经都提到OA一词,什么是OA啊.我也想做做上面的题目练练,请问怎么在网上去找啊?thank you very much!
回复 支持 反对

使用道具 举报

我的人缘0
xiaoxin213 发表于 2015-1-12 14:20:19 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
chenwoo 发表于 2015-1-12 13:14
sorry to hear that.   你好,请教个问题哈。最近看面经都提到OA一词,什么是OA啊.我也想做做上面的题目练 ...

是Online Assessment
回复 支持 反对

使用道具 举报

我的人缘0
chenwoo 发表于 2015-1-14 07:08:40 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
.本文原创自1point3acres论坛
Thanks, 请问怎么得到OA的机会啊?具体流程怎么做的啊?
回复 支持 反对

使用道具 举报

我的人缘0
int_179 发表于 2015-1-14 09:29:15 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
我去 答的这么好都挂了 不科学啊
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-28 04:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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