[八我司] Expedia一年半遊:这是一個特別適合養老待退的地方

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 5747|回复: 18
收起左侧

Zenefit OA#2 分享

[复制链接] |试试Instant~ |关注本帖
我的人缘0
nole 发表于 2015-6-9 15:18:15 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

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

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

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

x
周么做了OA ZEN TEST 2. 题目有人已经发过了,我再发一遍,方便查找。
第一题: filp 1 or 0
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 . visit 1point3acres for more.
R represent the left-most and right-most index of the bits marking the .留学论坛-一亩-三分地
boundaries of the segment which you have decided to flip.. 留学申请论坛-一亩三分地

What is the maximum number of '1'-bits (indicated by S) which you can obtain in
the final bit-string?
'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
.本文原创自1point3acres论坛
我是用三个变量,扫描一遍数组:
- 如果元素是1, 1出现的次数+1,0的个数-1,但保持0的个数>=0;. 1point3acres
- 否则,0的个数+1, 如果0的个数>maxZeros, 更新maxZeros
- 最后返回1的个数 + maxZeros

. 围观我们@1point 3 acres


第二题:
. from: 1point3acres
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: .1point3acres网
N -number of leaves
A - Given array of integers
.本文原创自1point3acres论坛
Output Format: . 留学申请论坛-一亩三分地
An integer denoting the number of uneaten leaves.
. 一亩-三分-地,独家发布
Sample Input: . 一亩-三分-地,独家发布
N = 10
A = [2,4,5]

Sample Output:
4


因为N很大, K相对较小,所以不适合用数组来做。我是用Inclusion-Exclusion Principle做的。算法如下:
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
             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) {
        while (b != 0) {
                long temp = b;
                b = a % b;. 1point3acres
                a = temp;
        }
        return a;
}

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

俺是新手,能给点米吗?谢谢!. 1point 3acres 论坛

评分

参与人数 9大米 +94 收起 理由
cheryllol + 2 感谢分享!
whdawn + 40
diors + 3 感谢分享!
sevensevens + 1 感谢分享!
tiantiana + 1 谢谢你的介绍!
MRlfy + 5 感谢分享!
wrj5518 + 40
辉哥哥 + 1 谢谢分享啊
liuyuxinxin + 1 超棒!

查看全部评分


上一篇:Drawbridge 被虐哭了
下一篇:昨天 OA, 附上new language 原题
我的人缘0
acex000 发表于 2015-6-17 08:07:30 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
请问一下楼主,第二题,你说的集合那里,要生成很多个集合啊?那是怎么实现的啊。。。?另外复杂度不会很高嘛?
回复 支持 反对

使用道具 举报

我的人缘0
stplaydog 发表于 2015-10-27 13:13:58 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
用power set 算法。
回复 支持 反对

使用道具 举报

我的人缘0
Kevin73S 发表于 2016-1-30 11:29:57 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
LZ 第二题所有 Test都过了吗?
. 留学申请论坛-一亩三分地
我有两个一直过不去 Test6和8
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| nole 发表于 2016-1-30 11:42:09 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
是的。都过了。
回复 支持 反对

使用道具 举报

我的人缘0
UCLA_andy 发表于 2016-2-10 04:09:52 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
请问楼主,可以知道你要做的是第几套OA吗?我刚刚收到了OA的邮件。
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| nole 发表于 2016-2-10 04:25:40 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
这个是第二套。
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| nole 发表于 2016-2-10 04:26:59 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
最近也有人做的第三套。皇后最大威胁的那套。
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
UCLA_andy 发表于 2016-2-10 04:34:25 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
nole 发表于 2016-2-10 04:26
最近也有人做的第三套。皇后最大威胁的那套。

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

使用道具 举报

我的人缘0
Newneo 发表于 2016-2-16 04:46:30 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
大家做完了oa,提交以后会收到confirmation email之类的么?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| nole 发表于 2016-2-16 04:55:07 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
没有email确认。Hackranker 会告诉你已经提交。
回复 支持 反对

使用道具 举报

我的人缘0
Newneo 发表于 2016-2-16 05:08:03 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
就是点了I am done with the test.。显示已经提交了就没了是么
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| nole 发表于 2016-2-16 05:09:35 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
yes. you will be reached quickly by zenefits.
回复 支持 反对

使用道具 举报

我的人缘0
UCLA_andy 发表于 2016-2-16 05:40:33 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
nole 发表于 2016-2-16 05:09
yes. you will be reached quickly by zenefits.

好像还要发邮件给HR吧?大概多久会收到HR的邮件?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| nole 发表于 2016-2-16 08:45:48 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
他们很快滴
回复 支持 反对

使用道具 举报

我的人缘0
UCLA_andy 发表于 2016-2-17 02:55:21 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

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

使用道具 举报

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

使用道具 举报

我的人缘0
UCLA_andy 发表于 2016-2-18 05:46:27 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
Newneo 发表于 2016-2-17 13:59. 围观我们@1point 3 acres
我今天早上收到邮件说move forward with interview.但是。。由于他们正在重新衡量招人计划,要我等着进一步 ...
. visit 1point3acres for more.
是吗?我就收到了让我填个时间,然后说10分钟的背景。。。没回复我了。
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| nole 发表于 2016-3-5 08:40:36 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
贴上我的实现,供大家参考。

  1. import java.util.ArrayList;
  2. import java.util.Deque;
  3. import java.util.LinkedList;-google 1point3acres
  4. import java.util.List;. 围观我们@1point 3 acres
  5. import java.util.Scanner;. From 1point 3acres bbs

  6. public class EatingLeaves {
  7.   /**
  8.    * Greatest common divisor
  9.    *
  10.    * @param x
  11.    * @param y. from: 1point3acres
  12.    * [url=home.php?mod=space&uid=160137]@return[/url] Greatest common divisor
  13.    */. from: 1point3acres
  14.   private static long gcd(long x, long y) {
  15.     while (y != 0) {
  16.       long temp = y;
  17.       y = x % y;
  18.       x = temp;
  19.     }
  20.     return x;. more info on 1point3acres
  21.   }

  22.   /**
  23.    * Least common multiplier
  24.    *
  25.    * @param x
  26.    * @param y
  27.    * @return Least common multiplier
  28.    */. 围观我们@1point 3 acres
  29.   private static long lcm(long x, long y) {
  30.     return x * y / gcd(x, y);
  31.   }

  32.   /**
  33.    * @param indices
  34.    * @param jumps
    . from: 1point3acres
  35.    * @return
  36.    */
  37.   private static long lcm(List<Integer> indices, List<Long> jumps) {
    . Waral 博客有更多文章,
  38.     if (indices.size() == 1) return jumps.get(indices.get(0));
  39.     long multipler = jumps.get(indices.get(0));
  40.     for (int i = 1, n = indices.size(); i < n; ++i) {
  41.       multipler = lcm(multipler, jumps.get(indices.get(i)));
  42.     }
  43.     return multipler;. from: 1point3acres
  44.   }

  45. 来源一亩.三分地论坛.
  46.   /**. Waral 博客有更多文章,
  47.    * @param comb
  48.    * @param numJumps
  49.    * @return
  50.    */
  51.   private static Deque<List<Integer>> nextCombinations(
  52.       Deque<List<Integer>> combinations,
  53.       int numJumps) {

  54.     if (combinations.isEmpty()) { // Build combination with size of one
  55.       for (int i = 0; i < numJumps; ++i) {. 留学申请论坛-一亩三分地
  56.         List<Integer> combination = new ArrayList<Integer>();
  57.         combination.add(i); // index
  58.         combinations.add(combination);
  59.       }
  60.       return combinations;. more info on 1point3acres
  61.     }

  62.     // Build next combinations with one more in length
  63.     for (int i = 0, n = combinations.size(); i < n; ++i) {
  64.       List<Integer> combination = combinations.poll();.留学论坛-一亩-三分地
  65.       for (int j = combination.get(combination.size() - 1) + 1; j < numJumps; ++j) {
  66.         List<Integer> newComb = new ArrayList<>(combination);
  67.         newComb.add(j);
  68.         combinations.addLast(newComb);
  69.       }
  70.     } 来源一亩.三分地论坛.
  71.     return combinations;
  72.   }

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

  86.   /**
  87.    * @param args
  88.    */
  89.   public static void main(String[] args) {
  90.     // TODO Auto-generated method stub
  91. //                Scanner scanner = null, lineScanner = null;
  92. //                try {
  93. //                        scanner = new Scanner(System.in);
  94. //.1point3acres网
  95. //                        List<Long> jumps = new ArrayList<>();
  96. //                        Long N = scanner.nextLong();. 留学申请论坛-一亩三分地
  97. ////                        System.out.println(N);
  98. //                        scanner.nextLine();
  99. //                        lineScanner = new Scanner(scanner.nextLine());
  100. //                        while (lineScanner.hasNextLong()) {. Waral 博客有更多文章,
  101. //                                jumps.add(lineScanner.nextLong());
  102. //                        }
  103. ////                        System.out.println(jumps.toString());
  104. //                        long unletenLeaves = computeUneatenLeaves(N, jumps);
  105. //                        System.out.println(unletenLeaves);
    . 围观我们@1point 3 acres
  106. //. 1point 3acres 论坛
  107. //                } catch (Exception e) { // TODO: Handle exception elegantly
  108. //                        System.out.println(e.getMessage());
  109. //                } finally {
  110. //                        if (scanner != null) scanner.close();-google 1point3acres
  111. //                        if (lineScanner != null) lineScanner.close();
  112. //                }. more info on 1point3acres
  113. //               
  114.     List<Long> jumps = new ArrayList<>();
  115.     jumps.add(2L);
  116.     jumps.add(3L);.留学论坛-一亩-三分地
  117.     jumps.add(4L);
  118.     long N = 24;. 一亩-三分-地,独家发布
  119.     long unletenLeaves = computeUneatenLeaves(N, jumps);. Waral 博客有更多文章,
  120.     System.out.println(unletenLeaves);
  121.   }
  122. }
复制代码
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-6-19 10:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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