找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 13051|回复: 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 编辑
6 ^. c8 A* ?( s' u& L3 ]3 G% D8 K6 u8 r/ m( x0 k, y
上个月网申的Two Sigma,一周之后HR联系。结果HR放鸽子,我发信去问,又重新约的时间。到了重新约好的时间后,HR过了20分钟才打过来电话。之后就是非常常规的问题。我的背景,Why Two Sigma之类的。跟她交谈的过程中感觉对方很疲劳,有些不耐烦。在谈话结束后收到HackerRank上的OA的连接。
0 ~. o, X0 Z7 N两天后打开OA做题,两道题,3小时。第一道是Friend cycle,第二道是Longest chain length。都是老题了。看到过别人发的面经。自己也在下面先做了做。1小时两道做完,都能通过全部测试。结果3天后收到据信!时间都花了,结果也OK,但却什么都没得到! 真不知道为什么:-(. T; h4 c% o  X

" q: g; O6 l# O7 m) J附上我的solution。大家帮忙看看我的code到底又什么问题。第一段是longest chain的代码,分割线后是friend cycle的代码。, s9 q  V4 w; h8 @
大家看后多给写积分啊!多谢!多谢!% C! L: {4 N8 L

! j' m, A4 O7 u$ cimport java.io.*;& O) D/ N; s0 r5 |; {
import java.util.*;
( ~8 m* }- ^7 W  n5 I% E
7 V' x1 d, P8 t$ D0 I! u1 R: P. @( `
public class Main {
/ {1 Z3 B! g& q/ H# B' j
# @% Y; M7 d  S# ^% M# J8 F' p* _, c8 D- g$ F1 s; _4 p% W
    public static ArrayList<String> words;
5 }  y4 n! M8 \/ s: J
; U# j7 ^8 c2 G: ~- J/ G8 L    public static int longestchain(ArrayList<String> words){
6 h) D) |6 {3 \        HashSet<String> dict = new HashSet<String>();, }2 [! t  F* O6 P" |) J+ @7 G; v
        HashMap<String, Integer> map = new HashMap<String, Integer>();% ~$ v; X; \) a/ h: I
        for(String s:words){
/ J; B1 O# G0 B: f- H" x            dict.add(s);- F# D4 X; e0 V  o8 J9 }
        }4 D' [+ H" C9 k* Q

% r8 U, F: C- L3 @& U) q        int longest = 0;
, g7 Z0 [/ g. C( }" m4 \        for(String s : words){. m6 W6 d0 d7 W1 C
            if(s.length() <= longest){1 p- p# T4 w6 k; p, h4 x
                continue;
1 n! e5 E; }: C3 u            }, `) y5 F. d5 Y, ~# K
            int len = helper(s, dict, map) + 1;
& p& ^+ \* U; T            map.put(s, len);
8 m1 v- h* ^" w3 l& ]) \+ X            longest = Math.max(longest, len);
+ g( F& m3 V0 s        }
% ]; l  C% y+ K4 Y" \        return longest;5 ^7 A8 C) O* R/ D
    }
4 D: s4 ]% [% ~; \, g) V/ a+ H3 }& J

( Y! }* c! T, ?    public static int  helper(String s, HashSet<String> dict, HashMap<String, Integer> map){1 O2 L( J; j  k4 t& s" I5 b( z
        int result = 0;/ a9 X  N. ?8 c% M! }7 Q4 f
        for(int i = 0; i < s.length(); i++){  @# r3 R0 S  l8 @2 {" j
            String newStr = s.substring(0, i) + s.substring(i+1);
" T( S3 ]0 I! |* L            if(dict.contains(newStr)){
1 P: [% d! z! F6 w- y# o" w                if(map.containsKey(newStr)){1 O# ?/ R1 h: b. Q9 t5 F8 w( |0 W
                    result = Math.max(result, map.get(newStr));
+ c1 p1 w% U* m& ?3 C0 {. {! l: l' e                }else{5 g$ `4 G" Q" w2 F# N
                    result = Math.max(result, helper(newStr, dict, map) + 1);
" g5 h/ V8 `3 M6 `3 ]4 L1 H                }
+ I, m: w( l/ y6 f3 O. V8 t/ k$ R            }
/ D: F% Y7 s9 h. I9 d& U        }9 P8 e1 g' ~% i. Z, B" e% X
        return result;  x1 u( K) L# ?% H: h
    }
+ q- M8 _9 _; n( X8 u1 m/ L' F
% q4 _0 i+ J, ~    public static void main(String[] args) {5 a& d" |) c' s& v
    // write your code here
2 }8 i3 q' O5 D+ R7 h( E0 R( N7 U+ m  ^# a! r$ O5 P' F' h
        System.out.println("Longest Chain");
# Q6 G4 C: b; z. _3 `        load_parameters();; N" y9 t! a: [: S
/ o9 F/ G6 S5 r! g
        System.out.println("words = " );
& w) M; f3 M: U) K3 Z8 X' ~        for(int i = 0 ; i < words.size(); i++){
. g0 A* p( V6 \2 m- `            System.out.print(words.get(i) + ", ");6 b- h/ x7 g0 g* U. q
        }
/ T1 u  \; ~; i, o9 A5 g" C+ b        System.out.println();! w" k4 E# H* U3 q; d, }( y1 Y
; j3 I& e% d: t: i  B% i% ], T2 T
        int length = longestchain(words);
! I' Q3 ^4 ?; L) R$ S. [- D        System.out.println("result = " + length);  I* i0 j4 x+ _5 ?7 d3 e

! j9 q  J' W" e+ s
6 [) \1 m' {/ {& B/ r+ I, e        System.out.println("Done");
! p. q% x: f; u4 m+ ^2 J# M4 z    }
. D0 l5 D( v2 {6 g5 s}
: O6 w) N! ~* W7 i% [- c9 H, K" W/ o# i( `( P4 I5 Y4 P
======================================================$ E; I4 z7 ~* [7 R' F
# b8 }6 r+ ^% p% x' a
/ D. l5 u/ m6 Y
import java.io.*;8 M/ W0 E! X- s* M/ `( Q/ n! i& F
import java.util.*;5 K  {; ~; Z- w' w, M9 A$ O

% c: }4 A7 p# s5 X. {, v$ g0 k0 L6 o. B* K3 v* P2 n
public class Main {) ]9 S- U! s$ c- t7 l) S6 O. ^
/ y! O5 [* T! O7 G
    public static int N;; c2 u$ @2 n+ t+ N5 j
    public static List[] adjList;2 T) \4 t" B3 _: S! a

6 V' r! S' X9 m! s. B- s% s    public static void load_parameters(){  `4 e% A% m6 |7 r* `; z
        // write your code: M% L& v3 V1 d
        String fileName = "input001.txt";9 W) r9 B! Y0 e
        String line = null;
. ?; s* _' ^. @# |        try {. X8 Z8 G) V8 f) \! ?) t  }
            FileReader fileReader =5 t/ r+ p( D7 c9 }$ ]4 I
                    new FileReader(fileName);
5 B( q" G, @; d' a- ?  N9 A' V2 K8 Z3 H% L% Y) u
            BufferedReader bufferedReader =2 f( [+ A. p6 s5 f/ ?) E
                    new BufferedReader(fileReader);8 w; {- q1 h0 B$ b
5 g( }, c5 J6 k6 v, s9 w0 ~7 L
            String numberOfPeople_str = bufferedReader.readLine();$ r! h8 H8 S' f
            N = Integer.valueOf(numberOfPeople_str);" z# m. S8 V2 K  k0 ?7 ?
            adjList = new List[N];# \$ u" o. ]8 O7 _

' B$ L4 X% l2 d8 O3 [: K            int row = 0;
$ S2 p3 C% J) t            while((line = bufferedReader.readLine()) != null) {" p" Q& h3 e9 T( d' R; @
                System.out.println(line);
; W$ _4 r7 a5 q                adjList[row] = new ArrayList<Integer>();; Q( a2 e  f, a/ X9 ?9 @# F
                for(int col = 0; col < line.length(); col++){
$ f* i4 Z0 }! v                    if(col != row && line.charAt(col) == 'Y'){
# U9 X) H9 i8 [2 X6 X& |; ]/ {                        adjList[row].add(col);
2 V) m- _6 J! P3 F  r/ H                    }
  C/ L' s: p( h1 e6 @5 ~, u* J                }5 Z& o* ^6 g- b) `% I; `
                row++;6 ~1 N- H7 g& m: X9 U; q# `
            }, y6 a/ G0 M  s9 T  z

# M3 Q- h5 @; s            bufferedReader.close();
5 c: K* `8 S- U            return;
# c3 c- }0 Z9 H) g- u        }9 x9 Y, b- Q! F7 K) l7 H& `
        catch(FileNotFoundException ex) {& l* c9 z! n' c0 m. ]3 f
            System.out.println(1 m' e. P9 v+ d! \: `1 K1 F
                    "Unable to open file '" ++ n- w9 _" H7 A4 t* B
                            fileName + "'");
! ^8 n. d+ K+ [8 x" g: R( E% q        }
1 t  R; _0 M" C8 K+ l' ?6 \% w        catch(IOException ex) {
: F3 m! N0 Q. a) J8 h6 e% |            System.out.println(
4 z2 T" n7 q3 p/ z/ y$ N                    "Error reading file '"
) v. c# I) L9 w+ I                            + fileName + "'");$ g1 {+ p3 `: I: a
        }0 z+ N7 `+ i( v$ Q0 B

; |4 b) B; c1 g3 p9 ]4 C( E        return;
: p: w+ b- l' u0 r. _    }  o3 d$ t- g9 a+ S+ F, P' X; H/ y
8 `7 p+ B# K, u
  C+ L2 c2 q+ F! I+ H5 j& e
5 s6 o. V# s9 F# }0 `
    public static int countComponents(int n, List[] adjList) {
$ x/ c  E* p# M2 Y+ S  ^! y' u) P; ~2 A1 \$ P4 h
        boolean[] visited = new boolean[n];//visited nodes. [% j2 G, h9 `5 n' `
4 q" M% |2 g: M. }$ [& g/ w
        int count = 0;
* k6 [3 D" x; v1 J$ j8 z; ?        for(int i = 0; i < n; i++){* D6 h7 h" e2 m" x$ {
            if(visited【i】 == false){
* v. o) o7 u: ~. s* A# F" h                count++;
3 W0 Y1 o6 _, H6 T! E8 e                countCCHelper(i, adjList, visited);
) u+ o( }  s4 P9 e/ D2 h            }( x% h* x* |5 j
        }' u& S& A. E' e3 {- d
        return count;- n, \+ X5 K0 R3 q. o4 i# [
    }
3 ?0 t9 R* @: M$ Y9 O3 M( w, n" ~* f; }- l( b8 ]( I3 k9 N) |
    public static void countCCHelper(int curr, List[] adjList, boolean[] visited){
' z7 e6 ~8 a( @# c' w* y% @  d8 b        if(visited[curr] == true){1 A& W+ }4 T- c% k. T" H7 B- M
            return;
2 A) w/ o5 z0 K& p, j+ B4 o        }
5 E( {8 B5 ]/ i
4 m! D& p+ S2 I( T3 ^' U' q: K: L+ n        Queue<Integer> Q = new LinkedList<Integer>();/ s; i- j* M9 Z3 B
        Q.offer(curr);" m7 `) B" z6 l6 r* H8 I4 [

+ I6 g$ V/ D4 G- {7 v& f        while(Q.isEmpty() == false){1 ?/ {2 P# j7 Z  Y2 E( e+ R
            int node = Q.poll();4 `6 n) b$ o. a# v; r& m  G1 e
            visited[node] = true;1 g" }9 N1 Z+ b/ J( E( J3 p
            List<Integer> neighbor_list = adjList[node];
1 b( {) |, H5 y/ P; @' d) G            for(int neigh : neighbor_list){6 {( C, ^. R% W( m: g8 r. m* ^
                if(visited[neigh] == false){: u" t/ n; \. k
                    Q.offer(neigh);
+ Y' a" [/ i! E' L                }
3 V, G- W- \( P: Y5 {9 }6 @6 ~            }
$ E4 t2 ?/ A; D; R# q        }  v# Y  c, x2 V
        return;' a, w# y9 |7 J! A) M* ]9 J
    }; g) a6 e* z9 d1 U- O
' w4 A- i9 k8 x- M
    public static void main(String[] args) {' l3 R2 }) I5 c% a
    // write your code here4 d! X: h3 R8 D2 z' M1 v/ k& v
& Z* P% j) A, v7 K3 R
        System.out.println("Friend Cycles");9 z4 B! e- p8 Q1 O2 Z. }2 l
        load_parameters();
9 X& W4 m' e8 W3 |- L9 u" S! a# X$ d1 _3 f
        System.out.println("matrix");
1 @2 d8 S4 @! T% u1 u6 D7 f1 F) Z        for(int i = 0; i < adjList.length; i++){: t% b  G& W6 z9 g& S5 u
            System.out.print(i + ": ");
" f  a. t/ |% s+ f            for(int j = 0; j < adjList【i】.size(); j++) {
# Y' T" S9 h% S! x. B8 z6 f                System.out.print(adjList【i】.get(j));
, z5 r: g3 N% U2 ~2 X  e& j8 b                System.out.print(", ");: e6 ^6 F7 R8 @1 k* ^3 D: m1 ^9 `
            }
8 ~. |( \8 X5 c9 E6 l: u            System.out.println();) b0 t& U, p. b0 C# B
        }3 B4 N" j0 @+ j* C, x) U1 ~

" I+ ~( b/ H* ~: ]$ P6 _% c. p  l; h4 {
        int num = countComponents(N, adjList);
" U. }' s& [) ?- d( v1 ~* q        System.out.println("num cycles = " + num);9 ^  \+ ^7 D$ E) Z. s# I
$ X! w5 g. Y6 P9 e+ r' o1 R

) B9 i4 G/ P" H# J3 n7 K8 a! W. z        System.out.println("Done");; x7 b8 z6 w1 g% t
    }
8 n3 |  b9 b$ C8 |, E6 T. a* q}
+ f# n! n$ s/ M1 m/ q% X+ k. y4 R2 u1 ~5 n/ V3 F
( Y% Q: M" P- i6 {

  }3 z/ N! D& r& |2 \9 {4 k% H9 s3 i- d# u/ U9 Y% x

- |# y8 W0 P2 Q5 a/ E
5 g- p5 w8 u3 G) j, w/ Q3 ^. e* I6 L

评分

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

查看全部评分

0

主题

0

精华

0

积分

新米人

Rank: 1

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

使用道具 举报

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

使用道具 举报

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

本版积分规则

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