May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

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

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

Zenefits OA 1-4整理

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

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

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

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

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

OA-1

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


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

OA-2
-google 1point3acres
1.flip 0 or 1


2. uneaten leaves  




OA-3


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做。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
. 1point 3acres 璁哄潧

-google 1point3acres
第二题,有一个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 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
Solution for OA-4 permutation index, 要想过所有testcase,记得用biginteger,或者其他可以处理长度超过long的整数
  1. public long permutationIndexII(int[] A) {
    . 1point 3acres 璁哄潧
  2.     if (A == null || A.length == 0) {
  3.         return 0;
  4.     }
  5.     long res = 1;
  6.     long factor = 1;. 1point 3acres 璁哄潧
  7.     Map<Integer, Integer> map = new HashMap<>();. visit 1point3acres.com for more.
  8.     for (int i = A.length - 1; i >= 0; i--) {
  9.         int count = 0;
  10.         Integer val = map.get(A[i]);. Waral 鍗氬鏈夋洿澶氭枃绔,
  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]) {
  18.                 count++;
  19.             }
  20.         }
  21.         res += count * factor / duplicatesFactor(map);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  22.         factor *= (A.length - i);
  23.     }. visit 1point3acres.com for more.
  24.     return res;
  25. }
  26. private long duplicatesFactor(Map<Integer, Integer> map) {. 鍥磋鎴戜滑@1point 3 acres
  27.     long res = 1;
  28.     for (int val : map.values()) {
  29.         res *= getFactor(val);
  30.     }
  31.     return res;
  32. }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  33. private long getFactor(int num) {
  34.     long res = 1;
  35.     for (int i = 1; i <= num; i++) {
  36.         res *= i;. 鍥磋鎴戜滑@1point 3 acres
  37.     }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  38.     return res;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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.     }
  11.     long tickets = m;
  12.     while (tickets > 0) {
  13.         int count = queue.poll();
  14.         res += count;
  15.         queue.offer(count - 1);. more info on 1point3acres.com
  16.         tickets--;. From 1point 3acres bbs
  17.     }
  18.     return res;. visit 1point3acres.com for more.
  19. }
复制代码
Solution 2:
  1. public  long sellTicket(int[] arr, long m) {
  2.     long res = 0;
  3.     int threshold = 0;
  4.     int l = 0;
  5.     int r = 0;. more info on 1point3acres.com
  6.     for (int num : arr) {
  7.         r = Math.max(num, r);
  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;
  15.         } else if (sum1 < m) {
  16.             r = threshold;
  17.         } else {
  18.             l = threshold;. more info on 1point3acres.com
  19.         }
  20.     }
  21.     long tickets = 0;
  22.     for (int num : arr) {-google 1point3acres
  23.         if (num >= threshold) {-google 1point3acres
  24.             tickets += num - threshold + 1;
  25.             res += ((long) (threshold + num) * (long) (num - threshold + 1)) / 2;
  26.         }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  27.     } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  28.     res -= (tickets - m) * threshold;
  29.     return res;
  30. }

  31. private long getSum(int threshold, int[] arr) {
  32.     long res = 0;
  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 | 显示全部楼层
关注一亩三分地微博:
Warald
好多难题,看的好晕
回复 支持 反对

使用道具 举报

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

所以这个题关键就是,如何求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. 1point 3acres 璁哄潧
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: 1point3acres.com/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++){-google 1point3acres
  8.             if(!mapPosition.containsKey(jumpNumber[i] * j)){
  9.                 mapPosition.put(jumpNumber[i] * j, 1);. Waral 鍗氬鏈夋洿澶氭枃绔,
  10.                 countEaten++;
  11.             }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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 | 显示全部楼层
returning 发表于 2015-10-12 12:27. Waral 鍗氬鏈夋洿澶氭枃绔,
求链接,多谢。

额,一下子找不到了。但是第一题的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
我刚刚做了第三套,关键是网上居然还有个博客,里面直接有代码。。。。。

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

使用道具 举报

 楼主| 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
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-28 10:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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