找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

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

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

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

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

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

x
本帖最后由 Sophia 于 2-14-2016 02:37 PM 编辑 7 o: U7 Y6 k) Z

- y* {- J2 ~) Z7 T( ^$ I刚看了个题 貌似是Barclays的面试——虽然没听过这个公司。。。。4 b/ f. V  x# t! M4 M
, c4 X0 }& [& e

8 n( g- b8 M. U: D" |6 f! vInteger V lies strictly between integers U and W if U < V < W or if U > V > W.
; ]2 u# G6 D$ q
/ U4 _$ q/ ^7 y. ?# i3 A) E! H

5 g5 g& b) [9 ^! g, \, ^% D' mA 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].
+ l( l5 i4 l! M4 ?
8 _2 l0 P6 p3 y9 Q1 B4 G0 Y8 B

( J" M' z+ `- A  Z' ]! hFor example, in array A such that: ; C/ u: @" C( n- p! b
A[0] = 0 & V! ~) Q' D- A" w1 ~/ M9 ?9 J
A[1] = 3   F( c% R+ M5 T2 p( R+ X( m
A[2] = 3 ; N9 o) j7 C8 W0 D
A[3] = 7
; N) t4 b4 Q0 h7 u! ^7 xA[4] = 5
) G; M! f( s7 mA[5] = 3 , c( G) S# r4 ?
A[6] = 11
6 Y0 @) T0 U& {! ~7 }A[7] = 1 , a  I5 p; m  Z
the following pairs of indices have adjacent values: 5 h% W! W. @% _8 r) p

) c( m- s, h$ }' R% U
) J% {' q4 P6 Z3 x! l1 ^
(0, 7), (1, 4), (1, 7), , K, |0 l- M2 b0 {/ Y& [
(2, 4), (2, 7), (3, 4), " {; r) ^  n/ s4 |& U
(3, 6), (4, 5), (5, 7). - v$ v$ o% }) N# |
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. % k% H$ Z2 u3 U% R1 z; N" X
% P! i0 E, W; ~+ b, U; A
2 H5 g4 W# R3 D
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.
$ Q4 z+ j  _0 _9 w1 @
7 {, l6 ~1 I( F0 Z; ~
, Z# M: A3 s& `. g: [5 {
Write a function: . M. f/ H1 T* b; i3 z

! v; I% C! F$ p6 v& ]& [1 _8 ^5 F  y

8 q0 c- A. o/ g+ k; p, g3 I6 c6 |( \int solution(int A[], int N); # ?1 K; U5 f$ H% m/ Z& d' q

. b6 k# p/ S2 q# j
) L8 U( E/ p* B! 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. * ~3 s1 H5 C% G1 I

; L3 e# o- i9 T1 A' S, P5 ]% T
: e. z5 Z0 c* _: C
For example, given array A such that: + p9 |& @  Q& K' `, M

  Q$ B! |$ R/ u- n7 |

+ o! A# Z! E1 J8 S) ^2 p. sA[0] = 1
/ t" [1 J  K# p% U5 `3 b$ fA[1] = 4 8 I$ D! m* Z+ B7 v3 f
A[2] = 7 $ c- c" M" e* C
A[3] = 3 6 b/ \/ E# P2 [( \1 t/ z: M6 V
A[4] = 3
8 d" M$ g4 h0 P0 `  r+ ?7 t% cA[5] = 5
/ e: R* {4 D4 t' H' sthe function should return 4 because:
% f& z  N/ e" K0 y2 p, X' u: D. F& L; ]3 t. X6 Q! H
0 Y; ?% e/ D: Z' 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; ; d) |6 f* d- H- z' J
the distance between these indices is abs(0 - 4) = 4; # t7 ~2 \% d" E1 I; |2 }* d
no other pair of adjacent indices that has a larger distance exists. * G# j8 O/ X( a! V. I9 A
Assume that:
2 [0 S' a1 S# U- V/ l# Q* U- U/ [
3 B/ j+ k0 M; D& V
N is an integer within the range [1..40,000]; ) c- u; c0 ]  G* b) W9 ]& @
each element of array A is an integer within the range [-2,147,483,648..2,147,483,647]. # k" D& j8 m# R  w: ?8 e
Complexity:
/ h) K7 e6 l# E0 n' Z
0 f) Y. J5 o! h- i

8 ~) ^" }! b  P/ Kexpected worst-case time complexity is O(N*log(N)); " X9 c/ J0 T2 I. ?! H% `$ k7 [
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
# L' ^3 i" Z; L4 Z& C( j, W- |Elements of input arrays can be modified.
# G* e% L6 r2 W# n+ \' U2 X9 b) {. f- D9 l6 ~% v, E( J* n
& D, U, @6 q3 w) H- B+ j* N
这个题的风格还是很不错的,有输入,输出,复杂度要求,数据范围……) }/ M( Z( a* z+ h6 f5 Q- Y
题目也不难,如果把数重新排好顺序,那么选择的区间一定是数值上相邻的两个数(中间不能有别的数)。注意定义是整个数组没有它们之间的数,而不是P,Q下标之间……开始我把问题想难了,后来发现是简单题。 可以stable sort,也可以直接用index做sort,然后像去重那样选择每个数第一次和最后一次出现的位置,当然还可以用map记录每个数第一次和最后一次出现的位置,然后按key递增遍历map,其实就是算数值上相邻的两个数的下标差值的最大值而已。我的函数是vector的和它给的不同。: q0 N7 Y9 U# y. D

9 @* f# ~1 R) c$ u  X
* T2 o' n1 L3 ?# `% T
  1. vector<int> b;
    9 V& K+ f( c5 e
  2. bool cmp(const int &x,const int &y) {$ N* V1 Q1 M; W; @. r
  3.         return b[x] < b[y];/ @7 |7 D& w( k3 x0 z; _
  4. }1 E" y5 w) H1 k: Z0 C! ^; s* k

  5. ) ^- q$ D3 g' t* D2 Z
  6. int abs(int x) {% w* n' \$ y8 ^1 l" X7 p, Z
  7.         return (x >= 0)?x:(-x);! T3 u3 E  P6 F6 @
  8. }% }3 k1 J9 ^" ^. `, [

  9. $ _* n4 H; g6 j, Z: D+ S* v9 L
  10. int cal(vector<int> &a) {0 d3 j* v8 u0 n0 g0 m2 T4 R) L
  11. int n = a.size();' l7 b" I* J* M) R
  12. vector<int> ind(n);
    + J' J2 j1 w. a) u
  13.         b = a;
    1 ^0 O0 G/ k/ E% w% v* V0 F
  14.         for (int i = 0; i < n; ++i) {$ T9 A8 l3 n7 Z0 p. l( j- G* ?3 m/ [
  15.                 ind【i】 = i;
    1 P  q7 V6 ^  ~% ]
  16.         }% J$ X! C. c8 u8 K/ |) @
  17.         7 {( @5 u; L8 L  H" ~2 {8 `
  18.         sort(ind.begin(), ind.end(), cmp);
    . R) n1 ^0 U; h) k( m
  19.         int early, late, answer = -1;
    3 u: Y% G, J( Q% ]/ H- |5 s+ x
  20.         bool first = true;& E9 D  R( V& B3 W
  21.         for (int i = 0; i < n; ) {
    , s6 ?8 D/ U7 D2 W  n
  22.                 int oldEarly = early, oldLate = late;6 s$ }* r9 q/ _+ j# J. |/ M
  23.                 early = late = ind【i】;
    % P+ V% a2 d% F& U/ z1 |( Z
  24.                 for (++i; (i < n) && (a[ind【i】] == a[ind[i - 1]]); ++i) {# s7 D$ ^: @! _, ^
  25.                         early = min(early, ind【i】);8 |: f4 M6 @) O% D
  26.                         late = max(late, ind【i】);
    $ _" J. n  E  }9 I) C( y
  27.                 }5 ^( O( h$ V- @5 s
  28.                 if (first) {9 [. D) B# P9 D: ~7 ~
  29.                         first = false;1 R1 ~. [8 _1 V3 P
  30.                 }+ X) X1 \) Y4 M9 ]
  31.                 else {4 V6 }3 O9 O" O: l* P
  32.                         answer = max(answer, abs(early - oldEarly));
    - @* s9 V! p% T- Q( u* _
  33.                         answer = max(answer, abs(early - oldLate));4 T: Y" x0 V' x" ^$ r% u! K) _: s
  34.                         answer = max(answer, abs(late - oldEarly));
    8 V! M  H/ |' m; K
  35.                         answer = max(answer, abs(late- oldLate));' @/ f0 b& K* D7 M2 ]
  36.                 }
    ( \5 X1 s0 \; m8 s
  37.         }5 n. E% f% X6 r1 ~6 v
  38.         return answer;) q7 T$ o+ o' ]* g$ ]
  39. }4 o) T" {7 ]( U' s! [$ y
复制代码
' j6 T9 }0 }9 [3 W1 g/ A% r. ]

9 \* E3 Y. m! v+ y8 F! L! Y. L
6 G9 z* v' c' A& S2 d0 `
' N* r, M) ]9 j& @
5 b% @0 S# G' \5 V
2 [' G% E% {) W/ S8 ?/ F, y+ 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 | 显示全部楼层
多谢分享 讲解非常详细
回复 支持 反对

使用道具 举报

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

本版积分规则

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