找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 16714|回复: 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 编辑
$ |7 f4 l& m, m6 x; [, A' Z
& l6 b1 m. F5 f! n% @5 O上个月网申的Two Sigma,一周之后HR联系。结果HR放鸽子,我发信去问,又重新约的时间。到了重新约好的时间后,HR过了20分钟才打过来电话。之后就是非常常规的问题。我的背景,Why Two Sigma之类的。跟她交谈的过程中感觉对方很疲劳,有些不耐烦。在谈话结束后收到HackerRank上的OA的连接。' }* ]5 @8 k7 q0 k7 J4 W
两天后打开OA做题,两道题,3小时。第一道是Friend cycle,第二道是Longest chain length。都是老题了。看到过别人发的面经。自己也在下面先做了做。1小时两道做完,都能通过全部测试。结果3天后收到据信!时间都花了,结果也OK,但却什么都没得到! 真不知道为什么:-(( \% v1 @- O' w# H% N7 B! m
0 t& t  m% O: `
附上我的solution。大家帮忙看看我的code到底又什么问题。第一段是longest chain的代码,分割线后是friend cycle的代码。8 c- u4 I4 i3 O6 w- e' @" ~9 K2 a1 Z
大家看后多给写积分啊!多谢!多谢!
  [# Y. ~& X! F' S/ y2 K
: v6 G' N$ A5 V+ ]import java.io.*;+ G- @$ D$ k. ^! ]) Y" M; M
import java.util.*;
, M3 c+ u5 J1 [! K, `1 ~5 s6 j+ Z* e# B* F1 Y, {

: G' L: k! P1 Upublic class Main {
3 V5 K: W4 E$ G7 j. o  n6 z- L
$ l9 w6 S; G/ v) [( J' H1 |( L; n
    public static ArrayList<String> words;7 l: F1 p% @3 ^8 l) P; _/ _1 a. B

- o6 p3 U! y# |$ q/ L1 V& _    public static int longestchain(ArrayList<String> words){
0 u9 t+ n& W2 ^; h1 A9 {8 G        HashSet<String> dict = new HashSet<String>();( p% K& z1 P2 R9 \- `8 C0 B# \1 B
        HashMap<String, Integer> map = new HashMap<String, Integer>();
4 }* T5 M* }7 O; Z% Q        for(String s:words){; v6 F% m6 H0 l
            dict.add(s);
! ~8 M0 {- y. x: @1 [6 |; q5 y% r        }
, ?1 k6 D' ~" @3 K4 D1 ?. J
& E! G8 O8 `' s3 V$ y        int longest = 0;! o! k; R! u1 r3 o4 h" Y  ]6 F
        for(String s : words){7 D$ y  f7 u$ Y8 ]2 Z$ _7 r
            if(s.length() <= longest){2 V+ k! }$ z- B1 ?
                continue;
5 T( u3 Y5 I  s; V            }
6 p, ]; P( h8 ^; v% ~& P; ?- J            int len = helper(s, dict, map) + 1;5 w- r+ Y& D" ^
            map.put(s, len);
/ F1 t. a8 N9 ]( }. {9 \% y            longest = Math.max(longest, len);( J+ d% T5 o0 Z8 d. N/ }% S
        }
1 l* q* [4 H0 d        return longest;
6 M: T! D' r' g! s, Q2 l+ l0 d    }
6 k) v" A! x; ^$ ?$ b, d# V$ T3 T! S9 Y* ?/ a5 L2 ?! D9 w2 Q) B: N

7 {7 C, h0 C2 r! l; P6 I8 H. ~    public static int  helper(String s, HashSet<String> dict, HashMap<String, Integer> map){
: m  g: Q" A, S/ q/ j        int result = 0;' b1 y, K2 w8 P& V$ S* {$ \
        for(int i = 0; i < s.length(); i++){
$ F: i& d; w; N: L            String newStr = s.substring(0, i) + s.substring(i+1);
1 u0 h* ^- @* D            if(dict.contains(newStr)){- N& d# T! q$ A* S+ S3 a
                if(map.containsKey(newStr)){
  J0 [3 }8 w7 P. i% a                    result = Math.max(result, map.get(newStr));  q6 M2 Z  D$ m3 x! P
                }else{8 i7 a9 o9 @7 a2 P& D8 x- H: z
                    result = Math.max(result, helper(newStr, dict, map) + 1);# Z( P+ K% a: r2 \
                }
+ q+ |1 _7 f8 B            }
: ]. o" B$ Z7 N' Y& Y  t( F0 i, e! X- C        }3 `, \+ [6 j2 F$ `
        return result;; C6 X. G7 H9 u! ^0 o
    }! [' h9 }  @  s- G

4 }9 `  @3 s  Q  y  n    public static void main(String[] args) {
) q0 x% V% L; w6 }3 ~1 e) u    // write your code here
" N$ H0 r$ f4 y4 u; K1 k
, E7 M9 r0 d* {! o! n        System.out.println("Longest Chain");" v% g2 A+ f! T; U* d; g( X4 U' `1 q
        load_parameters();2 L6 x, Q" T8 U# }! Z  }6 t$ p
% r1 \. _. Y+ z7 c! ?9 g
        System.out.println("words = " );
4 ^: F# l/ e5 }0 @2 B  l        for(int i = 0 ; i < words.size(); i++){! H9 E9 Y6 {4 F7 o' J5 {+ {
            System.out.print(words.get(i) + ", ");7 b; a6 I1 B  @' U( \( D3 E
        }4 l1 U7 c8 a! l2 O
        System.out.println();0 e4 K4 F* R" S

( x0 K- G9 s9 `- d8 v* v" Z        int length = longestchain(words);
6 U' Y1 K9 Y3 F, Z4 q+ Y- b        System.out.println("result = " + length);: D+ K8 H  `2 q$ c- w% Q6 I+ m% f3 ?
$ X# \: a; W: Y! P
% I, U5 u% H/ r9 M- |& W! h  {
        System.out.println("Done");
0 x/ f' c- V" A5 J% _5 w) ~$ y0 v    }
9 t; }: F7 V8 j+ @5 r, p}
$ b3 L6 }# U, X9 |; N; t) {, h
5 v" y- X. j/ E4 I) @/ x======================================================
3 s1 V2 t" J* y" D  m. X9 L- G6 G8 d5 c9 |( @8 M

7 h' `0 O4 N! w# N; u! {import java.io.*;
, g$ P3 L7 W- H9 q4 jimport java.util.*;5 A: f3 @7 j5 a: H0 N% D

- W/ z# a7 ~- x; L- a
& A& z/ ]0 z# H" i2 a9 R0 ]public class Main {
: D0 f  @; h  j" ?+ S$ P2 R6 [4 h8 U0 n0 O' c" ^. k& O
    public static int N;( t. J/ b  k6 _- p" P( {
    public static List[] adjList;. f  y8 t1 A$ A/ A! @" }, B

2 V$ W" k, r$ O8 @& _' I7 O$ U$ V+ V1 P    public static void load_parameters(){$ c$ ~9 j  q8 F& r) Y8 v
        // write your code
3 x. e" |! D9 q8 ]& c        String fileName = "input001.txt";5 G7 }5 m) K' v' v2 C4 O. j
        String line = null;# e& B0 N9 S1 b+ ?
        try {
7 Y- _  N8 t6 y1 S            FileReader fileReader =+ c% G& \. d6 _) W% D7 \: z+ z9 C5 h
                    new FileReader(fileName);
7 l( N) ?+ t. a! W9 i* d" m
  w  Z+ V8 I' d            BufferedReader bufferedReader =. @4 m  E0 ^: h/ H% Q( _! m2 J6 H
                    new BufferedReader(fileReader);
7 o4 L2 t& a' p6 ^$ r/ G: ^* y
0 b" p+ ^4 m4 j' p" R* [            String numberOfPeople_str = bufferedReader.readLine();
* k9 x2 S+ J+ }5 r7 ]8 W9 \; v7 e            N = Integer.valueOf(numberOfPeople_str);
% e5 q* E+ \5 i4 e' [# _            adjList = new List[N];
1 U: m' J- C. w' L0 U
0 ]4 P2 a$ T# C" o2 X3 ^* l            int row = 0;
0 k# J3 C' Z2 h1 K% M2 ~            while((line = bufferedReader.readLine()) != null) {
1 y/ |8 \8 e, @8 R' j                System.out.println(line);  i: n2 T. c8 T# b! f: E; p
                adjList[row] = new ArrayList<Integer>();* K3 J+ u+ `. A) r! W
                for(int col = 0; col < line.length(); col++){
) ?7 H1 z8 A& k- J4 y; F                    if(col != row && line.charAt(col) == 'Y'){5 Y2 O, ^$ v: S9 m
                        adjList[row].add(col);
1 P4 r) Y/ h7 R0 a4 I                    }
) Y. J; l1 b  U- }( R8 w9 C$ W* _                }0 A/ H  u6 U* Q4 u
                row++;
1 P$ q" m# W/ t/ E) O. t            }
8 {& L7 V+ J1 e  E  X
0 \! c0 x( M7 Z) H            bufferedReader.close();6 z( B0 t1 z/ U- F# |" ^7 L; C9 w
            return;) `! f% t% q, f0 M2 i$ a
        }2 \- E. h. l! C; y( y% a( v
        catch(FileNotFoundException ex) {) J$ s) C$ o$ N! t% l" i5 H8 I
            System.out.println(
$ D5 s8 I, O% Y5 R) i                    "Unable to open file '" ++ i7 q1 y& s, J  F% X
                            fileName + "'");5 Z. w7 m+ o6 p# c6 E
        }
& C. e. _% E$ n! P1 \& l: B        catch(IOException ex) {
8 ]! I, k- u' i2 w+ s" r2 @            System.out.println(
' L* D7 a" v8 h3 o/ K# J- Y* x9 \3 T                    "Error reading file '"
. S4 H6 z; M- y  d% R! L# f                            + fileName + "'");, X% V* y$ l) F7 D% f
        }
4 o% W3 `( e/ f2 U: \
; e0 U( j' s4 c0 N5 Q        return;
' z8 {5 C4 I( e    }
" o9 l/ s* D: [5 O- l9 Z$ \1 j( \9 _
. E1 {6 \" y. Z0 M1 n+ ~
9 c' L: t! d& i" a1 w5 k
    public static int countComponents(int n, List[] adjList) {
7 p7 b2 }/ E# q, D0 P' A, O4 L
7 W' M; b; y9 A/ W$ g* ]% N6 Y        boolean[] visited = new boolean[n];//visited nodes. a8 ]  s# t- M/ W8 V5 W0 H

, {9 j0 A, f7 d% j: T7 R        int count = 0;. N  C, h: E( o. }
        for(int i = 0; i < n; i++){" P. K, }2 @! I7 T6 f
            if(visited【i】 == false){' x" o/ b9 Z6 J
                count++;2 L: c7 ^% h1 c" z: o" F
                countCCHelper(i, adjList, visited);8 B3 t/ h9 X4 [0 `# B
            }
# _6 \+ |3 ?, D7 f2 _        }
, D" k: ~1 T( K        return count;# U1 r) }# X; U2 m3 U) e. g
    }9 J" Q% e! G' Q/ c+ r4 m* N

  x% m6 h* o/ X8 p" |5 L% d    public static void countCCHelper(int curr, List[] adjList, boolean[] visited){1 H$ L0 a/ [9 P2 x( G5 U/ x/ F
        if(visited[curr] == true){
" b- G3 d1 D/ w  ~8 ~            return;% A! ~' S0 Y+ X1 r
        }
- m  j8 q8 E1 E$ P* S( a) k
: x0 a- `/ {/ h( D        Queue<Integer> Q = new LinkedList<Integer>();
1 r+ B+ j7 }$ Y, M6 K7 V: e- d        Q.offer(curr);
" q2 _, f0 X2 n8 J- {
# x. P, s9 ]: K* A+ S$ R, v5 w/ E        while(Q.isEmpty() == false){
6 X2 ?0 F. e, f            int node = Q.poll();( V/ M' C0 m# f
            visited[node] = true;# O! S% m: c6 k: J: D- m7 r/ h1 ]
            List<Integer> neighbor_list = adjList[node];2 A4 J6 v7 i. Y, H
            for(int neigh : neighbor_list){; Q5 A% R8 J. |% X  o
                if(visited[neigh] == false){
5 J' I7 A, Y3 a& \8 [                    Q.offer(neigh);
1 w, ~4 V- ?( @9 W3 b- \" k                }
% l$ S2 c' C  x3 M; v) B            }
; U+ \0 Q% a& w# g$ I6 B        }
* ~/ ~6 Z6 I% \0 V: b& _        return;2 _/ U" t+ ^" S. W
    }9 N9 X" a1 M- r: K, k/ ]" Y
. |. M4 Y) a9 I+ I& [( G# M! b
    public static void main(String[] args) {
( z& V/ V# l- @: e5 T& L    // write your code here4 O' _& M$ S# h  C2 L( N& p  o

8 O) f, a1 R. [        System.out.println("Friend Cycles");
# i$ |. T1 {* `) v1 p- S: p7 q1 }        load_parameters();
! U) T; m5 E/ W5 e% I% C/ L3 s$ h
7 q, R0 C& z4 N4 b        System.out.println("matrix");: E( _# }# A5 ?8 g6 z! T& j
        for(int i = 0; i < adjList.length; i++){2 W* Y- n, R. {, h4 J9 Y9 D: s2 N
            System.out.print(i + ": ");  P: W# F$ A% a# d3 g7 j& u
            for(int j = 0; j < adjList【i】.size(); j++) {$ ]+ i$ G5 w  A8 k5 V
                System.out.print(adjList【i】.get(j));
7 J3 j' `1 N4 K1 M. w; |% I                System.out.print(", ");/ H  F+ z/ a5 ^( c5 x6 O
            }/ y/ k& q! D& D" u
            System.out.println();
# D) ^9 E' s" }' R+ w$ W        }3 }" U; ]6 k! {0 ^

7 ?: s/ S+ _) A9 i0 J+ {$ k" ^8 J% V4 {
        int num = countComponents(N, adjList);+ J$ M& d3 [5 X/ d6 ?+ [
        System.out.println("num cycles = " + num);
6 u! O9 r4 v/ O1 Z+ ~) u3 O& D/ o( C' G" [: v7 u  V: ]& a; g, R

: L+ W! l) E$ @2 \! ~        System.out.println("Done");
9 d0 Z3 y8 x8 F1 O( ?) m6 }    }1 [& A) `; ~/ Z; V) i! p5 K7 v
}! r/ W0 Q7 I5 D& C2 H2 I

, v3 {, ?' J8 S2 X, `$ ]. e9 x8 |

! ^/ `0 u9 m1 v1 l1 \: \
0 y, f9 M8 D+ A8 A2 I* G
, O' i: t/ X. J8 k: \* H
' B; F: `5 n( r% e! w

评分

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

查看全部评分

0

主题

0

精华

0

积分

新米人

Rank: 1

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

使用道具 举报

发表于 3-22-2016 03:49 PM | 显示全部楼层
感谢您的认真和用心的分享!大米满满送上!
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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