一亩三分地论坛

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

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

Zenefits OA 1-4整理

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

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

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

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

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

OA-1

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

. more info on 1point3acres.com

第二题是实现一个super stack。操作有push, pop。 还有一个是increase a b。实现stack
的bottom a个数都加b。要考虑输入比较大的情况。

OA-2
.鏈枃鍘熷垱鑷1point3acres璁哄潧
1.flip 0 or 1


2. uneaten leaves  




OA-3
. 1point3acres.com/bbs

new:
Longest String Chain
N Queens Most Threats



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情况。.





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

评分

7

查看全部评分

本帖被以下淘专辑推荐:

 楼主| 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;
  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--) {
  9.         int count = 0;
  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()) {
    .1point3acres缃
  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++) {. from: 1point3acres.com/bbs
  36.         res *= i;
  37.     }
  38.     return res;
  39. }
复制代码
Solution for OA-4 Sell ticket

Solution 1: priority queue, 答案正确,没有在oa上试过
  1. public long sellTicket1(int[] arr, long m) {
  2.     long res = 0;
  3.     PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
  4.             public int compare(Integer el1, Integer el2) {
  5.                 return el2 - el1;
  6.             }
  7.     });
  8.     for (int num : arr) {
  9.         queue.offer(num);
  10.     }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  11.     long tickets = m;
  12.     while (tickets > 0) {. more info on 1point3acres.com
  13.         int count = queue.poll();
  14.         res += count;
  15.         queue.offer(count - 1);
  16.         tickets--;
  17.     }
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  18.     return res;
  19. }
复制代码
Solution 2:
  1. public  long sellTicket(int[] arr, long m) {
  2.     long res = 0;. more info on 1point3acres.com
  3.     int threshold = 0; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  4.     int l = 0;
  5.     int r = 0;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  6.     for (int num : arr) {. from: 1point3acres.com/bbs
  7.         r = Math.max(num, r);. 1point 3acres 璁哄潧
  8.     }
  9.     while (l <= r) {
  10.         threshold = l + (r - l) / 2;
  11.         long sum1 = getSum(threshold, arr);
  12.         long sum2 = getSum(threshold + 1, arr);
  13.         if (sum2 <= m && m <= sum1) {
  14.             break;. Waral 鍗氬鏈夋洿澶氭枃绔,
  15.         } else if (sum1 < m) {
  16.             r = threshold;
  17.         } else {. 1point 3acres 璁哄潧
  18.             l = threshold;
  19.         }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  20.     }
  21.     long tickets = 0;
  22.     for (int num : arr) {
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  23.         if (num >= threshold) {. From 1point 3acres bbs
  24.             tickets += num - threshold + 1;
  25.             res += ((long) (threshold + num) * (long) (num - threshold + 1)) / 2;
  26.         }. from: 1point3acres.com/bbs
  27.     }
  28.     res -= (tickets - m) * threshold;
  29.     return res;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  30. }

  31. private long getSum(int threshold, int[] arr) {
  32.     long res = 0;.1point3acres缃
  33.     for (int num : arr) {
  34.         res += num - threshold >= 0 ? num - threshold + 1 : 0;
  35.     }
  36.     return res;
  37. }
复制代码
回复 支持 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;
    . From 1point 3acres bbs
  4.     Map<Integer,Integer> mapPosition = new HashMap<>();
  5.     for( int i = 0; i < catArraySize; i++ ){
  6.         int catervalue = jumpNumber[i];
  7.         for(int j = 1; j * catervalue <= numberLeaves; j++){
  8.             if(!mapPosition.containsKey(jumpNumber[i] * j)){. 1point3acres.com/bbs
  9.                 mapPosition.put(jumpNumber[i] * j, 1);
  10.                 countEaten++;
  11.             }
  12.         }. 1point3acres.com/bbs
  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 | 显示全部楼层
. visit 1point3acres.com for more.
额,一下子找不到了。但是第一题的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. From 1point 3acres bbs
我刚刚做了第三套,关键是网上居然还有个博客,里面直接有代码。。。。。

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

使用道具 举报

 楼主| 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是吗?
就是第一题用heap,第二题next permutation的解法。
回复 支持 反对

使用道具 举报

俩王四个二 发表于 2015-10-13 08:40:43 | 显示全部楼层
dxpppi 发表于 2015-10-12 12:57
郁闷啊,遇到的是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了吧?謝謝

恩恩,理论上是
回复 支持 反对

使用道具 举报

 楼主| wish 发表于 2015-10-13 11:10:25 | 显示全部楼层
dxpppi 发表于 2015-10-13 01:57. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
TEST CASE是在题目下面附的zip包里吗?我点开真的只有1-2个……

需要submit
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 00:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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