找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

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

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

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

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

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

x
本帖最后由 Sophia 于 2-14-2016 02:37 PM 编辑 3 @: Q$ t! H7 l3 ]1 v6 T
0 ?+ _, F, |( @+ T
刚看了个题 貌似是Barclays的面试——虽然没听过这个公司。。。。
+ s; _  [6 Y1 ]) N! E: i7 R5 }  l# I' A: G

  B' F' f" I! U! Y$ t1 eInteger V lies strictly between integers U and W if U < V < W or if U > V > W.
( O% b$ I8 @0 s! t3 x! i0 ^2 U' e5 G3 C  y: g/ ~1 q4 W6 q
& Y8 J8 U6 z  v8 f, E
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].
  R" L/ P* q2 J6 |& `0 a, z( s! z7 `: Y2 U' W  n& P/ T" o: l* k

  A* v8 V! M* ~7 i- O2 ^. i( RFor example, in array A such that: / x  b4 n* u% G7 w
A[0] = 0
: @' f9 x- W3 e( C/ o1 s) k  EA[1] = 3 , ^; h3 Q8 O$ x9 U: ~/ S
A[2] = 3 " v5 i3 t& Z- y! [! }2 u* I. b6 P0 z& [
A[3] = 7
7 W5 V* G' I! CA[4] = 5
! O8 p! J! |, B" u: k$ `3 o) h2 }A[5] = 3 ; f/ \3 o" T5 D. z2 x2 @
A[6] = 11
5 h/ A1 E% W" o4 A4 s0 c9 \: r+ ?. ]A[7] = 1 / j2 v* K9 }1 p$ ~1 x6 b
the following pairs of indices have adjacent values:
( H7 f4 V6 j1 G% U6 b; }
/ n% p* d6 |# c( C* E" e, \9 [

; l3 ^; D5 P) j9 d(0, 7), (1, 4), (1, 7),
  J8 M; ]6 C" t: I* N9 i2 G# a$ K(2, 4), (2, 7), (3, 4), " o% ?0 r7 Q' O+ S
(3, 6), (4, 5), (5, 7). ( q. U3 f; [9 K; ]
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.
4 ~7 i/ r+ S! h! n8 I2 |" o
! g$ v& d8 r/ X# u

2 W: N. t- I4 n: @3 Y+ U) c4 r2 EGiven 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. ; U' z# j/ N' P  c3 ^
$ N1 H/ k2 e7 e8 A) q9 t0 q  {- E
5 N; s. Z  w4 L- |" U9 B
Write a function:
6 M8 I7 K. L- ~9 D  L
$ w' X& x! ~: l, b+ R
. X3 i' k/ y' D2 f
int solution(int A[], int N);
& w- W% W0 C* E. \9 v- J- K4 h  E2 C5 N0 z+ ]
# x' M) W5 i) A( {- Q, U9 s
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. 6 T4 m( u$ j, t- J6 f5 M
) M8 O0 S3 h& c  |

' w; ~) ~6 ?% Z; t1 r/ j& c- \8 KFor example, given array A such that: - c; F8 e! r* Z0 R& w# p
' \' _/ q( k* v2 O2 [

3 j+ _8 Y* y# L% V; v3 r/ e! SA[0] = 1 ; J4 R) h6 r, h/ r. p
A[1] = 4
- F' ^" R) ^7 v' [2 r6 l% G- `; eA[2] = 7 , M1 Y$ U" ~: k6 J6 D8 z
A[3] = 3 ; D5 W/ j& E  s3 r7 }* W
A[4] = 3 & T5 h& i7 \* z% g+ r! Q- o
A[5] = 5   ?. Z3 y4 f3 v/ L% U/ U8 X3 s7 y
the function should return 4 because: & r* f4 m. b# g9 T

( D0 T2 U' ]4 K. t* S( f7 b
7 `. ~) C5 d  s1 C) e1 C( c2 s
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;
' L  L$ {9 J, }* @the distance between these indices is abs(0 - 4) = 4;
4 n% e, a/ [7 \! x1 @* r" D! Ino other pair of adjacent indices that has a larger distance exists.
) ?" M4 ^+ R/ o6 m7 p# WAssume that: ' N2 H! d# F/ |% Y7 n
) y* f4 E1 |2 A/ C& T
6 I( c" y9 i- L& J
N is an integer within the range [1..40,000];
; V0 ?6 n4 v/ ?6 k  d& W; ]# R' Heach element of array A is an integer within the range [-2,147,483,648..2,147,483,647].
5 C+ {0 |4 a+ PComplexity: 1 O" Y  u3 E" m* H  v8 c
% L3 C( C) V* `% {* t

! s( t0 g8 Z* dexpected worst-case time complexity is O(N*log(N));
/ j& W& F. n  zexpected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments). # i( u" \* G- i' Q
Elements of input arrays can be modified.
+ {3 F- t4 V- e7 g4 ~1 H, p
5 ?* Q$ |: e. G1 G; S4 K

9 d; Z  f/ G: b6 h  d这个题的风格还是很不错的,有输入,输出,复杂度要求,数据范围……
) S) a2 p' r: d1 e) u4 u题目也不难,如果把数重新排好顺序,那么选择的区间一定是数值上相邻的两个数(中间不能有别的数)。注意定义是整个数组没有它们之间的数,而不是P,Q下标之间……开始我把问题想难了,后来发现是简单题。 可以stable sort,也可以直接用index做sort,然后像去重那样选择每个数第一次和最后一次出现的位置,当然还可以用map记录每个数第一次和最后一次出现的位置,然后按key递增遍历map,其实就是算数值上相邻的两个数的下标差值的最大值而已。我的函数是vector的和它给的不同。+ v* b! n; U4 ^. s) k9 f+ F8 }
, k# W' X4 i# r2 F5 F

5 c$ f1 e+ v$ P  s% O2 J. O8 c
  1. vector<int> b;# x+ o4 O' j9 v. Z: p. u
  2. bool cmp(const int &x,const int &y) {
    - J1 |, F) E7 v
  3.         return b[x] < b[y];
    - I: ]7 u" o% T( [- E$ l" `
  4. }
    " n3 {' Q3 s$ e4 K' H0 F4 n0 B
  5. $ n4 B3 i$ P$ V6 ~
  6. int abs(int x) {. ^3 N6 D0 x' Y7 A0 U' Q# x' W
  7.         return (x >= 0)?x:(-x);. j% M8 A- r: [9 f; s
  8. }" z/ }3 B+ s# d* N1 Z9 Q1 I3 d' b
  9. 6 Q1 C: h9 j; r
  10. int cal(vector<int> &a) {
    , q" N  R0 l7 ]9 S9 g6 M
  11. int n = a.size();7 z  K8 T' x' a5 h) s
  12. vector<int> ind(n);
      y- W: m  |, q7 z; u3 C7 ~
  13.         b = a;6 n; K. k. Q- i3 f
  14.         for (int i = 0; i < n; ++i) {
    - m+ z; P$ d! j% ]; E
  15.                 ind【i】 = i;
    " X3 ^- F; J9 F" p2 z2 @: q* H  I
  16.         }! V% h- {$ v( _4 M: W: v
  17.         2 o. X$ M# I' n; E/ X& j
  18.         sort(ind.begin(), ind.end(), cmp);$ C: U2 j* m  c( g- ^
  19.         int early, late, answer = -1;* F& J4 u. u* \( [
  20.         bool first = true;  W) @! H' v% y9 y
  21.         for (int i = 0; i < n; ) {
    5 F! n+ S! Y# z6 \1 e
  22.                 int oldEarly = early, oldLate = late;' G& B8 _/ p7 j9 @" s8 F8 \' \
  23.                 early = late = ind【i】;
    ) U$ A. X# }0 m5 N1 [9 K
  24.                 for (++i; (i < n) && (a[ind【i】] == a[ind[i - 1]]); ++i) {
    ! o' F4 x8 w' G& P# z5 N$ |
  25.                         early = min(early, ind【i】);4 U, j0 B; O! P5 n
  26.                         late = max(late, ind【i】);
    $ @9 n1 F2 Q  {) b  j2 h2 o
  27.                 }
    + R0 ^- N0 P/ Z; Z& B! n6 v
  28.                 if (first) {
    4 Z7 I: W9 O- o7 n$ `0 y; S
  29.                         first = false;' ~/ ^" v3 ?5 W2 a( }
  30.                 }
    ! w. `" }; A4 i! B
  31.                 else {
    9 r2 ?3 M# ]- V
  32.                         answer = max(answer, abs(early - oldEarly));
    4 o8 O. {; X7 L" N5 w# l
  33.                         answer = max(answer, abs(early - oldLate));! C: v6 {- [9 B) H8 m& Q+ w' H$ Y% V; R
  34.                         answer = max(answer, abs(late - oldEarly));# R& w" P7 U4 Y2 u1 \
  35.                         answer = max(answer, abs(late- oldLate));; E- I& u: Q/ z" r
  36.                 }9 U5 S0 [7 Y* \2 J& l# j" u; T$ L
  37.         }
    " t2 u7 ~$ g  C' u* b1 O
  38.         return answer;
    9 z. E( R1 R# L  O) [8 J
  39. }
    4 M) w  v7 Q! R4 B4 g  X0 s# s
复制代码

, ~  M6 L1 a! x9 z7 f9 y+ @4 ]3 r; e3 P  z

* K, y! M& a6 ^2 C2 n
  y+ ^! a& f- O4 [  q1 c$ B2 t
* i( L9 K; m, B5 x  |0 w  }: q6 u
- @' {  |8 J, L* z. U) r2 P
我们始终相信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 | 显示全部楼层
多谢分享 讲解非常详细
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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