找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 4352|回复: 9
收起左侧

[Facebook] 10月20日FB电面

[复制链接]

8

主题

5

精华

357

积分

高级会员

Rank: 3Rank: 3

积分
357
发表于 10-21-2015 01:47 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
10月20日FB电面% X# b- C' ^' i8 J$ k5 f
! `3 b5 l1 ~! ~" f- c# s2 r9 P  {
1. LC, H-index, 不过换了种问法 给一个数去, 里面的数都是[0..n] 让你找出最大的一个值max, 在数组里面存在max 个>=max的数,
% R; u" e2 A/ h& g, G想了半天发现是H-index5 ^& f9 c! W5 M+ D' h& H0 C+ j  m
$ |: \3 e; O$ |# w
[ans:]0 s! a( U+ k, L: H, e/ B, C. W
way 1: sort the array, left tranverse, find the first arr【i】>=len-i; . \: C9 r7 X9 g# @
public class Solution {# _+ A$ w% h: s- T9 W$ a
    public int hIndex(int[] citations) {+ \) }! s& o6 C; j  Q
        if(citations==null || citations.length==0) return 0;
" a# z# y9 c& }1 P        Arrays.sort(citations);. k' T! @# }; @
        int len=citations.length;
% W+ Z. T( D4 ^2 L/ g& C, L" E
& [/ f1 q& E4 f4 R# Y        for(int i=0; i<len; i++){
( G) @- `5 v7 I/ Y( h            if(citations【i】>=len-i) return len-i;
3 g, ^# S7 n' h' W        }7 e% @  b$ |, W% I  S

: W$ `9 w" [: q/ }( o7 [        return 0; 9 M! |8 ^8 v! z- o1 b/ r
    }
2 b8 Q9 `8 Q: P$ \}
  s- D3 ?1 e# z0 Dway 2: sort the array, use binary search to find the arr【i】>=len-i;! M1 B9 g# b2 u$ f4 {
public class Solution {
0 `  h2 J6 n( @: P    public int hIndex(int[] citations) {
  D) t! ]* `3 V        if(citations==null || citations.length==0) return 0; ! M. |' W1 N" s4 E3 \& A# y; M
        int len=citations.length;
0 L" y# j" @, l- O6 v- Q3 L0 |/ x
        int begin=0, end=len-1; $ w" j% p% S, K% C! |
        while(begin<=end){5 V- Q, Y3 ^8 h: P5 S
            int mid=begin+(end-begin)/2;2 W$ O7 [3 p1 @# T+ y! A; M$ t4 K, Y
            if(citations[mid]<len-mid) begin=mid+1;
+ S$ F8 Y! W8 l. X! o            else end=mid-1; : g) P; C& n1 [' e2 `+ x# G
        }
) j' u. ]( G! C. J+ ^        // if(begin==len) return 0;
- M5 d, {8 c  L        return len-begin;$ a  b% _) ~+ e
    }- G: Q6 {" u: |  K
}
& x6 r5 O) c+ Z: Lway 3: bucket sort idea,
* T5 z/ n( z& m$ l9 ~public class Solution {; S* Y+ |8 U1 I+ @5 I! F; h) E) \
    public int hIndex(int[] citations) {: L9 s: M- g, j0 ~" y3 |
        if(citations==null || citations.length==0) return 0;
+ k3 m( |! i, z1 b6 o        int len=citations.length;% k! r/ [  u7 \2 P
4 `' `: W/ K/ z+ W: {
        int[] arr=new int[len+1];" o8 k- ]- l7 S8 u; Z, v9 }  ]! ?
        for(int i=0; i<len; i++){" A# Q# ?3 a3 f% a! W  m4 C
            if(citations【i】>=len) arr[len]++;
7 I# H9 Y- B. b! [4 c            else arr[citations【i】]++;+ Q# v3 C5 h* ^+ V7 Q
        }
4 y/ Q; g5 Y5 c# E: Z) a/ Y' k# j* D3 z
        for(int i=len; i>=0; i--){3 J0 n: j) j" q: y; l1 [0 \
            if(arr【i】>=i) return i;
- d, E: g: Z' w: N0 F            if(i>0) arr[i-1]+=arr【i】;/ ?1 p7 g1 B7 F. |
        }0 F8 R3 e$ D5 M' P' S3 C8 p5 I
        return 0; ( d: L: o# G/ |# w# ]& B
    }
: ?% Z' z: `. v' F& [}
& k6 R5 S0 Q5 y# F0 f写了第一种方法, 然后描述了第二种和第三种
! K) W5 B0 @5 j! G6 p
- \& h' Q- y3 l7 \$ K名字查出来是波兰人, 可是确是印度口音, 小哥说只准备了1个题,所以就来了第二个# \+ c& x4 x; P7 g  @: }2 ]
1. LC Reverse LinkedList, require inplace
1 Q* n. y7 W; K- g- e) c9 D[ans:]
7 Y- d* p( C  E7 r% q5 r; away 1: recursive/ e$ |. l) H6 N' l1 S
way 2: iterative( n% ^3 O' Q8 K; E
写了iterative 的方法, 结果小哥感觉意犹未尽, 就又来了个follow up
) q' z& [8 b- ]) H1.1 Follow up7 [( @& ]' e# E2 h
how to do it without change pointer, 有幸前两天在某海外论坛 看到有google电面问这个, 就大概描述了下, 用recursive 方法带2个指针, 0 n% Y8 X- `. B
没让写code, 回来自己写了个, 也过了LC OJ 了。
, m. m0 E- K3 |public class Solution {* ?0 Q0 [. C7 c. D! c
    ListNode left=null;
$ q6 \" i3 X! c5 a4 {# q    boolean meet=false; 5 ?# w, {3 f8 _9 U# s. |
* \. i) T7 @! Z$ J4 U, h8 `/ _
    public ListNode reverseList(ListNode head) {
1 C6 g$ b, |9 L# Y& Y        if(head==null || head.next==null) return head;3 |' u+ [0 d' w2 {- e
        left=head; ! D5 ]  w  j$ C3 `3 E
        meet=false;
+ _$ K' p( X# M* t5 q' b! }* S( \        helper(head);
( a% f& z0 s  M0 p* ]8 p        return head; & U6 E0 U% @- s  A' F
    }
  p2 b2 s. D) w0 f5 _3 T4 ~6 K1 O% Z1 H7 I% d2 B4 |8 X
    public ListNode helper(ListNode head){
+ C6 V7 I: H6 ~" n        if(head.next==null) return head;
  `# S. I$ E- P6 W# [( J9 r2 s+ ~. q/ {4 M% _
        ListNode right=helper(head.next);4 o7 Z5 H4 X/ ?) b7 c1 K
        if(!meet){
/ {9 D0 Z& \" o. }" D  v. ?: {1 R            int tmp=left.val; & a2 n) @8 \& R/ ^9 H
            left.val=right.val;
6 L; z  ?+ O% n0 `- m            right.val=tmp; ) I6 X( a; k, ^3 \
            if(left==right || left.next==right) meet=true;
; V1 f# X; B4 N  P$ y5 V            left=left.next;
* K$ I2 L/ g3 s+ e' g' Z6 N        }
, C* f5 d. ^& t8 E. L+ v8 H        return head;
6 m3 ?1 D: _2 K8 j- r3 C! C3 l3 z! `4 a    }: X$ L2 \3 {9 f" k# ~. n4 ]
}% ~1 X+ m6 [4 t7 T  ]
' K1 w# A: r) K  S- c4 r
攒人品, 发详细面经, 希望下面的onsites 能给个offer.
1 A( T4 N7 b: e, C& e- N3 Z4 c: t# s, f8 a5 t& b

评分

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

查看全部评分

5

主题

1

精华

75

积分

资深会员

Rank: 2

积分
75
发表于 10-21-2015 02:46 AM | 显示全部楼层
还自己加了code  太感谢!

12

主题

5

精华

249

积分

高级会员

Rank: 3Rank: 3

积分
249

最佳新人

发表于 10-21-2015 08:21 AM | 显示全部楼层
面完就给了onsite吗?
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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