找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

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

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

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

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

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

x
本帖最后由 Sophia 于 2-14-2016 02:37 PM 编辑 7 i/ q' V! a9 ^# n

' G, t( Q6 r1 F刚看了个题 貌似是Barclays的面试——虽然没听过这个公司。。。。
  i' u. Z9 b2 \
, O: \8 N) v( {% N6 w( l1 E
- b& b6 o' A+ v. b; @" T- u
Integer V lies strictly between integers U and W if U < V < W or if U > V > W.
2 E. Y: {( M! n- `! B; c# t3 B! R+ v- ^

% i2 W) s( i# \. g. {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].
% N2 w( G# g; s! U5 Z* T, ^3 S# z+ _% [6 \- e+ G8 m% z
: K# l6 Y8 [. o! k  B6 s8 _+ Q
For example, in array A such that: , g7 n/ m7 Q8 a  X3 `% J6 J% J
A[0] = 0
7 ]: X9 V0 Q* t! OA[1] = 3
' L! T) L  \! @% E1 M/ g# c' bA[2] = 3
: c; k: u  b* p; @% H# v$ tA[3] = 7 % g+ @3 h) J9 S
A[4] = 5 7 e( T& V2 ~- n
A[5] = 3
3 l# n& ~$ T6 @! q4 ^: SA[6] = 11
4 X# L: f/ f% L0 `+ lA[7] = 1
5 c* i$ Y$ \* b) s" u* Kthe following pairs of indices have adjacent values:
+ i. ?+ K5 ?0 `4 S$ F+ ^3 m  I1 D* t4 q! D+ Z; j8 v, K8 R) e! }

) I2 r! S. n# s5 }+ a! d* O1 c% S# J(0, 7), (1, 4), (1, 7), ! I* ~. H0 t5 j
(2, 4), (2, 7), (3, 4),
( Z( N* ?& d) z2 @3 ^1 A(3, 6), (4, 5), (5, 7). ' k& V1 O: r: Z! }9 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. 0 p0 X, f" H; r5 D2 M

; _% T) x9 Z7 q5 ~, A1 p

3 n4 E0 ?' k! O; n: _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.
; D$ ]0 d8 l8 I# E# U( s/ @) ]' l0 k. |

% \0 @& Q; d6 N9 z, U+ tWrite a function:
$ J$ S8 u  ?6 {8 I
% E9 B1 s# E3 P
+ j: [2 h  M6 m6 e7 b
int solution(int A[], int N);
: `" U2 ?, I( Y! o5 w/ r$ R0 t7 `6 j% e, N% i2 p, t. |% X
" g  }8 |* H9 y. F/ ]& u
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.
. a$ {* E6 C' ?  E* a+ l
( Y) ]* [2 \  J6 h1 r* l9 Q- ]

# ]/ o$ z+ t( D/ y& i) }( d+ FFor example, given array A such that: ! _: L2 z. I. s; C: ^

# h8 S" n: K. }
7 {! L3 c6 T) E0 L! \. ?. T) d
A[0] = 1
6 Z, `4 [% g! r0 W, wA[1] = 4
+ A: D, w# u6 C# w5 R* UA[2] = 7 ' W3 ?( D; G! W
A[3] = 3 # E6 ?/ V* ?# \; Q4 u
A[4] = 3
! F# w0 Y! h  H  V8 q, l+ yA[5] = 5
1 T% T# Z6 K3 ^2 y4 rthe function should return 4 because: ! t' Y! n/ c4 M2 s( Q$ y; k1 M9 g; H& n* a
. V! ]8 M# q0 O8 V

1 u* t; }1 c' b* z& Eindices 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; , h7 l7 s' c. r9 }3 O1 o8 S
the distance between these indices is abs(0 - 4) = 4;
: b8 q  C: ]! a- R0 @2 y( Ino other pair of adjacent indices that has a larger distance exists.
/ T; v3 Y+ ~! ^' q& ^8 x) pAssume that: - S) }' A6 c$ Z$ e; F* B

2 @. B0 i8 O. g( ^4 ]* Y

0 U. y2 M% H& [6 c9 E. o4 lN is an integer within the range [1..40,000];
- H5 b" N$ ?9 \each element of array A is an integer within the range [-2,147,483,648..2,147,483,647]. ! u4 \- M4 P3 b! Y
Complexity:
5 \6 F( y+ u/ `, o7 M
/ e% S) @; \8 |4 ~" k
8 c( A# u) w+ ]3 X" c) A
expected worst-case time complexity is O(N*log(N));
$ Q+ F2 z! L7 _5 }expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments). . \$ Z$ X- G: B8 _5 u1 ]2 g. G4 P+ ~
Elements of input arrays can be modified.
3 r) S, P+ t9 G( L! s) Z4 C! O3 v2 k: ]" t
  g$ ^1 M9 K+ ~
这个题的风格还是很不错的,有输入,输出,复杂度要求,数据范围……
( X& s3 l1 }8 X% E5 ?8 H8 G题目也不难,如果把数重新排好顺序,那么选择的区间一定是数值上相邻的两个数(中间不能有别的数)。注意定义是整个数组没有它们之间的数,而不是P,Q下标之间……开始我把问题想难了,后来发现是简单题。 可以stable sort,也可以直接用index做sort,然后像去重那样选择每个数第一次和最后一次出现的位置,当然还可以用map记录每个数第一次和最后一次出现的位置,然后按key递增遍历map,其实就是算数值上相邻的两个数的下标差值的最大值而已。我的函数是vector的和它给的不同。
- V' X0 r5 V! k: i( q
. ?) V$ D9 I' R1 W% A4 x' C
( {1 [# P7 \* Y  k9 k# g2 U
  1. vector<int> b;  X  n0 W2 Q0 M  T) \- }, P
  2. bool cmp(const int &x,const int &y) {
    / @' T* n5 k8 x% p9 f) X
  3.         return b[x] < b[y];; N$ {0 e; Q2 H2 [& I  Q
  4. }2 A; U- J& G0 ^5 \

  5. 8 M1 R) a$ a/ i, I' }; V$ H7 y' W
  6. int abs(int x) {
    7 [! ]# d/ [& r7 t* _% L  \
  7.         return (x >= 0)?x:(-x);
    4 I- h, G; Z) m9 G
  8. }
    ( A; E  j! i: ~, ]9 v, s

  9. % G: p1 F5 m& c4 W
  10. int cal(vector<int> &a) {
    4 D9 i8 d8 F2 o0 q
  11. int n = a.size();
      S7 s% W3 Q8 f9 z: l# ^
  12. vector<int> ind(n);) K, \' b1 D" P; f
  13.         b = a;- ~1 G$ y# @2 w' A7 ]' A' t3 `
  14.         for (int i = 0; i < n; ++i) {
    4 X" }) x  b. |5 L$ ^3 a2 `1 P
  15.                 ind【i】 = i;
    1 H, F9 q& A/ h0 D9 K9 `
  16.         }
    8 D' r6 y) s- E/ [2 ~
  17.         8 |" O# M' z* w0 [8 y/ }
  18.         sort(ind.begin(), ind.end(), cmp);# e7 w7 ]$ t* `* k4 R* e
  19.         int early, late, answer = -1;
    + h! F, N4 ?) q6 e7 U$ v7 K; H
  20.         bool first = true;
    , ^6 x2 |2 w0 |0 ~5 T/ ]# w, i
  21.         for (int i = 0; i < n; ) {$ D  r, O9 ?  ?6 `2 C# J* C
  22.                 int oldEarly = early, oldLate = late;0 ]7 i8 l% J! V# s
  23.                 early = late = ind【i】;* p& F: ^0 S+ B2 _
  24.                 for (++i; (i < n) && (a[ind【i】] == a[ind[i - 1]]); ++i) {, B4 R; b, b2 `' r& u7 u
  25.                         early = min(early, ind【i】);) A- T, m9 r1 u5 A! j2 S# P
  26.                         late = max(late, ind【i】);
    - ^' ~' O4 v/ p+ T8 h2 s
  27.                 }) }  I" w4 E3 ?- c5 x7 f
  28.                 if (first) {
    9 \! j7 {- T0 _( m2 O8 P
  29.                         first = false;4 K3 ~5 T$ H9 X3 m9 x* n
  30.                 }
    * F" b# d- K* k) ^* j
  31.                 else {
    & |. h+ O6 M- I, {; m
  32.                         answer = max(answer, abs(early - oldEarly));
    5 S5 J. o. ?2 t; C# q( T: ~
  33.                         answer = max(answer, abs(early - oldLate));
    : k) B& X) K1 X0 G. T/ E
  34.                         answer = max(answer, abs(late - oldEarly));6 ~& U5 T( ~' w3 p
  35.                         answer = max(answer, abs(late- oldLate));
    4 `: g% [- g4 z0 ~) k
  36.                 }
    , U" U" P+ ~  G& B: T! D
  37.         }
    + L( x' a9 J+ O: `3 \
  38.         return answer;& h/ i8 S$ F! l% u5 f5 N
  39. }1 a% R1 S& o; L0 b$ k. I
复制代码
. J4 k7 H+ r: U/ ^- A0 E. [

; g: {; `3 L3 |# N& h
) N; u/ K3 x$ w# F) h1 M

9 U" _. k% i8 f
, @' P6 b  @% A6 w, d; {
1 }' M8 M9 N1 Q6 `, q! R( `( O7 [
我们始终相信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 | 显示全部楼层
多谢分享 讲解非常详细
回复 支持 反对

使用道具 举报

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

本版积分规则

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