一亩三分地论坛

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

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

Rocket fuel OA以及店面

[复制链接] |试试Instant~ |关注本帖
ki87uj 发表于 2015-1-12 05:42:33 | 显示全部楼层 |阅读模式

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

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

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

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


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

class Racer {
        int ID;
        long start;
        long end;
        int score;
        public Racer(int id,long start,long end){
                this.ID = id;
                this.start = start;
                this.end = end;
    }
    public void setscore(int score){
                this.score = score;. 鍥磋鎴戜滑@1point 3 acres
        } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        public int getscore(){
                return this.score;
        }
}
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        int n = Integer.parseInt(line);. from: 1point3acres.com/bbs
        //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]));
                   A.add(r1);
        }-google 1point3acres
        //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;. more info on 1point3acres.com
                        }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                });
        //System.out.println("A size is "+A.size());. From 1point 3acres bbs
        //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));-google 1point3acres
        HashMap<Integer,Long> map = new HashMap<Integer,Long>();
        int i = 0;
        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){. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                                 if(r1.end < r2.end). 1point 3acres 璁哄潧
                    return -1;
                 else
                    return 1;
                             }
.1point3acres缃                      });
            Buckets.add(new ArrayList<Racer>(bucket));
        }

        //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;
                        }
                });
        Collections.sort(A, new Comparator<Racer>(){
                        public int compare(Racer r1,Racer r2){
                                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
-google 1point3acres        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);. 1point 3acres 璁哄潧
        for(int u=0;u<q;u++){
            Racer p = Buckets.get(i).get(u);
            if(p.start > r.start)-google 1point3acres
                count++;
        }
        */
        return sum + count;
    }. 鍥磋鎴戜滑@1point 3 acres

    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). visit 1point3acres.com for more.
            return bucket.size();
        int l=0,r=bucket.size()-1;
        //the bucket already sorted by endtime, so do BST
        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;
        }
        return 0;.1point3acres缃
    }
}



店面,广告商问题
有百万个广告,反正很多很多
Millions of Ads [n]

比如下面五个,左边是id,右边是广告名字
1 -> new york (y)-google 1point3acres
2 -> new york city (n)
3 -> new york police department (y)
4 -> new york york (y).1point3acres缃
5 -> york new (y)
[k] = average number of words in an ad. visit 1point3acres.com for more.

我们要设计一种查询,如果输入一个关键字,立刻能得到结果。比如我们输入:
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

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. 鍥磋鎴戜滑@1point 3 acres
. 鍥磋鎴戜滑@1point 3 acres
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.1point3acres缃

然后反过来构造一个vector 对应广告id的hashmap
step 3:  O(N)
hashmap2  <vector, set<ID>>  from step 1
1 1 0 ...     ID= {1, 5}
. 1point3acres.com/bbs
查询输入的时候,计算出查询的所有subsets,然后逐个去查hashmap。
step 4: O(query.wordscount)
Assumption: query is a not very long sentance
get all subsets from query vector
ex:
   1 1 0 1 1. from: 1point3acres.com/bbs
   的subsets包括
   1 0 0 0 0. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
   1 1 0 0 0
.....

   search in hashmap2  


下面是代码,但是我没写完,比较乱,仅作参考
// process data, step 1
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++;
        }
    }
}



HashMap<Integer,vector[]> map1 = new HashMap<Integer,vector[]>();. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
.鏈枃鍘熷垱鑷1point3acres璁哄潧
for(i : Ads){
    int[] vector = new int[set.size()];
    for(k : i.content){
        vector[map.get(k)] = 1;
    }
    map1.put(i.ID,vector); //ID=1   vector= 1 1 0 0 ..... 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
}

//step 2
int[] Q_vector = new int[set.size()];
for(i : query){
    Q_vector[map.get(i)] = 1;
}


//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))
        map2.put(map1.get(i),new ArrayList
}.鏈枃鍘熷垱鑷1point3acres璁哄潧


最后挂了。   


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


评分

1

查看全部评分

chenwoo 发表于 2015-1-12 13:14:45 | 显示全部楼层
sorry to hear that.   你好,请教个问题哈。最近看面经都提到OA一词,什么是OA啊.我也想做做上面的题目练练,请问怎么在网上去找啊?thank you very much!
回复 支持 反对

使用道具 举报

xiaoxin213 发表于 2015-1-12 14:20:19 | 显示全部楼层
chenwoo 发表于 2015-1-12 13:14. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
sorry to hear that.   你好,请教个问题哈。最近看面经都提到OA一词,什么是OA啊.我也想做做上面的题目练 ...

是Online Assessment
回复 支持 反对

使用道具 举报

chenwoo 发表于 2015-1-14 07:08:40 | 显示全部楼层

Thanks, 请问怎么得到OA的机会啊?具体流程怎么做的啊?
回复 支持 反对

使用道具 举报

int_179 发表于 2015-1-14 09:29:15 | 显示全部楼层
我去 答的这么好都挂了 不科学啊
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 23:16

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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