一亩三分地论坛

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

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

Zenefits电面

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

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

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

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

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]
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. 鍥磋鎴戜滑@1point 3 acres
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] 这样不行吗?

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

使用道具 举报

kelvinzhong 发表于 2015-10-14 14:00:36 | 显示全部楼层
楼主遇到的题目都好难。。。
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

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


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

使用道具 举报

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

使用道具 举报

majiamajia 发表于 2015-10-14 15:06:24 | 显示全部楼层
第一题看都看不懂什么玩意简直了
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

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

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

可以,你把它想成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] 这样不行吗?
. Waral 鍗氬鏈夋洿澶氭枃绔,
第二题应该求最大公约数+最小公倍数

对,第二题你的理解是对的.就是这个意思
回复 支持 反对

使用道具 举报

 楼主| 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变来变去.
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

 楼主| nothingtrouble 发表于 2015-10-15 09:28:58 | 显示全部楼层
贴个解法,第一题 in Java

        // m: H counts, n: V counts, k: kth sequence to get. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        public static String sequence(int m, int n, int k){
                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';. from: 1point3acres.com/bbs
                                k-=c; //update k if V is picked
                                n--; // total count of V . 1point3acres.com/bbs
                        } 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
                }-google 1point3acres
               
                // 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--;
                }. more info on 1point3acres.com
                return new String(arr);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        }

        public static int combinatorialNumber(int n, int k){
                long ret = 1;. Waral 鍗氬鏈夋洿澶氭枃绔,
                for(int i=0;i<k;i++){
                        ret*=n-i;
                        ret/=i+1;
                }
                return (int)ret;
        }. visit 1point3acres.com for more.
       
        //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));-google 1point3acres
        }
. more info on 1point3acres.com
回复 支持 反对

使用道具 举报

majiamajia 发表于 2015-10-15 09:45:44 | 显示全部楼层
nothingtrouble 发表于 2015-10-15 09:28
贴个解法,第一题 in Java.1point3acres缃

        // m: H counts, n: V counts, k: kth sequence to get
. from: 1point3acres.com/bbs
谢谢楼主
回复 支持 反对

使用道具 举报

kennethinsnow 发表于 2015-10-18 14:02:41 | 显示全部楼层
  1. int GCD(int a, int b){. more info on 1point3acres.com
  2.              if (a < b) return GCD(b, a);
  3.              return b == 0 ? a : GCD(b, a % b);.1point3acres缃
  4.         }
  5.         int LCM(int a, int b){. from: 1point3acres.com/bbs
  6.            return a * b / GCD(a, b);
  7.         }
复制代码
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

Augustus 发表于 2015-12-24 04:17:29 | 显示全部楼层
鄙人愚见,第一道题把h看成0,v看成1,然后就是机器码,n的机器码。。。不知道是不是。。。

补充内容 (2015-12-24 04:18):
果然是愚见,h和v的个数是固定的,没想到这茬,见笑了。。。
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-1-23 21:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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