SQL 电面试题

贴一个今天一家大保险公司的SQL电面试题：

1. Given a table numbers that has column "n" which is a sequence of integers with a step of 3, find the gap:

numbers
+--+
|n |
+--+
|3 |
|6 |
|9 |
|12|
|18|
+--+

write a query: Expected Output: 15

我写好一个QUERY, 看哪位大神有更好思路，都是实战面试题。

如果知道只有最多一个gap number的话，那用一个lead lag function就可以了。如果
gap number数目不定的话，我觉得可能要用一个recursive cte。

【 在 river08 (sh) 的大作中提到: 】
: 贴一个今天一家大保险公司的SQL电面试题：
: 1. Given a table numbers that has column "n" which is a sequence of
integers
: with a step of 3, find the gap:
: numbers
: +--+
: |n |
: +--+
: |3 |
: |6 |
: |9 |
: ...................

发个图。

【 在 TheMatrix (TheMatrix) 的大作中提到: 】
: 如果知道只有最多一个gap number的话，那用一个lead lag function就可以了。如果
: gap number数目不定的话，我觉得可能要用一个recursive cte。
: integers

first generate a column called ID = identity (1,1). 也就是每一行都有了一个
ID，从1 开始增加直到最后一行。 然后就 select * from numbers where ID * 3 <> n

上机试了一下，aggregate function max不能用在recursive cte的recursive部分，
max number要提出来，用join。见图。

【 在 TheMatrix (TheMatrix) 的大作中提到: 】
: 发个图。

recursive cte的问题是有depth限制，sql server上缺省是100层，这是很小的，指望
它做循环是不行的。

所以这里要有一个生成循环index的方法。一般实际问题中数据table或者它的join就是足够的空间。这个问题中，也可以写一个join recursive cte用指数函数方式生成
index空间。

【 在 TheMatrix (TheMatrix) 的大作中提到: 】
: 上机试了一下，aggregate function max不能用在recursive cte的recursive部分，: max number要提出来，用join。见图。

用2的指数函数的方式生成了index空间，recursive cte 100层的限制不是问题了，可
以生成2^100 index空间。见图。

【 在 TheMatrix (TheMatrix) 的大作中提到: 】
: recursive cte的问题是有depth限制，sql server上缺省是100层，这是很小的，指望
: 它做循环是不行的。
: 所以这里要有一个生成循环index的方法。一般实际问题中数据table或者它的join就是
: 足够的空间。这个问题中，也可以写一个join recursive cte用指数函数方式生成
: index空间。

recursive cte据说效率低下，我觉得可能还是和循环次数有关，如果循环次数少应该
没有问题吧？这个我不太清楚。sql我是以逻辑的方式在用，内部实现效率我不熟悉。

比如一个经典的自join问题，manager employee link table，打印全部manager
employee path。如果知道path长度不太长，那么用recursive cte应该不会影响效率吧？

【 在 TheMatrix (TheMatrix) 的大作中提到: 】
: 用2的指数函数的方式生成了index空间，recursive cte 100层的限制不是问题了，可
: 以生成2^100 index空间。见图。

是我想的太简单了？

SELECT prevnum + 3
FROM ( SELECTn, LAG(n,1) OVER(ORDER BY n) AS prevnum
FROM numbers)
WHERE prevnum IS NOT NULL AND n - prevnum <> 3

【 在 river08 (sh) 的大作中提到: 】
: 贴一个今天一家大保险公司的SQL电面试题：
: 1. Given a table numbers that has column "n" which is a sequence of
integers
: with a step of 3, find the gap:
: numbers
: +--+
: |n |
: +--+
: |3 |
: |6 |
: |9 |
: ...................

現在面試出這麼難的題。 看來我再也找不到工作了。

你这个只能找gap为一个的情况。

【 在 gunu (败家女) 的大作中提到: 】
: 是我想的太简单了？
: SELECT prevnum + 3
: FROM ( SELECTn, LAG(n,1) OVER(ORDER BY n) AS prevnum
: FROM numbers)
: WHERE prevnum IS NOT NULL AND n - prevnum <> 3

nope,
2,5,8,11,14,17,23,26,29,32,38
output
20
35

哦我的意思是gap长度，不是gap数量。

【 在 gunu (败家女) 的大作中提到: 】
: nope,
: 2,5,8,11,14,17,23,26,29,32,38
: output
: 20
: 35

自己创造一个正常的列有所有的值，然后去查这个检测的列，凡是查不到的，都是缺失的。。。想那么麻烦干嘛？

Try the solution in the attachment

【 在 river08 (sh) 的大作中提到: 】
: 贴一个今天一家大保险公司的SQL电面试题：
: 1. Given a table numbers that has column "n" which is a sequence of
integers
: with a step of 3, find the gap:
: numbers
: +--+
: |n |
: +--+
: |3 |
: |6 |
: |9 |
: ...................

我用tsql试了一下：

Declare @row int, @max int, @s int, @e int
Declare @table Table (n int)

If Object_ID('tempdb..#table') is not null Drop Table #table
Select pn, n, Row_Number() Over (Order By n) rn Into #table
From
(
Select n, LAG(n,1,0) Over (Order By n) pn, n-LAG(n,1,0) Over (Order By n) dnFrom [table]) t
Where t.dn > 3

Select @max = Count(*) From #table
Set @row = 1
While @row <[email protected]
BEGIN
Select @s = pn+3, @e = n From #table
Where rn = @row
While @s < @e
BEGIN
insert into @table
select @s
Set @s = @s + 3
END
Set @row = @row + 1
End

Select n from @table

跟我的第一个solution几乎一样。

我想起了Ken Thompson说，有一次和好像是Ritchie，两个人不小心各写了一段程序，C语言的，完成同一个任务，第二天俩人一对照发现一摸一样，literally。

【 在 duobaobei (多宝花蓓) 的大作中提到: 】
: Try the solution in the attachment
: integers

aggregate function好像不能直接用在recursive cte里面，可以考虑先赋值给变量后
再做recursive。

【 在 duobaobei (多宝花蓓) 的大作中提到: 】
: Try the solution in the attachment
: integers

如果有连续两个missing, 会有问题。
18，21，30。。。

【 在 gunu (败家女) 的大作中提到: 】
: nope,
: 2,5,8,11,14,17,23,26,29,32,38
: output
: 20
: 35

不用那么麻烦,self join可以解决

select a.n
from numberTable a
where not exists (select b.n from numberTable b where a.n + 3 = b.n )

你这个结果不对，output should by 15

【 在 coolbid (Dreams bring hopes) 的大作中提到: 】
: 不用那么麻烦,self join可以解决
: select a.n
: from numberTable a
: where not exists (select b.n from numberTable b where a.n + 3 = b.n )

这是我写的：

With CTE As
(
Select n,
Lead(n,1,0) Over (Order by n) as NextN
From numbers
)
Select
MAX(Case When n+3 = NextN or NextN =0 then 0
else n+3 end ) As GapNumber
From CTE

这是我写的：

With CTE As
(
Select n,
Lead(n,1,0) Over (Order by n) as NextN
From numbers
)
Select
MAX(Case When n+3 = NextN or NextN =0 then 0
else n+3 end ) As GapNumber
From CTE

你这个参见前面用lag写的那个算法。问题也是一样的。

【 在 river08 (sh) 的大作中提到: 】
: 这是我写的：
: With CTE As
: (
: Select n,
: Lead(n,1,0) Over (Order by n) as NextN
: From numbers
: )
: Select
: MAX(Case When n+3 = NextN or NextN =0 then 0
: else n+3 end ) As GapNumber
: ...................

这个逻辑比较清晰：

SELECT A.[ROW_NUMBER] * 3 AS [GAP]
FROM
(SELECT
ROW_NUMBER() OVER (ORDER BY [n]) AS [ROW_NUMBER],
[n],
LAG([n]) OVER (ORDER BY [n]) AS [PREVIOUS_VALUE]
FROM [numbers]
) AS A
WHERE A.[n] - A.[PREVIOUS_VALUE] >3;

这不是一样吗？你把18换成21，其他数不变，你看看结果。

【 在 river08 (sh) 的大作中提到: 】
: 这个逻辑比较清晰：
: SELECT A.[ROW_NUMBER] * 3 AS [GAP]
: FROM
: (SELECT
: ROW_NUMBER() OVER (ORDER BY [n]) AS [ROW_NUMBER],
: [n],
: LAG([n]) OVER (ORDER BY [n]) AS [PREVIOUS_VALUE]
: FROM [numbers]
: ) AS A
: WHERE A.[n] - A.[PREVIOUS_VALUE] >3;

问题变成找一个等差数列中缺那几个数了，那就一个一个查呗，all_tab_columns 可以换成任意一个有足够行数的systable.

怎么贴的图？不让贴code了

选择 (ROWNUM-1) * 3 + (选择MIN(n) 从 NUMBERS)
从 all_tab_COLUMNS
哪里 ROWNUM <= (选择(MAX(n) - MIN(n))/3 + 1 从 NUMBERs)
和 (ROWNUM-1) * 3 + (选择 MIN(n) 从 NUMBERS)
NOT IN (选择 N 从 NUMBERS)

嗯，这个问题的本质就是需要一个足够长的table，用的也只是它的row number。

【 在 gunu (败家女) 的大作中提到: 】
: 问题变成找一个等差数列中缺那几个数了，那就一个一个查呗，all_tab_columns 可以
: 换成任意一个有足够行数的systable.
: 怎么贴的图？不让贴code了
: 选择 (ROWNUM-1) * 3 + (选择MIN(n) 从 NUMBERS)
: 从 all_tab_COLUMNS
: 哪里 ROWNUM <= (选择(MAX(n) - MIN(n))/3 + 1 从 NUMBERs)
: 和 (ROWNUM-1) * 3 + (选择 MIN(n) 从 NUMBERS)
: NOT IN (选择 N 从 NUMBERS)

发现这Row_Number * 3 结果不对，if have more than one gap number
【 在 TheMatrix (TheMatrix) 的大作中提到: 】
: 这不是一样吗？你把18换成21，其他数不变，你看看结果。

This one also work, but litter confuse with sub query self join:

SELECT (n + 3) As GapNum
FROM numbers as n1
WHERE NOT EXISTS
(
SELECT NULL
FROM numbers as n2
WHERE n2.n = n1.n + 3
)

你的几个算法都有同样的问题，就是只能选出gap长度为1的gap number。

【 在 river08 (sh) 的大作中提到: 】
: This one also work, but litter confuse with sub query self join:
: SELECT (n + 3) As GapNum
: FROM numbers as n1
: WHERE NOT EXISTS
: (
: SELECT NULL
: FROM numbers as n2
: WHERE n2.n = n1.n + 3
: )

这个query本身没有问题，subquery可以引用主query的table。其中的column name用
scope确定。

【 在 river08 (sh) 的大作中提到: 】
: This one also work, but litter confuse with sub query self join:
: SELECT (n + 3) As GapNum
: FROM numbers as n1
: WHERE NOT EXISTS
: (
: SELECT NULL
: FROM numbers as n2
: WHERE n2.n = n1.n + 3
: )

--In Oracle
select n from (
select level * 3 as n from dual
connect by level <= (select max(n)/3 from numbers))
where n >= (select min(n) from numbers)
minus
select n from numbers;

【 在 TheMatrix (TheMatrix) 的大作中提到: 】
: 你的几个算法都有同样的问题，就是只能选出gap长度为1的gap number。

oracle好像有不少自己的关键字。

【 在 alexandria05 (alex) 的大作中提到: 】
: --In Oracle
: select n from (
: select level * 3 as n from dual
: connect by level <= (select max(n)/3 from numbers))
: where n >= (select min(n) from numbers)
: minus
: select n from numbers;