找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

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

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

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

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

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

x
本帖最后由 Sophia 于 2-14-2016 02:37 PM 编辑 , a/ h3 I/ Y' ?7 V+ l7 ~
+ [$ h; P' l* T  l+ ]/ S
刚看了个题 貌似是Barclays的面试——虽然没听过这个公司。。。。: f- S" {. S5 T
& |) s' {& e. K+ ?% N5 @) b: p: S

# K) m6 o/ \* G* bInteger V lies strictly between integers U and W if U < V < W or if U > V > W. $ ~, y4 e& G) \0 y8 R

2 E  E+ R$ j" Q1 W) B% H" i3 K: z

. B# D5 b# d  g- LA 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]. , Y& L6 I# H5 a; V

$ l$ r- U8 U, j: U0 ]

0 c4 a: f+ `# OFor example, in array A such that:
' _7 ^  \% U* h/ L' RA[0] = 0
6 j4 S/ {7 y" |8 b8 O: g4 `7 FA[1] = 3
; N, M8 L6 l9 t; l: [A[2] = 3 ' R) @5 X& ?$ a/ T- h
A[3] = 7 : h/ Q; T  q; T! ~% d4 w
A[4] = 5 " w' l- O* O1 R/ r
A[5] = 3
: i/ n9 w* ~0 E, VA[6] = 11 3 w$ w- l/ A( [6 e: V
A[7] = 1
! {0 _  T! n& s# `* gthe following pairs of indices have adjacent values: 3 R! [# y  S+ ]( f: e5 I7 E

$ w% l5 [9 i; i# ]2 J6 H4 R
: a6 a; X' w  ]( K5 S
(0, 7), (1, 4), (1, 7),
- r4 v% g. J$ v# i3 T" J(2, 4), (2, 7), (3, 4),
; Z! e7 _8 D- T; n. `( S9 j1 [(3, 6), (4, 5), (5, 7). & ]0 Z  b' q7 V" c# J& c6 s, s
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.
- p1 X8 M/ u5 Q, P( v; U0 F# e+ z8 s( K
) D5 P/ \' j) T. c- U5 [. ^
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. * L0 E+ Y4 V1 g" X6 g# t5 n4 z

0 e, |! o  {. d$ J

2 ~1 h! @8 `+ k+ V& wWrite a function: ! y' Y6 L& b1 p6 `0 i: L6 \( f; [
4 s# R' F! z9 y2 `9 R; B
' `5 ]; Z$ @* Q6 E' o& n! r9 c* E" }
int solution(int A[], int N);
3 l; @7 X5 Z; [# n: ]) |
( g1 B: {! Z2 @3 Q" l) _' X
+ }6 {( h2 C' A3 t% n1 Y
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.
* w# C4 s+ m3 |# d7 Q; d+ l6 }+ I1 t# J/ b

+ E$ e! F1 X& M7 }  XFor example, given array A such that:
7 d5 v% s9 S3 Y, z& g9 k8 m. g/ g* h1 K2 E3 P/ Z

3 J. }4 w* f: I, G/ B8 ~A[0] = 1
$ F5 I' `( L! d. LA[1] = 4 ) g4 k5 \2 ~# v' ~! t- v
A[2] = 7
! k$ `) b! }: A9 P+ WA[3] = 3
  m5 `! u% Y( ^4 Z7 eA[4] = 3 0 X9 H( |5 ?( r2 E6 q
A[5] = 5
8 W6 P4 A$ R7 ]3 i+ \. x2 T4 kthe function should return 4 because:
+ I1 f; n, q* x& a- L6 w( ^8 C( p( ^* e2 s. ?1 ^* G
( `6 E; D. ]0 ]' F1 u9 Q9 u
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;
; x- u% `; d% y3 a# F8 rthe distance between these indices is abs(0 - 4) = 4; 8 L, \+ h' x1 J: ]' D9 c* f0 G0 `
no other pair of adjacent indices that has a larger distance exists. / L* O4 x, S0 y8 w
Assume that: ( w: G0 q1 ?) o9 J  W
8 C2 r4 K* Z1 L

* U& O7 u, R* K, C6 A" s, |, q3 C1 AN is an integer within the range [1..40,000]; * X% r& I# c$ i
each element of array A is an integer within the range [-2,147,483,648..2,147,483,647]. & o7 B, f* B% V( B9 w7 L9 W
Complexity:
: F! I, d5 S3 e; V: E" y" J2 s5 G% X0 K& i4 ^2 A
' M$ i$ o: S4 S$ {. I
expected worst-case time complexity is O(N*log(N)); . ?2 {! j) t+ S3 k
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments). * u# {0 V3 l# O) I
Elements of input arrays can be modified.1 L) U; @/ Z! l: O

3 N. t( C" B9 P. g: K. X) P& y# K# [
& P& r% }+ @% w
这个题的风格还是很不错的,有输入,输出,复杂度要求,数据范围……
2 W3 R8 ~+ c" t) [. E题目也不难,如果把数重新排好顺序,那么选择的区间一定是数值上相邻的两个数(中间不能有别的数)。注意定义是整个数组没有它们之间的数,而不是P,Q下标之间……开始我把问题想难了,后来发现是简单题。 可以stable sort,也可以直接用index做sort,然后像去重那样选择每个数第一次和最后一次出现的位置,当然还可以用map记录每个数第一次和最后一次出现的位置,然后按key递增遍历map,其实就是算数值上相邻的两个数的下标差值的最大值而已。我的函数是vector的和它给的不同。
, C: L4 E7 {$ E" j1 \+ b9 H% @+ p! y5 m  e; Q  ]
  {& f0 O/ m0 |
  1. vector<int> b;& B9 y6 }1 R/ B, B; n4 `
  2. bool cmp(const int &x,const int &y) {
    * u! u: y2 ~3 B& L
  3.         return b[x] < b[y];$ @. x* W- S  n- G/ l2 V
  4. }
    7 _* W8 ^5 a) l0 U  z& E2 @6 C/ R% G

  5. 1 ^1 q5 \3 b- l- Z  z
  6. int abs(int x) {( l# Z0 ^$ v: |0 n1 {( N
  7.         return (x >= 0)?x:(-x);
    3 S( B0 }; R) ~: c; b
  8. }% R$ C3 b0 J! j

  9. # P* _9 L# M! \0 k& f$ w2 k  v
  10. int cal(vector<int> &a) {8 y' Q: e4 U- ~4 e. z- Q
  11. int n = a.size();9 m6 p; J$ H8 ^) E
  12. vector<int> ind(n);
    # K* b" Z( O% p% S$ |& |
  13.         b = a;
    & f  z5 M& B& Q' m. |) A
  14.         for (int i = 0; i < n; ++i) {2 G" z! l) I  R1 t7 G. K8 @+ q
  15.                 ind【i】 = i;
    * \# a: p! j. [6 V0 U# I
  16.         }
    4 b6 ]; u7 Z9 J  A" N8 p3 [
  17.         9 |' s% d: S- g3 M- @0 e; {* ?# l
  18.         sort(ind.begin(), ind.end(), cmp);
    ( V1 C$ t$ D/ y' k: G8 I
  19.         int early, late, answer = -1;
    4 P) ?) n5 d; o) o/ k" f
  20.         bool first = true;
    - l3 W5 G+ u- ?: R9 L
  21.         for (int i = 0; i < n; ) {
    9 \' j) t3 k2 e
  22.                 int oldEarly = early, oldLate = late;
    + u" w2 R& p4 v' ~0 Y; K
  23.                 early = late = ind【i】;
    , ?* p5 |3 A1 \" e
  24.                 for (++i; (i < n) && (a[ind【i】] == a[ind[i - 1]]); ++i) {3 F% {4 K% h; v( R, J7 k) o! h
  25.                         early = min(early, ind【i】);7 G! V$ Y& ^0 r; A* P
  26.                         late = max(late, ind【i】);
    . |; G; k+ r, L" w( t. T7 g
  27.                 }5 [& Y% y+ i/ C$ o' r
  28.                 if (first) {; s& j7 o  F) |
  29.                         first = false;
    4 r5 c: S' ^* k
  30.                 }
    ( P3 O5 t) A; G! @4 S8 m
  31.                 else {4 y9 ~1 }4 I8 A1 D+ O
  32.                         answer = max(answer, abs(early - oldEarly));
    ; K8 O- V7 f- l% t3 Y1 b% n4 ~
  33.                         answer = max(answer, abs(early - oldLate));
    & P) o3 f- {1 A
  34.                         answer = max(answer, abs(late - oldEarly));; h0 Q# O# u3 P! r9 D% p
  35.                         answer = max(answer, abs(late- oldLate));
    2 t  c4 B7 D2 [* a! z2 I! F
  36.                 }
    ! ]) k' a( B7 |) {  I, S8 e3 I% ~
  37.         }
    4 i' n8 z4 I. H$ \
  38.         return answer;
    4 F0 B9 P- |1 o$ G# P
  39. }9 _3 g5 h, X% y# ]8 U4 J: C
复制代码
4 J% |- {, ~" U5 U# D" l
; j- c2 h/ q5 n3 Y
/ m- B: R" O) H9 Y
( e. [) p" `3 P, L6 j; Y1 u2 g
+ R; Y2 S: V* C8 a
9 c2 p% F, y& P% D3 V* s0 n( ]
我们始终相信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 | 显示全部楼层
多谢分享 讲解非常详细
回复 支持 反对

使用道具 举报

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

本版积分规则

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