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

0x0x0x · 发表于 2012-5-22 12:34

我用心算算出是17
用SQL没试过~
不过我在书城的一本剑破冰山的书中好像见到过~

0x0x0x · 发表于 2012-6-20 11:06

回头看看这题，感觉不用递归也行

SQL> with t as
  2  (select rownum rn,t.name,t.time from bridge_crossing t),
  3  tt as (select t1.name n1,t2.name n2,t3.name n3,t4.name n4,t5.name n5,t6.name n6,
  4  t1.time time1,t2.time time2,t3.time time3,t4.time time4,t5.time time5,t6.time time6,
  5  greatest(t1.time,t2.time)+least(t1.time,t2.time)+
  6  greatest(t3.time,t4.time)+
  7  least(greatest(t1.time,t2.time),t3.time,t4.time)+
  8  greatest(t5.time,t6.time) sum_time
  9  from t t1,t t2,t t3,t t4,t t5,t t6
10  where t1.name<>t2.name and t3.name<>t4.name and t1.name<>t6.name
11  and t1.rn<t2.rn and t3.rn<t4.rn and t5.rn<t6.rn
12  and instr(t1.name||t2.name||t3.name||t4.name||t1.name||t6.name,'A',1,1)>0
13  and instr(t1.name||t2.name||t3.name||t4.name||t1.name||t6.name,'B',1,1)>0
14  and instr(t1.name||t2.name||t3.name||t4.name||t1.name||t6.name,'C',1,1)>0
15  and instr(t1.name||t2.name||t3.name||t4.name||t1.name||t6.name,'D',1,1)>0 ),
16  ttt as (select min(sum_time) min_time from tt)
17  select n1,n2,n3,n4,n5,n6,sum_time from tt,ttt where tt.sum_time=ttt.min_time
18  /

N1       N2       N3       N4       N5       N6          SUM_TIME
---------- ---------- ---------- ---------- ---------- ---------- ----------
A       B       C       D       A       B                17

SQL>

解释下：第一次是N1N2过去，第二次N3N4过去,第三次N5N6过去

newkid · 发表于 2012-6-21 04:26

0x0x0x 发表于 2012-6-20 11:06
回头看看这题，感觉不用递归也行

最后那一堆instr条件是什么意思？为什么没有t5而t1出现两次？
你这个写法局限性很大。join的次数是固定的，受限于人数；现在的sum_time计算公式已经这么复杂，而且仅限于每次两人，很难再扩展。

0x0x0x · 发表于 2012-6-21 08:34

newkid 发表于 2012-6-21 04:26
最后那一堆instr条件是什么意思？为什么没有t5而t1出现两次？
你这个写法局限性很大。join的次数是固定的 ...

一堆instr是为了过滤掉不合理的排列组合，t5 t1的问题是打错字。已更正。
这种自连接的写法的确是局限性很大。
木办法，我还是不太适应用SQL写复杂的递归查询！

尽管这个语句有很大的局限性，我还是决定更正过来：

SQL> set timing on;
SQL> with t as
  2  (select rownum rn,t.name,t.time from bridge_crossing t),
  3  tt as (select t1.name n1,t2.name n2,t3.name n3,t4.name n4,t5.name n5,t6.name n6,
  4  t1.time time1,t2.time time2,t3.time time3,t4.time time4,t5.time time5,t6.time time6,
  5  greatest(t1.time,t2.time)+least(t1.time,t2.time)+
  6  greatest(t3.time,t4.time)+
  7  least(greatest(t1.time,t2.time),t3.time,t4.time)+
  8  greatest(t5.time,t6.time) sum_time
  9  from t t1,t t2,t t3,t t4,t t5,t t6
10  where t1.name<>t2.name and t3.name<>t4.name and t5.name<>t6.name
11  and t1.rn<t2.rn and t3.rn<t4.rn and t5.rn<t6.rn
12  and instr(t1.name||t2.name||t3.name||t4.name||t5.name||t6.name,'A',1,1)>0
13  and instr(t1.name||t2.name||t3.name||t4.name||t5.name||t6.name,'B',1,1)>0
14  and instr(t1.name||t2.name||t3.name||t4.name||t5.name||t6.name,'C',1,1)>0
15  and instr(t1.name||t2.name||t3.name||t4.name||t5.name||t6.name,'D',1,1)>0
16  and t1.name||t2.name<>t3.name||t4.name
17  and t3.name||t4.name<>t5.name||t6.name),
18  ttt as (select min(sum_time) min_time from tt)
19  select n1,n2,n3,n4,n5,n6,sum_time from tt,ttt where tt.sum_time=ttt.min_time
20  /

N1       N2       N3       N4       N5       N6          SUM_TIME
---------- ---------- ---------- ---------- ---------- ---------- ----------
A       B       C       D       A       B                17

已用时间:  00: 00: 00.09
SQL>