推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

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

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

新鲜出炉 Palantir OA

[复制链接] |试试Instant~ |关注本帖
wwtwxlwjh 发表于 2016-9-25 10:12:21 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Palantir - 校园招聘会 - 在线笔试 |Otherfresh grad应届毕业生

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

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

x
楼主前几天收到他家OA,题目是 Catching an Insider Trader, 关注了地里一些日子,貌似还没有人发上来
. 鍥磋鎴戜滑@1point 3 acres


时间75min 做一道题,最后有10个test case,说明通过正确率筛人。
题目大意就是给一个string数组,里面有股票day|price的信息,还有trader交易的信息day|name|BUY|amount,这种格式。要求找到符合条件的trader,并排序返回
1. Buy了之后三天之内, 股票涨幅*amount >= 5million
2.Sell了之后三天之内,股票跌幅*amount >= 5million
题目意思挺好理解的,最后debug了一会,要注意最后结果的排序,要现根据day 再根据name排序

怒赞rp,祝大家都找到好工作!. 1point3acres.com/bbs

评分

6

查看全部评分

littlewhite 发表于 2016-10-17 15:13:03 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
感谢楼主的面经,刚刚做完了,10个test case都通过了。
用的是类似扫描线的算法,先把所有价格存成一个array,例如p[1]是第一天,p[5]是第五天,空余的地方补上前一天的价格。
然后把所有trade存成一个list,扫一遍,取每个trade day往后看三天是否符合条件,符合就输出。最后排序。
时间O(m * 3),m是trade数。

评分

2

查看全部评分

回复 支持 1 反对 0

使用道具 举报

muybienw 发表于 2016-10-16 01:44:49 | 显示全部楼层
关注一亩三分地微博:
Warald
今天写了一下,10个test case都通过了,主要几点:
1. 用TreeMap存价格。题目里面讲到,如果某一天的价格没有,那么就按它之前最近一天的价格来算(0那天一定有个价格),所以treemap可以加速搜索。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
2. 输出结果要排序并且去重,所以在读取交易记录的时候要把重复的删除掉。重复的交易记录应该是四个变量都相等的。-google 1point3acres
3. 因为价格和交易记录是混在一起的,所以可以先分别存好价格map和交易list,然后再scan交易记录查找可疑交易。
4. 总时间O(m * k * logn),m是交易的数量,k是窗口大小,n是价格数量。

评分

2

查看全部评分

回复 支持 1 反对 0

使用道具 举报

xzhuge 发表于 2016-9-27 10:41:48 | 显示全部楼层
whoyo123 发表于 2016-9-27 10:26
楼主能说明一下输入和输出的形式吗?比如股票价格和交易信息是在同一个string数组里的吗?输出是只需要trad ...

输入输出都是vector<string>, 股票价格和交易信息都在同一个vector<string>, 每一行一条信息,但是都是交叉的,给的例子是按时间有序的。 输出是时间加trader name, 先时间排序,时间相同trader排序。 OA已挂,祝你成功!
回复 支持 1 反对 0

使用道具 举报

leixiang5 发表于 2016-9-25 10:29:30 | 显示全部楼层
感谢楼主啊!!!!给你大米!!!
回复 支持 反对

使用道具 举报

leixiang5 发表于 2016-9-25 10:38:54 | 显示全部楼层
问一下..不是很理解题目..按照什么排序?.只要trader交易了一次中符合1 或者2条件的话..她就在output里?
回复 支持 反对

使用道具 举报

xzhuge 发表于 2016-9-25 11:10:04 | 显示全部楼层
感谢楼主分享, 请问题目中的day是以哪种形式表示的, 日期还是数字?
回复 支持 反对

使用道具 举报

神罗天征 发表于 2016-9-25 11:17:54 | 显示全部楼层
leixiang5 发表于 2016-9-25 10:38. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
问一下..不是很理解题目..按照什么排序?.只要trader交易了一次中符合1 或者2条件的话..她就在output里?

群主你是内推吗?
回复 支持 反对

使用道具 举报

 楼主| wwtwxlwjh 发表于 2016-9-25 11:46:30 | 显示全部楼层
leixiang5 发表于 2016-9-25 10:38
问一下..不是很理解题目..按照什么排序?.只要trader交易了一次中符合1 或者2条件的话..她就在output里?

每次交易只有一个type,Buy或者Sell。 day是int,name是string,然后day一样,再排name
回复 支持 反对

使用道具 举报

 楼主| wwtwxlwjh 发表于 2016-9-25 11:46:37 | 显示全部楼层
xzhuge 发表于 2016-9-25 11:10
感谢楼主分享, 请问题目中的day是以哪种形式表示的, 日期还是数字?
. 鍥磋鎴戜滑@1point 3 acres
一个数字
回复 支持 反对

使用道具 举报

 楼主| wwtwxlwjh 发表于 2016-9-25 11:46:56 | 显示全部楼层

好像是careerfair投的。。。。。记不清了。。。
回复 支持 反对

使用道具 举报

leixiang5 发表于 2016-9-25 12:17:21 | 显示全部楼层

- -我没内推..骚扰了recruiter + 网投..不知道哪个奏效了..
回复 支持 反对

使用道具 举报

leixiang5 发表于 2016-9-25 12:17:51 | 显示全部楼层
做完了...卡在case 7 - -..貌似没排序..
回复 支持 反对

使用道具 举报

whoyo123 发表于 2016-9-27 10:26:07 | 显示全部楼层
楼主能说明一下输入和输出的形式吗?比如股票价格和交易信息是在同一个string数组里的吗?输出是只需要trader name, 还是其他什么形式?. 1point3acres.com/bbs
多谢了!!!
回复 支持 反对

使用道具 举报

nsy297172408 发表于 2016-9-30 14:36:43 | 显示全部楼层
求问楼主 Input 有说是sorted by date吗? 然后每条String的format是 day|price|name|BUY|amount?  股票价格和交易信息是一起的? 也就是说如果是两个不同的人在同一天做交易,那么input是 “1|500|Bob|BUY|30”, "1|500|Alan|BUY|20"?  

感激不尽!给楼主攒攒RP .鐣欏璁哄潧-涓浜-涓夊垎鍦
回复 支持 反对

使用道具 举报

FENGXIANGLFX 发表于 2016-9-30 17:48:00 | 显示全部楼层
1.求问下支持java码代码吧?
2.vector<String>中,每个String既可能是交易员信息也可能是股票的信息?
3.是不是有交易员有两次交易都符合筛选可能?
回复 支持 反对

使用道具 举报

xzhuge 发表于 2016-10-1 07:42:25 | 显示全部楼层
FENGXIANGLFX 发表于 2016-9-30 17:48
1.求问下支持java码代码吧?
2.vector中,每个String既可能是交易员信息也可能是股票的信息?
3.是不是有 ...

. 1point3acres.com/bbs1. 支持呀. 1point3acres.com/bbs
2. 对的
3. 对。
回复 支持 反对

使用道具 举报

laonong15 发表于 2016-10-1 13:57:01 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 反对

使用道具 举报

laonong15 发表于 2016-10-1 13:59:37 | 显示全部楼层
有朋友问我这个 , 因为没有足够信息  所以给了个参考解。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
仅仅分享  如果OA不过  那是你的错
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
import java.util.HashMap;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.SortedMap;
import java.util.SortedSet;
import java.util.TreeMap;
import java.util.TreeSet;-google 1point3acres

public class CatchInsider {
         Map<Integer,Double> priceMap  = new HashMap<>();
        SortedMap<Integer,SortedSet<Transaction>> transactionMap = new TreeMap<>();. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷        public Set<String> catchInsiders(String[] input) {
                initialData(input);
                Set<String> result = new HashSet<>();. 1point3acres.com/bbs
                for (Integer key : transactionMap.keySet()) {. more info on 1point3acres.com
                        SortedSet<Transaction> currentSet = transactionMap.get(key);
                        for (Transaction tr : currentSet) {
                                double curValue = tr.amount * priceMap.get(key);
                                for (int i = 1; i <= 3; i++) {
鏉ユ簮涓浜.涓夊垎鍦拌鍧.                                         if (priceMap.get(key + i) != null) {
                                                double delta = tr.amount * priceMap.get(key + i) - curValue;
                                                if ((tr.buy && delta >= 5000000) || (!tr.buy && delta <= -5000000)) {
                                                        result.add(tr.name);
                                                }.鐣欏璁哄潧-涓浜-涓夊垎鍦
                                        }
                                }. 1point3acres.com/bbs

                        }
                }.1point3acres缃
                return result;

        }
        private void initialData(String[] input) {. 鍥磋鎴戜滑@1point 3 acres
                for(String st : input){
                        String[] stArr = st.split("\\|");
                        if(stArr.length == 2) {
                                priceMap.put(Integer.parseInt(stArr[0]),Double.parseDouble(stArr[1]));. visit 1point3acres.com for more.
                        } else {
                                Transaction trans = new Transaction(Integer.parseInt(stArr[0]),stArr[2].equals("BUY"),
                                                stArr[1],Integer.parseInt(stArr[3]));
                                int key = Integer.parseInt(stArr[0]);
                                if(!transactionMap.containsKey(key)){
                                        transactionMap.put(key,  new TreeSet<Transaction>());
                                }
                                transactionMap.get(key).add(trans);
                        }
                }
        }
        public static void main(String[] args) {
                String[] data = new String[]{"1|700", "2|10000","3|50","4|700", "5|10","6|50000","1|Bob|BUY|30000", "1|Alan|BUY|20000"
                                ,"2|tob|BUY|30000", "3|Ann|BUY|20000","5|Bb|BUY|30000", "4|Aggn|BUY|20000"};
                CatchInsider cs = new CatchInsider();
                System.out.println(cs.catchInsiders(data));. more info on 1point3acres.com
        }
       
        class Transaction implements Comparable<Transaction> {
                int day;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                boolean buy;. from: 1point3acres.com/bbs
                String name;
                int amount;.鐣欏璁哄潧-涓浜-涓夊垎鍦
                public Transaction(int day, boolean buy, String name, int amount) {
                        this.day = day;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                        this.buy = buy;
                        this.name = name;
                        this.amount = amount;
                }
               
                @Override
                public int compareTo(Transaction t2) {
                        if(this.day == t2.day){
                                return  this.name.compareTo(t2.name);
                        } else {
                                return this.day -t2.day;
                        }
                         
                }
                 
                . Waral 鍗氬鏈夋洿澶氭枃绔,
        }. 1point3acres.com/bbs

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

FENGXIANGLFX 发表于 2016-10-1 14:20:58 | 显示全部楼层
想问下能用java内置的Collections.sort(List,comparator)做么,需不需要自己写排序函数
回复 支持 反对

使用道具 举报

laonong15 发表于 2016-10-1 14:48:01 | 显示全部楼层
TreeSet<Transaction> tset = new TreeSet<>( new Comparator<Transaction>(){
                        public int compare(Transaction t1, Transaction t2) {
                                if(t1.day == t2.day){
                                        return  t1.name.compareTo(t2.name);. Waral 鍗氬鏈夋洿澶氭枃绔,
                                } else {
                                        return t1.day -t2.day;
                                }
                        }});
回复 支持 反对

使用道具 举报

yiyizheliu 发表于 2016-10-2 02:15:34 | 显示全部楼层
问下楼主,trader的名字会不会有重复?就是一个人交易过多次?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-25 21:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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