找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 15739|回复: 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 编辑
8 @0 F- m4 `4 i5 a9 V' |' G( L9 m7 |- p4 ^/ J' ?* z! @2 z" j, Z- j
上个月网申的Two Sigma,一周之后HR联系。结果HR放鸽子,我发信去问,又重新约的时间。到了重新约好的时间后,HR过了20分钟才打过来电话。之后就是非常常规的问题。我的背景,Why Two Sigma之类的。跟她交谈的过程中感觉对方很疲劳,有些不耐烦。在谈话结束后收到HackerRank上的OA的连接。" G; D3 a8 o* l* S
两天后打开OA做题,两道题,3小时。第一道是Friend cycle,第二道是Longest chain length。都是老题了。看到过别人发的面经。自己也在下面先做了做。1小时两道做完,都能通过全部测试。结果3天后收到据信!时间都花了,结果也OK,但却什么都没得到! 真不知道为什么:-(
* p( @" E1 Z% k! ~! A# H5 T. `, [& b( G, k
附上我的solution。大家帮忙看看我的code到底又什么问题。第一段是longest chain的代码,分割线后是friend cycle的代码。2 x! A& l' F7 |8 P& ]$ J
大家看后多给写积分啊!多谢!多谢!, g3 m1 j3 a/ {2 E

6 O4 P' E' I$ C' fimport java.io.*;$ E1 c  j% Y/ _2 y. E: R
import java.util.*;  _) Z7 `7 N2 f; Q

; }5 f$ ^+ \+ f9 v" ?. m; _" I; e# V
public class Main {
1 |9 D" p" {0 j- ~! R: H1 c1 b6 e4 W$ g0 V
/ [! m- V6 B( K8 y( a8 z
    public static ArrayList<String> words;
" Q' X4 U, v6 ~4 H% x! [6 t9 _5 R8 x1 U$ s
    public static int longestchain(ArrayList<String> words){6 \; Y* X6 O* m! a
        HashSet<String> dict = new HashSet<String>();+ _/ V. C3 G' k: D$ D+ ~* Y# s
        HashMap<String, Integer> map = new HashMap<String, Integer>();+ M- E  O$ ?0 _7 e' L, i2 w2 K
        for(String s:words){0 i) a' ?0 L) j- i
            dict.add(s);% `, h( g- I1 H2 [, ~8 z! ^+ `3 ^# U
        }
6 ?# W1 I# I' t+ K/ T
3 w0 _) [5 ^0 t0 R" e        int longest = 0;1 E0 Z3 Z8 _. b5 O
        for(String s : words){
$ ?( l( ^9 k+ B' ?" D; ]            if(s.length() <= longest){! a- V% q# P& L; K/ ~
                continue;
9 |: d# ?: J; D! ^* W            }
% v* V* @& E- u4 t( r; h            int len = helper(s, dict, map) + 1;4 Q" ^5 m# a! l! X/ _# S, J
            map.put(s, len);
- i# |  [  ^$ D" _            longest = Math.max(longest, len);
$ i) I* W4 ?7 i8 y        }/ }6 m" J5 `5 f$ c3 x
        return longest;
  z# e' _7 D5 @$ O7 m8 w    }
" b- n; G3 {$ ~4 Q; d; R; G9 F+ _8 o6 w; j/ O

9 D5 i  a- O1 n* [7 n    public static int  helper(String s, HashSet<String> dict, HashMap<String, Integer> map){
; Z. D* v; a  }0 @: }8 t& U' C9 [        int result = 0;1 b! y  v- @' U! w/ r, U
        for(int i = 0; i < s.length(); i++){* ^( A( T' ?+ v" i2 t
            String newStr = s.substring(0, i) + s.substring(i+1);* U6 m; L: u' w: \' _7 H' i0 w
            if(dict.contains(newStr)){
6 v/ d9 F4 i* ]/ L* Q                if(map.containsKey(newStr)){" _; Q+ k. I9 [4 B5 c9 R" r
                    result = Math.max(result, map.get(newStr));
* T% Y+ ^: }$ [& x                }else{3 B& I6 }9 ~+ }  [' u
                    result = Math.max(result, helper(newStr, dict, map) + 1);2 M1 N" n5 i) q2 C
                }
- v+ v: y2 N3 Q% d0 i$ \            }
( `. w1 ^/ F3 w: ]" m) f  ^' s        }
" w# ]* |7 G. @        return result;4 g$ c% B5 J2 h1 w0 {  ?
    }( W0 Q, }( |  M0 j+ b

; u+ o, E' D7 ?# i9 H    public static void main(String[] args) {
# V+ m; t8 J: `+ b% y1 e    // write your code here
$ d+ L7 u8 [# U; o! D4 |# a/ O
9 f+ M6 D+ b- w! U4 t  k( I        System.out.println("Longest Chain");
5 {+ P' s/ `7 i" l: p        load_parameters();
6 \$ _' ]5 ?# }4 P3 |% K  O& B0 \* b4 Q0 m) i
        System.out.println("words = " );$ Z4 ?3 c. d! {
        for(int i = 0 ; i < words.size(); i++){8 j4 u: E5 c9 {5 d) I
            System.out.print(words.get(i) + ", ");
7 k2 U1 V7 k7 h; R; m; r        }% t' E( V& u# g2 p2 K. K4 r
        System.out.println();
& h+ J: a# K) [, G/ I& t% B- e
! D0 |' ]6 ^; [: G$ W! N! J6 [        int length = longestchain(words);
, f7 b7 ], j" o: X0 _7 B/ Z, g        System.out.println("result = " + length);$ ~8 T* S2 Q" R: ], G) L
8 s" J2 G+ n; u0 i2 @9 F
2 ?, J: V& r* s5 h  S
        System.out.println("Done");& |1 P0 G: k- ]" _  m8 y$ m- `! t
    }
% x& w$ [4 S' G; T}
6 Y% ?2 [% C# b% t
5 U$ f* ^' i- _" T, t======================================================8 B2 ]& ~+ @/ b$ o) I  U  z0 A
3 U& u" P* j8 P  z; }

5 X9 M7 N8 N) g+ K: M+ _import java.io.*;+ `- @; {! V# U) A
import java.util.*;) z9 U- m6 Z7 j) K2 Z# p

& X+ @& G& K; Z4 `8 [7 r' S( d( }0 f  i9 ?/ L8 ?
public class Main {
$ D( z8 Y. y' C; z' i8 i# U0 f) \; L- o& y/ w3 Y: I- h
    public static int N;: L) {# {1 ?/ [
    public static List[] adjList;
4 C8 f2 I# V. x
$ @# c  P: |. E2 Z+ R( b. `    public static void load_parameters(){  g7 x: E+ H. ^* a: C/ a, ?
        // write your code" G" u0 z0 X% x' {1 ^
        String fileName = "input001.txt";
/ \( t( \0 J2 w/ E; r        String line = null;
3 @( B2 b5 s( }! h0 `        try {
) b4 ^& o# t$ @/ @6 [% q            FileReader fileReader =% G9 P  t6 C) `' @5 G
                    new FileReader(fileName);5 \3 Z6 e' o/ D% }
. s; f% R; x* W- U8 Y, V
            BufferedReader bufferedReader =
- S$ u9 v7 W5 Z                    new BufferedReader(fileReader);
6 c2 o$ I* k7 b; j6 c8 y2 z% L* E- C& h6 N: U0 }
            String numberOfPeople_str = bufferedReader.readLine();- k+ k. z6 L7 u/ H- Z
            N = Integer.valueOf(numberOfPeople_str);7 a8 \! w; J/ K6 M/ e
            adjList = new List[N];1 Z$ d* U. v, S5 @9 O) Z

4 J# u6 w% c% O$ I            int row = 0;' E/ J. u# |6 o- [1 w8 @# o
            while((line = bufferedReader.readLine()) != null) {
# S9 X) p9 ~7 \) P: i7 b/ b                System.out.println(line);8 K1 A' ]) r* \! z) L3 G
                adjList[row] = new ArrayList<Integer>();8 J, b+ r; _3 ~2 ~8 j& M) W" i
                for(int col = 0; col < line.length(); col++){
2 m. b( R  T$ o+ B8 j" i; y3 P                    if(col != row && line.charAt(col) == 'Y'){5 p8 q. \% H: t; S
                        adjList[row].add(col);( L! H$ k# r( q* H, m
                    }
% f" g# W+ Z" d3 B- G# n                }
1 {5 R- X- D8 f1 s, Y                row++;
& k# M9 ~3 n7 Y4 b0 B            }: x1 W7 \- k$ [8 t- U

3 D" N  I* U2 ]7 Y* r; A+ ?            bufferedReader.close();& k+ @- K2 A" w% X. s' o
            return;' \) ~/ G% ]" N  H+ D% \' A/ u
        }
: u& s6 n0 [  k) \5 l2 B6 g        catch(FileNotFoundException ex) {) J. _5 D% a( ?
            System.out.println(
: C, v0 C! d1 F0 _5 u+ Y3 `+ U                    "Unable to open file '" +# z6 {) Z! [. L5 ~
                            fileName + "'");2 v4 o5 E8 I$ W. W9 Z& \
        }
; e2 P; D- @: U" ~        catch(IOException ex) {
$ p5 E8 z' W) T' u            System.out.println(
# p* ^  x. k& I+ b& D" M                    "Error reading file '"
# A- r( F' t' @- b6 u6 t                            + fileName + "'");: O* u3 I1 y4 K% ?* \; A: N
        }
4 _9 r6 R# e' L: G- G6 I0 Z0 E7 G8 i
        return;; V1 @5 \/ H  N/ y) A- i/ G$ [
    }$ O" l7 E# f/ W& Z  i. E& m) |

* ^( k; v  E% Q$ Q' y6 v0 q6 d4 a. Q3 G0 f+ t
7 d4 [% H/ B3 J8 ^; N
    public static int countComponents(int n, List[] adjList) {+ h! y& a+ i1 X; ^' i# _8 v3 z' T* f

  ]8 h8 `0 C$ U  B        boolean[] visited = new boolean[n];//visited nodes# b" M% I& Z% T4 H8 t
7 _# s( r$ B2 g: {& S3 k8 d
        int count = 0;
3 @! `& w5 @2 v5 y1 ]/ `        for(int i = 0; i < n; i++){: o5 W0 Q( Z% F3 d' P8 [
            if(visited【i】 == false){
9 A( {9 M( i* [% m3 \$ ]& j; a' u                count++;" d! }) [7 |$ W2 a% y/ m4 _) K
                countCCHelper(i, adjList, visited);
* T, ?7 ~  @4 E( m/ i5 ^            }
4 N! D) h6 R4 d/ v) O; K        }6 E! U/ A4 y: K4 r, J  U2 p
        return count;
4 b! P! s9 X7 |1 K0 n& n% o- F2 `* H    }
7 _) e% U2 a6 l  b5 n% g5 S- P$ Z: q4 P/ L0 _% |0 J
    public static void countCCHelper(int curr, List[] adjList, boolean[] visited){" m- J1 ^' V8 L* |
        if(visited[curr] == true){
( A& B' _% m! K* O! d9 \            return;# d8 T5 v2 S0 u$ G2 }, {
        }9 U6 S- G4 @  x( r( `
- _0 u( Y' ?- y' R5 v
        Queue<Integer> Q = new LinkedList<Integer>();
0 x% b( L- E% x3 `4 }        Q.offer(curr);$ V% p! Z/ g# a! M7 B

3 A+ R/ z& l. L4 c/ H% X        while(Q.isEmpty() == false){
, m0 B0 n& k' m; y  B4 t9 V            int node = Q.poll();& n3 @- \) s7 v% h0 ]
            visited[node] = true;
3 U; P+ B5 I2 Y: o4 @8 y            List<Integer> neighbor_list = adjList[node];
8 K8 l! b* i4 u) t3 S            for(int neigh : neighbor_list){7 F. |3 h4 q+ w: z/ S* [% ?
                if(visited[neigh] == false){# c) q& J9 W7 W. \
                    Q.offer(neigh);3 y0 r" N8 z/ ^' u) p
                }9 V, y( r/ P" L" n& ~
            }9 k$ T) f* N$ N
        }
) B* Q/ m: j  C; t% ?        return;6 K9 R) X; X" o* U! n
    }
7 T! l, _+ Q' z$ U+ T. f/ O5 j9 \% E; c- c, L% h+ i
    public static void main(String[] args) {5 F2 I$ s, b0 l/ @
    // write your code here2 ]1 u6 W; d. i( X& Q/ x$ L

1 t$ |, {5 u) G# y2 p4 j        System.out.println("Friend Cycles");
% ]5 ~+ C2 N5 X1 r! ]        load_parameters();
; u8 S' d8 O4 r1 v5 I$ |0 t' I4 @
. R% i+ Q' n0 P" y0 x+ s, D) l; N( C$ j        System.out.println("matrix");
" b3 U8 O" V  N  x) Q/ r        for(int i = 0; i < adjList.length; i++){  a" L7 Q5 w% ]' C( R/ |. ?
            System.out.print(i + ": ");
, P# L2 L" v* [, o" v3 L            for(int j = 0; j < adjList【i】.size(); j++) {
+ s( H* n/ x3 Z6 H& y! T5 A                System.out.print(adjList【i】.get(j));
+ _$ ?& ~, k5 _7 J2 _0 r6 O. t                System.out.print(", ");' @* _, b2 @1 e$ R! O
            }4 ~+ v5 t$ B/ b  d0 o$ X
            System.out.println();
% g8 n2 `, i# n" |* n        }
! o! k0 ~" t+ `* Q& s% Z3 p% a, ^* z0 T! K! P

6 A' z4 l4 X: x' v8 o8 H        int num = countComponents(N, adjList);% l7 z# K1 o% R2 _
        System.out.println("num cycles = " + num);
0 h# X% n1 j1 l* ^# g2 o2 U% U
$ [7 }# `* B( _- {; |3 w3 x, `( d
5 k8 `1 r5 f, A" K! M% I        System.out.println("Done");
2 w' a% G3 j" f5 Y4 o$ s2 p    }
$ C' ]" P" l6 c}! S- U' m! H- y5 U7 ^$ b$ k

- K% h( ]  z: d: E! ~, A
( d1 `3 Z! v/ |
, z) R; V: `2 d' g8 P% R- v8 n! D0 m) t. D1 Q1 L

; `" @4 [# T% m% s& e% L
- B6 q7 J) E* U' u& r$ F

评分

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

查看全部评分

0

主题

0

精华

0

积分

新米人

Rank: 1

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

使用道具 举报

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

使用道具 举报

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

本版积分规则

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