找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 28935|回复: 13
收起左侧

[TwoSigma] Two Sigma OA都成功通过测试了却收到据信

  [复制链接]

5

主题

2

精华

67

积分

资深会员

Rank: 2

积分
67
发表于 3-21-2016 05:14 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 Sophia 于 3-28-2016 11:57 AM 编辑 2 N5 v0 e, `9 h7 j" B

1 j4 K: h: ~6 Y5 {上个月网申的Two Sigma,一周之后HR联系。结果HR放鸽子,我发信去问,又重新约的时间。到了重新约好的时间后,HR过了20分钟才打过来电话。之后就是非常常规的问题。我的背景,Why Two Sigma之类的。跟她交谈的过程中感觉对方很疲劳,有些不耐烦。在谈话结束后收到HackerRank上的OA的连接。4 F7 t' h( n6 z% G( ]+ q' e
两天后打开OA做题,两道题,3小时。第一道是Friend cycle,第二道是Longest chain length。都是老题了。看到过别人发的面经。自己也在下面先做了做。1小时两道做完,都能通过全部测试。结果3天后收到据信!时间都花了,结果也OK,但却什么都没得到! 真不知道为什么:-(
3 j0 X- Z0 X1 s( p$ z  D: W! X( S; B/ s+ j# W# s1 v
附上我的solution。大家帮忙看看我的code到底又什么问题。第一段是longest chain的代码,分割线后是friend cycle的代码。
& \8 Z1 z# \7 \. C. t大家看后多给写积分啊!多谢!多谢!! e8 }& l' q; f3 w8 }
; C" k& S; ?; \
import java.io.*;  ]) R1 J- \" D: x2 C# }
import java.util.*;) w- u' V4 C4 Y7 h! q9 e

" F1 w0 j0 o3 e4 |- G
# m2 G3 }7 j# g8 O* Apublic class Main {) }% _( f  X2 ~( u3 h

; X4 @) H: }! \5 T
6 o0 s0 H( b) J1 W( b; Y/ r0 w    public static ArrayList<String> words;
% v' ]+ W: T9 I1 i0 J) q/ K8 n6 C* b
  B1 V0 Y9 C* i6 {* W! Q+ {    public static int longestchain(ArrayList<String> words){& ^2 c! I7 q( w3 X) R; J
        HashSet<String> dict = new HashSet<String>();
0 ^1 h8 o8 g% D        HashMap<String, Integer> map = new HashMap<String, Integer>();/ ~. b% Y2 @, t2 N1 g
        for(String s:words){5 O, M& D, i" z2 N5 K
            dict.add(s);
4 f3 c) g! A. V# ~3 J# ^9 B        }- g( e$ z$ X; {, K

# N' H8 V* Y1 m' P+ W* r        int longest = 0;, g1 A8 M7 B5 n& a  [4 r
        for(String s : words){
0 _* |; j* L" e2 E' y4 W            if(s.length() <= longest){0 l% I! M' [* r+ y3 F
                continue;
; }: T/ y# x* w6 R7 h            }
, V7 J( G9 ^( K+ `% Z( u            int len = helper(s, dict, map) + 1;+ c' s& z! S* R1 z0 s/ ^
            map.put(s, len);1 Y$ K& _6 e# f  `- B- J& H+ V
            longest = Math.max(longest, len);
( ^$ ?3 i6 Q2 }, Y& K* f: }! _' }        }
; J9 b, W6 M# U        return longest;
) M* o  _2 s# ?7 M    }
% U& |! c5 R, K/ Y: a! I+ z7 W6 I5 D) [  y9 t6 U2 |
1 I2 n2 s: k2 O
    public static int  helper(String s, HashSet<String> dict, HashMap<String, Integer> map){( y" Q4 w. Z) b# D; F' ~, d; R1 p% o
        int result = 0;
. m- I# s; g" K3 C; ^/ b+ ]( s        for(int i = 0; i < s.length(); i++){
$ k2 s5 Y. _# O            String newStr = s.substring(0, i) + s.substring(i+1);4 |3 q9 e' q2 g, o1 ^7 P) a
            if(dict.contains(newStr)){
9 `3 N; r4 U, u; p6 [                if(map.containsKey(newStr)){9 ]; I& Q  b. I( c4 V
                    result = Math.max(result, map.get(newStr));
# d- v" x: I$ n! J" e4 n                }else{5 H, r, t2 R# a/ ]5 U
                    result = Math.max(result, helper(newStr, dict, map) + 1);
' Q# e- i  X9 M6 @* n9 C& v                }
8 h  e$ U- X/ _1 u  q. A            }
3 D( O9 @% h6 u; L& M) W* Z        }8 l6 I8 @0 w" F+ w
        return result;
: X# R1 }; X, Z% o# E/ F0 ~2 h4 [    }
0 ~% s" k. c( Y8 _/ P' J: h& r+ i, H) |( {8 o4 D  C, M  y
    public static void main(String[] args) {
& a8 s7 n' [6 G4 p3 f7 c    // write your code here/ X3 ^# V4 W9 |; [4 p
$ r1 U) Y' t1 }2 c! P5 `; k
        System.out.println("Longest Chain");
2 M4 }1 y/ W1 ^; n) u9 U+ K        load_parameters();. O& c. T1 q' _* [7 T- p; {

0 c# @" h( P, M( {        System.out.println("words = " );
# I3 I7 t8 x4 t  s; z, ?- W        for(int i = 0 ; i < words.size(); i++){
6 \- y+ d/ R1 r; g            System.out.print(words.get(i) + ", ");) Y$ Y8 r3 q& b: t7 ^$ ~1 O
        }; D$ J9 ~3 m0 k; G
        System.out.println();
2 p3 J' o% H& ]" v0 p8 X
6 ~: [! a' h: h5 u% A        int length = longestchain(words);9 E) ?$ g# h3 r0 x! i& x
        System.out.println("result = " + length);+ U3 h0 w7 [; F9 c

5 L! s& i* }1 P: P0 X
: }0 P, M2 V: ?% d& d! k1 ]8 n/ N        System.out.println("Done");
+ C7 e# w3 a) x# j- Y) s9 q    }5 v2 _8 x0 W8 q" n3 W6 x4 v
}
4 m: Q- b: q) J* ~5 ^) ]
+ G6 N5 W8 L: l  `6 \======================================================
. F  _+ b  H! l) O( Q  l
, z6 K$ A* w. |
. W$ O; @! L1 Vimport java.io.*;+ x1 K. ~$ X1 u
import java.util.*;8 M' \- x) d6 ^( L! |" V
) a/ H' W% `7 Z/ L/ Y: ]
, e& t9 H5 B+ Q- m, u% R
public class Main {. s/ G' J  s7 }1 \$ K( Y

) }; d& z  z! D. t8 m    public static int N;0 I; @# k4 D' e4 P$ d
    public static List[] adjList;- v5 }% q8 w( y% G' N8 }
# L8 a' n' q( |; z0 ]
    public static void load_parameters(){
3 H* T- _  f0 v# f        // write your code& z8 y* d7 p/ v3 P
        String fileName = "input001.txt";" O1 m7 R2 [5 s9 i
        String line = null;% F- y1 k1 V5 c" ]7 W$ ?# U
        try {; F- E$ \7 R9 c+ q+ ?! k) a
            FileReader fileReader =/ U) m* Y) U5 ]: o3 D! n9 t
                    new FileReader(fileName);
0 C- n/ e3 O0 Q+ ]) H' ]8 O1 l- d
& N* ]/ O6 T/ W) s- z0 L7 N            BufferedReader bufferedReader =$ _% ?0 s; w  i% N# A3 X
                    new BufferedReader(fileReader);
$ r8 D7 B4 E4 F6 B, Z( X/ |; v8 `0 x
            String numberOfPeople_str = bufferedReader.readLine();, e3 w; t( P* Z. {; a( w
            N = Integer.valueOf(numberOfPeople_str);
7 F1 C9 C0 n# H( p            adjList = new List[N];' j0 m+ ^) u% W1 U( }+ P* J% K6 T

. k8 N5 D% [' Z+ i/ e            int row = 0;
9 ^' G/ P& Y  y0 u  ^3 o            while((line = bufferedReader.readLine()) != null) {
* S! m; Z$ p" N0 w; t4 m                System.out.println(line);
! P9 a4 x' }% h  h$ a                adjList[row] = new ArrayList<Integer>();" R: D" v" j/ p) W
                for(int col = 0; col < line.length(); col++){
' R4 |! F9 v# K# X; f  p                    if(col != row && line.charAt(col) == 'Y'){
" @5 C0 W! I) B2 h7 D$ |1 e: y1 K                        adjList[row].add(col);
2 H* w* y3 |; D( r                    }" r$ L6 z1 A; `. w, Q
                }
) m9 h& @$ K3 _( Y                row++;
# x8 b9 Q2 d6 Z            }
5 d3 e0 R9 t: c; x1 D
6 _0 k) y* ?1 ^4 a  x7 t. h& y            bufferedReader.close();
1 H: I$ ?. B* x            return;# o7 F/ G4 n/ ^" ^( N# ?6 C4 ?- t
        }
& Z( S$ ^5 r) M; K        catch(FileNotFoundException ex) {2 r" u: P. p# A" j8 `/ y4 x
            System.out.println(
" \" ?, ]- j2 n3 [                    "Unable to open file '" +5 ^2 x6 m  e3 D6 V# B
                            fileName + "'");2 l5 r& }: H8 g0 _
        }
! J" {4 H) k6 A+ {) D! e        catch(IOException ex) {6 m4 o/ z: o! S+ d. X, f
            System.out.println(
2 t) v$ [3 R1 f* M0 s& S) c' d                    "Error reading file '"
3 `7 a6 A0 C& x+ _+ b& P                            + fileName + "'");0 X* U/ c4 r& v! H/ }
        }: P) A, f8 D- j4 q5 h! M
) Y  }8 @& P, j9 Y: V
        return;. l+ e7 i7 x9 k2 W) I0 J
    }
3 T# ^2 u+ h6 T6 i& j1 F
" i. U# ]3 I# q% Y0 L# N2 n- j( m+ s* k- b' ~$ d8 c

8 K* X% z7 W4 I) l    public static int countComponents(int n, List[] adjList) {
% w3 o; ^. t3 d, m/ t; c# C9 ?0 D
3 p# A8 C, n- d2 p4 y        boolean[] visited = new boolean[n];//visited nodes
: o" _3 K3 P' g& z9 w$ K
0 k0 X' v9 a) N5 i0 H$ T4 U        int count = 0;$ `7 Z: T: V; y/ E. g
        for(int i = 0; i < n; i++){* x. I* r' M1 _
            if(visited【i】 == false){- v, @% a1 y; p
                count++;( i: U" B$ [; z3 [( t$ S) K
                countCCHelper(i, adjList, visited);2 B3 V- E3 E4 }4 }
            }
: C& h. e* m5 v; I: T* J  x        }* k3 |9 x% H9 r
        return count;+ _3 I) B$ D  v/ X( [! P
    }
; p& m; e6 l, S  ~6 {
/ m0 \  V% x9 p$ p1 T' A4 ]& ]    public static void countCCHelper(int curr, List[] adjList, boolean[] visited){1 Y' {8 J' ]' H, U) p% {8 n
        if(visited[curr] == true){8 n+ K8 W: y8 N+ P  @
            return;
, c# o# H; C/ @8 j        }
( R! g3 @8 E9 K( q! t; x
" \3 L: o" \/ e0 {0 m& v2 n        Queue<Integer> Q = new LinkedList<Integer>();
- @: T! b8 K1 N& }( {0 k) s# z        Q.offer(curr);
' z. B. x* z" M- F  ]6 e& p) v- V: Y% M+ B9 r  E6 ?0 h0 c
        while(Q.isEmpty() == false){( r* v  V% A+ u  `0 E
            int node = Q.poll();9 x* Q# z5 I# m. g1 u( _# E
            visited[node] = true;! T% m! j% F# R: y0 m! x3 I+ ~! y
            List<Integer> neighbor_list = adjList[node];
. f6 W+ Y( B% }- |5 E1 d* O- Y            for(int neigh : neighbor_list){
2 c1 {0 f& ~" b$ x' _                if(visited[neigh] == false){
# o* W+ m: h9 g& v4 w: Z' z; k                    Q.offer(neigh);) K& U$ e; ]& J9 b
                }
$ g. Y7 ?) W+ T/ `, ]            }4 g8 C5 I. Y1 J& S) g
        }+ q( K/ c* [1 c' U8 C% h5 d3 b% C
        return;
) [5 M: B9 L7 ~3 R% p    }
# L6 `7 f4 T3 Q) ?* D& k% w5 Y- w
0 |8 ^1 L9 J5 X. m' L8 _4 B    public static void main(String[] args) {2 M+ _+ T9 i1 x
    // write your code here
$ V! c, Z; ]/ D2 ^5 {8 I+ _+ \  b2 L2 I0 ^( I1 y3 m
        System.out.println("Friend Cycles");
4 ~. ^: r1 y+ U8 |( J        load_parameters();+ M& _, D, i/ k, F- r3 O- _" Q

8 v5 A; G2 c7 a! T  t        System.out.println("matrix");
" h9 ]$ N, K  f% R) t        for(int i = 0; i < adjList.length; i++){
# |% X& t0 X4 w. a& a            System.out.print(i + ": ");
1 [0 e* o6 [  h6 S% Q+ n; x" L/ [            for(int j = 0; j < adjList【i】.size(); j++) {. X% N  ^2 ?' {; z
                System.out.print(adjList【i】.get(j));
5 y5 `+ L/ H' B; C9 ?7 D                System.out.print(", ");; m( x- z) e* U4 ]
            }( _' G8 X# n0 t' F1 O" K0 q1 l! p) T
            System.out.println();" q. R4 k( o/ s5 C; y5 C% W) H
        }. W8 B$ }. r. ], z, R7 y8 g  B
1 A- L+ Z, L$ O, @

% n; f* k; X- n8 Y! {6 ]4 L0 q        int num = countComponents(N, adjList);! F9 S2 @$ v% `
        System.out.println("num cycles = " + num);
& h0 Z( Z9 g% n, h1 k3 x
7 ^& x/ P8 W6 n* ?
( l: _9 J% }( }6 j        System.out.println("Done");
. W! F; [# P5 I" q* @, m    }: S5 a2 |' {6 O: N, @9 p& m. H
}
, X0 e1 |; N5 D! v9 R  E0 ]3 H' d7 M$ U6 }4 _9 i) k0 M

( L3 y: G; g) B% V+ p2 Z$ ?0 N( G( n( a. C, V# C0 j; p

5 w* }, B0 R, v5 L: X& l4 ]1 f: l7 ~% o
; j4 A5 X9 `2 v7 [; J" T* `  a

评分

参与人数 1金钱 +2 收起 理由
Sophia + 2 感谢您的认真和用心的分享!大米满满送上!

查看全部评分

0

主题

0

精华

0

积分

新米人

Rank: 1

积分
0
发表于 3-21-2016 05:14 PM 来自美国米群网手机版 | 显示全部楼层
感谢chicagoloop分享~~~好人一生平安~~~

781

主题

575

精华

5670

积分

顶级版主

Rank: 9Rank: 9Rank: 9

积分
5670

活跃会员热心会员优秀版主

发表于 3-22-2016 03:49 PM | 显示全部楼层
感谢您的认真和用心的分享!大米满满送上!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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