找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

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

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

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

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

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

x
本帖最后由 Sophia 于 2-14-2016 02:37 PM 编辑
( J; L) [: x0 V, n) N6 P2 b# z1 r
刚看了个题 貌似是Barclays的面试——虽然没听过这个公司。。。。( D. B: H! Z, |. G; Q8 A0 Z8 p% i
2 J; n& }) V7 y$ B& O* y" Z( w

. A, X( o, E6 `Integer V lies strictly between integers U and W if U < V < W or if U > V > W. 2 c# r+ t% _2 i+ t' `; ?
1 z  I2 t* ^: ^
: f' |4 m) V& C- e' V: t
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].
$ z7 `7 G; T3 ]
7 M/ W: b- J5 Z8 g. _/ r
+ Q) r: m7 ]6 m' c; k
For example, in array A such that:
( p4 E1 l$ q6 s) VA[0] = 0 : g& t. F, t% P8 L2 p  O8 M
A[1] = 3
+ q/ V) U1 L% \8 [! XA[2] = 3
4 O3 Q- `0 @0 M6 n9 q6 WA[3] = 7
( B  N6 C- E2 t) |A[4] = 5 8 N! U/ C" k( z& o, d9 H2 G" p1 `
A[5] = 3
) v& b0 o3 g  W$ u, h1 A* DA[6] = 11 : d: v; }/ R# z6 m
A[7] = 1
+ I5 o) A8 k" _% c, _4 |the following pairs of indices have adjacent values:
; z2 f& `' `/ U# ^) ^, R
' P0 u% y0 Z# V  H+ _- a7 w
: u: I4 W2 f; f3 @( x  o1 s
(0, 7), (1, 4), (1, 7),
$ o% `+ t. l7 M6 u$ M(2, 4), (2, 7), (3, 4), 2 G; Q/ j$ U, a3 S
(3, 6), (4, 5), (5, 7).
5 ?3 G/ X# U2 x/ `# {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. 0 q% U: r- Q) d+ J6 {
2 E4 E6 W5 Z3 s2 P. U# n5 E
) p; N! j4 ]7 b* \
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.
2 M$ C" b9 x$ Z+ X/ `
( i3 n! A& ^/ n! T6 Y: _$ N4 g
" v3 q2 r2 Q6 A
Write a function:
9 o1 y+ r! z7 `, P6 y* A  T( E4 o# M% {2 j

- m; e% h; _9 F0 M+ ~int solution(int A[], int N);
6 n; s" ^7 l: a8 E  ~- Y
# `7 p: k- V. w+ t

; ?9 \$ w6 A# f5 p  A* pthat, 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. + X( w2 v* B- c' q9 K2 D1 |
1 a* D1 w& b$ Y# f7 z# u
' \  v8 p: t7 \9 K0 n6 ~  G* d
For example, given array A such that:
) M+ O9 d' q* n& L4 e+ j
: W4 S0 a. e8 M
. d; I3 n# ?" k9 L
A[0] = 1 4 g! \9 @; H" d; D5 j
A[1] = 4 : F3 V: h0 S) r, y. ~& e, K, x
A[2] = 7
; w. [& k; G  H! e$ ~A[3] = 3 & o( h$ l7 }& S# Y( r
A[4] = 3
5 z. B+ X* m8 H$ o8 jA[5] = 5
  r0 z* T: _$ u. jthe function should return 4 because:
5 K% {3 O: Q5 x  h& \
8 P0 m& ^8 Z4 F* |* E+ N/ v/ ^

5 @* T6 s7 _, Z& Sindices 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; 2 F* q/ A( u. ?5 s
the distance between these indices is abs(0 - 4) = 4;
9 W& \* \" I0 ~5 U7 ?, L( A2 cno other pair of adjacent indices that has a larger distance exists.
0 \' h+ f$ X% b, Y- \! cAssume that: 2 K6 f# l0 C( a: ?6 j3 u/ ^9 C

0 o- Q2 h2 V+ Z9 K$ k! b
, U7 F% h% e) ?: e  `
N is an integer within the range [1..40,000];
0 g2 g& o) J# f$ Oeach element of array A is an integer within the range [-2,147,483,648..2,147,483,647]. / K  m8 S4 s7 m. a
Complexity: + b; `+ E1 T' K

& H  H+ M; ~. N, [2 V8 Z

8 B" F7 q. s  I  U6 t" zexpected worst-case time complexity is O(N*log(N)); " N* E+ Y3 j/ o$ T8 G& b
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments). 1 h. e( N! f' a  l7 m* x
Elements of input arrays can be modified.
* h9 C2 E1 i; x7 l' a# w7 ^8 o8 T, k" U1 _. ~6 d; g5 ?- n

5 U. {* N7 {- P* }6 ]; A! ^4 `这个题的风格还是很不错的,有输入,输出,复杂度要求,数据范围……9 k3 P  b. p% h7 h* N
题目也不难,如果把数重新排好顺序,那么选择的区间一定是数值上相邻的两个数(中间不能有别的数)。注意定义是整个数组没有它们之间的数,而不是P,Q下标之间……开始我把问题想难了,后来发现是简单题。 可以stable sort,也可以直接用index做sort,然后像去重那样选择每个数第一次和最后一次出现的位置,当然还可以用map记录每个数第一次和最后一次出现的位置,然后按key递增遍历map,其实就是算数值上相邻的两个数的下标差值的最大值而已。我的函数是vector的和它给的不同。
" z1 U& w% Y5 o/ _
. a6 D+ O/ P$ s+ O- C& I

5 w$ X( }! J+ x  J$ B0 _- L
  1. vector<int> b;: C! l5 e* B+ _" H  f
  2. bool cmp(const int &x,const int &y) {
    , K8 F2 u& x5 x+ J0 T
  3.         return b[x] < b[y];' I* d) Q. T: k" p5 w/ t+ Z6 L
  4. }$ ?7 G- j- t  X+ p' t& y
  5. % \% R% H  e& E" X8 f2 h
  6. int abs(int x) {6 f6 H6 y. n, f
  7.         return (x >= 0)?x:(-x);
    $ g0 J$ w; R! }$ S
  8. }& T5 ^6 k7 e* g# R2 i

  9. , K; Z) G2 R! e7 V$ y6 C) `
  10. int cal(vector<int> &a) {# t( }- o' r4 @3 [# k/ ]% L
  11. int n = a.size();, |8 B7 e3 X$ C3 o3 {; e& S8 V% R
  12. vector<int> ind(n);. i, W% M& K7 U. G5 R
  13.         b = a;
    1 x+ @( r* F+ ^: f6 y# p' g
  14.         for (int i = 0; i < n; ++i) {2 ]$ ~' [* Z( H- C" @4 _
  15.                 ind【i】 = i;
    1 Q3 D+ c+ `6 {7 L: w  s
  16.         }
    ! h- d/ \4 Y; |" |
  17.         
    + Q) x& k9 D: u3 C8 D4 C
  18.         sort(ind.begin(), ind.end(), cmp);
    ) f# z. ]  s! x; {3 e+ A' w' F
  19.         int early, late, answer = -1;, g5 X: O+ Y# @: ]: L
  20.         bool first = true;
    4 y, Z; k  h( ?1 j
  21.         for (int i = 0; i < n; ) {
    0 `% w9 q0 x1 b% Y3 w3 [  k; k
  22.                 int oldEarly = early, oldLate = late;. K. m0 R  _2 N4 }( s
  23.                 early = late = ind【i】;
    ' Y8 s! J: [2 i1 G7 a- H: l- ~
  24.                 for (++i; (i < n) && (a[ind【i】] == a[ind[i - 1]]); ++i) {
    $ u* u; u4 Z+ Y# w, V
  25.                         early = min(early, ind【i】);
    / }' q/ e& E9 y) w
  26.                         late = max(late, ind【i】);
    % r7 C: h% q5 V/ z: n
  27.                 }/ k1 I5 Z5 B; g
  28.                 if (first) {
    " M5 w: D- N% {4 D' z: F- I. C
  29.                         first = false;
    1 e1 Z% V+ p# p" |8 ?4 c
  30.                 }
    & H1 y8 r/ k: t) m  l
  31.                 else {3 j4 C" Y, Y  B& [, g! u0 P
  32.                         answer = max(answer, abs(early - oldEarly));
    , `, N8 R3 i+ v& |# k6 x
  33.                         answer = max(answer, abs(early - oldLate));
    ; e) K" @" `* U0 c
  34.                         answer = max(answer, abs(late - oldEarly));
    + d7 @8 s5 W# }* n2 P
  35.                         answer = max(answer, abs(late- oldLate));
    ; p+ p5 X2 W, e% W/ `) i) _
  36.                 }
    ! ~$ i6 j1 G) F
  37.         }- \4 I' X- O$ U( |& Z
  38.         return answer;, A$ ^' S4 Y3 O6 m- P
  39. }
    4 m4 ]: ~, F+ \4 m0 F1 D/ M- u
复制代码
- D. w4 U/ s' [2 ~6 A2 M9 {5 d
4 o0 c" D3 d2 c! ~  T5 B6 X
8 k4 C# B9 p& p4 T9 B9 C
3 Y3 n" c! Y5 c

5 M" I& ?; {" [3 F& Z! m
0 ~/ V( {$ a8 e! F& O, s. E% b
我们始终相信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 | 显示全部楼层
多谢分享 讲解非常详细
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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