找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 13834|回复: 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 编辑 ; j) @, J$ Q) s: Y4 L
  g5 ~0 T* z7 F4 A2 a
上个月网申的Two Sigma,一周之后HR联系。结果HR放鸽子,我发信去问,又重新约的时间。到了重新约好的时间后,HR过了20分钟才打过来电话。之后就是非常常规的问题。我的背景,Why Two Sigma之类的。跟她交谈的过程中感觉对方很疲劳,有些不耐烦。在谈话结束后收到HackerRank上的OA的连接。. |1 R  U  E% I' o1 P
两天后打开OA做题,两道题,3小时。第一道是Friend cycle,第二道是Longest chain length。都是老题了。看到过别人发的面经。自己也在下面先做了做。1小时两道做完,都能通过全部测试。结果3天后收到据信!时间都花了,结果也OK,但却什么都没得到! 真不知道为什么:-(8 ?& ]5 [7 M8 @! q' {/ |

7 c! D& R  Q6 W, R) ~附上我的solution。大家帮忙看看我的code到底又什么问题。第一段是longest chain的代码,分割线后是friend cycle的代码。
8 s" u$ O$ }, c大家看后多给写积分啊!多谢!多谢!
1 O% i5 }+ o8 b3 a: {# j3 u
' d/ ]: J0 c$ Q- V: L; e9 qimport java.io.*;
0 d5 f) i  r* A4 \import java.util.*;
; x" t' B2 q4 G0 V3 P
: C7 y  q0 Q! K, ?% T( S1 W3 |$ o# T2 r7 U; D6 z, m5 w, w) H# V
public class Main {# q6 i$ ~: v+ l& H' ^$ ]
! A; Q5 U% k% J. L( j
5 D; E' B$ `9 J4 E0 b& ]
    public static ArrayList<String> words;
7 ]0 `# K* O7 Q4 I- U2 U
  e, k$ j1 W1 |( d" A# b5 e- U) ^    public static int longestchain(ArrayList<String> words){
7 {8 B! z, H- Y2 i7 h& W5 G1 w        HashSet<String> dict = new HashSet<String>();2 l& j, l& Y/ s3 a0 U; h
        HashMap<String, Integer> map = new HashMap<String, Integer>();) G+ i0 `" E8 l: i
        for(String s:words){1 [, ?- H/ ~/ q
            dict.add(s);- V9 |7 x) o+ i/ z( u) ]/ A
        }# B+ R) X5 H1 u- o- j: l9 t) i& e

/ V/ {4 s* h$ A8 X  }4 K        int longest = 0;3 j6 m4 c. e. G' b5 x+ C2 h
        for(String s : words){) `0 N1 R( Z& K$ Q( c
            if(s.length() <= longest){
* V" K* o2 \( V: {6 \, c. C                continue;" h- ^, U5 H2 |4 h% B' x
            }
3 n  p, m. Q  T3 e- D9 E+ T  E) Z/ K            int len = helper(s, dict, map) + 1;
% K& ?/ ^/ q  j            map.put(s, len);
: n" E5 V( o& I$ o            longest = Math.max(longest, len);8 \( J; U8 Y% |4 M) T1 `9 I
        }% r7 A8 r/ [* V9 g/ G2 P9 x
        return longest;* x! ~4 |6 P/ |# W
    }
! [9 `. r( \$ w7 W3 v! E2 V- ?, X
& I8 M( e0 C2 k/ ]/ m8 S
, P! b/ i1 \8 l, Y0 r    public static int  helper(String s, HashSet<String> dict, HashMap<String, Integer> map){! n5 M  b: j1 _2 x- U& V  w& @, q
        int result = 0;
$ P; B3 @. ^4 |* F# t        for(int i = 0; i < s.length(); i++){  e$ e* s2 V5 S! k  @
            String newStr = s.substring(0, i) + s.substring(i+1);1 k; ~7 u' a' S/ z. Z
            if(dict.contains(newStr)){
7 j9 Z, r+ _( D" x/ h4 M# k7 ]                if(map.containsKey(newStr)){8 P3 Y6 m; w' S+ P$ ]
                    result = Math.max(result, map.get(newStr));
* E7 _3 t& U$ }6 R- P                }else{+ j( b0 L  b5 O( c( ]+ Z$ I
                    result = Math.max(result, helper(newStr, dict, map) + 1);
4 U& J1 C  i' r0 c: T4 O- x8 e' @                }
% O. V6 f7 _& V            }% O/ Y+ o8 R) |# m0 o1 _
        }
+ M, d8 E$ z# |3 M4 q, b& Z. b        return result;1 a/ p# O$ D$ ]; l
    }) c" D) E/ j1 m/ d: X6 X+ I* ^
- w8 ^$ a8 f' [. E
    public static void main(String[] args) {
$ C8 }  N  B8 ~$ Q9 Z    // write your code here
- M  {+ p9 R/ v8 t
! I, [9 h1 G1 Q) @        System.out.println("Longest Chain");9 C! l6 l6 D9 e5 _1 ?- B& |. J3 z4 j
        load_parameters();
4 R# c' c0 c% x: V+ K) X- R5 Y* X! `  ]( o  b& F
        System.out.println("words = " );
* s/ e( U5 P6 u; g5 P& G/ a        for(int i = 0 ; i < words.size(); i++){
8 F1 d$ i/ R) H            System.out.print(words.get(i) + ", ");1 e, ~% _3 o0 U5 ?* P- P
        }
$ e( w. o0 S; x        System.out.println();
: s% G) z7 h# t$ m( @$ p" M9 U' }! G; s7 ~3 b
        int length = longestchain(words);* i. d3 `  L* i! F& R1 G: p4 Y
        System.out.println("result = " + length);
, P! }1 h6 Q8 W% @5 g5 W) D5 R' ?- q0 V9 U' R" P4 y% p
3 t* Y$ D9 Y, N2 W" i/ n
        System.out.println("Done");# ]' Z' O2 o4 b* T
    }
  v5 n& _( b6 R7 N+ u* t}- V4 D6 L! \0 d4 c2 n% a
; m; D3 V: q) f+ s; O/ a
======================================================
8 H; V& i4 O0 b0 r7 ]: ?0 r' W8 l, c1 C$ l% U

! N" A, x5 v5 c, F; aimport java.io.*;
* d& `+ F) i) ^9 A0 Eimport java.util.*;
& I$ o6 K2 q) d; H
4 V, E/ E  c8 u7 [+ G; t7 S, I1 X) d* W1 L- D  a) j! `4 ~
public class Main {. t5 q0 V2 I" w& n' ^
" h% I& F; L! ^% s, f8 K9 W2 i7 p! |
    public static int N;
  ]0 D' s" |' ~) ^( j- D0 ?4 z    public static List[] adjList;
8 i" N$ h3 R9 V5 B1 A% |$ w9 l! y$ f
    public static void load_parameters(){
! i: L! W# {/ H: R        // write your code8 X7 D' W8 o1 U2 |5 S6 u
        String fileName = "input001.txt";
5 D- g! g! }" @4 Y: i        String line = null;7 }" x  c/ S: P
        try {
% }" a4 t9 K0 o- i            FileReader fileReader =
! C) E) r4 x! e9 T8 J                    new FileReader(fileName);% o! I" |" p1 E; `1 _

+ `7 V1 J) t/ L2 L' {            BufferedReader bufferedReader =
! ~2 W' B7 A4 h% E3 s                    new BufferedReader(fileReader);
/ U" @' K) i& P3 S1 k7 l; p+ i! j3 U( E7 t9 G; p* A
            String numberOfPeople_str = bufferedReader.readLine();# n" w$ O8 S( `9 @* S
            N = Integer.valueOf(numberOfPeople_str);/ F( r# p  c; j8 i7 P  @; Z
            adjList = new List[N];
( k! x& C  r* d1 n  e2 ~: u, s6 j" |1 y, r- o
            int row = 0;
5 C6 y9 r1 X+ U            while((line = bufferedReader.readLine()) != null) {* w( h3 x8 F# ~* C
                System.out.println(line);1 V1 h. m0 S3 C" S! u9 v* G0 \
                adjList[row] = new ArrayList<Integer>();
; G/ D1 R3 @5 v, g+ v' B                for(int col = 0; col < line.length(); col++){
* _& \  A) T% |- k2 `0 U1 X                    if(col != row && line.charAt(col) == 'Y'){& E% u+ a0 W" A" S
                        adjList[row].add(col);
8 e4 W& h6 j, L( ^9 ?                    }; P' [1 B- m8 W& z
                }! A# A2 K$ ~$ ^* c! l! Q0 F* ~
                row++;
# a( I: M# a" q# D2 d" G  S            }0 Z4 n+ l' `, m2 p# R
. n" Z0 r2 M7 @* C% ^
            bufferedReader.close();
6 D4 v4 D# y3 I* N6 i* }            return;
  X8 x; [( p5 j0 C) |        }' o8 L1 G0 @/ `1 e& q  i) q
        catch(FileNotFoundException ex) {' Y7 `! [7 h" M; I. z3 e
            System.out.println(
$ L% o6 s0 J. p( W; h7 t' o+ p9 L                    "Unable to open file '" +
1 q9 k* R3 t( @  n' ]7 I, z                            fileName + "'");
+ d6 V" Q( w# \2 ?7 c7 e7 N6 p2 R) D, K        }
0 ^9 D4 K  O2 j$ ^% `0 s" G        catch(IOException ex) {
) }3 I$ w4 P! a' `7 d3 z            System.out.println(
. h$ B, m* J. b9 E4 }                    "Error reading file '"  G! D% C; T3 u2 p5 H# p: [, V  \
                            + fileName + "'");1 P' c0 n  o1 g1 Z# X0 J
        }
: C5 W# d. s" D" u# _% g+ h
0 l7 f1 g7 C9 i" B$ D0 y        return;
' p- ~* ^9 T9 j% ?4 }    }) r9 ]; u7 Z$ Z9 M

$ E. D" W; \" a1 H9 |
/ T1 e* L/ _7 T1 j2 m; n( j6 A# |) t2 d9 \1 Q
    public static int countComponents(int n, List[] adjList) {
% X3 n9 v" O. r
$ i# [3 \/ {; ?' s3 h        boolean[] visited = new boolean[n];//visited nodes
6 A0 S( f# X- y. L/ a0 [8 e" ?! G! n1 g# z, w/ A4 a3 o
        int count = 0;# r" y- u( R* q7 o9 ^# v
        for(int i = 0; i < n; i++){# b1 W  z& L; |' J  n$ r
            if(visited【i】 == false){- _5 r9 a8 n9 |8 [3 Q- m% o
                count++;
, k7 m( m# H, ^6 B- l                countCCHelper(i, adjList, visited);
1 i8 R& j3 B8 R- |6 U4 Z) v* `            }
2 H; |0 H' q% i        }
) F6 W) z5 V2 L7 v        return count;7 n' ?* |) e! @$ N" {' m
    }8 a- A, _1 _. k7 w& {

; f8 z6 D: D0 p3 j' K    public static void countCCHelper(int curr, List[] adjList, boolean[] visited){
. E2 [1 y/ \/ d1 L8 ~% Z        if(visited[curr] == true){
  m* g0 Z9 F# w2 t7 ~            return;
8 }6 j7 d  w+ ~( ]! S7 D6 m        }4 n) L; A3 h6 c" w- L, t
  X0 a, q% q/ H3 i$ @$ l* Q
        Queue<Integer> Q = new LinkedList<Integer>();, r! E& p: l4 J% K9 ^. ~5 M8 f
        Q.offer(curr);5 f) _1 V' J! U" O" \

9 z4 ]. g( m1 \+ B% _5 o! ~1 {        while(Q.isEmpty() == false){
) E7 v. _9 d' j: ~2 D4 l            int node = Q.poll();
' |. s2 y* E' g* A- b8 F            visited[node] = true;
* u' k: @  t. u4 @- D3 a            List<Integer> neighbor_list = adjList[node];. _+ H' b3 [! S( `+ u9 N
            for(int neigh : neighbor_list){( B9 h. R$ }  w% V
                if(visited[neigh] == false){
4 P/ Z2 V) \6 L( }- h                    Q.offer(neigh);
: |# Z# `3 G% ]9 ^1 x6 E                }
, x: k4 L5 a+ R8 u% S6 @6 I            }+ c1 ^: w. S% M
        }. U8 n; q# P" A* _' R8 D% }" T
        return;
% v3 e# l* M4 o; C) @# `    }. y! K- Y( b2 [5 K- _

* @. Z- b- H! R/ x6 \; ?" c- x    public static void main(String[] args) {' s' Z  \/ `; k1 L
    // write your code here- \# f+ q3 U0 c+ ~% ~- R8 H6 H
/ z% p0 N6 `& Y4 s: n
        System.out.println("Friend Cycles");
6 V- o! ^& O; w% s' a+ d        load_parameters();( n+ Z5 l/ j. X$ C4 `# L
9 B$ U# E) ]1 U* _2 A
        System.out.println("matrix");9 m* Q( k/ Z1 {* P
        for(int i = 0; i < adjList.length; i++){
& a3 Q5 `% Z* L) j            System.out.print(i + ": ");
% w3 Y4 \6 }( m% `* g& a            for(int j = 0; j < adjList【i】.size(); j++) {
, |* F4 M* W2 ]8 X$ W5 t0 m7 w8 s                System.out.print(adjList【i】.get(j));
. }8 N" a# u$ g. f: T& a; I7 h                System.out.print(", ");
: N9 {( `2 g: G9 E7 G$ ~            }$ ]7 v; j" v. \8 @
            System.out.println();
& O' w8 _4 R6 S( I& A' p4 O+ X        }
; H) x, _9 l1 M
) N% O$ n& e7 C7 U9 r: y% G( r
        int num = countComponents(N, adjList);7 P! B/ e; L, P: B; e: ]9 @9 X; y
        System.out.println("num cycles = " + num);
& |3 K. C/ ~: H1 f7 o1 |" @/ h6 Z  r$ s
; N& X+ U. q" s4 I- j/ `
        System.out.println("Done");) S" S: h% E7 Z. D4 ^
    }
/ e# {+ s4 w2 K, l4 \/ z. L}# Y# p- h% ]! m& a; I# I! B

; y4 i0 ~; B8 J7 L: r
; O: M$ l( i! k+ j; Z# Q, |, _2 i$ c  [6 K

3 z2 @  D8 o- ^& e" r9 e# u5 N
, G. Q& Q2 v# T  y: }8 u
/ u3 y! q2 p' i" E% S2 J( \

评分

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

查看全部评分

0

主题

0

精华

0

积分

新米人

Rank: 1

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

使用道具 举报

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

使用道具 举报

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

本版积分规则

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