趣味SQL：微软面试题：过河

chrisrate · 发表于 2012-3-28 16:35

说明：
A、B 过去 2 分钟
A 返回 1 分钟
C、D 过去 10 分钟
B 返回 2 分钟
A、B 过去 2 分钟

A B, A, C D, B, A B 17

oversoul · 发表于 2012-3-28 19:17

SELECT pass,time
FROM    (SELECT    LEVEL lvl,
                  LTRIM (SYS_CONNECT_BY_PATH (UPPER (NAME), ','), ',') pass,
                  REPLACE (SYS_CONNECT_BY_PATH (NAME, ','), ',', '') str,
                  dbms_aw.eval_number (LTRIM (SYS_CONNECT_BY_PATH (TIME, '+'), '+'))
                                                                                 time
      FROM    (SELECT LOWER (NAME) NAME, TIME, 1 num
                  FROM bridge_crossing
                  UNION
                  SELECT a.NAME || b.NAME, GREATEST (a.TIME, b.TIME), 2 num
                  FROM bridge_crossing a, bridge_crossing b
                  WHERE  a.NAME < b.NAME)
      START WITH num = 2
      CONNECT BY DBMS_RANDOM.VALUE IS NOT NULL
      AND       LEVEL <= 5
      AND       MOD (LEVEL, 2) + 1 = num)
WHERE lvl = 5
AND    REPLACE (REPLACE (TRANSLATE (str, 'BCDbcd', ' '), ' ', ''), 'Aa', '') = 'A'
AND    INSTR (REPLACE (TRANSLATE (str, 'BCDbcd', ' '), ' ', ''), 'AA', 1) = 0
AND    INSTR (REPLACE (TRANSLATE (str, 'BCDbcd', ' '), ' ', ''), 'aa', 1) = 0
AND    REPLACE (REPLACE (TRANSLATE (str, 'ACDacd', ' '), ' ', ''), 'Bb', '') = 'B'
AND    INSTR (REPLACE (TRANSLATE (str, 'ACDacd', ' '), ' ', ''), 'BB', 1) = 0
AND    INSTR (REPLACE (TRANSLATE (str, 'ACDacd', ' '), ' ', ''), 'bb', 1) = 0
AND    REPLACE (REPLACE (TRANSLATE (str, 'ABDabd', ' '), ' ', ''), 'Cc', '') = 'C'
AND    INSTR (REPLACE (TRANSLATE (str, 'ABDabd', ' '), ' ', ''), 'CC', 1) = 0
AND    INSTR (REPLACE (TRANSLATE (str, 'ABDabd', ' '), ' ', ''), 'cc', 1) = 0
AND    REPLACE (REPLACE (TRANSLATE (str, 'ABCabc', ' '), ' ', ''), 'Dd', '') = 'D'
AND    INSTR (REPLACE (TRANSLATE (str, 'ABCabc', ' '), ' ', ''), 'DD', 1) = 0
AND    INSTR (REPLACE (TRANSLATE (str, 'ABCabc', ' '), ' ', ''), 'dd', 1) = 0
ORDER BY time

Row# PASS TIME
----------------------------------------------
1 AB,A,CD,B,AB 17
2 AB,B,CD,A,AB 17
3 AB,A,AC,A,AD 19
4 AC,A,AD,A,AB 19
5 AD,A,AC,A,AB 19
6 AD,A,AB,A,AC 19
7 AC,A,AB,A,AD 19
8 AB,A,AD,A,AC 19
9 AB,A,AC,B,BD 20
10 BD,B,AC,A,AB 20
11 BD,B,AB,A,AC 20
12 BC,B,AD,A,AB 20
13 BC,B,AB,A,AD 20
14 AB,B,BD,A,AC 20
15 AB,A,AD,B,BC 20
16 AC,A,BD,B,AB 20
17 AD,A,BC,B,AB 20
18 AD,A,AB,B,BC 20
19 AC,A,AB,B,BD 20
20 AB,B,BC,A,AD 20
21 AB,B,BC,B,BD 21
22 BD,B,BC,B,AB 21
23 BD,B,AB,B,BC 21
24 BC,B,BD,B,AB 21
25 BC,B,AB,B,BD 21
26 AB,B,BD,B,BC 21
27 AB,A,AC,C,CD 23
28 AC,A,AB,C,CD 23
29 CD,C,AB,A,AC 23
30 CD,C,AC,A,AB 23
31 AB,A,CD,C,AC 23
32 AC,C,CD,A,AB 23
33 AB,B,BC,C,CD 24
34 AB,B,CD,C,BC 24
35 CD,C,BC,B,AB 24
36 CD,C,AB,B,BC 24
37 BC,C,CD,B,AB 24
38 BC,B,AB,C,CD 24
39 AC,A,AD,C,BC 26
40 AC,C,BC,A,AD 26
41 BC,C,AD,A,AC 26
42 BC,C,AC,A,AD 26
43 AD,A,BC,C,AC 26
44 AD,A,AC,C,BC 26
45 AC,C,BD,A,AC 26
46 AC,A,BD,C,AC 26
47 AC,C,BC,B,BD 27
48 BC,C,AC,B,BD 27
49 BD,B,BC,C,AC 27
50 BD,B,AC,C,BC 27
51 BC,C,AD,B,BC 27
52 BC,B,BD,C,AC 27
53 BC,B,AD,C,BC 27
54 AC,C,BD,B,BC 27
55 AC,C,BC,C,CD 30
56 BC,C,AC,C,CD 30
57 AC,C,CD,C,BC 30
58 CD,C,AC,C,BC 30
59 CD,C,BC,C,AC 30
60 BC,C,CD,C,AC 30
61 AB,A,AD,D,CD 33
62 AD,A,AB,D,CD 33
63 CD,D,AD,A,AB 33
64 CD,D,AB,A,AD 33
65 AD,D,CD,A,AB 33
66 AB,A,CD,D,AD 33
67 AB,B,BD,D,CD 34
68 AB,B,CD,D,BD 34
69 BD,B,AB,D,CD 34
70 CD,D,BD,B,AB 34
71 CD,D,AB,B,BD 34
72 BD,D,CD,B,AB 34
73 AC,A,AD,D,BD 36
74 AD,A,BC,D,AD 36
75 AD,D,BC,A,AD 36
76 AD,D,BD,A,AC 36
77 AD,A,AC,D,BD 36
78 BD,D,AD,A,AC 36
79 BD,D,AC,A,AD 36
80 AC,A,BD,D,AD 36
81 AD,D,BC,B,BD 37
82 BC,B,BD,D,AD 37
83 BD,D,AD,B,BC 37
84 CD,D,AB,C,CD 37
85 CD,C,AB,D,CD 37
86 BD,D,AC,B,BD 37
87 BD,B,BC,D,AD 37
88 BD,B,AC,D,BD 37
89 BC,B,AD,D,BD 37
90 AD,D,BD,B,BC 37
91 AC,C,BD,D,CD 40
92 CD,D,BD,C,AC 40
93 CD,D,AD,C,BC 40
94 CD,C,BC,D,AD 40
95 CD,C,AC,D,BD 40
96 BD,D,CD,C,AC 40
97 BD,D,AC,C,CD 40
98 BC,C,CD,D,AD 40
99 BC,C,AD,D,CD 40
100 AD,D,CD,C,BC 40
101 AC,C,CD,D,BD 40
102 AD,D,BC,C,CD 40
103 AD,D,BD,D,CD 50
104 CD,D,AD,D,BD 50
105 CD,D,BD,D,AD 50
106 BD,D,CD,D,AD 50
107 BD,D,AD,D,CD 50
108 AD,D,CD,D,BD 50

changhe325 · 发表于 2012-3-28 20:18

最笨的方法写了个加了注释：
SELECT * FROM (
SELECT
a.NAME||b.NAME first_go,
c.NAME first_back,
d.NAME||E.NAME second_go,
f.NAME second_back,
f.NAME||G.NAME last_go,
greatest(a.TIME,b.TIME)+c.TIME+greatest(d.TIME,E.TIME)+f.TIME+greatest(f.TIME,G.TIME) total_time
FROM bridge_crossing a,bridge_crossing b,bridge_crossing c,bridge_crossing d,bridge_crossing E,bridge_crossing f,bridge_crossing G
WHERE 1=1
AND a.NAME <> b.NAME --简单判断，两个去的人不同↓
AND d.NAME <> E.NAME
AND f.NAME <> G.NAME --简单判断，两个去的人不同↑
)
WHERE 1=1
AND instr(first_go,first_back)>0 --第一次回来的在第一次去的人当中
AND instr(REGEXP_REPLACE(first_go,first_back,'')||second_go,second_back )>0--第二次回来的在第一次去除去第一次回加上第二次去的人当中
AND instr(REPLACE(REPLACE(first_go,first_back,'')||second_go ,second_back,'')||last_go ,'A')>0--保证都到对岸了↓
AND instr(REPLACE(REPLACE(first_go,first_back,'')||second_go ,second_back,'')||last_go ,'B')>0
AND instr(REPLACE(REPLACE(first_go,first_back,'')||second_go ,second_back,'')||last_go ,'C')>0
AND instr(REPLACE(REPLACE(first_go,first_back,'')||second_go ,second_back,'')||last_go ,'D')>0--保证都到对岸了↑
ORDER BY total_time

FIRST_GO FIRST_BACK SECOND_GO SECOND_BACK LAST_GO TOTAL_TIME

BA A DC B BA 17
AB A DC B BA 17
BA A CD B BA 17
AB A CD B BA 17
BA B DC A AB 17
AB B DC A AB 17
BA B CD A AB 17
AB B CD A AB 17
DA A CA A AB 19
AD A CA A AB 19
CA A DA A AB 19
AC A DA A AB 19
DA A AC A AB 19
AD A AC A AB 19
CA A AD A AB 19

没法去重。。

newkid · 发表于 2012-3-28 21:09

lugionline 发表于 2012-3-28 10:03
记在左岸为0，在右岸为1，于是问题化为：
求状态空间 (0,0,0,0, 0) 到 (1,1,1,1, 1)的最短路径 // 前面四个 ...

一看就是行家出手！
我也是用的这个方法，只不过我没把手电筒当作一位而是单独的一列，但原理是一样的。
你来写个SQL SERVER的？我知道你们有CTE可用。我负责翻译成ORACLE语法。

newkid · 发表于 2012-3-28 21:12

oversoul 发表于 2012-3-28 19:17
SELECT pass,time
FROM (SELECT LEVEL lvl,
LTRIM (SYS_CONNECT_BY_PATH ( ...

你的CONNECT BY中没有前后关系，就是一种状态怎么有效地变为另一种，这样中间结果集会很大，你再用WHERE事后过滤，效率不够理想。

newkid · 发表于 2012-3-28 21:16

changhe325 发表于 2012-3-28 20:18
最笨的方法写了个加了注释：
SELECT * FROM (
SELECT

把WHERE变成：
AND a.NAME < b.NAME
AND d.NAME < E.NAME
AND f.NAME < G.NAME
可以去除重复，因为同一批过去的两个人就无所谓先后。
这个方法还是固定人数的。

guostong · 发表于 2012-3-28 22:02

本帖最后由 guostong 于 2012-3-28 09:08 编辑

递归写法，可以任意个人：

with steps (name, past_name, back_name, time, step) as
(
  select a1.name || b1.name name ,a1.name || b1.name past_name ,  '' back_name,
greatest(a1.time, b1.time)  time, 1 step
from bridge_crossing a1, bridge_crossing b1
where a1.name < b1.name
  union all
  select case when mod(s.step,2) = 1 then replace(s.name, ax.name, '')
            else s.name || ax.name || bx.name
      end name,
      case when mod(s.step,2) = 1 then s.past_name
            else s.past_name || ax.name || bx.name
      end past_name,
      case when mod(s.step,2) = 0 then s.back_name
            else s.back_name || ax.name
      end back_name,
      case when mod(s.step,2) = 1 then s.time + ax.time
            else s.time + greatest(ax.time, bx.time)
      end time,
      s.step + 1 step
from steps s, bridge_crossing ax, bridge_crossing bx
where s.step < (select count(1)-1 + count(1)-2 from bridge_crossing)
and
(
   mod(s.step,2) = 1 and instr(s.name, ax.name) > 0 and bx.name = ax.name
   or
   mod(s.step,2) = 0 and instr(s.name, ax.name) = 0 and instr(s.name, bx.name) = 0
      and ax.name < bx.name
)
)
select * from steps where step = (select count(1)-1 + count(1)-2 from bridge_crossing)
order by time;

NAME    PAST_NAME  BACK_NAME       TIME    STEP
---------- ---------- ---------- ---------- ----------
CDAB    ABCDAB    BA                17       5
CDAB    ABCDAB    AB                17       5
DBAC    ADABAC    AA                19       5
DCAB    ADACAB    AA                19       5
CBAD    ACABAD    AA                19       5
CDAB    ACADAB    AA                19       5
BDAC    ABADAC    AA                19       5
BCAD    ABACAD    AA                19       5
ACBD    ABACBD    AB                20       5
ADBC    ABADBC    AB                20       5
BCAD    ABBCAD    BA                20       5

guostong · 发表于 2012-3-28 22:37

guostong 发表于 2012-3-28 09:02
递归写法，可以任意个人：

with steps (name, past_name, back_name, time, step) as

人多了效率有点问题

guostong · 发表于 2012-3-28 22:50

本帖最后由 guostong 于 2012-3-28 11:36 编辑

加上对回头的人的限制以后，效率好多了。
规定用最快两个人做回送。

with
messenger as
( select name from
(select name, rank() over(order by time) as od from bridge_crossing)
  where od <= 2
),
steps (name, past_name, back_name, time, step) as
(
  select a1.name || b1.name name ,a1.name || b1.name past_name ,  '' back_name,
greatest(a1.time, b1.time)  time, 1 step
from bridge_crossing a1, bridge_crossing b1
where a1.name < b1.name
  union all
  select case when mod(s.step,2) = 1 then replace(s.name, ax.name, '')
            else s.name || ax.name || bx.name
      end name,
      case when mod(s.step,2) = 1 then s.past_name
            else s.past_name || ax.name || bx.name
      end past_name,
      case when mod(s.step,2) = 0 then s.back_name
            else s.back_name || ax.name
      end back_name,
      case when mod(s.step,2) = 1 then s.time + ax.time
            else s.time + greatest(ax.time, bx.time)
      end time,
      s.step + 1 step
from steps s, bridge_crossing ax, bridge_crossing bx
where s.step < (select count(1)-1 + count(1)-2 from bridge_crossing)
and
(
   mod(s.step,2) = 1 and instr(s.name, ax.name) > 0 and bx.name = ax.name
      and ax.name in (select name from messenger)
   or
   mod(s.step,2) = 0 and instr(s.name, ax.name) = 0 and instr(s.name, bx.name) = 0
      and ax.name < bx.name
)
)
select * from steps where step = (select count(1)-1 + count(1)-2 from bridge_crossing)
order by time;

guostong · 发表于 2012-3-29 00:34

本帖最后由 guostong 于 2012-3-28 13:11 编辑

扩展到桥的容量为3个人：

-- 3 poeple
with
t_accessory (totalsteps, cnt, md) as
(
  select round((count(1)-3)/2)*2+1 totalsteps, count(1) cnt, mod(count(1)-1,2) md from bridge_crossing
)
,
steps (name, past_name, back_name, time, step) as
(
  select a1.name || b1.name || c1.name name ,
   a1.name || b1.name || c1.name past_name ,  '' back_name,
greatest(a1.time, b1.time, c1.time)  time, 1 step
from bridge_crossing a1, bridge_crossing b1, bridge_crossing c1
where a1.name < b1.name and b1.name < c1.name
  union all
  select case when mod(s.step,2) = 1 then replace(s.name, ax.name, '')
            else
            case when t.totalsteps > s.step + 1 or t.totalsteps = s.step + 1 and t.md = 0 then
                        s.name || ax.name || bx.name || cx.name
                     when t.totalsteps =  s.step + 1 and t.md <> 0 then
                        s.name || ax.name || bx.name
                     else
                     s.name
            end
      end name,
      case when mod(s.step,2) = 1 then s.past_name
            else
               case when t.totalsteps > s.step + 1 or t.totalsteps = s.step + 1 and t.md = 0 then
                        s.past_name || ax.name || bx.name || cx.name
                     when t.totalsteps =  s.step + 1 and t.md <> 0 then
                        s.past_name || ax.name || bx.name
                     else
                     s.past_name
               end
      end past_name,
      case when mod(s.step,2) = 0 then s.back_name
            else s.back_name || ax.name
      end back_name,
      case when mod(s.step,2) = 1 then s.time + ax.time
            else s.time + greatest(ax.time, bx.time, cx.time)
      end time,
      s.step + 1 step
from steps s, bridge_crossing ax, bridge_crossing bx, bridge_crossing cx, t_accessory t
where s.step < t.totalsteps
and
(
   mod(s.step,2) = 1 and instr(s.name, ax.name) > 0 and bx.name = ax.name and cx.name = ax.name
   or
   mod(s.step,2) = 0
   and
   ( (t.totalsteps > s.step + 1 or t.totalsteps = s.step + 1 and t.md = 0)
      and instr(s.name, ax.name) = 0 and instr(s.name, bx.name) = 0 and instr(s.name, cx.name) = 0
      and ax.name < bx.name
      and bx.name < cx.name
   or
      t.totalsteps =  s.step + 1 and t.md <> 0
      and instr(s.name, ax.name) = 0 and instr(s.name, bx.name) = 0
      and ax.name < bx.name
   )
)
)
select steps.* from steps, t_accessory t where step = t.totalsteps order by time;

[精华] 趣味SQL：微软面试题：过河