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


一亩三分地论坛

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

Zenefits OA 1-4整理

  [复制链接] |试试Instant~ |关注本帖
wish 发表于 2015-10-11 11:58:32 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Zenefits - 内推 - 在线笔试 |Otherfresh grad应届毕业生

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

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

x
感谢内推版好心人内推,今天刚做完在线oa,在这里贴下自己整理的内容,方便后面人查看

OA-1

一题是给一串数,判断是否有对应的BST可以产生preorder的序列跟给的数串一样。



第二题是实现一个super stack。操作有push, pop。 还有一个是increase a b。实现stack
的bottom a个数都加b。要考虑输入比较大的情况。
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.

OA-4

1. 第一题,有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情况。.

. From 1point 3acres bbs



补充内容 (2015-10-13 11:05):
有人问oa-4 solution, 已经在18楼回复,希望对大家有帮助,另外在上面的两个链接也可以得到一些idea

评分

8

查看全部评分

本帖被以下淘专辑推荐:

 楼主| wish 发表于 2015-10-13 11:03:05 | 显示全部楼层
Solution for OA-4 permutation index, 要想过所有testcase,记得用biginteger,或者其他可以处理长度超过long的整数
  1. public long permutationIndexII(int[] A) {
  2.     if (A == null || A.length == 0) {
  3.         return 0;. from: 1point3acres.com/bbs
  4.     }
  5.     long res = 1;
  6.     long factor = 1;
  7.     Map<Integer, Integer> map = new HashMap<>();
  8.     for (int i = A.length - 1; i >= 0; i--) {. From 1point 3acres bbs
  9.         int count = 0;. From 1point 3acres bbs
  10.         Integer val = map.get(A[i]);
  11.         if (val == null) {
  12.             map.put(A[i], 1);
  13.         } else {
  14.             map.put(A[i], val + 1);
  15.         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  16.         for (int j = i + 1; j < A.length; j++) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  17.             if (A[i] > A[j]) {. visit 1point3acres.com for more.
  18.                 count++;
  19.             }
  20.         }
  21.         res += count * factor / duplicatesFactor(map);
  22.         factor *= (A.length - i);
  23.     } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  24.     return res;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  25. }
  26. private long duplicatesFactor(Map<Integer, Integer> map) {
  27.     long res = 1;
  28.     for (int val : map.values()) {
  29.         res *= getFactor(val);
  30.     }
  31.     return res;
  32. }
  33. private long getFactor(int num) {
  34.     long res = 1;
  35.     for (int i = 1; i <= num; i++) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  36.         res *= i;
  37.     }
  38.     return res;
  39. }
复制代码
Solution for OA-4 Sell ticket. from: 1point3acres.com/bbs
. 1point3acres.com/bbs
Solution 1:
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
回复 支持 1 反对 0

使用道具 举报

returning 发表于 2015-10-12 01:49:29 | 显示全部楼层
好多难题,看的好晕
回复 支持 反对

使用道具 举报

returning 发表于 2015-10-12 02:10:49 | 显示全部楼层
caterpillars那道题,我会先找出k个数中所有的质数,这是因为如果一个数能够被M整除,那意味着能够被M的质数因子整除,求所有质数的算法很固定。然后,假设质数集合是U,U中所有数乘积是V,那么我们可以得到1-V中能够被至少一个质数整除的数个数,知道这个数的话,后面就简单了。
我看了很多地方,貌似都没有说用这个来算, 不用使用什么inclusion-exclusion principle,因为那需要生成很多数,是O(N)量级的,不知道我理解错没有。

所以这个题关键就是,如何求1-V中能够被至少一个质数整除的数个数,当然这也是基本求质数的算法,如果能够和第一步结合起来做一次遍历就理想了。

补充内容 (2015-10-12 03:41):
sorry, 还是需要用inclusion-exclusion,只是说对所有质数求,但是还是很麻烦的。因为,求1-V中所有质数还是很耗费时间,因为V比k大多了。
回复 支持 反对

使用道具 举报

303002319 发表于 2015-10-12 07:26:40 | 显示全部楼层
请问一下,已经有新题的情况下,会不会还有可能使用老的题目?
回复 支持 反对

使用道具 举报

 楼主| wish 发表于 2015-10-12 08:26:51 | 显示全部楼层
returning 发表于 2015-10-12 01:49
好多难题,看的好晕

可以做之前准备下
回复 支持 反对

使用道具 举报

 楼主| wish 发表于 2015-10-12 08:28:20 | 显示全部楼层
303002319 发表于 2015-10-12 07:26
请问一下,已经有新题的情况下,会不会还有可能使用老的题目?

感觉现在就是上面的四套题,并且发oa时你能看到是第几套,因为有编号~建议是把所有的题都看看,然后把自己要做的那套题写一遍,这样应该就没问题啦
回复 支持 反对

使用道具 举报

 楼主| wish 发表于 2015-10-12 08:31:08 | 显示全部楼层
returning 发表于 2015-10-12 02:10
caterpillars那道题,我会先找出k个数中所有的质数,这是因为如果一个数能够被M整除,那意味着能够被M的质 ...

除了inclusion-exclusion principle外我觉得下面这个方法也还可以,在时间上
  1. public int countUneatenLeaves(int[] jumpNumber, int numberLeaves) {
  2.     int catArraySize = jumpNumber.length;
  3.     int countEaten = 0;
  4.     Map<Integer,Integer> mapPosition = new HashMap<>();
  5.     for( int i = 0; i < catArraySize; i++ ){. from: 1point3acres.com/bbs
  6.         int catervalue = jumpNumber[i];
  7.         for(int j = 1; j * catervalue <= numberLeaves; j++){
  8.             if(!mapPosition.containsKey(jumpNumber[i] * j)){
  9.                 mapPosition.put(jumpNumber[i] * j, 1);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  10.                 countEaten++;
  11.             }
  12.         }
  13.     }
  14.     return numberLeaves - countEaten;
  15. }
复制代码
回复 支持 反对

使用道具 举报

303002319 发表于 2015-10-12 11:21:24 | 显示全部楼层
wish 发表于 2015-10-12 08:28
感觉现在就是上面的四套题,并且发oa时你能看到是第几套,因为有编号~建议是把所有的题都看看,然后把自 ...

我刚刚做了第三套,关键是网上居然还有个博客,里面直接有代码。。。。。
回复 支持 反对

使用道具 举报

returning 发表于 2015-10-12 12:27:25 | 显示全部楼层
303002319 发表于 2015-10-12 11:21
我刚刚做了第三套,关键是网上居然还有个博客,里面直接有代码。。。。。

求链接,多谢。
回复 支持 反对

使用道具 举报

303002319 发表于 2015-10-12 12:50:27 | 显示全部楼层

额,一下子找不到了。但是第一题的longestChain的那题,我自己在电脑里面写了。而且也处理了最长string并不在result中的可能。
回复 支持 反对

使用道具 举报

dxpppi 发表于 2015-10-12 12:57:45 | 显示全部楼层
郁闷啊,遇到的是OA1,太简单都没怎么准备。然后hacerrank提供的test case就一两个。各写了十几分钟test完就submit了……现在想想好后悔没把code写的更好一点
回复 支持 反对

使用道具 举报

 楼主| wish 发表于 2015-10-13 00:28:28 | 显示全部楼层
303002319 发表于 2015-10-12 11:21. more info on 1point3acres.com
我刚刚做了第三套,关键是网上居然还有个博客,里面直接有代码。。。。。

看来做的很顺利~恭喜哈
回复 支持 反对

使用道具 举报

 楼主| wish 发表于 2015-10-13 00:31:37 | 显示全部楼层
dxpppi 发表于 2015-10-12 12:57
郁闷啊,遇到的是OA1,太简单都没怎么准备。然后hacerrank提供的test case就一两个。各写了十几分钟test完 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
我做的OA4, 记不清具体多少testcase,好像都是8-10个,做的其他其他公司在hackerrank上的OA也是8-10个,一两个test的题没有遇到过诶,好奇怪
回复 支持 反对

使用道具 举报

dxpppi 发表于 2015-10-13 01:57:26 | 显示全部楼层
wish 发表于 2015-10-13 00:31
我做的OA4, 记不清具体多少testcase,好像都是8-10个,做的其他其他公司在hackerrank上的OA也是8-10个, ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
TEST CASE是在题目下面附的zip包里吗?我点开真的只有1-2个……
回复 支持 反对

使用道具 举报

zhangyh1990 发表于 2015-10-13 07:13:45 | 显示全部楼层
谢谢lz!
请问可以分享下OA4的做法吗?好像常规解法只能过一半test case是吗?. more info on 1point3acres.com
就是第一题用heap,第二题next permutation的解法。
回复 支持 反对

使用道具 举报

俩王四个二 发表于 2015-10-13 08:40:43 | 显示全部楼层
dxpppi 发表于 2015-10-12 12:57-google 1point3acres
郁闷啊,遇到的是OA1,太简单都没怎么准备。然后hacerrank提供的test case就一两个。各写了十几分钟test完 ...

我也收到的是OA1,郵件寫著1就是1了吧?謝謝
回复 支持 反对

使用道具 举报

Quinny 发表于 2015-10-13 10:30:57 | 显示全部楼层
谢楼主分享,这几天正好要做OA
回复 支持 反对

使用道具 举报

 楼主| wish 发表于 2015-10-13 11:07:30 | 显示全部楼层
俩王四个二 发表于 2015-10-13 08:40
我也收到的是OA1,郵件寫著1就是1了吧?謝謝
.1point3acres缃
恩恩,理论上是
回复 支持 反对

使用道具 举报

 楼主| wish 发表于 2015-10-13 11:10:25 | 显示全部楼层
dxpppi 发表于 2015-10-13 01:57
TEST CASE是在题目下面附的zip包里吗?我点开真的只有1-2个……

需要submit
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-20 15:45

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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