找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 4690|回复: 1
收起左侧

[精选面经题目] fb的一个面试题——警察捉小偷

[复制链接]
发表于 2-29-2016 03:03 PM | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 Sophia 于 2-29-2016 05:43 PM 编辑 * m" W% w2 `+ W1 E

) \8 c! v! T7 ^7 Z9 d1 H我觉得算个智力题吧,其实早就见过,没有细细想过——好像有人发过,也没说具体怎么答的。9 K* K% c; x% a$ A# V
题目描述:有一排房间(可以理解为数组)。一个小偷起初在某个房间里。警察白天行动,看他是否在某个房间里,如果不在,小偷在晚上会移动到相邻的房间里。警察白天再看,小偷晚上再移动……请问警察有没有办法一定捉住小偷?有什么策略保证警察在最差情况下用最少的天数抓住小偷?8 j( S: d" M. I( t( |& G; X

, v. y( A2 @8 ]5 }! T5 F4 O5 \- x记忆:我记得我在本论坛看到有人发面经好像有这个题。他当时回答的好像是算小偷可能的位置,例如第一天可能在哪里,第二天可能在哪里,枚举第一天位置bfs……,面试官follow up是能不能同时算若干天?他回答好像是可以,可以把初始天n个位置都放入队列一起做bfs,而且是在n列的矩阵上做,小偷第i天能否在第j个房间决定于小偷第(i - 1)的位置,再接下来follow-up是可否省空间?其实矩阵只有相邻两行有用,于是面试官就很满意了。。。。
3 q! x  r( `' s* T$ K: O' t我看了之后,大概知道他想说什么,但是他好像没给出策略。。。。- ?; ~6 M4 y/ ]" A& j& f( y, `: w
我自己写了个bfs试验了一下,状态是小偷当天可能呆的房间,每一步选择一个可能在的房间检查,然后产生新的状态。其实这是一个2^n个状态的状态图。我们可以用0来表示小偷不可能在某个房间,1表示小偷可能在某个房间。状态转换是对状态x,我们先得到状态x\',x\'是把x的一个1变成0的状态,表示我们检查了这个房间——因为算最差情况,我们继续考虑下一天,下一天小偷可能在的房间是x\'中为1的位置的全部邻居,其余位置为0。这就是状态和转换规则,我们检查一下按照这种转换,从2^n - 1 到0, 一共要多少步。
& s; q4 P2 w6 r2 S; e! H5 p% I假设房间编号从0开始
- c8 t" h; |# c3 e6 i5 b
2 a3 P7 A4 b  V
  1. 对n = 1,3,5,7,9的结果:
    ; E; r& L4 l3 c; B/ {
  2. n = 1
    * F- X3 {/ N  |9 P8 Q3 g% @1 C% e' J
  3. 1- }2 \' o* J+ T7 a0 t
  4. test 0
    , p3 F& Z9 o. q) g+ @1 Y/ {4 b
  5. 0
    7 Q% I1 W+ K! m* d2 u" ~
  6. * W7 S. h; V( Y- l" F/ `. b0 D
  7. n = 3
    9 ]* K# y% H, p0 b# j/ R; |, L
  8. 111
    ' t8 j+ H% _: C* j! Q
  9. test 19 R* V4 B# O1 j8 v/ g- V
  10. 010" Q, \0 C, |' M6 K% {1 `) Z7 I
  11. test 1
    ( v, M0 C" y% F2 O
  12. 000+ o$ m, l( h) y) c  ^5 H
  13. * A$ q, |* O1 S; I% e. H1 w+ _& x
  14. n = 5, j! _4 j2 P( M1 J" q
  15. 11111
    & d% ^4 Q7 g" |* R: Q& c$ }9 C& c
  16. test 1
    $ K* L" v. r! D+ f5 B
  17. 011112 V$ f1 Q# K/ f5 v
  18. test 2
    # P6 O3 i9 w" V: J
  19. 10111
    ! ~1 V1 e7 R5 \  ?/ b
  20. test 3
    . S- _* d+ r( v4 f' H) \% ~. a
  21. 01010
    / d$ X6 {7 l* m! k! I7 I' a& Q
  22. test 11 }6 L; |5 n! {( V- y! D& G
  23. 001019 E( w/ L% e" D4 @* l
  24. test 2  A. c* n: }" V. a+ z( Y& n
  25. 00010( |4 O% h) y/ \6 Y: ]
  26. test 3- [( X# }1 ?  U4 \( H0 _
  27. 00000# ^6 M: }  Z2 D  L
  28. 2 ]. L1 t& j# r0 K+ ^; Z8 ^' |
  29. n = 7  ?# z8 x$ y0 Q1 N* x" \
  30. 1111111
    ( s7 O6 v) G. D( k0 V! w1 v
  31. test 1
    & z) i4 o& L3 B
  32. 0111111
    4 Z* Q. T+ y9 H& S
  33. test 2
    ; b( P2 X( W9 [! y
  34. 1011111
    , N. n+ ?6 s/ ^# Q& O
  35. test 3$ N. c1 G) R6 k1 f/ J
  36. 0101111! @  |& ]& x! n6 A! S
  37. test 49 a9 q  a& p: r2 `  V
  38. 10101116 B+ B4 A1 S$ P0 {
  39. test 5, o9 z9 ~" M5 `* [- L" L2 w
  40. 01010102 e# R5 T1 u7 o. N+ b3 W% V
  41. test 1# w+ T* G1 L+ g7 |" N0 D
  42. 0010101
    6 Q! @( w8 `8 h; W  m. U2 J% x+ j8 Q
  43. test 2  Q+ V4 w2 G8 f$ O' B" D0 k
  44. 0001010! n1 ?4 b6 I) {# `% e! N
  45. test 3
    : d& V/ [! o1 W) D* p
  46. 0000101
    0 Y: d0 l! o9 P% t4 R
  47. test 4
    & J1 o. K5 g4 T2 e2 I0 [! Z
  48. 0000010
    - U5 `0 ]( Z4 |: U8 }
  49. test 5
    & p# x# j7 r$ N: ^
  50. 0000000
    0 F- C: Q; e, \

  51. ! \+ C+ l8 {1 Y
  52. n = 93 [% V3 `: h/ T
  53. 111111111  U) F" [) q, @- |- i7 Z
  54. test 10 s+ ~2 {4 F" v# I* z+ @5 c
  55. 011111111( b3 p  d4 D4 |, o$ `% e) o. a% Y- f
  56. test 2) K/ Q. G! Z3 ~) S% }) k
  57. 101111111
    8 Y3 t& V! d4 {7 d1 \
  58. test 3
    $ K- t: v7 {% _
  59. 010111111
    4 O% n4 k% q4 K1 n
  60. test 4( N. Y$ q* N; u
  61. 101011111
    ; m  d, b: g8 W+ X
  62. test 5
    & q8 V) I! A  l( ]
  63. 010101111
    - s* ]9 d1 W0 ]! G3 d' x- i
  64. test 6: A4 v8 y# ]+ E3 D- n$ w
  65. 101010111
    ; I: G' j& {% e1 e/ I3 U6 |
  66. test 7
    % z) ~* ^5 X( _  Q4 G( R1 l8 }; @
  67. 0101010103 G7 h0 Y9 R" J+ N6 t, V8 t
  68. test 1
    + u2 {' d$ b: y0 |
  69. 0010101018 e) d9 B6 y$ c
  70. test 2
    # C3 B% y* ^$ h' C8 |8 a
  71. 000101010
    ) _3 J7 O, Z8 ~
  72. test 3
    # B% F+ J1 Q- c: {6 @
  73. 000010101
    5 l; M, G- P9 e4 F# T8 O8 \* h) K
  74. test 4
    # \8 E8 M" l4 e! b
  75. 000001010( o5 s. z# g# O7 E+ p! p
  76. test 5. ^& }# n* t" Z2 A! M
  77. 000000101
    3 X+ a' B7 b4 D+ {8 Y: u/ ~
  78. test 6
    + d% O( B7 Y7 }2 N) y
  79. 000000010$ [5 q# ?5 o3 {2 F0 ^2 m0 S2 V% z
  80. test 79 ~! F7 j9 h2 b+ y; `
  81. 000000000/ ]0 r  C6 L% n, Z

  82. + {, R% n/ e/ q  P1 W4 t
  83. 对于n = 2,4,6,8,10,结果如下:" W0 K& b+ d; N
  84. n = 2
    1 p5 j1 `; B: E* W
  85. 11
    ) g* U9 C  P6 o# n
  86. test 01 r6 o& D+ W4 h$ K  h8 e* A
  87. 10
    $ o5 ?  o7 [/ F* o) ^
  88. test 09 z. S0 E7 Q7 d' D4 \
  89. 00
    ) \+ S1 l- D" s4 n  v/ b

  90. 6 z; {( a* J2 D. B
  91. n = 4
    9 X2 [+ v8 o# F$ D5 ^
  92. 1111
    7 }; N; S7 ]: X* A6 R! d2 L
  93. test 1
    : N* Q9 j& z. a# r2 o+ @
  94. 0111; ?) O5 P0 y) b, Y
  95. test 2- P1 A/ Z! N, z. Q
  96. 1010" _; T, Q. Q4 s- h& d1 e/ s  I
  97. test 2. X$ P8 i# T$ L/ @
  98. 0100
    4 Q3 w* `/ P8 u7 \
  99. test 1$ b+ P9 m1 w$ X
  100. 0000
    5 V: ]" y& V+ h9 e9 Y" k" L
  101. , F: q% v! g3 L& ^
  102. n = 6# S4 x/ s, S  C$ p6 p1 K& h
  103. 111111  E8 C. e/ C* k
  104. test 1) L6 n+ g6 o9 F  a* u
  105. 011111
    * B  ~' v. _% L* {; k* K$ H2 B( C
  106. test 28 f2 i) T* A7 g5 e; z' z# H
  107. 101111: o& X! y, Y: h/ y8 I/ M/ f6 ~
  108. test 3# d" o8 l) u5 {# u/ l; d, ]
  109. 0101110 `0 `: n5 o' X
  110. test 4
    $ @# J- x* q6 T% O8 v
  111. 1010107 u; v4 J% D5 J4 U. H1 u
  112. test 4: p# g/ H8 R; r% z* S, P
  113. 010100; [$ t1 p2 g8 E6 j0 ^$ a
  114. test 3
    3 q& G" E/ l* t# w2 Z, g
  115. 101000! k7 C. O; i; k7 g( E
  116. test 2
    9 `  r0 k1 F: T4 F) E  w
  117. 010000; H+ B1 w" d! K6 |6 u
  118. test 1
    % A) G0 g" D. j2 I
  119. 000000# l# t* r% j. T! h- K( [9 i
  120. + G. m: k, r6 S% H( v6 X: B! X; I
  121. n = 8- x3 e2 e" M: X/ X" `: `: {8 Y
  122. 11111111
    * k# z- \% f5 t* Z# p
  123. test 13 S6 ^9 \1 h- d
  124. 01111111* m" [; B5 t. }# ^$ G- g0 I3 z, ~
  125. test 2/ n) V- ]1 }' l% [( o
  126. 10111111
    ! A7 ]6 n$ |. c: q+ ~
  127. test 3
    1 D& O! [- Q& z6 _% U# b
  128. 01011111
    2 V  a) `' U6 A! _' x
  129. test 4
    / \) ]/ ~4 ^3 Z6 R: i
  130. 10101111
    5 j+ S8 e1 ^0 L  K5 P6 R  e8 h
  131. test 5, n: O* f$ z9 H& t' D- ~3 m
  132. 01010111
    ) p/ j) V5 w7 @: T4 g- g
  133. test 6
    ( \0 f/ m7 ?. `, c3 o3 z
  134. 101010106 j3 P; \9 V" ^* l2 w
  135. test 6# j1 b! F$ @8 p* K" u
  136. 01010100
    + c+ q! X) I6 q  m8 x# L
  137. test 50 I' H- @0 {7 K! d: ^8 I. D4 O
  138. 10101000: p3 p! m! ~2 j6 L1 m
  139. test 4- |5 o# d9 i+ F* a) p+ n8 Y% ^
  140. 01010000
    0 h- e- h* d+ \6 z2 m+ e
  141. test 3
    % n/ _! k+ M$ ~0 k& W$ J4 O
  142. 10100000
    " E; p" V% c0 x. j- ~; c
  143. test 2
    1 v' Q# u: {4 v/ G! S4 v5 a4 F
  144. 01000000% [* M& ?6 l# z4 s
  145. test 1! x5 _9 K  k3 `/ B
  146. 00000000
    9 `; t- o5 `( k1 ?# ?0 E
  147. ! ?2 b5 f0 j( D& d
  148. n = 10
    * j2 Y$ G& k& G. A6 Q
  149. 1111111111
    . G6 L% b: b; r% y
  150. test 1
    * L- {4 P6 _* u' }
  151. 01111111117 F8 c/ N1 m# G4 D+ Y) F6 n
  152. test 2
    . s6 h4 _; U+ d4 z) o: m( R
  153. 1011111111& P7 W: ~% p( D) ?; N, S
  154. test 3+ g. ^) e/ m1 h  _9 _2 S
  155. 0101111111
    - e' ^2 E1 ?% `( e; e( @
  156. test 4
    & V+ \3 }1 f* i: a( L- _
  157. 1010111111
    " {5 B1 I2 W" p+ U
  158. test 5
    ) {$ b0 [: n9 [
  159. 01010111119 Z) w/ c6 J( _$ P, |
  160. test 61 Y) o6 M% ^9 q! A
  161. 10101011112 B, q  n7 W& R6 |! k8 R
  162. test 7! i1 ^8 {+ V% g
  163. 0101010111: @; X" d: g7 t) E& P- k
  164. test 8# I2 c( {7 N4 m8 m
  165. 1010101010$ g% v  o. T  q% _: X0 r
  166. test 8% P) h+ r: w" {1 F
  167. 0101010100
    6 |5 Z+ C. C: k6 z3 B( Y4 a
  168. test 7, ]0 M2 \7 D& b' ?
  169. 1010101000
    ' S" o% K2 I- l1 o9 l! i0 E- N: `
  170. test 6( h) ?7 p  h3 V; K1 u% ]# \0 B
  171. 0101010000
    4 D) k: {4 ?/ S: {% v% x8 T
  172. test 5. D; v# U0 t0 Q) N$ [7 \
  173. 1010100000
    2 t5 |5 w) X+ h* R2 g9 S
  174. test 4. L, N5 N! H6 U
  175. 0101000000* m. t. w, f, n, Q( L
  176. test 3( F- Y: Q7 V3 @1 c  X: B
  177. 1010000000
    + n8 f( [! [" d+ p7 m
  178. test 2
    ' J2 i1 j6 K7 k0 |( W
  179. 0100000000& J, U% m- `8 {* r" K: o6 e
  180. test 18 k" r2 p5 b- _8 U6 b8 i* N
  181. 0000000000
复制代码

) V, T: g8 h9 |* K& G5 B, ?/ X# ?* z; g* o" |8 j5 b
% X* L  ~: E3 t+ c" h/ ~5 w7 U
2^n个状态,直接感觉转化也是指数的,试验发现是线性的。+ W7 @1 v) |3 @
具体规律:
/ t. {* G! M  F* E5 @- R(1) 当n是奇数的时候,检查的房间是从1到(n - 2),再重复检查一次。所以需要2(n - 2)次检查—— n = 1的时候除外
* U) |! x6 `, W" m(2) 当n是偶数的时候,检查的房间是从1到(n - 2),再反过来一次从(n - 2)到1,所以也需要2(n - 2)次检查——n = 2的时候除外。  U5 m4 B/ C  Z$ |& p; Q6 z" w
仔细观察状态变化,其实我们就试图先把状态变成01相间的,缩小小偷活动范围,再把剩余的1逐个变为0。: ]2 ~# D# b4 i+ h3 H
$ d/ P$ p9 N, Q4 k! L" [" J8 u4 l3 F
, \; Q1 R& u4 F+ ~, M  y: Q. a

: m& `7 V4 r% B7 o5 l! v8 L1 L
0 x) @3 m* k- e# u: _- c* ~来源: fb的一个面试题——警察捉小偷
我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!

10

主题

0

精华

132

积分

资深会员

Rank: 2

积分
132
发表于 2-29-2016 06:14 PM | 显示全部楼层
顶一下,赞楼主人品!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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