找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 27119|回复: 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/ o3 V- a% ~) W5 d; k# i
) i$ Z; `1 L  E# T% \0 r; J0 @% U上个月网申的Two Sigma,一周之后HR联系。结果HR放鸽子,我发信去问,又重新约的时间。到了重新约好的时间后,HR过了20分钟才打过来电话。之后就是非常常规的问题。我的背景,Why Two Sigma之类的。跟她交谈的过程中感觉对方很疲劳,有些不耐烦。在谈话结束后收到HackerRank上的OA的连接。
7 N4 f3 k1 b  H' D. F两天后打开OA做题,两道题,3小时。第一道是Friend cycle,第二道是Longest chain length。都是老题了。看到过别人发的面经。自己也在下面先做了做。1小时两道做完,都能通过全部测试。结果3天后收到据信!时间都花了,结果也OK,但却什么都没得到! 真不知道为什么:-(
3 X  I# B1 ?; l/ s
* M( b8 z+ V4 W) ?# s9 n5 r6 S! u+ t& m附上我的solution。大家帮忙看看我的code到底又什么问题。第一段是longest chain的代码,分割线后是friend cycle的代码。; k7 M; A4 T* Z  j! |$ g, F
大家看后多给写积分啊!多谢!多谢!5 U* C' x: n+ W
2 a$ W) ]+ J  n
import java.io.*;5 \% v  `1 y) c+ y. r1 u' H( C
import java.util.*;
( l8 a- v' b, x3 V* z( w  g9 N0 u9 E& ]$ F$ B% c* `2 m
# V4 v/ X- {0 z9 j, ]7 S6 S7 Z; ]
public class Main {
+ e* Y' Q3 L5 t0 l# \- F  v2 B; ~: l
4 A  _- k0 T; Z1 _7 a
    public static ArrayList<String> words;
6 W& c5 b8 K% h+ B/ Y. u
5 @5 i& h  ]- ^' R: D" F    public static int longestchain(ArrayList<String> words){
* v! A: v. \$ S+ _# G7 ^' b        HashSet<String> dict = new HashSet<String>();. b' `" A3 }3 ^2 R4 K$ b2 v
        HashMap<String, Integer> map = new HashMap<String, Integer>();9 ?1 a7 c$ Z! `/ n& l/ c$ P
        for(String s:words){
0 ?# z* I- [; e            dict.add(s);$ Q0 V  {& N: U$ X/ O' ?% `' Z
        }
3 o9 R* L# S: F" s! {2 X, {! j" U4 Q
2 X8 U# `6 ]" j# c; d# I        int longest = 0;8 N/ _/ l; Z& R1 X& U
        for(String s : words){
, w% X" f+ \+ `            if(s.length() <= longest){. N# r0 c9 w$ \+ h  f
                continue;* s) ]5 g, }* \9 H5 b# v5 t
            }# g$ A0 d* Z7 X
            int len = helper(s, dict, map) + 1;
5 E4 A+ T3 o% }% `; e$ a: S            map.put(s, len);
8 ]# M. d) C3 y& ^/ h            longest = Math.max(longest, len);
; \+ E9 F, P  p' g1 U% x        }9 k/ K! k) x7 m/ T+ ~7 o0 O+ T
        return longest;
: h; ~6 t4 T+ y1 `    }* d* I+ o8 u* ^8 d8 r8 G% M! o
7 I+ D) ?! S5 H: Y

; b; z8 z% k6 Q  h9 l    public static int  helper(String s, HashSet<String> dict, HashMap<String, Integer> map){, a2 N; d! ^' p$ L) X" {
        int result = 0;
) C: r* {5 M; j4 ?0 r        for(int i = 0; i < s.length(); i++){
, u* j, Z! z2 \% g            String newStr = s.substring(0, i) + s.substring(i+1);
& M: j8 F+ d7 k. {! Y            if(dict.contains(newStr)){+ o# r" p7 F& `# L9 @0 T; [
                if(map.containsKey(newStr)){, [( ]) K8 S* z% o) j- E9 e5 h; n
                    result = Math.max(result, map.get(newStr));
4 W$ y, J1 o7 @1 Q                }else{
3 H% |" Z" |$ [' \                    result = Math.max(result, helper(newStr, dict, map) + 1);; g5 t1 m2 J( x) Z, \
                }
; E& L! b+ q' U. o: m! y( T+ s            }
' S6 _# [* K5 ^$ g        }
+ d; S; v* |, y  [$ \) D0 V! L        return result;
' C1 S- Z) @  k$ L* U8 ]  x+ @    }
& L! d6 S+ i9 Z3 |8 m
/ H. i$ z+ u! w+ H. z0 l    public static void main(String[] args) {
8 |; F# e2 f( m/ x1 k% c: S    // write your code here$ u- p$ ?; }6 ^8 d

4 k: T! ]2 n! m, j/ y9 X        System.out.println("Longest Chain");
+ f$ o! _( j+ k- X- ]        load_parameters();' B" @# m1 k$ C* x7 K' d
. f) h3 J2 P5 K% B9 z- C8 @
        System.out.println("words = " );0 V; @# n+ y3 v( {
        for(int i = 0 ; i < words.size(); i++){+ r% K' t' v1 K5 e8 |
            System.out.print(words.get(i) + ", ");) a" ?" P/ b" @9 {! j- r
        }! {" G% N! F0 {) x, {9 a1 K
        System.out.println();
' }. \8 G& [8 o! ~7 M4 r2 @) C# _8 b  `! Y+ j+ c! d# f/ b
        int length = longestchain(words);1 e0 N. m' b% q3 }9 ?! r  u
        System.out.println("result = " + length);7 W- F' g0 s$ k2 r: z) W: j( z
, D  ?2 r, V: I7 T& e: t% B5 G) n8 Q

4 E$ F) Y) Z! _5 y0 P3 A0 G' \1 U        System.out.println("Done");# V$ Y* q; o6 x( L6 x) S
    }
# V7 |9 L& w" O  x) w}
9 N4 ]0 {1 X4 F( n* ?" @* C0 H- _8 H! T/ H: I; S
======================================================
+ @$ p* b+ I; B( l. p2 C' u" ?6 C4 a9 F$ }6 p

9 }7 S5 V& b0 O  u  ~" C( r' simport java.io.*;" l( H- x7 l! D8 w' p+ I
import java.util.*;
9 |, d2 ^* [) ~8 Z. K( Z- T6 U1 u
8 [  U0 {4 V6 c$ w! s
7 o* T( f; t) ~( H# K# Bpublic class Main {
8 E: s6 {* n8 u1 @8 {9 B1 |) h5 c, {3 }2 X
    public static int N;
$ P' k& ?* }) a$ x. f4 I* C, E. T    public static List[] adjList;0 |! _; R  s( l; a# j- C

* ~- ~$ |6 f  I- o. I' c; O* x9 O    public static void load_parameters(){; |# X$ A# S# Q3 k! I  z5 t
        // write your code8 Y7 G) U4 b. P3 T9 b6 Y& [, C2 {
        String fileName = "input001.txt";
6 p6 \$ I# T8 g        String line = null;
2 `/ b  y( w! i: G1 k        try {2 D2 n( H8 M3 |# p: O: v9 \+ o' ?! |
            FileReader fileReader =
: X0 P8 [, X$ t2 q7 O' U* n                    new FileReader(fileName);, _% c# K5 e  h

; [& y$ `7 e. F% R* w9 N            BufferedReader bufferedReader =" _, n% X3 u6 n
                    new BufferedReader(fileReader);2 A2 g' @/ \; u' e) e8 d

' V; O  G3 H) p! y            String numberOfPeople_str = bufferedReader.readLine();
# a) _* f! f, d0 ~            N = Integer.valueOf(numberOfPeople_str);
( S  N+ `# B: M( `            adjList = new List[N];* h# o# W3 U' |2 A

7 r, a7 g) S8 W/ ^$ M            int row = 0;- J$ _% Q5 l# v
            while((line = bufferedReader.readLine()) != null) {; W; L; z5 v& b. s; I# L
                System.out.println(line);
( h4 p) J9 T4 }  y5 t0 |5 x                adjList[row] = new ArrayList<Integer>();+ X! o$ n/ f, N
                for(int col = 0; col < line.length(); col++){
9 T( T% a; [/ D, `/ [& Z# }7 f                    if(col != row && line.charAt(col) == 'Y'){
* c1 A8 N% o. Y+ F* x& @. Y                        adjList[row].add(col);9 o% n9 u/ E! v& C( w
                    }1 r! U/ `$ d5 c- J3 {; y
                }
$ C! K" _8 C* W5 E+ n                row++;
; U$ o2 K2 P( [7 a& |( e            }
7 Z4 f5 R. t6 G; S0 Z
; I  P. T* e% I3 M1 u6 m7 [* Z            bufferedReader.close();  }) p9 ^. h9 ^6 K% r
            return;2 N, F# ^" \5 y
        }  \& ^2 b$ Q: q) }) u* X0 j3 c& {
        catch(FileNotFoundException ex) {
+ D, H1 F" R) [# m) O+ }+ p0 b            System.out.println(
% E) s* a9 T5 T: U                    "Unable to open file '" +" i4 s, @% u# p( s5 i1 ~
                            fileName + "'");
2 V2 v4 J5 Z4 M/ p9 n  l* H        }
- X+ ]% s$ z! F4 h, M* N        catch(IOException ex) {7 p3 z1 f+ r2 X5 ]) `7 v& U5 h& h
            System.out.println(
& Z4 Q6 M- H+ O( X5 _5 ~% F; d                    "Error reading file '"
1 |- ~: R4 r3 Z! t0 E9 W7 K, h7 w( X                            + fileName + "'");( N; e' P3 L; S$ s! v
        }$ M  {! N) v4 x8 D
9 W$ d8 v' c; B: v) ^
        return;
. |4 V3 F+ y* }3 G, G% L$ H    }
2 O6 v- D; A0 V# H2 r* b1 q# q. R+ R3 o

) S( B1 C( W) F' k3 q" P+ G" R7 U. |& @# ^: n- C
    public static int countComponents(int n, List[] adjList) {
. `5 h4 S' v$ C, G
% E9 d) H1 V& E, h        boolean[] visited = new boolean[n];//visited nodes: @3 G* ^: a: L1 w2 I

' k% M+ \! b7 A* _        int count = 0;
' R9 [1 D. X% w. y! w        for(int i = 0; i < n; i++){1 I# x& m; I+ Y: L3 v' I
            if(visited【i】 == false){
1 D- F/ O( |- j, P% k                count++;
3 [1 k& j1 I) |! D2 f( C! U8 y0 }                countCCHelper(i, adjList, visited);
2 ]- j9 p0 i5 g" O4 C8 f7 U            }
* W& p) x! S7 u: U, \        }
$ ]9 ^: G  l9 Z' T8 w9 f  v- K3 M        return count;
% ~7 u# {6 S. ~& ?1 t    }
& `1 Z6 }0 v; L1 {, ~
% j0 z6 v' G; j5 t4 f    public static void countCCHelper(int curr, List[] adjList, boolean[] visited){
5 \; i( S; P9 o/ B( M        if(visited[curr] == true){
: T; v$ t! a/ G2 r            return;  [0 l& h7 j* b0 Y( f
        }
- {* o1 ~( u) e9 M& `5 Y2 s: ~. L; @' V4 `
        Queue<Integer> Q = new LinkedList<Integer>();
9 d' j9 m( K  f        Q.offer(curr);# f$ k- a; C6 v) T7 y+ I

  h" B# e7 U% M4 s, t" J1 W        while(Q.isEmpty() == false){
! u& V. H1 L7 O2 ]+ x            int node = Q.poll();
6 c7 S& u. i' ~) T5 [# b            visited[node] = true;
! Z3 {/ L+ p1 T2 f$ `; }            List<Integer> neighbor_list = adjList[node];
3 {; D& c( W$ L! A2 l0 J  V            for(int neigh : neighbor_list){1 C5 g; u' X! D
                if(visited[neigh] == false){
4 }- M0 T( S6 D- x5 z                    Q.offer(neigh);
: J+ o3 k' a' `7 d& l                }$ ]% x# g  N( O/ k( Q- f0 p; {
            }
  C6 S5 i6 t! k4 h; A% @' }4 M1 d        }- S9 @  d( @% x# B+ A/ S
        return;
( _! g, K/ Z* `7 t    }! D2 x  S  F9 i" P1 o
  N4 K, E2 V7 O, \
    public static void main(String[] args) {( I! E  [: {/ y+ e
    // write your code here5 z& w7 v# B+ H  y
0 P0 J, w$ Z. z) A
        System.out.println("Friend Cycles");; r( q; e7 ^  U0 o
        load_parameters();
+ z* I/ c* V# {! l
4 g- [( W0 U3 q2 y! o# ~        System.out.println("matrix");
! z) ^, S/ v5 g! L: a$ E        for(int i = 0; i < adjList.length; i++){" `+ T/ y1 w0 T' s& p: T
            System.out.print(i + ": ");
9 H" u- m, k3 [& [5 y, d* x1 {. H            for(int j = 0; j < adjList【i】.size(); j++) {/ c% D* Z+ |9 C9 J) f+ O
                System.out.print(adjList【i】.get(j));
1 q4 P6 }3 p2 ?1 _* e4 ]) u0 w                System.out.print(", ");9 Y5 H9 z$ M. n' g2 E! B
            }0 I9 F4 g( G2 {& t& ^2 C
            System.out.println();
) t7 T8 e6 A: u. [6 J9 S        }
  U. M( L' I. u, y) y3 o" R7 n. R$ t: V: B
1 M" L+ Z5 y9 p, W; m, J8 P
        int num = countComponents(N, adjList);: q* m# |' v' X9 M. \2 T
        System.out.println("num cycles = " + num);
7 v* P1 c+ c$ X" T$ q" Y+ e
: I' v9 }: ]# y0 ]) n  q; u! W/ ]5 b4 K2 K# V
        System.out.println("Done");
/ c0 A7 s; C; n' M    }
6 j4 ]3 s5 ^5 e* r- J- z, I8 E}
* c+ l/ @& w* r1 p: p
( L' P6 F# P) _2 }! A( z# P( ]+ m
( L( G$ C( X9 D! z) h. b: {% }  C$ g" o/ A5 d4 |9 o

5 ^+ o/ p" o0 w# w$ B
( [) X  b# y& Z6 \) r
% [' `/ s+ l( x  m

评分

参与人数 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 | 显示全部楼层
感谢您的认真和用心的分享!大米满满送上!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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