|
亲!马上注册或者登录会查看更多内容!
您需要 登录 才可以下载或查看,没有帐号?立即注册
x
电面: 1. Trapping Rain Water, LC原题,写了DP, 面试者要求用Time O(n), Space O(1), 就是双指针
& a* @. i) m9 _; J6 HOnsite: 6 ?+ _4 G& f& J& ^, q5 n
第一轮 : , Y$ ?/ p0 a6 j/ g5 R$ p1 p0 }
1. LC新加的Word Pattern2
4 p0 O6 k' N# j2 P2. 给一个由 0, 1组成array: ex 0 0 1 0 1 1 0 1, 可以在一个范围内将0翻转为1,1翻转为0,其结果为,array里得到最多的1; B0 x/ U$ ]! o9 d; d3 Q
9 q. E6 Y, `2 Z3 r' M
, O5 n0 l; X/ e5 h0 s6 _第二轮: ' r& j$ I% c J3 E" a; J
1. LC Generate Parentheses, 不用的是要加缩进,例如 n = 3
6 x8 |# o6 R- g/ G/ ]0 T [. k输出:
: o/ [0 G# T2 T" Y% I{ { { {
1 a/ G% _! {( f} { { }) R5 V' _5 S8 S7 `9 m
{ } { {( X6 B: A. B* p Y; M r0 M
} } } {
1 F5 z. U% {1 V1 }& N{ { } }
; Q; M; f# H% ~} } } }
; p2 J' {0 P3 p: u& J, A不仅要会用递归,也要写For 循环的
# e/ [. K# q* c# O3 Z: q3 k2. LC 的word search, 但可以往八个方向进行,会问一些代码细节
; x3 D2 V: ]: x& Q4 U w9 `) h7 R6 a' Z6 W# F+ s
第三轮:
w/ Y6 ?: d- }1. 分数加法, 输入为若干字符串, 求和, 例如: "1 / 3" "1 / 2" 输出 "5 / 6", 又问了一个float的数如何转换为分数就是 0.25 转换为 "1 / 4"
- k( F: s$ W; U! k( b3 e2. 实现一个cache, 储存int值,要求add, remove, contains, removeAll 都为O(1)% L, Y1 R9 |2 [& R1 k/ J
注意这题不是LC的LRU cache, 大体做法为:5 f% c- Q7 E$ c Y
public class cache {5 C0 G5 u& b& V% \
private int seed;
; k2 I3 x6 I9 a+ ~ HashMap<Integer, Integer> map;0 v6 \+ m+ c. i
cache () {7 H) ^1 B. w& n Y* U% `
seed = 0; map = new HashMap<>();& ]' J5 D' Q) ~, ?0 ?
}& x! i: a! C6 b' E0 H5 E1 r
public void add(int val){
" B: P7 `* ^0 M% d4 H h c if (!contains(val)) {% {/ E& w! {! Z0 [7 C
map.put(val, seed);" c5 G2 k F2 j/ w/ Z7 Y+ v% K
}7 B( [" o0 A5 g3 U
}
* j7 V2 T( x! G0 N9 |# T" ?8 e- r
public boolean contains(int val){
8 u1 o+ S( O" N' g! q return map.get(val) == seed;
! k8 t1 s' f4 p. n) x. V }$ g2 e* S+ f' `6 t9 R4 }: o) t! z, R
# w" V/ ]( X) l' d9 c3 _3 X
public void remove(int val){
6 K; X) y: S! O if (contains(val)) {' D! A( g% d/ M
map.remove(val);
7 K% M; [1 m# p }* `. d d5 S% p$ S* D% r
}6 |; B' i! j% q* A& A9 |* x
2 `0 Y, U' D6 s9 _ d1 H
public void removeAll(int val){! p" Y2 a0 T, w5 s" ~; L
seed++;
) s) C% L& r4 R/ J5 R6 w+ K2 r }& c6 a. e$ }, a
}
" N! f* w" e6 m第四轮: 来了个大佬纯聊天 3 r9 B% M5 T7 z/ _, M4 t* W7 M
& m4 _/ _ C" v; |+ s
* f2 ]" P/ }( u% a
. q/ \ v/ G! L# D0 K4 v( v0 N
: ]3 n m# z$ a' U& M3 ^4 `2 K7 k) [8 M! d
补充内容 (10-26-2015 01:37 AM):
1 y7 J* [ v2 `# U电面:白人
5 E3 `# S( W7 r/ B6 [, AOnsite: 前三都是烙印 最后是巴基斯坦 |
评分
-
查看全部评分
|