找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 28113|回复: 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 编辑
: B( a) p. T, K. b# l+ X- Q$ m
2 b7 Y0 I/ g# A9 c4 ]& q3 [' J上个月网申的Two Sigma,一周之后HR联系。结果HR放鸽子,我发信去问,又重新约的时间。到了重新约好的时间后,HR过了20分钟才打过来电话。之后就是非常常规的问题。我的背景,Why Two Sigma之类的。跟她交谈的过程中感觉对方很疲劳,有些不耐烦。在谈话结束后收到HackerRank上的OA的连接。& V' ^$ q. ^/ ~  N: ^
两天后打开OA做题,两道题,3小时。第一道是Friend cycle,第二道是Longest chain length。都是老题了。看到过别人发的面经。自己也在下面先做了做。1小时两道做完,都能通过全部测试。结果3天后收到据信!时间都花了,结果也OK,但却什么都没得到! 真不知道为什么:-(
) v/ `! o9 v. g, `. h# l
8 I* c1 y, d' w; L$ p附上我的solution。大家帮忙看看我的code到底又什么问题。第一段是longest chain的代码,分割线后是friend cycle的代码。
& \+ \$ ^' C3 Q: `2 @9 x8 b: s+ Y大家看后多给写积分啊!多谢!多谢!
6 @0 z  {) {7 _/ R; [" Y' Y! w1 D  E: Y" N: y8 O
import java.io.*;
. u' ]% k, Z& D7 zimport java.util.*;( {6 e; s; n6 Y. ^$ u3 h7 u
3 E  m8 @& x- U# I9 u6 z+ m7 V: M2 [
2 v5 g$ x# e  X
public class Main {
# a/ t. k0 {* {" E8 t
4 b9 _; [+ b! S- k4 H# g2 E; q8 @. r& |# {, D9 z$ q* I
    public static ArrayList<String> words;1 H3 j/ N4 M2 [' V* c/ L. y3 C' I
' u6 W5 T4 l. [% d8 C7 {8 b
    public static int longestchain(ArrayList<String> words){
0 p3 w3 I' R  D: A) Y        HashSet<String> dict = new HashSet<String>();
8 x% i3 Q; |1 }/ N7 {        HashMap<String, Integer> map = new HashMap<String, Integer>();' w4 [- O) F( S8 V! L
        for(String s:words){
7 g) ^5 c6 p7 m            dict.add(s);
1 ^7 V0 J6 i3 R0 m& \$ x" t1 E8 v        }) q, U& T( D! A' f6 [0 {6 m& z

" w( }- L1 M: c8 O        int longest = 0;# ?: A& ~" b  W8 |. Z! @. y8 g
        for(String s : words){
+ S' f" G+ Q# G- B; _/ S& }            if(s.length() <= longest){
; [  @# O" T3 X                continue;
% {+ P+ H( n3 L/ u% o            }0 A6 z1 j. m5 I# i$ X2 [
            int len = helper(s, dict, map) + 1;1 C7 `- E* r- w) w0 c' d
            map.put(s, len);
9 D3 }  Q0 }2 e: P            longest = Math.max(longest, len);
7 J5 @) @0 Y6 l8 V% r' y7 c% s' ~        }
( J4 T9 y& L6 x7 d2 a        return longest;
% _. x& X  u1 I0 ^- q3 g8 T    }
+ ^, k* X: f" {0 b
7 t' }" l) w/ K& `' c$ M+ {: R0 P; i1 J. _6 q
    public static int  helper(String s, HashSet<String> dict, HashMap<String, Integer> map){( }# M, F0 g* D) A( n( R7 H) \+ f
        int result = 0;2 m4 N( V/ c" i( ]
        for(int i = 0; i < s.length(); i++){% u1 [' B( `; A) U6 z. n" |
            String newStr = s.substring(0, i) + s.substring(i+1);
3 }3 X3 e% h7 w( S            if(dict.contains(newStr)){- V6 [+ l, t5 m; I; G% b) t! w
                if(map.containsKey(newStr)){6 I/ u( E1 T( O
                    result = Math.max(result, map.get(newStr));+ l4 X1 u( b  v7 d
                }else{, J: j2 r9 B- M0 e) z/ b3 ]1 Y
                    result = Math.max(result, helper(newStr, dict, map) + 1);2 z0 h9 ], y  `, Z8 B
                }3 w7 _% U; G6 z0 D. \% c8 e
            }
3 R$ w6 @( W1 w- t1 J8 ?        }" [" P( y) _* R) n. P6 A
        return result;7 ~9 j' [1 Q( d
    }0 A: c$ h5 ]) Z6 \+ ~! U6 @0 W( ~
/ v' T9 x- c! O- e
    public static void main(String[] args) {/ r- Y1 W3 I' |* b* ~
    // write your code here
! B; Z5 n- p* J6 o. k. R1 e# A, _1 c( B' ]/ j/ W8 t/ L
        System.out.println("Longest Chain");
1 D" _% b7 `( T" G  ]* v$ d        load_parameters();
) |8 Q0 ?; A" t0 \) O7 i6 @& R
/ E0 I% N4 v  M: D" h$ d+ [0 ^        System.out.println("words = " );) }, R& Q$ p, j
        for(int i = 0 ; i < words.size(); i++){
1 N* N3 M" }1 R- X4 ^            System.out.print(words.get(i) + ", ");
/ `# u) B5 Y' I! v6 Q" I+ I. }/ Q        }
1 ?% a& R9 t/ P# q7 r1 R# l        System.out.println();
) j. ]. e$ ~( H! r# ]
- v7 ^7 n5 d7 u6 |4 Q        int length = longestchain(words);
, z1 E! `: q) n2 P) W4 u; Z* H        System.out.println("result = " + length);
& Z" ~- f$ H* x5 T: a. f
( i" _5 m  N8 J0 u. d
. |( y  H5 s  g  U; D        System.out.println("Done");1 F; D, Z; t& W6 J5 n2 ?) g
    }4 X0 M! Z5 K9 o) {6 Z% i9 o
}
9 R5 X( I: k( n6 K0 V% H9 R/ X5 {8 K# B. U1 U+ E5 R% u
======================================================
( v  R$ L1 I8 f  s9 P: I( R( Y2 U+ \' d8 K6 A. C3 k- H
* t& j# }  y. D! X
import java.io.*;
8 N+ @5 l, K. m" U- z/ P9 i! p% Simport java.util.*;2 P; k1 R# N, M7 F1 k- B/ J. u! p) V
( F( t. l9 c1 u5 c2 {

" u  F$ O6 H% E0 J7 H# o$ Mpublic class Main {/ c9 a0 l0 n, ~4 s- d1 M
, d# y8 X% q+ t: P
    public static int N;
$ F: n+ R; S, g& j: @    public static List[] adjList;
1 W0 ?2 t, V  B4 h0 i( r& z# O; V9 v. C1 L: p, }
    public static void load_parameters(){* O) B& [# J, l( a3 c* T
        // write your code8 n& n' I( ?$ y+ X2 m, H9 F
        String fileName = "input001.txt";" A+ Q$ X1 g1 J2 w( j& C3 M
        String line = null;
% ~3 j$ c8 R3 r% f3 h        try {
, f: S9 z1 J9 E0 O' _            FileReader fileReader =, v6 V. X2 {: Q9 @6 t
                    new FileReader(fileName);" k# s  o, _& K. p. X6 c
+ K, @- c' h1 P  p3 w+ m1 h
            BufferedReader bufferedReader =0 s7 y! j' }2 N* I! m
                    new BufferedReader(fileReader);
% P7 p  Z1 x6 n; u+ o# j% E" p2 v4 ]5 h5 Y$ v9 b. z# U! G' f
            String numberOfPeople_str = bufferedReader.readLine();
& h9 d% N6 S# ~' h5 ]* @            N = Integer.valueOf(numberOfPeople_str);) Z4 f9 u; Q3 ~! e3 y
            adjList = new List[N];$ l! \1 Y  d1 M& W
: O& a9 ^0 G3 v8 ]$ i0 A
            int row = 0;
! \) z& V3 Z; x- v% [) N( y& _            while((line = bufferedReader.readLine()) != null) {; \( Q4 w* L& {2 N
                System.out.println(line);
/ W$ p# b; N; G  I5 d5 L6 G6 v6 \* v                adjList[row] = new ArrayList<Integer>();
- Y1 w% G; k' M0 d( m                for(int col = 0; col < line.length(); col++){' ]% d* I, o5 @' L
                    if(col != row && line.charAt(col) == 'Y'){- |" r, ]1 T0 Y3 d2 c* {$ Z
                        adjList[row].add(col);1 e2 c4 P$ t8 J! X# W  J
                    }
) Y/ _5 N4 ?+ ^                }2 Q8 r" O1 l# D# _
                row++;
7 v6 W1 Y% H5 C( x8 i            }! Y9 f4 `6 o( a

0 _' A& t. j6 E% Q# }            bufferedReader.close();
" t# u- N$ _2 X; e. X            return;- F$ `% W: e1 D
        }0 v- r" b. _. [- S) U& C
        catch(FileNotFoundException ex) {7 N9 N4 L& A& q, ]
            System.out.println(( {& g4 e8 X& h7 V
                    "Unable to open file '" +
4 u. Z1 D. O0 c+ W5 D: j                            fileName + "'");1 p& v& T, r+ U/ h
        }
; E0 y# T6 b) Z+ J        catch(IOException ex) {
* }% R/ F3 A& S# X$ l; J$ }            System.out.println(
1 ?; [- C9 W3 I* o                    "Error reading file '"$ c  |6 T; R% o! Y1 D. [
                            + fileName + "'");
7 n! `' O& J& r9 h, ^9 U& U$ Q( w        }
# P1 }. `( h- ~. }/ m; K
2 k' `* B: p& N# Z& R: z$ V        return;
1 u7 H& h9 p, z# d1 ?. e    }
5 ]' S2 F1 V* T2 V$ k, a& L' c( H! V' l- n0 h, m. K5 ?- w- n2 ]: e/ @" A

/ v4 d1 Z- {1 ]* }5 }# A) j4 G/ T4 {$ l, Z: X; F3 ^5 T- y
    public static int countComponents(int n, List[] adjList) {
! p' _1 M7 P# |
7 V" P, C0 S+ H+ E        boolean[] visited = new boolean[n];//visited nodes
% |# m; z9 Z& ~( R" M: W7 c1 D2 G( _' r% K# c- s6 ~( u8 M+ t" R
        int count = 0;
( G1 _$ a. Q) y& o, |7 C- v: W        for(int i = 0; i < n; i++){
  @, N% F- m* P* Y1 z* S$ P            if(visited【i】 == false){
4 V" l% M) Z3 ]5 [# v+ B                count++;
2 N6 l! |& [+ |9 ^                countCCHelper(i, adjList, visited);
0 }6 ~% l) a' N6 {* ~% D/ }            }8 z1 p. P  g2 e2 ^) I; c- C) R! G
        }, G+ K5 u1 F0 f5 n2 ^
        return count;
: N& }$ o9 O# L$ r- f: d+ h/ w    }
; e3 j, E+ {0 E8 `! F  t% R2 C7 b& T  o  v; U; I. a: {; q
    public static void countCCHelper(int curr, List[] adjList, boolean[] visited){
+ s+ M$ s+ b( e6 t) I& V        if(visited[curr] == true){
  p; {, [: j* U  e2 G6 V; ^; u5 }" \            return;  e. C: V1 x  a6 [. B
        }
, Z2 a, P' q; N0 U( \) h6 C9 ~( f+ ~% J- M! T, D
        Queue<Integer> Q = new LinkedList<Integer>();2 x# S/ Y7 H+ l8 p3 W/ `4 Z. ?: X
        Q.offer(curr);
+ [/ @  d2 f9 n% m+ u1 G) u# f( k- r3 Q1 `7 s  x: ~
        while(Q.isEmpty() == false){1 F+ L+ o% U% S
            int node = Q.poll();
+ W% h6 s0 {4 q8 W, {7 U            visited[node] = true;; i1 P# c% V9 a. a& P  k% Z8 Y
            List<Integer> neighbor_list = adjList[node];
' i0 g" W6 |) b! g            for(int neigh : neighbor_list){" N. z. `/ P# w3 a' z
                if(visited[neigh] == false){
7 |" [* D1 H4 r- O5 C                    Q.offer(neigh);
0 k8 _- m! y" P9 s4 N: d% j9 k$ @% T                }4 b9 X7 ?' E: O) P2 P
            }
* d. L+ ?1 z9 C; X8 _        }
7 T" O, M4 }. V0 i8 c        return;( C+ S) M4 ^3 y8 m7 n
    }
' Z  u0 r7 o3 Y+ n. ~$ w5 H4 B- _/ ~( h3 T
    public static void main(String[] args) {/ z5 {0 ]# _3 L0 H/ A
    // write your code here
) p# m& F* f+ v
( r' k, k- p, |0 N2 w        System.out.println("Friend Cycles");5 C4 z9 S4 _" Z& w; [: |
        load_parameters();+ J' I) v# ]/ }1 a0 C7 R4 S) X5 |6 U
* p! m5 |4 ~. m
        System.out.println("matrix");
" p! G2 v( l* m2 j" F9 f0 L' X        for(int i = 0; i < adjList.length; i++){
6 n- c0 X  W) L            System.out.print(i + ": ");' a# L: q7 b+ S
            for(int j = 0; j < adjList【i】.size(); j++) {
7 {3 ]' L# p! u2 s6 i7 w& R                System.out.print(adjList【i】.get(j));$ d; n9 D- m3 s, h9 I# M
                System.out.print(", ");
3 J: W' f. W& t: _( Y            }% R' [; o' `1 _$ J* B6 I
            System.out.println();  L1 Z" }9 U: s  G
        }
* L! V9 {+ Q# e- C4 q( R+ U9 a5 s/ M8 r

# E) J4 F  e5 K, F        int num = countComponents(N, adjList);
) u3 y  m; l2 R, F' ^" m        System.out.println("num cycles = " + num);6 X, U# q0 q6 V" f
# Y6 i1 o4 u  G  ^% K0 [  s' [7 D
: \( v& U$ }3 |$ }3 m2 j
        System.out.println("Done");! k" u- \7 s8 P( b/ w
    }5 |- V; T* w  ^; G0 \+ t
}
$ P, X' J: P3 A2 d$ e; F! \5 ]) J4 S6 f" y3 I4 M) o
2 \# E0 X) P7 @, E4 |* J
- F- `* }" C% N  Y2 S
" K5 E$ m1 D( {* R' C! U

" y! Q/ H* B8 Q8 b
! x/ b4 K7 j/ \2 q1 H0 V

评分

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

查看全部评分

0

主题

0

精华

0

积分

新米人

Rank: 1

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

781

主题

575

精华

5670

积分

顶级版主

Rank: 9Rank: 9Rank: 9

积分
5670

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

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

本版积分规则

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