找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 15068|回复: 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 编辑 ' @. O' g9 u3 [5 h2 r( f

, T! I6 }; q2 m) R, Y上个月网申的Two Sigma,一周之后HR联系。结果HR放鸽子,我发信去问,又重新约的时间。到了重新约好的时间后,HR过了20分钟才打过来电话。之后就是非常常规的问题。我的背景,Why Two Sigma之类的。跟她交谈的过程中感觉对方很疲劳,有些不耐烦。在谈话结束后收到HackerRank上的OA的连接。
; o/ Z3 m6 M  T; O. z! T! X两天后打开OA做题,两道题,3小时。第一道是Friend cycle,第二道是Longest chain length。都是老题了。看到过别人发的面经。自己也在下面先做了做。1小时两道做完,都能通过全部测试。结果3天后收到据信!时间都花了,结果也OK,但却什么都没得到! 真不知道为什么:-(
$ @1 |( o3 T0 M% W5 \" n; |1 f) Y) b0 j) ?9 _8 e$ g% ?
附上我的solution。大家帮忙看看我的code到底又什么问题。第一段是longest chain的代码,分割线后是friend cycle的代码。
- Q% a8 c5 J: m; b大家看后多给写积分啊!多谢!多谢!9 ~& j# _3 ^3 E3 f  T
% e; q9 E5 ~8 K2 `) t% G; ?
import java.io.*;
. B, V7 b7 f+ E  t" Mimport java.util.*;
+ [1 d3 A. a( g" u1 K+ k/ O1 I9 u7 m3 q

9 ~* Y8 U5 m( [5 c+ L7 fpublic class Main {! Q4 K: H' x0 t! ~5 N, p. W

/ n3 m( k  _2 r* O8 W
0 x! @. S4 R0 }: o% j0 p! a    public static ArrayList<String> words;& A( x6 h) l1 Y9 D) i. \, \# U
; Z$ A7 Q1 R0 ?; w2 j: X
    public static int longestchain(ArrayList<String> words){9 E6 o# f% u) R! d3 P6 e
        HashSet<String> dict = new HashSet<String>();
' X6 }  V3 x; }. u3 G; q        HashMap<String, Integer> map = new HashMap<String, Integer>();9 D- H& f6 C, E9 B' [0 \
        for(String s:words){
  z) _3 F! O5 t4 R; y3 u            dict.add(s);
' J# |: p9 O, o7 d4 G& O& z& M        }# G; g+ k4 g9 c2 M

, f: u0 c; `, e" g        int longest = 0;1 _& q9 M9 I+ O% d5 h
        for(String s : words){1 V9 H/ O5 ?6 u
            if(s.length() <= longest){
- S9 S, @; h8 y3 u                continue;
6 l' o: l; j& C( S, A' \: X            }
/ X4 L; ?9 B6 G; r9 g$ c5 y            int len = helper(s, dict, map) + 1;
" O8 X) t4 b% \: V1 b            map.put(s, len);
/ |- t  y, m* d8 o) F0 h            longest = Math.max(longest, len);
! C# i# y1 Z2 p+ n% Z        }2 B& b9 P  L' }& c3 R% F
        return longest;6 j/ u1 e& U; U' {) Y
    }
9 ^: H: D* y% d( ~* y1 _. [% ~, ?2 d9 Q! H+ \4 D

$ e# `& ~0 z8 t* D0 u    public static int  helper(String s, HashSet<String> dict, HashMap<String, Integer> map){
- q. }9 r6 Z- M+ p8 H3 @        int result = 0;
% F- E8 R6 J# v2 ^1 y! U* \        for(int i = 0; i < s.length(); i++){
1 b5 O( S4 p# B* q& K2 p. e            String newStr = s.substring(0, i) + s.substring(i+1);) |; N9 i7 c' O: l5 e" P
            if(dict.contains(newStr)){& [, J# _# C+ }$ }" N6 o( d  g
                if(map.containsKey(newStr)){
( E) K9 n) i3 A% c: h. Q+ u                    result = Math.max(result, map.get(newStr));: w- C+ W" g/ M* a6 ^+ J+ A
                }else{
8 T" k# }1 y/ V8 T5 N                    result = Math.max(result, helper(newStr, dict, map) + 1);
  z% K; a/ G* P8 j" p& p5 s1 X( }! E                }
& |& D! g$ I2 u6 f; P            }' }/ s! n# I4 W5 K0 H+ M/ P+ ~
        }
* v, p# |; ~# n" ~, i# Q        return result;& W+ }8 Z0 G, p, ]1 l
    }: s# _& M# f. ]& N8 F  y. W: }

. W9 ~" c0 s* G* @    public static void main(String[] args) {
5 T# p! v0 z" H# l, X. K2 |, v, ]" V- J    // write your code here
' F. r' _) b: E* g* {2 P; I/ R6 q8 X% r4 l7 ?5 L; S+ o% u9 d
        System.out.println("Longest Chain");% B( c: U( p  k& n; t
        load_parameters();
/ @) ?: q6 g3 m: w& A1 L4 t$ L% `3 S& ]3 p" B8 p9 m
        System.out.println("words = " );
. u0 ?$ x) \9 t* Q2 S4 Y        for(int i = 0 ; i < words.size(); i++){
2 [3 ]( h: w' B# U2 {8 K4 z7 t) d            System.out.print(words.get(i) + ", ");
4 A( a5 a8 l2 b        }
. e' ~5 c4 x& b) C  j+ q        System.out.println();
" E  J, y6 ~5 H# K+ L; V8 |
* I0 `$ g% k9 R( G* w        int length = longestchain(words);
, w8 r7 L, v& z9 a        System.out.println("result = " + length);
# x# o+ b8 C; d3 x" v- m3 x0 [2 D1 g% a: R( z' \

3 v+ d7 _0 f* x" i        System.out.println("Done");
) D' M3 j5 I0 M7 y& Y3 e    }
3 O4 P5 ]; H: V3 a6 V3 W) ~}4 D" c/ h0 n: q$ j' f& ]" \$ L: ]

5 V# y, X: e, q; m1 z" a* j======================================================  y5 ^: G* B  O7 ^
0 ^' r  ^, O3 ?* d; m

( E5 R. N2 l% L% Eimport java.io.*;
4 u% [% ?9 I0 W: q% J7 Mimport java.util.*;
, o2 M! Y' @4 {/ O
0 R: K- f, R4 ]  K7 w. Y' t+ u) g8 b' ^
public class Main {! B# D' ~8 D2 O* r* S& L
* N  P" h1 D# r. {
    public static int N;) O1 A2 X0 F$ ^9 G% b
    public static List[] adjList;, y. [( E- S0 X+ j

/ d1 ]8 I! P1 }; i    public static void load_parameters(){" M3 k: }4 e( `
        // write your code4 U1 z, R6 \+ s+ `' k4 t' o
        String fileName = "input001.txt";% A2 w" }! B( s0 S
        String line = null;
; B3 t* Y0 D! W' E' ~% y        try {
! ]5 t2 |8 j' Y# C* p9 J9 L            FileReader fileReader =9 h7 @; E  a% f0 A& Q
                    new FileReader(fileName);& ^/ p" D4 P% I7 j/ d

3 F; R2 [6 r8 x; p2 j7 l) ]1 o            BufferedReader bufferedReader =. \9 P$ I0 m( o7 y# h3 ?  Z5 P
                    new BufferedReader(fileReader);4 a! l/ O3 j+ X+ Z7 F

% j0 u6 _3 z2 _9 s- q8 C            String numberOfPeople_str = bufferedReader.readLine();
! B- B+ ]9 g& S! X8 p3 ?- a            N = Integer.valueOf(numberOfPeople_str);
: H4 F6 a& _% H: Y: h1 S0 F            adjList = new List[N];
4 M2 q& M( p0 h  ^& N+ e- |% w8 N8 D6 S6 o& ^, e* Q
            int row = 0;7 l2 X7 |8 Q1 n3 B8 p1 [
            while((line = bufferedReader.readLine()) != null) {
; I& D0 @1 f4 e8 P% C                System.out.println(line);! C! T' C! H' s4 r0 S! Z2 k7 U, a7 A
                adjList[row] = new ArrayList<Integer>();" v; X6 r1 |' S1 R  m0 T
                for(int col = 0; col < line.length(); col++){
7 j+ m( [. {: h" t& f% g9 m5 I                    if(col != row && line.charAt(col) == 'Y'){
9 m) p) H7 p  `9 f+ x3 k- x                        adjList[row].add(col);) \4 j" B2 d0 Z3 P! ?* ]8 ~
                    }7 W* }3 t: e0 @
                }
: f3 E$ F7 a' B) ]- U! {! s                row++;
& ]/ R0 Y, {& I. D& ^& L            }+ o- S  {: e1 R# N

7 J) c9 Y! G# a4 o. x            bufferedReader.close();
4 [) e) E' b& O: j            return;
% i: @7 c" R2 ^/ L8 `- N0 y        }
0 p8 a. K, j4 a" U( J) D+ Y        catch(FileNotFoundException ex) {
$ A# e5 d# \: q5 h7 r+ f9 ], y            System.out.println(% B' ?' B3 N! o& b3 d6 p
                    "Unable to open file '" +
: P2 [' ]5 C5 h                            fileName + "'");
3 ^0 h6 i  ^5 x4 q* {- d        }5 j) ]% [+ i+ u: M
        catch(IOException ex) {1 f4 d. a6 D1 v7 l+ X# t) M5 s+ Z
            System.out.println(- m& O4 P$ x4 W& U
                    "Error reading file '"/ i8 y( D; _: w3 G) R# }4 j
                            + fileName + "'");
& q' o+ i1 [0 U2 W; d        }
$ J0 i! N6 u/ N# V2 G' u5 ?
' W, X: ?6 k2 D' \        return;/ x: M3 j  |" ]$ a* I* G
    }- M$ D2 _2 [* r+ I% E
+ `, ?$ n' Q3 K% i7 F( K6 x5 h' K

* s/ [0 h  \1 w
: q% E8 o6 `9 j    public static int countComponents(int n, List[] adjList) {
$ j* f0 q5 N% o2 M) c6 f6 {
+ v5 I" d; D5 G- r  I# j( h- Q& U4 o        boolean[] visited = new boolean[n];//visited nodes) @+ ~2 }0 ?& P/ I& t! k4 N

' a$ T0 O2 Q( o. \! Y1 V6 h! j9 f        int count = 0;* t+ H9 A, [* w, z
        for(int i = 0; i < n; i++){, s6 l# U4 ]6 I* H0 J% ]* `0 n
            if(visited【i】 == false){
1 K' O4 g6 ~8 m                count++;
% v+ g" ]  a2 d9 x- _, M" |( a                countCCHelper(i, adjList, visited);
' {. b/ B! L" f8 C, G& h2 r            }
& B: q3 s6 k- S( ]7 p/ F+ M        }: ~" f6 d/ v: K* S# N
        return count;
+ U' m& a, F! c. u* ^1 }    }
: n' ]+ A% w3 D7 t; t7 G7 @( E: d3 y* R+ Q) N7 t  x
    public static void countCCHelper(int curr, List[] adjList, boolean[] visited){
* l% t' W9 s# M( k        if(visited[curr] == true){
% |' o3 R% N! {- }, j5 }, Y            return;) a! D  l9 K5 A/ T  L# M
        }" ~- E/ a* X* q* P8 [
" S+ a5 y* j0 h1 i5 t) j; S
        Queue<Integer> Q = new LinkedList<Integer>();
- h2 Q: `' g( o3 E" |1 i2 ?        Q.offer(curr);
; [0 T2 w1 R2 K" R8 x8 K! i( `
! L/ M# `* f' {0 C1 u3 F        while(Q.isEmpty() == false){2 c! |: u1 ]% ^
            int node = Q.poll();- n5 V  T! F9 c6 K
            visited[node] = true;
; a- l) x8 v* i: i+ M: Z            List<Integer> neighbor_list = adjList[node];
5 P0 S3 {! N1 R3 L# T# k6 E! V            for(int neigh : neighbor_list){( M- D) w& \& T  C
                if(visited[neigh] == false){
6 s3 Y' L! N% k- ~                    Q.offer(neigh);
% c; ^/ Q: I$ ~$ }- h2 x  {) C                }
# j: c) X2 ?( O. b2 s            }0 C" ]7 o* t" @$ z, ~4 }
        }. D7 _: w, F7 Y- z6 n
        return;
1 u" B- D5 [; O% \! Z1 N* h    }
' K' T2 z$ u3 g9 X( X1 d- q* Y* E) K
    public static void main(String[] args) {; x0 G7 E2 D- B+ T  G
    // write your code here9 c" q# V5 V# i7 n4 I% ?

6 p" p, x  l+ V$ x' j        System.out.println("Friend Cycles");+ P) a" R( N+ C5 l
        load_parameters();
* @6 u! r! o9 I1 ?( m3 h
, w8 _; i# Q7 v' g$ ?        System.out.println("matrix");4 R5 x1 U0 K' N. @% l; H2 w
        for(int i = 0; i < adjList.length; i++){- m; d) [  y+ \6 X0 ^
            System.out.print(i + ": ");, i# a) ?. I3 \* s: E+ y4 t
            for(int j = 0; j < adjList【i】.size(); j++) {
9 p3 Y+ E& g% M+ |% b8 U$ k                System.out.print(adjList【i】.get(j));0 D8 @4 ~" Z0 Y
                System.out.print(", ");& b0 Y2 X& ^( p! J6 t5 X4 Y
            }2 V- I7 S3 f! p. O
            System.out.println();0 M! v: h) \9 @3 a- U2 a1 K
        }
7 T6 U: q: g9 e5 R$ c9 M6 |1 a4 J+ I* I

' u+ t0 _! o  v        int num = countComponents(N, adjList);
" R& H" _& J8 W2 [. s        System.out.println("num cycles = " + num);
6 A0 N1 c2 t7 {$ J* h' K# h1 B4 q# ]& G/ t4 Q
1 E, U* [: x( O3 Q! J5 P
        System.out.println("Done");. b$ k# u3 B2 J& X, I  H2 p- b% D
    }
6 p0 \$ }* O; Z}$ s  T% w9 b5 b- X7 _1 e4 @
# `) ?  D( Q3 \. f+ F) Y

/ a& I% l0 F0 x) Q4 S( J$ P+ z& A& _/ @* n( {: N
5 l2 ~. L6 M' y* H8 V" Z2 u& n# m  M
) N/ d" X  f/ z
0 g) B" ~/ D) v" e

评分

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

查看全部评分

0

主题

0

精华

0

积分

新米人

Rank: 1

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

使用道具 举报

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

使用道具 举报

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

本版积分规则

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