找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

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

[Facebook] 10月20日FB电面

[复制链接]

8

主题

5

精华

357

积分

高级会员

Rank: 3Rank: 3

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

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

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

x
10月20日FB电面
8 @5 f) I: K3 N8 s) u9 a, `$ g7 p+ V4 x- W
1. LC, H-index, 不过换了种问法 给一个数去, 里面的数都是[0..n] 让你找出最大的一个值max, 在数组里面存在max 个>=max的数,
7 `7 v7 ^. _5 U8 s- u3 j: S想了半天发现是H-index
/ O$ y/ T/ {, a% r
5 _2 S# w8 f7 f$ j' a[ans:]
" H4 a0 c4 A' ~+ R" W1 Kway 1: sort the array, left tranverse, find the first arr【i】>=len-i; / E  j, Y: Y6 \. L5 [
public class Solution {/ v' z7 ~3 S4 ^2 ?$ Q! ]
    public int hIndex(int[] citations) {
$ w' F4 R/ H2 X9 o( p' T        if(citations==null || citations.length==0) return 0; 8 u1 x5 j$ N+ f- Q6 o; C
        Arrays.sort(citations);# k# r/ }% `( {( l2 {9 |( W
        int len=citations.length;
4 L+ L+ I, D' P& E2 X9 ^+ _! W
9 X1 P) Q$ n  a  K; V6 f% p/ k        for(int i=0; i<len; i++){% ]* [3 M# T3 ?( E7 M
            if(citations【i】>=len-i) return len-i;
5 h# }/ ^3 p3 K2 u9 k5 N        }6 \- p. a; V4 e+ m8 ^8 |( }

6 ~: q! N+ A- Q: G/ V& T. l        return 0;
4 T/ F$ W: c8 M    }5 @& I7 G7 j) V% V' G* B+ N
}
( \2 k$ e# C/ d& z# y  G! }way 2: sort the array, use binary search to find the arr【i】>=len-i;
- |0 k) p1 J$ _. r; ?; s! r3 Zpublic class Solution {7 j( |- y; z6 Z0 P. X7 N9 [* |
    public int hIndex(int[] citations) {) o8 U4 D* s. r
        if(citations==null || citations.length==0) return 0; ; S2 V/ b. L8 S. S  f0 i
        int len=citations.length;
4 x9 o$ e( Y) r2 T' V( l2 [
# p! u, m6 I' j4 h0 t        int begin=0, end=len-1;
, x0 Q8 C) j3 M. Q1 d7 }% Z6 O) _7 f        while(begin<=end){  o9 g3 D; P+ j  ?
            int mid=begin+(end-begin)/2;# M/ g5 V! ]& _1 z3 B
            if(citations[mid]<len-mid) begin=mid+1;
( T. Y+ @4 J: _7 h8 `% }            else end=mid-1; $ r5 G' p9 r3 g7 C) R$ \+ Z- [# S
        }
- `, X& X: C. g; ?$ }        // if(begin==len) return 0; % t, }7 F6 b8 C) J
        return len-begin;3 W( s, i; C' V. w
    }" a- Q7 Z2 ^6 h$ e2 Q' j
}; a2 U4 g# v7 W6 I
way 3: bucket sort idea,
! t& r& }; y6 v0 H- ^public class Solution {
  q; D/ g( u5 X    public int hIndex(int[] citations) {
9 u5 L* ?' q* W5 ?/ V  Q$ K+ k6 D        if(citations==null || citations.length==0) return 0; 3 z( d* n7 A5 A# E/ v1 O) A
        int len=citations.length;
" h' b8 f. b* y3 _) m( H9 q9 t9 X+ @; O" E! v
        int[] arr=new int[len+1];+ h0 {+ ?# Q) i* N8 s
        for(int i=0; i<len; i++){, Q8 s4 q& p& o' b2 p
            if(citations【i】>=len) arr[len]++;
( I; z' z& u( o* y6 f( s( c) c7 [            else arr[citations【i】]++;
. V% w0 v: G7 z9 E        }
. j  i9 w# u/ [/ o
' a! ^4 i3 x# S. }2 Z% d: Z        for(int i=len; i>=0; i--){) E, ~( Z0 f7 g6 F$ v1 U0 h
            if(arr【i】>=i) return i;
9 F0 m1 N2 W8 Y            if(i>0) arr[i-1]+=arr【i】;
7 k. ~2 W; J, u  r        }( [' r5 B  k8 g: c
        return 0;
( V- \  n$ o. V* m. w4 h) }; R    }* R. G# v+ U) H: p* p9 K
}
9 ]0 v: ]8 l8 {* V: D( A9 i写了第一种方法, 然后描述了第二种和第三种
; L* K5 s: |+ T. k. T& h; g9 M3 a# ?" o
名字查出来是波兰人, 可是确是印度口音, 小哥说只准备了1个题,所以就来了第二个
$ l! }2 ?7 \& {7 z) z1. LC Reverse LinkedList, require inplace
" O) ?9 a9 f) x2 j" x# T[ans:]
* l1 R) n+ H2 z* uway 1: recursive
- C; C( f& Y! Z' f- jway 2: iterative
6 r: K: J# _* o7 a& a) N& q% Q写了iterative 的方法, 结果小哥感觉意犹未尽, 就又来了个follow up" E8 H: w) A6 a4 F: b: ^# n
1.1 Follow up9 l2 G: F' j4 v+ y+ I" {3 f& w
how to do it without change pointer, 有幸前两天在某海外论坛 看到有google电面问这个, 就大概描述了下, 用recursive 方法带2个指针, : k& |: K/ w& J# [9 z: X
没让写code, 回来自己写了个, 也过了LC OJ 了。 8 C, n; v: E$ z& C
public class Solution {! o& q) m- h1 C2 t9 Y$ y
    ListNode left=null; 7 k2 F8 C1 D2 O. U7 f. X& Z
    boolean meet=false;
6 J7 ^; {+ u1 M6 D) E& F/ `
* B9 [3 `# `' {! o9 @4 z% D; D    public ListNode reverseList(ListNode head) {4 M1 y* {# k5 {* B/ {7 h; n" q
        if(head==null || head.next==null) return head;
1 O5 s6 b0 K* |) f        left=head; % v7 J! d4 p1 G" o* o; d
        meet=false; " Q) W/ I" {# q6 W$ K& r7 E; ]: H
        helper(head);
7 R8 V/ Z, W; r' B9 [        return head;
- g- |" e' {* f) p3 y    }
3 C+ W: T( _1 \! K! H) o* t5 H2 i0 P3 t. J7 X8 d* w7 a7 d, a+ M
    public ListNode helper(ListNode head){% H5 R5 r5 Q& a5 L) t/ c: M
        if(head.next==null) return head;
0 O3 t$ D! S8 z  l) T
5 x6 l  ?* G9 B        ListNode right=helper(head.next);
# P8 ?$ {) o& c, l5 l        if(!meet){- c; ]9 t: d3 `: B) w4 W( G
            int tmp=left.val; $ P; i. o' s0 q7 \" |
            left.val=right.val;
! v, r1 V  r, l* p/ |" t  ?            right.val=tmp; 9 w8 [8 c# N1 q* V5 o+ n3 ]. g% M9 w
            if(left==right || left.next==right) meet=true;
; L: H) I7 N7 o! z, Y  i. f            left=left.next;0 u( W  t) L; L& o1 a% t9 G8 t
        }  w, x+ M1 c; o! o5 C
        return head;   c8 V6 A; d) E% N& F0 f
    }$ J" `' o" X% Q  U$ H3 X" q
}
) W! f* G2 t, ]
: u9 S7 L, P9 g8 F; o* F5 X6 f攒人品, 发详细面经, 希望下面的onsites 能给个offer. 7 H. M+ }0 [, D
, l; f2 N; b# u7 b8 A% [

评分

参与人数 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吗?
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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