《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 9390|回复: 43
收起左侧

Zenefits Test 4

[复制链接] |试试Instant~ |关注本帖
pyzhangyi 发表于 2015-4-8 05:01:57 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@Zenefits - 网上海投 - 在线笔试 |Failfresh grad应届毕业生

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

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

x
两道题,在HackerRank上做,三个小时足足够用,由于测试前同意不贴代码,这里只说下思路吧。
第一题,有n个售票口,每个售票口剩下多少张票,那这一张票就卖多少钱。比如,一个售票口剩下5张票,那这一张就卖5块,卖出这张后剩下4张,下一张就卖4块。问如果一共要卖出m张票,最多能卖多少钱。
解法多种多样,可以用 leetcode那道Heap题的思路merge排序做,也可以用Hashmap,我个人能想到的最好解法是用heap做(C++)。每次循环都make_heap一下,然后res加上第一个元素,然后让第一个元素减1,直到m为0了,或者vector里只剩下0了。但是当时由于不太清楚make_heap的消耗,所以稳妥的选择了hashmap做。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
第二题,有一个vector<string>, 每一个string都有permutation, 然后permutation从小到大排序,看看这条string是第几个index,就把这个index放到vector<int> result里,最后返回result。
想到的两种解法:
第一种,leetcode第31题,next permutation的思路。设一个string temp等于原字符串,然后把temp给排序,然后循环看看temp是否与原字符串相等,如果不等,就找temp相邻的permutation,如果相等,就返回当前index值。这种方法效率不是特别高。
第二种,leetcode第60题,permutation sequence的思路。但是要注意的一点就是这里的string里会有duplicate的字符。这种方法比第一种效率高,但解决duplicate情况。
. Waral 鍗氬鏈夋洿澶氭枃绔,
刚收到邮件,已挂~

评分

1

查看全部评分

nibuxing 发表于 2015-4-8 05:15:08 | 显示全部楼层
楼主这两道题Test case过了几个
回复 支持 反对

使用道具 举报

 楼主| pyzhangyi 发表于 2015-4-8 05:20:00 | 显示全部楼层
nibuxing 发表于 2015-4-8 05:15
楼主这两道题Test case过了几个
. from: 1point3acres.com/bbs
第一道题直接Run code一个测试都通不过,因为Main函数是空的,所以就在Main函数里写了程序可以让用户自己输入。
第二道用的是next permutation的方法,效率不是很高,通过了三四个测试吧,其他的都是exceed time limit。
回复 支持 反对

使用道具 举报

nibuxing 发表于 2015-4-8 05:23:23 | 显示全部楼层
pyzhangyi 发表于 2015-4-8 05:20
第一道题直接Run code一个测试都通不过,因为Main函数是空的,所以就在Main函数里写了程序可以让用户自己 ...

第一题是我BB的电面题,可以直接一个pointer来做。
回复 支持 反对

使用道具 举报

 楼主| pyzhangyi 发表于 2015-4-8 05:41:56 | 显示全部楼层
nibuxing 发表于 2015-4-8 05:23
第一题是我BB的电面题,可以直接一个pointer来做。

用make_heap做,一个pointer都不用,只要一个变量result就成。
回复 支持 反对

使用道具 举报

BlackidsS 发表于 2015-4-8 05:58:40 | 显示全部楼层
已跪+1,昨天做的今早收到邮件,借楼分享下。

第一题我用最大堆做,共8个testcase 过了4个,后面过不了的是因为testcase里有输入无效值,题目要求输入的数组每一项即售票口的剩余票数在1~100000之间,我debug的时候在发现输入无效值的时候抛出异常,结果程序确实中断了,最后不知道怎么处理这种情况,搞了1小时放弃了....... Waral 鍗氬鏈夋洿澶氭枃绔,

第二题10testcase个过了4个,估计问题出在求模值那里,题目要求结果要模上10^9+7,还给了个求模逆元素的算法,想了半天不知道怎么用就没用上,2道题写完不用1小时,调了2小时就没能多过一个test case,就当练手了......

祝大家好运!
回复 支持 反对

使用道具 举报

yabay91 发表于 2015-4-8 06:15:43 | 显示全部楼层
我也挂了。。。. From 1point 3acres bbs

第一题用的max heap做,8个case通过了5个,剩余3个显示timeout
. visit 1point3acres.com for more.
第二题一开始用Long保存,过了3个case。换成bigInteger之后全都过了

可是还是挂了- -
回复 支持 反对

使用道具 举报

 楼主| pyzhangyi 发表于 2015-4-8 06:24:46 | 显示全部楼层
yabay91 发表于 2015-4-8 06:15
我也挂了。。。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第一题用的max heap做,8个case通过了5个,剩余3个显示timeout

第一次用HackRank答题,请问第一题是怎么测试的啊,Main函数里什么都没有~我直接写了段程序,让用户自己输入
回复 支持 反对

使用道具 举报

BlackidsS 发表于 2015-4-8 06:25:05 | 显示全部楼层
yabay91 发表于 2015-4-8 06:15
我也挂了。。。.鏈枃鍘熷垱鑷1point3acres璁哄潧

第一题用的max heap做,8个case通过了5个,剩余3个显示timeout
. From 1point 3acres bbs
请问一下,第一题你是怎么处理a>100000的,第二题你用了他给的算法求模吗?我用long long 是不是还不够? 谢谢
回复 支持 反对

使用道具 举报

yabay91 发表于 2015-4-8 06:30:00 | 显示全部楼层
pyzhangyi 发表于 2015-4-8 06:24
第一次用HackRank答题,请问第一题是怎么测试的啊,Main函数里什么都没有~我直接写了段程序,让用户自己 ...

Scanner sc=new Scanner(System.in);
int n=sc.nextInt();这种
回复 支持 反对

使用道具 举报

yabay91 发表于 2015-4-8 06:33:55 | 显示全部楼层
BlackidsS 发表于 2015-4-8 06:25
请问一下,第一题你是怎么处理a>100000的,第二题你用了他给的算法求模吗?我用long long 是不是还不够?  ...

我没有处理a>100000。。。。。不知道是不是这个影响我。。.鐣欏璁哄潧-涓浜-涓夊垎鍦

第二题求模了啊,比如bigInteger a. a.mod(BigInteger.valueOf(1000000007))
回复 支持 反对

使用道具 举报

haiken 发表于 2015-4-9 09:46:02 | 显示全部楼层
楼主的第一题的Heap方法过通过了所有测试了吗?
. from: 1point3acres.com/bbs
补充内容 (2015-4-9 09:46):
说错了, 楼主的hashmap方法通过了所有测试了?
回复 支持 反对

使用道具 举报

averillzheng 发表于 2015-4-9 23:59:51 | 显示全部楼层
yabay91 发表于 2015-4-8 06:30
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();这种

你能用你的link替我测一下第一题的code 吗? 我不用做OA 放心,我只是想测试一下我的想法。
回复 支持 反对

使用道具 举报

haiken 发表于 2015-4-10 03:06:14 | 显示全部楼层
averillzheng 发表于 2015-4-9 23:59
你能用你的link替我测一下第一题的code 吗? 我不用做OA 放心,我只是想测试一下我的想法。

他做不到的, 因为这种link一旦做过就没办法再登陆了
回复 支持 反对

使用道具 举报

dsq704136 发表于 2015-4-10 08:10:54 | 显示全部楼层
请问下楼主这个测试可以选择Python答么?
回复 支持 反对

使用道具 举报

dsq704136 发表于 2015-4-12 06:56:42 | 显示全部楼层
yabay91 发表于 2015-4-8 06:15
我也挂了。。。

第一题用的max heap做,8个case通过了5个,剩余3个显示timeout

想问一下第二题,如果字符串是aaa, 是不是只有一种排列?
回复 支持 反对

使用道具 举报

hit_piggy 发表于 2015-4-12 10:23:51 | 显示全部楼层
不知道我理解对第一题题意没有,想问下为啥不用dp做?
回复 支持 反对

使用道具 举报

hit_piggy 发表于 2015-4-13 04:30:10 | 显示全部楼层
第二题我的代码,求帮看下有没有问题。阶乘那边还可以优化

  1. public class PermutationIndex {
  2.     public void rank() throws IOException {
  3.         InputStreamReader isr = new InputStreamReader(System.in);
  4.         BufferedReader reader = new BufferedReader(isr);
  5.         int line = Integer.parseInt(reader.readLine());. From 1point 3acres bbs
  6.         for (int i=0; i<line; i++){
  7.             String str = reader.readLine();
  8.             char[] arr = str.toCharArray();. 鍥磋鎴戜滑@1point 3 acres
  9.             TreeMap<Character, Integer> map = new TreeMap<Character, Integer>();
  10.             for (int j=0; j<arr.length; j++){
  11.                 if (map.containsKey(arr[j]))
  12.                     map.put(arr[j], map.get(arr[j])+1);. 1point 3acres 璁哄潧
  13.                 else map.put(arr[j], 1);.1point3acres缃
  14.             }
  15.             int rank = 0;
  16.             for (int j=0; j<arr.length; j++){
  17.                 char cur = arr[j];
  18.                 for (char ch:map.keySet()){-google 1point3acres
  19.                     if (ch>=cur||map.get(ch)<=0) break;
  20.                     map.put(ch, map.get(ch)-1);
  21.                     rank += allNo(map);
  22.                     map.put(ch, map.get(ch)+1);
  23.                 }
  24.                 map.put(cur, map.get(cur)-1);
  25.             }
  26.             System.out.println(rank);
  27.         }-google 1point3acres
  28.     }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

  29.     private int allNo (TreeMap<Character, Integer> map) {
  30.         int count = 0;
  31.         int repCount = 1;
  32.         for (int rep:map.values()){
  33.             if (rep<=0) continue;
  34.             count += rep;
  35.             repCount *= factorial(rep);
  36.         }. 1point 3acres 璁哄潧
  37.         int res = factorial(count)/repCount;. 1point 3acres 璁哄潧
  38.         return res;.1point3acres缃
  39.     }

  40.     private int factorial (int n) {
  41.         if (n<=0) return 0;
  42.         int res=1;
  43.         for (int i=1; i<=n; i++) res *= i;
  44.         return res;
  45.     }
  46. }
复制代码
回复 支持 反对

使用道具 举报

limingli1991 发表于 2015-4-13 06:37:49 | 显示全部楼层
dsq704136 发表于 2015-4-10 08:10-google 1point3acres
请问下楼主这个测试可以选择Python答么?
.鏈枃鍘熷垱鑷1point3acres璁哄潧
可以的  你在选择语言的栏里面搜python就有了
回复 支持 反对

使用道具 举报

limingli1991 发表于 2015-4-13 06:48:15 | 显示全部楼层
nibuxing 发表于 2015-4-8 05:23
第一题是我BB的电面题,可以直接一个pointer来做。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
第一题怎么做啊
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-24 02:29

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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