找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

12
返回列表 发新帖
楼主: douya
收起左侧

[Zenefits] Zenefits oa 3 面经

[复制链接]

25

主题

7

精华

250

积分

高级会员

Rank: 3Rank: 3

积分
250
 楼主| 发表于 9-15-2015 08:24 PM | 显示全部楼层
1. 给个字典每次可以减少一个字母,求最长链2 V2 p  ?0 \1 ?. q) Z
2. 判断nquee是否争取,不对的话求出最大威胁数,这个很简单: V, \; [3 h# @8 X1 W
0 ?6 M! q- \( ?7 z. P! Z) f7 n
1.:
+ \3 ]& v3 P+ y' P6 I! O- t) C! f+ y+ ]  d        public int findChain(String[] w){( q- A4 ~9 R) |* }/ u
                HashMap<Integer,HashSet<String>> hm = new HashMap<Integer,HashSet<String>>();6 T/ x+ ~0 a% H3 O' G7 W
                int maxlen = 0;. n5 W8 @5 r: |% i9 d
                int minlen = Integer.MAX_VALUE;
3 P+ M- p$ t$ R! p% e                for(String s:w){
% x8 l, P1 I% d$ x* t$ I/ d! y                        int len=s.length();
- s3 _, ]% h1 q  P8 h                        maxlen = Math.max(maxlen,len);
) o9 c8 ]6 _! p# L3 c9 C  Y                        minlen = Math.min(minlen, len);& b% Z! i7 Z' |. M
                        if(hm.containsKey(len)){  _3 `! Y( D" g: {* ?6 h- d
                                hm.get(len).add(s);
) r1 `# T) i# L+ {' i7 v3 F  L                        } else {
5 {! k$ |" Y+ p$ B                                HashSet<String> hs = new HashSet<String>();+ c& ?$ Y- S% k. n# Q
                                hs.add(s);0 {1 B  }3 Y3 E
                                hm.put(len, hs);
2 D3 s7 y# ]' ^, M                        }
" s3 e) k! I* ^( d6 E' d+ ^                }
) r$ h: A3 J- H+ ]1 C               
- X0 O9 I: d/ r( h                int max = 0;* }( M9 B3 n9 a2 g, X
                int p=maxlen;* Y# \$ v/ O7 u+ T
                HashSet<String> visit = new HashSet<String>();6 N* _0 Y% a; s0 a- e) E# J
                while(p>=minlen){
9 l$ W% d5 t( K                        HashSet<String> hs = hm.get(p);
, [3 o; @& |$ W* \' ]( G                        if(!hs.isEmpty()){0 T4 y1 C0 b$ d" o, z, m
                                for(String s:hs){: {7 B+ y& M0 W0 I  O8 ?- y
                                        max = Math.max(max, helper(hm,s,visit));
: i9 M" e, J; @3 C  X8 H                                }
* ~2 \8 z! a& |7 w                        }
) P2 |) I: C3 S7 J* e  f                        p--;6 @6 `# M2 }  @) B
                }2 W$ h8 \2 T+ C9 ^* i( M6 t: e/ I& W/ {
                return max;
( E* p/ a, u2 r6 f        }
* s& U" D7 @! t  R! x4 ?       
4 S- G; y: E5 N# h' h        private int helper(HashMap<Integer,HashSet<String>> hm, String s, HashSet<String> visit){
( l9 _: K- r0 l: c. c) K                visit.add(s);
/ \. M' [1 B1 |3 P                int next = s.length()-1;
* a9 r6 ?+ \2 V& P" [" Y1 Q                if( next==0 || !hm.containsKey(next) || hm.get(next).isEmpty()) return 1;
3 r8 d/ L: F  b, v7 Z. a( C                HashSet<String> hs = hm.get(next);3 n1 c* O3 x2 E5 _8 g3 g5 g
                int max=0;0 @3 _; }+ ~* |% }9 _  c0 F
                //for(String str:hs){& M# B1 p' u% D7 }5 C" B
                        //if(!visit.contains(str)){: C; W: ]( {* K; d2 f3 q( {
                                for(int i=0;i<s.length();i++){
) K9 \" f& `- W$ ?9 I& B                                        StringBuffer sb = new StringBuffer(s);( |0 ~5 M' {1 U
                                        String nextstr=sb.deleteCharAt(i).toString();
* j  u9 W" |) d& V" h% }! @. K                                        if(hs.contains(nextstr) && !visit.contains(nextstr)){
/ k# i4 v1 |% a; v                                                max = Math.max(max,helper(hm,nextstr,visit));
# V; N" G) ~& ~3 [                                        }% L2 K; K( q+ K: u
                                }
' A/ W1 O# \8 k0 p1 t7 j                //        }2 u( R- F3 h/ S4 S! f) N
                //}; k' v6 @. ]0 _& C2 n
                //hm.get(next+1).remove(s);
, y3 I2 e& M4 D1 q+ k5 B4 m. L                return max+1;
5 {( ?; J% [9 d* t8 ?+ }        }
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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