找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 25800|回复: 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 编辑 : g' P; d7 i( s0 }+ d- _
$ N/ W! i$ M) O1 U1 _' i
上个月网申的Two Sigma,一周之后HR联系。结果HR放鸽子,我发信去问,又重新约的时间。到了重新约好的时间后,HR过了20分钟才打过来电话。之后就是非常常规的问题。我的背景,Why Two Sigma之类的。跟她交谈的过程中感觉对方很疲劳,有些不耐烦。在谈话结束后收到HackerRank上的OA的连接。, i6 v% q  w2 |$ {3 F
两天后打开OA做题,两道题,3小时。第一道是Friend cycle,第二道是Longest chain length。都是老题了。看到过别人发的面经。自己也在下面先做了做。1小时两道做完,都能通过全部测试。结果3天后收到据信!时间都花了,结果也OK,但却什么都没得到! 真不知道为什么:-(
# g* |* \6 _4 x# }& F% n4 W2 P5 t; d
附上我的solution。大家帮忙看看我的code到底又什么问题。第一段是longest chain的代码,分割线后是friend cycle的代码。
$ k6 }8 D; B1 Y- o大家看后多给写积分啊!多谢!多谢!
. p& L$ G( c: f% ?
& y- Z" ~/ \" c# `. }/ iimport java.io.*;
, g- d5 g7 q! r. |' T, _8 Jimport java.util.*;' d& k. c3 }( u9 C1 ^1 p3 T
) N9 z% X0 k2 j" E! e
5 I/ z2 z2 D6 J) X4 Q
public class Main {' d' }& ~# R- S* H
& W7 H2 r! R& j/ B! N* L

" V0 |# y' a$ U/ L+ x    public static ArrayList<String> words;
7 `7 e7 Y8 `) d# P- }& I3 l- Q
$ D, W' X9 z6 j: N* i    public static int longestchain(ArrayList<String> words){
5 h$ I* s1 s) {; y        HashSet<String> dict = new HashSet<String>();
3 u* Z# a' [2 c+ B" @# z        HashMap<String, Integer> map = new HashMap<String, Integer>();+ n" e5 k* X# f9 v) n9 B: _
        for(String s:words){/ R; P0 `+ y7 H
            dict.add(s);
! E( z4 X$ y) z/ q+ o        }
" R+ V8 i2 `% g0 j! b9 B* R- t; _# X5 K% C% x% u% @
        int longest = 0;
$ c1 r! R0 U1 y0 ^& j2 w        for(String s : words){
" P1 H* r7 c3 O8 v' ]9 I  Y4 O0 s$ {            if(s.length() <= longest){
/ E$ R0 I- X8 b1 x9 o6 J                continue;
$ n3 e4 E8 ~: q' x4 n            }4 T, l$ k8 E6 I$ M+ L5 b
            int len = helper(s, dict, map) + 1;4 v( u! V4 J, {* u
            map.put(s, len);
+ Q( z+ W1 e3 B            longest = Math.max(longest, len);0 P# L* N* T# h3 J
        }  @$ i4 i; I. Q$ w! t- ~
        return longest;$ A8 z2 t6 z# h0 r9 J: `$ P
    }
+ ]% B6 }+ `4 h  w7 }3 B6 D; v. a* @9 S. ~" R9 V  Z

' J7 q! r8 x) f2 }5 e' y    public static int  helper(String s, HashSet<String> dict, HashMap<String, Integer> map){3 N$ H& w0 C2 U: r9 f4 n& f
        int result = 0;0 y/ r. L, [+ m& }$ I' Y% q
        for(int i = 0; i < s.length(); i++){
/ J6 L1 g  ?" i$ _            String newStr = s.substring(0, i) + s.substring(i+1);
, X' s  C, o6 o0 V+ L            if(dict.contains(newStr)){/ f' T# [* i& ~9 i" Q7 o8 j# C
                if(map.containsKey(newStr)){
' C# U5 T& @+ Y$ P9 d# o, [2 s                    result = Math.max(result, map.get(newStr));! D. c  Y$ r  m: U" C, M
                }else{$ P% R7 ~5 I7 }0 K) B7 b/ K% k- G' C
                    result = Math.max(result, helper(newStr, dict, map) + 1);% Z3 `6 O* c/ l9 L$ f
                }
# q3 t% E4 k# E# d% G. c            }
6 t3 r! `) j+ y! E3 t6 ?  v        }' [: h3 P8 y# o+ t' ?& z/ Q
        return result;  r1 _; o/ @8 g
    }
3 A$ s2 Z2 W) t4 E! g
0 K5 o' t$ H+ c$ F; ]    public static void main(String[] args) {
, o* p( @" Y" w0 A/ B9 `    // write your code here
# w0 v2 ?" y! F6 P8 ~
2 s% P3 l! b& {4 c5 s+ n+ K' @# L        System.out.println("Longest Chain");, t- ~- V1 B4 _$ ]0 b: I
        load_parameters();8 [7 l" a! O% K

% i! b) a- R9 I5 }        System.out.println("words = " );
: P9 L" u9 u0 v        for(int i = 0 ; i < words.size(); i++){
: [- A) N: J# j            System.out.print(words.get(i) + ", ");: D' {( O5 m1 ~/ `* M
        }" j( B$ e0 k) i
        System.out.println();8 n+ l4 C+ r0 L3 b) a1 f6 e
: [' X1 o/ j2 o& S
        int length = longestchain(words);+ \; L6 n! s, @
        System.out.println("result = " + length);% C5 F: H/ X& W  F( b1 d

$ l( ]# |4 n% s) W
  m( S3 C% I6 c        System.out.println("Done");9 @& k, I. g- @9 T. h' s( T9 q
    }) L+ F4 q5 `' e: t" z
}$ q6 N) U! @$ M+ x/ p% G2 Q  q

. d$ t( n4 ?& N& c! v======================================================
% U" _9 ?& L' F. ]3 W! J4 f# A5 G8 u1 \' c' l0 b

% F7 D- C; n- p- @: Timport java.io.*;. ^0 [, `) w1 w4 W; f; j
import java.util.*;3 D8 l3 ^  D& {5 R3 d: A/ l) H
- A' ~! y3 q3 D* x- T' z% X
; v' c2 p, P5 b
public class Main {
, Q! V; |3 {8 {# o; v0 J, B+ x1 o# z: `
    public static int N;
  `8 c: [6 ~( i    public static List[] adjList;$ b( W/ z1 `! U/ _0 V
( w7 j3 P7 m( X9 Z
    public static void load_parameters(){
& E; T" B# `, p/ q" k        // write your code7 d" H; g* \( f# G( A: H
        String fileName = "input001.txt";
5 N& k! f) |) `        String line = null;! L7 ^( K9 l% K$ L, q% @) {" l
        try {# e& N( m  s) }: b- l
            FileReader fileReader =" V+ E' F* p* j& u
                    new FileReader(fileName);9 `9 A* [' Q# }* O

; b) |  t9 V! O: l" R. W- ~            BufferedReader bufferedReader =
  G0 Y% t# n, k6 P* r9 R+ F  r7 y) J                    new BufferedReader(fileReader);, n0 r2 e3 H, x

& K0 {! m8 N6 I! p9 a            String numberOfPeople_str = bufferedReader.readLine();
" G' S& P/ u) R; F9 Q9 w. D            N = Integer.valueOf(numberOfPeople_str);
* |, z. s9 V- N9 R! t1 `            adjList = new List[N];
5 ^/ b! |- d3 \; p& l, ]# Y
0 f- u4 B+ X/ i$ c, I7 @5 Z; O            int row = 0;
. V6 x5 t' w. e) ], D7 m( C            while((line = bufferedReader.readLine()) != null) {
5 R) r( l+ v$ c                System.out.println(line);
6 A9 V2 S2 }. s- G. e+ c' y# p/ b                adjList[row] = new ArrayList<Integer>();
) e: R  n3 b, N# F7 p                for(int col = 0; col < line.length(); col++){) l2 S; d3 L+ Y7 |4 {1 i' l
                    if(col != row && line.charAt(col) == 'Y'){
$ p5 r# b" ]) J$ @: H' ^9 q                        adjList[row].add(col);
( N1 J9 S7 p3 [% }2 p0 B! I                    }$ p9 Y6 C' ]% r. P1 ^
                }" F, V' G: p4 [* b7 H' L$ v
                row++;
, N8 f" x4 e& D            }
/ R% q5 r/ c( `8 z& J) p! M" @& n) [
            bufferedReader.close();
: m0 i# j0 E7 r1 Z4 i  M9 u, v7 h            return;7 H7 F/ t0 a8 e5 ~
        }/ }) |) T. @$ |  [
        catch(FileNotFoundException ex) {
* t+ K8 y1 b3 o6 C: y, v            System.out.println(& R& A3 e, i( n0 ]
                    "Unable to open file '" +: ~: W6 {; y. c: d& g7 }2 [$ S& l' |
                            fileName + "'");
0 a' j0 E/ J# y( n7 ?6 \        }
" L, G4 x/ ]7 R8 r/ G        catch(IOException ex) {
; {8 N, {0 @! x3 v( Q            System.out.println(6 }& L6 a2 c) ]9 P( S' f
                    "Error reading file '"5 _/ U; G6 i2 o" X& r- x2 L
                            + fileName + "'");" m, {1 X: s- J6 N1 M) V
        }- m4 R0 ~" I9 n- P' W/ t
+ O! y/ v+ v( X+ Y) K) s/ h
        return;# y3 _6 C5 I4 `+ V1 U' C2 R  T
    }
7 W" g/ N  K. U- s9 K8 _# A7 G
7 }5 X. q$ a0 T" R0 U( O1 o* Y9 ^+ C4 l

9 ^7 f& E5 |7 f& s) Q2 F* _# f9 Y  W/ t- g    public static int countComponents(int n, List[] adjList) {
$ W& L, s6 S4 U3 d% b! E# ?, [' E2 v% S
        boolean[] visited = new boolean[n];//visited nodes
8 g$ b) ^. [& B6 k8 l. ]
) h9 P% @4 I; K: }8 L+ s        int count = 0;
" N, |# o* N" N4 h' {# C        for(int i = 0; i < n; i++){
6 \+ u8 P# o( I/ L; g& s0 m! e2 A            if(visited【i】 == false){9 f% b) V4 z. r) Y, S
                count++;
* K7 ~8 o$ {% _                countCCHelper(i, adjList, visited);
7 E( W4 w& y2 m0 |) v( e) e            }4 L: j) l. {6 O4 q
        }
" T7 e4 O+ h3 @0 m        return count;5 A4 l! ^; `1 y0 U0 ]
    }
. B1 M1 v* W! R) j( T) U  t* d( E) A& ^
    public static void countCCHelper(int curr, List[] adjList, boolean[] visited){1 ]# B, U+ [+ f% I
        if(visited[curr] == true){
: ?* b2 o- Z; }( ^; p            return;3 v; ]8 G2 g" \/ b- _4 r
        }
& b* j/ v6 f& f4 I* h" z" P8 c7 {! j
        Queue<Integer> Q = new LinkedList<Integer>();  _6 S# a  J9 y! X0 ^/ k# ]
        Q.offer(curr);& J+ q# k! J: M  J# |  i
+ @: ~; U  A- N3 K* @4 {' e8 _
        while(Q.isEmpty() == false){
% V, D$ y. C7 z            int node = Q.poll();3 ^( N8 v$ S' u& |9 L4 ^
            visited[node] = true;  A& `4 M" \3 z) O
            List<Integer> neighbor_list = adjList[node];
1 E/ ?& V" C$ s( E  o+ N8 ~% d' @' i            for(int neigh : neighbor_list){: r0 z' I- j3 I, X0 O' A
                if(visited[neigh] == false){
7 r' A" w3 l# x8 \: ^! T7 ]* w: o. \                    Q.offer(neigh);
9 w+ {$ Z9 v, F( K; {+ B                }% }* U" W7 c' W" c  Q
            }
$ a) A' _6 p% N3 [# G        }
8 ~1 ]/ i  r+ f  ?; F        return;1 G* A. z. P, b2 d% f+ H9 ^
    }+ ]1 G: O2 v4 {& S: J) k5 M, Z+ [% y6 m# `

4 U2 C0 z* v  _' A    public static void main(String[] args) {
, ~! `, Z# f% \! j) w    // write your code here; o* D' q( F# {3 T, A8 D. c% a

8 W# O  R) \) a        System.out.println("Friend Cycles");
, A1 U$ D3 X) p        load_parameters();
+ {9 M9 j0 g  J2 z& y% `; V
3 L3 c! u3 {$ w. j        System.out.println("matrix");
4 H, u4 s* w/ z8 e2 p. ^7 ~        for(int i = 0; i < adjList.length; i++){
' k6 Y- c0 c' M2 q) }% _            System.out.print(i + ": ");
' `/ t) x3 x2 H  \, H7 `2 b            for(int j = 0; j < adjList【i】.size(); j++) {
3 T( N! b& A! ~* G1 F) c" R4 o- U                System.out.print(adjList【i】.get(j));
+ c* k" X7 A! f- e( X5 e9 b                System.out.print(", ");8 X7 x( S3 J( N% G( e
            }9 C; Z( Q  v+ k6 `# B3 M% z: D! W
            System.out.println();) i* @. L/ \" F. a- X
        }* S0 m- _. r. b% d" ^
2 A7 P" L/ T' {' W

! e& e- }. b, g8 l7 |+ @        int num = countComponents(N, adjList);* h( W' D& \5 R7 K- _  y2 M' c
        System.out.println("num cycles = " + num);/ H9 W. ~7 P' v! e

( F! g. X2 L, D' }5 a
* h1 R) u( A) W) Q  E) e- q        System.out.println("Done");$ b3 a7 u# }7 ?2 `' p/ ^+ S7 e9 g, `
    }
0 \8 h6 S' R' J$ y  i}
) k# c8 \2 v! f6 I: Z8 J: S' _! R) c: D* r# o" K
1 j  s& V9 G5 w- b' l$ P+ l

0 K  ?1 Z( y( W" W2 N: d
, d, ~' h4 \: p, U4 I' G& w4 U  w7 b3 m1 {

- j/ H2 Z3 f- d( L# `$ {

评分

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

查看全部评分

0

主题

0

精华

0

积分

新米人

Rank: 1

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

783

主题

577

精华

5685

积分

顶级版主

Rank: 9Rank: 9Rank: 9

积分
5685

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

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

本版积分规则

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