San Jose各个房价 <1.5m 区域买房总结

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 2501|回复: 13
收起左侧

Zenefits电面

[复制链接] |试试Instant~ |关注本帖
nothingtrouble 发表于 2015-10-14 05:28:23 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类General 博士 全职@Zenefits - 内推 - 技术电面  | Other | fresh grad应届毕业生

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

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

x
听说没有经过烙印的面试,不是完整的找工。于是今天圆梦了

烙印,迟到15分钟,上来不废话,问我:“你是想我给你难题目一道题目,还是两道简单的”。我说:“我能先看一下题目再选吗?” "NO" “那我选简单的”

1. 很绕,题目很长,需要自己parse string,get parameters。我一开始以为是unique path,造福大家,我直接给上题目意思了,真心讨厌在这么短时间里面贴好多文字过来。给定m,n,表示horizontal走m步,vertical走n步,那么m=2,n=2,其中一种走法就是 [ H H V V ] 另外一种是 [ H V H V ] , 从lexicographical order考虑,那么第二种要比第一种大,所以,给你k,求根据lexicographical order第k个path。其实就是kth permutation啦,只是有dups。lintcode上面那个题没做,我靠...唉,写了个nextPerm的方法搞的,老印很不屑。比如2,2的例子中,0th 就是[H H V V],1th 就是[H V H V]. 围观我们@1point 3 acres
2. 很绕,题目很长,需要自己parse string,get parameters. 题目的意思是rational number 表示是 a/b,有N个rational numbers a0/b0, a1/b1, ... aN/bN,求他们和的reduced form 即 a/b。简单说来就是根据input,parse成为N的 a,b两个数组,分表存了分子和分母,然后返回一个a_result b_result的string。核心思想看下面的这个例子:

a: 4 2 2 2
b: 2 4 4 3
返回 4/2 + 2/4 +2/4 +2/3的结果,也就是11/3。于是返回“11 3”这个string。

都写出来了,不过都不是最优,最后讨论了一下,就没时间了。像我这种刷习惯的leetcode的,看起来还得多去hackerrank什么的磨练一下。




评分

2

查看全部评分

lcysjw 发表于 2015-10-14 13:55:01 | 显示全部楼层
不知道为什么m=2,n=2的时候只有两种解法 [V V H H] 这样不行吗?. more info on 1point3acres

第二题应该求最大公约数+最小公倍数
回复 支持 反对

使用道具 举报

kelvinzhong 发表于 2015-10-14 14:00:36 | 显示全部楼层
楼主遇到的题目都好难。。。
回复 支持 反对

使用道具 举报

lcysjw 发表于 2015-10-14 14:01:32 | 显示全部楼层
第一题其实可以用数学的解法来做
答案应该是 Cn,0 + Cn,1 + Cn,2 + Cn,3 ... 这么多种走法
循环找到范围,然后再循环next这样会更快


-google 1point3acres补充内容 (2015-10-14 14:19):
可能可以直接推导出来,但是我不会,感觉可以
回复 支持 反对

使用道具 举报

cjlm007 发表于 2015-10-14 14:04:45 | 显示全部楼层
感觉算法方面对phd一般要求都比master高
回复 支持 反对

使用道具 举报

majiamajia 发表于 2015-10-14 15:06:24 | 显示全部楼层
第一题看都看不懂什么玩意简直了
回复 支持 反对

使用道具 举报

 楼主| nothingtrouble 发表于 2015-10-14 22:05:13 | 显示全部楼层
lcysjw 发表于 2015-10-14 13:55
不知道为什么m=2,n=2的时候只有两种解法 [V V H H] 这样不行吗?

第二题应该求最大公约数+最小公倍数
. 1point 3acres 论坛
可以,你把它想成H=1,V=2,那么permutation的第一个(0th sequence)就是1122 HHVV, 1st sequence也就是1212 HVHV. 2nd sequence 就是1221 HVVH.要你求kth sequence. 不难,不过太tm绕了
回复 支持 反对

使用道具 举报

 楼主| nothingtrouble 发表于 2015-10-14 22:05:41 | 显示全部楼层
lcysjw 发表于 2015-10-14 13:55
不知道为什么m=2,n=2的时候只有两种解法 [V V H H] 这样不行吗?

第二题应该求最大公约数+最小公倍数

对,第二题你的理解是对的.就是这个意思
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

 楼主| nothingtrouble 发表于 2015-10-14 22:11:30 | 显示全部楼层
lcysjw 发表于 2015-10-14 14:01
第一题其实可以用数学的解法来做
答案应该是 Cn,0 + Cn,1 + Cn,2 + Cn,3 ... 这么多种走法
循环找到范围 ...

可以直接求的,kth permutation with dups解法可以参照lintcode

http://www.lintcode.com/en/problem/permutation-index-ii/

这个更简单,其实只有两个char H,V变来变去.
回复 支持 反对

使用道具 举报

 楼主| nothingtrouble 发表于 2015-10-15 09:28:58 | 显示全部楼层
贴个解法,第一题 in Java
. Waral 博客有更多文章,
        // m: H counts, n: V counts, k: kth sequence to get
        public static String sequence(int m, int n, int k){. visit 1point3acres for more.
                int i,c,l=m+n;
                i=0;
                char[] arr = new char[l];
                while(k>0){
                        c = combinatorialNumber(l-i-1, n);
                        if(c<=k){ //if k is larger or equal than combinatorial number C(l-i, n), this position should pick V. 牛人云集,一亩三分地
                                arr[i]='V';
                                k-=c; //update k if V is picked
                                n--; // total count of V
                        } else { // if k is smaller than combinatorial number, this position cannot be V, in other words, should be H
                                arr[i]='H';
                                m--; //total count of m
                        }
                        i++; //shift to the next position
                }
               
                // Out of the loop, means to find 0th sequence. In that case, just put all 'H' following all 'V'
                while(m>0){
                        arr[i++]='H';
                        m--;
                }
                while(n>0){
                        arr[i++]='V';
                        n--;
                }
                return new String(arr);
        }

        public static int combinatorialNumber(int n, int k){-google 1point3acres
                long ret = 1;.留学论坛-一亩-三分地
                for(int i=0;i<k;i++){
                        ret*=n-i;
                        ret/=i+1;.留学论坛-一亩-三分地
                }
                return (int)ret;
        }
       
        //Main
        public static void main(String[] args){
                System.out.println(sequence(1, 1, 0));
                System.out.println(sequence(2, 2, 0));
                System.out.println(sequence(2, 2, 5));
        }

回复 支持 反对

使用道具 举报

majiamajia 发表于 2015-10-15 09:45:44 | 显示全部楼层
nothingtrouble 发表于 2015-10-15 09:28. Waral 博客有更多文章,
贴个解法,第一题 in Java
. from: 1point3acres
        // m: H counts, n: V counts, k: kth sequence to get

谢谢楼主
回复 支持 反对

使用道具 举报

kennethinsnow 发表于 2015-10-18 14:02:41 | 显示全部楼层
  1. int GCD(int a, int b){ 来源一亩.三分地论坛.
  2.              if (a < b) return GCD(b, a);
  3.              return b == 0 ? a : GCD(b, a % b);
  4.         }
  5.         int LCM(int a, int b){
  6.            return a * b / GCD(a, b);
  7.         }
复制代码
回复 支持 反对

使用道具 举报

Augustus 发表于 2015-12-24 04:17:29 | 显示全部楼层
鄙人愚见,第一道题把h看成0,v看成1,然后就是机器码,n的机器码。。。不知道是不是。。。
. visit 1point3acres for more.
补充内容 (2015-12-24 04:18):
果然是愚见,h和v的个数是固定的,没想到这茬,见笑了。。。
回复 支持 反对

使用道具 举报

lanluo_violet 发表于 2016-1-26 04:36:22 | 显示全部楼层
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-26 14:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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