|
亲!马上注册或者登录会查看更多内容!
您需要 登录 才可以下载或查看,没有帐号?立即注册
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% [
|
评分
-
查看全部评分
|