一亩三分地论坛

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

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

Zenefit OA#2 分享

[复制链接] |试试Instant~ |关注本帖
nole 发表于 2015-6-9 15:18:15 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 博士 全职@Zenefit - 内推 - 在线笔试 |Pass在职跳槽

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

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

x
周么做了OA ZEN TEST 2. 题目有人已经发过了,我再发一遍,方便查找。
第一题: filp 1 or 0. 鍥磋鎴戜滑@1point 3 acres
You are given a binary array with N elements: d[0], d[1], ... d[N -1].
You can perform AT MOST one move on the array: choose any two integers [L, R],
and flip all the elements between (and including) the L-th and R-th bits. L and
R represent the left-most and right-most index of the bits marking the -google 1point3acres
boundaries of the segment which you have decided to flip.
. visit 1point3acres.com for more.
What is the maximum number of '1'-bits (indicated by S) which you can obtain in .鐣欏璁哄潧-涓浜-涓夊垎鍦
the final bit-string?. visit 1point3acres.com for more.
'Flipping' a bit means, that a 0 is transformed to a 1 and a 1 is transformed to
a 0
Input Format
An integer N
Next line contains the N bits, separated by spaces: d[0] d[1] ... d[N-1]
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
Output:
S
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
Sample Input:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
8
1 0 0 1 0 0 1 0
Sample Output:
6

我是用三个变量,扫描一遍数组:
- 如果元素是1, 1出现的次数+1,0的个数-1,但保持0的个数>=0;
- 否则,0的个数+1, 如果0的个数>maxZeros, 更新maxZeros
- 最后返回1的个数 + maxZeros



. From 1point 3acres bbs
第二题:

There are a large number of leaves eaten by caterpillars. There are 'K' caterpillars which jump onto the leaves in a pre-determined sequence.
All caterpillars start at position 0 and jump onto the leaves at positions  1,2,3...,N. Note that there is no leaf at position 0.
Each caterpillar has an associated 'jump-number'. Let the jump-number of the  i-th caterpillar be A [i]. A caterpillar with jump number 7 keeps eating leaves
in the order 1,241,3*1,... till it reaches the end of the leaves - i.e, it eats  the leaves at the positions which are multiples of .
Given a set A of K element是, K<=15, N <=109, we need to determine the number of uneaten leaves.

Input Format:
N -number of leaves
A - Given array of integers . 鍥磋鎴戜滑@1point 3 acres
. Waral 鍗氬鏈夋洿澶氭枃绔,
Output Format:
An integer denoting the number of uneaten leaves. . From 1point 3acres bbs

Sample Input: . 1point 3acres 璁哄潧
N = 10
A = [2,4,5]

Sample Output: . Waral 鍗氬鏈夋洿澶氭枃绔,
4

. From 1point 3acres bbs
因为N很大, K相对较小,所以不适合用数组来做。我是用Inclusion-Exclusion Principle做的。算法如下:.鏈枃鍘熷垱鑷1point3acres璁哄潧
for each subsets ss of length len in [1, K]:
    for each subset s in ss:
        calculate least common multiplier of elements in s, let be lcm-google 1point3acres
             eatenLeaves = N / lcm
             totalEatenLeaves += len % 2 == 1 ? eatenLeaves : -eatenLeaves
return N - totalEatenLeaves


计算subsets时,我存的是index,因为index 是有序的,所以不许要排序。另外,我写的是nextSubsets,每次调用,在原来的sunsets的基础上多加一个更大的index.
计算lcm时,如果只有一个元素,lcm就是自身。一下是用来计算两个数的lcm.
static long lcm(long a, long b) {
        return a * b / gcd(a, b);
}

static long gcd(long a, long b) {-google 1point3acres
        while (b != 0) {
                long temp = b;
                b = a % b;
                a = temp;
.鏈枃鍘熷垱鑷1point3acres璁哄潧        }
        return a;
}

希望有所帮助。祝大家好好准备,都有大OFFERS.加油!

俺是新手,能给点米吗?谢谢!

评分

9

查看全部评分

acex000 发表于 2015-6-17 08:07:30 | 显示全部楼层
请问一下楼主,第二题,你说的集合那里,要生成很多个集合啊?那是怎么实现的啊。。。?另外复杂度不会很高嘛?
回复 支持 反对

使用道具 举报

stplaydog 发表于 2015-10-27 13:13:58 | 显示全部楼层
用power set 算法。
回复 支持 反对

使用道具 举报

Kevin73S 发表于 2016-1-30 11:29:57 | 显示全部楼层
LZ 第二题所有 Test都过了吗?

我有两个一直过不去 Test6和8
回复 支持 反对

使用道具 举报

 楼主| nole 发表于 2016-1-30 11:42:09 | 显示全部楼层
是的。都过了。
回复 支持 反对

使用道具 举报

UCLA_andy 发表于 2016-2-10 04:09:52 | 显示全部楼层
请问楼主,可以知道你要做的是第几套OA吗?我刚刚收到了OA的邮件。
回复 支持 反对

使用道具 举报

 楼主| nole 发表于 2016-2-10 04:25:40 | 显示全部楼层
这个是第二套。
回复 支持 反对

使用道具 举报

 楼主| nole 发表于 2016-2-10 04:26:59 | 显示全部楼层
最近也有人做的第三套。皇后最大威胁的那套。
回复 支持 反对

使用道具 举报

UCLA_andy 发表于 2016-2-10 04:34:25 | 显示全部楼层
nole 发表于 2016-2-10 04:26
最近也有人做的第三套。皇后最大威胁的那套。

同学,请问下,我申的intern,刚刚收到邮件做OA,可以知道我做的是第几套吗?谢谢。
回复 支持 反对

使用道具 举报

Newneo 发表于 2016-2-16 04:46:30 | 显示全部楼层
大家做完了oa,提交以后会收到confirmation email之类的么?
回复 支持 反对

使用道具 举报

 楼主| nole 发表于 2016-2-16 04:55:07 | 显示全部楼层
没有email确认。Hackranker 会告诉你已经提交。
回复 支持 反对

使用道具 举报

Newneo 发表于 2016-2-16 05:08:03 | 显示全部楼层
就是点了I am done with the test.。显示已经提交了就没了是么
回复 支持 反对

使用道具 举报

 楼主| nole 发表于 2016-2-16 05:09:35 | 显示全部楼层
yes. you will be reached quickly by zenefits.
回复 支持 反对

使用道具 举报

UCLA_andy 发表于 2016-2-16 05:40:33 | 显示全部楼层
nole 发表于 2016-2-16 05:09.鏈枃鍘熷垱鑷1point3acres璁哄潧
yes. you will be reached quickly by zenefits.
. from: 1point3acres.com/bbs
好像还要发邮件给HR吧?大概多久会收到HR的邮件?
回复 支持 反对

使用道具 举报

 楼主| nole 发表于 2016-2-16 08:45:48 | 显示全部楼层
他们很快滴
回复 支持 反对

使用道具 举报

UCLA_andy 发表于 2016-2-17 02:55:21 | 显示全部楼层

嗯,早上刚刚收到邮件说,安排10分钟的时间说你的背景还有什么you expect的。。之前没遇到过。
回复 支持 反对

使用道具 举报

Newneo 发表于 2016-2-17 13:59:21 | 显示全部楼层
我今天早上收到邮件说move forward with interview.但是。。由于他们正在重新衡量招人计划,要我等着进一步通知
回复 支持 反对

使用道具 举报

UCLA_andy 发表于 2016-2-18 05:46:27 | 显示全部楼层
Newneo 发表于 2016-2-17 13:59. from: 1point3acres.com/bbs
我今天早上收到邮件说move forward with interview.但是。。由于他们正在重新衡量招人计划,要我等着进一步 ...
. From 1point 3acres bbs
是吗?我就收到了让我填个时间,然后说10分钟的背景。。。没回复我了。
回复 支持 反对

使用道具 举报

 楼主| nole 发表于 2016-3-5 08:40:36 | 显示全部楼层
贴上我的实现,供大家参考。

  1. import java.util.ArrayList;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  2. import java.util.Deque;
  3. import java.util.LinkedList;
  4. import java.util.List;
  5. import java.util.Scanner;

  6. public class EatingLeaves {
  7.   /**
  8.    * Greatest common divisor. 1point 3acres 璁哄潧
  9.    *
  10.    * @param x
  11.    * @param y
  12.    * [url=home.php?mod=space&uid=160137]@return[/url] Greatest common divisor
  13.    */
  14.   private static long gcd(long x, long y) {
  15.     while (y != 0) {
  16.       long temp = y;
  17.       y = x % y;
  18.       x = temp;. Waral 鍗氬鏈夋洿澶氭枃绔,
  19.     }
  20.     return x;
  21.   }.鏈枃鍘熷垱鑷1point3acres璁哄潧

  22.   /**-google 1point3acres
  23.    * Least common multiplier
  24.    *
  25.    * @param x
  26.    * @param y
  27.    * @return Least common multiplier
  28.    */
  29.   private static long lcm(long x, long y) {. 鍥磋鎴戜滑@1point 3 acres
  30.     return x * y / gcd(x, y);
  31.   }

  32. -google 1point3acres
  33.   /**
  34.    * @param indices
  35.    * @param jumps. Waral 鍗氬鏈夋洿澶氭枃绔,
  36.    * @return
  37.    */. Waral 鍗氬鏈夋洿澶氭枃绔,
  38.   private static long lcm(List<Integer> indices, List<Long> jumps) {
  39.     if (indices.size() == 1) return jumps.get(indices.get(0));
  40.     long multipler = jumps.get(indices.get(0));
  41.     for (int i = 1, n = indices.size(); i < n; ++i) {
  42.       multipler = lcm(multipler, jumps.get(indices.get(i)));
  43.     }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  44.     return multipler;
  45.   }

  46.   /**
  47.    * @param comb
  48.    * @param numJumps.鐣欏璁哄潧-涓浜-涓夊垎鍦
  49.    * @return.鏈枃鍘熷垱鑷1point3acres璁哄潧
  50.    */
  51.   private static Deque<List<Integer>> nextCombinations(
  52.       Deque<List<Integer>> combinations,
  53.       int numJumps) {
  54. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  55.     if (combinations.isEmpty()) { // Build combination with size of one
  56.       for (int i = 0; i < numJumps; ++i) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  57.         List<Integer> combination = new ArrayList<Integer>();. more info on 1point3acres.com
  58.         combination.add(i); // index
  59.         combinations.add(combination);
  60.       }
  61.       return combinations;
  62.     }

  63.     // Build next combinations with one more in length. visit 1point3acres.com for more.
  64.     for (int i = 0, n = combinations.size(); i < n; ++i) {-google 1point3acres
  65.       List<Integer> combination = combinations.poll();
  66.       for (int j = combination.get(combination.size() - 1) + 1; j < numJumps; ++j) {
  67.         List<Integer> newComb = new ArrayList<>(combination);
  68.         newComb.add(j);
  69.         combinations.addLast(newComb);
  70.       }
  71.     }
  72.     return combinations;.1point3acres缃
  73.   }

  74.   public static long computeUneatenLeaves(long N, List<Long> jumps) {-google 1point3acres
  75.     long totalEatenLeaves = 0;
  76.     Deque<List<Integer>> combs = new LinkedList<>();
  77.     for (int len = 0, n = jumps.size(); len < n; ++len) {
  78.       combs = nextCombinations(combs, jumps.size());
  79.       for (List<Integer> c : combs) {
  80.         long multiplier = lcm(c, jumps);
  81.         long eatenLeaves = N / multiplier;
  82.         totalEatenLeaves += (len % 2 == 0) ? eatenLeaves : -eatenLeaves;
  83.       }
  84.     }
  85.     return N - totalEatenLeaves;
  86.   }

  87.   /**. From 1point 3acres bbs
  88.    * @param args
  89.    */
  90.   public static void main(String[] args) {
  91.     // TODO Auto-generated method stub
  92. //                Scanner scanner = null, lineScanner = null;
  93. //                try {
  94. //                        scanner = new Scanner(System.in);
  95. //
  96. //                        List<Long> jumps = new ArrayList<>();
  97. //                        Long N = scanner.nextLong();
  98. ////                        System.out.println(N);
  99. //                        scanner.nextLine();
  100. //                        lineScanner = new Scanner(scanner.nextLine());
  101. //                        while (lineScanner.hasNextLong()) {
  102. //                                jumps.add(lineScanner.nextLong());
  103. //                        }
  104. ////                        System.out.println(jumps.toString());
  105. //                        long unletenLeaves = computeUneatenLeaves(N, jumps);
  106. //                        System.out.println(unletenLeaves);
  107. //
  108. //                } catch (Exception e) { // TODO: Handle exception elegantly
  109. //                        System.out.println(e.getMessage());
  110. //                } finally {
  111. //                        if (scanner != null) scanner.close();
  112. //                        if (lineScanner != null) lineScanner.close();
  113. //                }
  114. //               
  115.     List<Long> jumps = new ArrayList<>();
  116.     jumps.add(2L);
  117.     jumps.add(3L);
  118.     jumps.add(4L);
  119.     long N = 24;
  120.     long unletenLeaves = computeUneatenLeaves(N, jumps);
  121.     System.out.println(unletenLeaves);
  122.   }
  123. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 06:16

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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