找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 9546|回复: 6
收起左侧

[精选面经题目] 面经上一个题及解法

[复制链接]
发表于 2-14-2016 08:11 AM | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 Sophia 于 2-14-2016 02:37 PM 编辑
/ \* u. u7 m" R* y; s" v3 x# z: S/ J$ S
刚看了个题 貌似是Barclays的面试——虽然没听过这个公司。。。。2 \/ S: Z9 r9 B5 i$ n: q6 C

  \# ~6 M$ E6 \& T  y+ g: A
  m. w! d- H" c( p- |& c
Integer V lies strictly between integers U and W if U < V < W or if U > V > W. ! e( N4 a+ l) h  S/ M) {- \

2 Y+ u7 ?5 w: U" D! K

$ K) s8 p* _; r( t5 C; M' F, |A non-empty zero-indexed array A consisting of N integers is given. A pair of indices (P, Q), where 0 = P < Q < N, is said to have adjacent values if no value in the array lies strictly between values A[P] and A[Q], and in addition A[P] A[Q].
) f' f, H' m) r% {- U3 @  ?& z/ C! m! d% `/ G
4 E% w! a+ o1 X. Z. i/ l) B
For example, in array A such that: % q6 @/ T) l& p2 D9 {% s
A[0] = 0
4 y; D: {* s. s% r/ bA[1] = 3
+ h1 n. A4 _0 jA[2] = 3 9 `: i4 s  P* f' B! h
A[3] = 7 - ?: @. I& Z2 E3 m1 `) j8 L, X; v
A[4] = 5 , C; f$ Z) W7 B9 S( l
A[5] = 3
5 a5 _' i8 M  @; pA[6] = 11   p: O8 A- k% R% d: M, K7 \% J( p0 A
A[7] = 1 # @, R% E( \$ o1 m2 ?- D( o. R
the following pairs of indices have adjacent values:
3 w6 y+ C9 j3 ~
2 \* X! G- r) y5 v" i& {
1 e; `4 W7 h1 }0 N2 w2 f/ f3 v
(0, 7), (1, 4), (1, 7),
0 ~6 |6 f' r# U8 N/ p- T) P(2, 4), (2, 7), (3, 4), ( r' B# O, N5 }0 y# s
(3, 6), (4, 5), (5, 7). 0 l. ]$ K) ~, U: e
For example, indices 4 and 5 have adjacent values because the values A[4] = 5 and A[5] = 3 are different, and there is no value in array A that lies strictly between them - the only such value could be the number 4, which is not present in the array.
2 U+ t- q# W9 e, Q  B
% j' o0 `& }1 H! B! W
# N  X5 \" j+ d6 z, r
Given two indices P and Q, their distance is defined as abs(P-Q), where abs(X) = X for X >= 0, and abs(X) = -X for X < 0. For example, the distance between indices 4 and 5 is 1 because abs(4 - 5) = (5 - 4) = 1.
3 h4 |7 J/ }+ W& n# X% i8 X
/ U: w  X  g2 g& S; {8 |+ L

8 @$ G( d2 y0 Z" J, X, jWrite a function:
  O$ ?% o- ~- u; H9 f; _; q# o5 q# U  R0 ?4 x9 I% p

) s  F5 D' `, @; }$ dint solution(int A[], int N);
0 D( w9 N- x. ^' v
' i- b* Q9 D% {1 y' i
) y, X' E" l5 P" p& ]* E
that, given a non-empty zero-indexed array A consisting of N integers, returns the maximum distance between indices of this array that have adjacent values. The function should return -1 if no adjacent indices exist. 7 O; R, i4 N/ `9 D% z

# J: w- Z. h' L) ^

- n# }6 c$ [& i  e" SFor example, given array A such that:
7 S! `, x7 ]5 t" h# L9 }& H+ J& J, V
0 ]. A, I0 k. H2 ?+ j4 D

" [  ^  K' A4 u7 rA[0] = 1 0 i, M1 R, ?) ?/ Z% S& f5 f  M
A[1] = 4
" l) U# ^. O+ s/ t0 ]: T. H$ DA[2] = 7 ) \9 a9 v+ _6 G
A[3] = 3
% j, Q) p, I! CA[4] = 3
: M4 y$ Z- l" ~4 {. Z+ k; k9 WA[5] = 5 3 i6 F4 }- a, ^, E3 w! f
the function should return 4 because: 5 {% Z" Q1 n2 w2 Z3 k: L# W1 l
' X) Z# Q0 W2 m8 ~# l4 h
+ Q  B6 V' m$ g$ m
indices 0 and 4 are adjacent because A[0] < A[4] and the array does not contain any value that lies strictly between A[0] = 1 and A[4] = 3;   z& K0 t. s- w. C/ V
the distance between these indices is abs(0 - 4) = 4; # D- t, F" q: I" N2 d3 T
no other pair of adjacent indices that has a larger distance exists.
* [- }7 b/ q. k0 C3 J  mAssume that: 0 [& o/ z# j  D- |0 o5 o5 J1 |% K: S9 X

9 g4 g; K9 M6 b6 ~  P) ]" F6 K2 F/ F
9 P( K+ j0 s3 a; b' m0 n# I
N is an integer within the range [1..40,000]; : x3 C) K) }  q7 U: y/ F3 I0 o& t
each element of array A is an integer within the range [-2,147,483,648..2,147,483,647]. - ^; a# G! g# k3 I6 T9 h9 n! P
Complexity:
: {8 \9 N, {! }' e4 A
) O& m& G1 P! u$ c, U

# N4 o* K0 l3 c8 }+ t# ]6 X! yexpected worst-case time complexity is O(N*log(N)); ; `8 @- A3 J' }/ v4 |. f% O# o) U- D
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments). # I7 S1 O6 V+ r" m* @+ Q0 H
Elements of input arrays can be modified.
% t% S0 o+ c4 d4 V4 @  _4 p6 P# b( x, [: E& v$ N% k

+ F. Q. j, C) U. t* h$ R7 N6 x" |! Q这个题的风格还是很不错的,有输入,输出,复杂度要求,数据范围……# V8 [  }; a- F* h1 b8 I
题目也不难,如果把数重新排好顺序,那么选择的区间一定是数值上相邻的两个数(中间不能有别的数)。注意定义是整个数组没有它们之间的数,而不是P,Q下标之间……开始我把问题想难了,后来发现是简单题。 可以stable sort,也可以直接用index做sort,然后像去重那样选择每个数第一次和最后一次出现的位置,当然还可以用map记录每个数第一次和最后一次出现的位置,然后按key递增遍历map,其实就是算数值上相邻的两个数的下标差值的最大值而已。我的函数是vector的和它给的不同。
: R, S$ t; g1 S* G- C: S% \3 J4 x; m/ H/ B( `: }

; s; C  f5 L; `) ^
  1. vector<int> b;5 g4 l- a/ s2 D& R( Z
  2. bool cmp(const int &x,const int &y) {
    6 N2 X5 \5 `& H. \6 C$ F
  3.         return b[x] < b[y];
    4 Y2 F0 a. j  p& |& r
  4. }7 y( k' u* }8 d" Z( _! |  O. X
  5. 8 _( ?2 X) Z3 z* B
  6. int abs(int x) {2 M% l) Y3 ?2 D) K& U
  7.         return (x >= 0)?x:(-x);
    # O1 D" G/ k' s3 M( s5 r+ \
  8. }
    - C3 r! Z6 V1 r0 \  U
  9. % [6 ?/ ~1 p- x+ W7 s
  10. int cal(vector<int> &a) {( @6 ]2 U. C! \, o; ^5 h
  11. int n = a.size();' H8 w1 E, ^: ]: W7 v5 c% N
  12. vector<int> ind(n);' ?: B0 }! H' l. i$ V, }* U
  13.         b = a;1 R3 J& E- Z: a+ s% B7 O+ ^
  14.         for (int i = 0; i < n; ++i) {, Y/ e, R0 @) M, L# C
  15.                 ind【i】 = i;. a# A; h# a4 h. }% {+ y& |6 ~3 b
  16.         }
    " d0 m, U8 x/ R8 C2 S4 N% u/ }
  17.         
      \3 x) X0 @' x  ~
  18.         sort(ind.begin(), ind.end(), cmp);
    & [- k! @. N. I, X5 \: y- P
  19.         int early, late, answer = -1;9 d: N7 J, w$ F$ `1 f4 H9 s) V  \: {1 S
  20.         bool first = true;
    % q/ X; ^- `+ X4 d' I$ a1 v6 C
  21.         for (int i = 0; i < n; ) {3 y& C& M6 ?4 u7 u; B8 N, o* }1 m
  22.                 int oldEarly = early, oldLate = late;
    4 U$ w& W" l% `) z
  23.                 early = late = ind【i】;
    5 o' ?4 W5 D0 x! e: E
  24.                 for (++i; (i < n) && (a[ind【i】] == a[ind[i - 1]]); ++i) {  e$ c3 m. A: T! Y+ Y3 n
  25.                         early = min(early, ind【i】);
    + u  Q, ^* B7 V  O
  26.                         late = max(late, ind【i】);
    ! k$ N1 e6 c9 t" f2 ^) w
  27.                 }
    * `% r: K2 i/ Y
  28.                 if (first) {, E' d0 c: b6 _' f) H, ]! \
  29.                         first = false;3 R, H% _9 j: N) j# X2 k2 T
  30.                 }$ g* h4 H) Q: m3 O
  31.                 else {
    4 s: T6 Y* M9 M  o$ Q6 |4 ^
  32.                         answer = max(answer, abs(early - oldEarly));
    % w. h! L# b  Q5 I
  33.                         answer = max(answer, abs(early - oldLate));. j) Q- v0 J/ |# }0 j0 F
  34.                         answer = max(answer, abs(late - oldEarly));
    7 r" o* p8 L3 `5 r7 \0 X" y: k
  35.                         answer = max(answer, abs(late- oldLate));% M( u9 i3 G% @1 T" C# l& S
  36.                 }
    - Y5 c1 n' I4 ^) Q) b5 f/ \5 ~
  37.         }
    2 L( ?! w/ w: D9 A. V
  38.         return answer;0 f% P1 D, L) k: F
  39. }
    8 \5 F) {6 [) _% C3 I+ x
复制代码
, L5 r1 M8 L6 Y2 |/ g1 ~. l
7 \, B* M1 `# ?4 ?
% S; w+ L9 C& G  R& R5 M

6 V2 W( m" m4 Z) y0 T6 w" i
  A% o$ M2 r: I  T

: Y4 `) U7 o* o% f! Z
我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!

26

主题

1

精华

207

积分

高级会员

Rank: 3Rank: 3

积分
207
发表于 2-23-2016 04:37 PM | 显示全部楼层
大赞!!!!!!!!!
回复

使用道具 举报

1

主题

0

精华

3

积分

新米人

Rank: 1

积分
3
发表于 4-27-2016 12:54 AM | 显示全部楼层
多谢分享 讲解非常详细
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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