Dudu Markovitz Dudu Markovitz - 1 month ago 9
SQL Question

SQL Challenge/Puzzle: Given a stack trace - How to find the top element at each point in time?


  • The op column can be removed from the question. When val is NULL then it is a "pop" operation otherwise it is a "push" operation.

  • I can guarantee that solutions exist in Hive, Teradata, Oracle, SQL Server and PostgresSQL



The Puzzle



A table, stack_trace ,contains the following columns:


  • i - Integer value that represents a point in time.

  • op - 2 possible operations: I ("in"/"push") and O ("out"/"pop").

  • val - The value inserted by the "in"/"push" operation or NULL for "out"/"pop" operation.

    The goal is to find what was the value at the top of the stack, at each point in time (i).



e.g.

(NULL values are represented here as empty spaces)

data:

i op val
-- -- --
1 I A
2 I B
3 O
4 I C
5 O
6 O


required result:

i top_of_stack_val
-- ----------------
1 A
2 B
3 A
4 C
5 A
6


Requirements




  • The solution should be a single SQL query (sub-queries are fine).

  • Only the following clauses are allowed: SELECT, FROM, WHERE, GROUP BY, HAVING, ORDER BY.

  • The use of WITH clause (CTE - Common Table Expression) is not allowed.

  • The use of T-SQL, PL/SQL etc. is not allowed.

  • The use of UDF (User Defined Functions) is not allowed.

  • The use of variables is not allowed.



Sample data



create table stack_trace
(
i int
,op char(1)
,val char(1)
)
;

insert into stack_trace (i,op,val) values (1,'I','A');
insert into stack_trace (i,op,val) values (2,'I','B');
insert into stack_trace (i,op,val) values (3,'I','C');
insert into stack_trace (i,op,val) values (4,'I','D');
insert into stack_trace (i,op,val) values (5,'I','E');
insert into stack_trace (i,op) values (6,'O');
insert into stack_trace (i,op) values (7,'O');
insert into stack_trace (i,op) values (8,'O');
insert into stack_trace (i,op,val) values (9,'I','F');
insert into stack_trace (i,op) values (10,'O');
insert into stack_trace (i,op,val) values (11,'I','G');
insert into stack_trace (i,op,val) values (12,'I','H');
insert into stack_trace (i,op) values (13,'O');
insert into stack_trace (i,op) values (14,'O');
insert into stack_trace (i,op,val) values (15,'I','I');
insert into stack_trace (i,op,val) values (16,'I','J');
insert into stack_trace (i,op,val) values (17,'I','K');
insert into stack_trace (i,op,val) values (18,'I','L');
insert into stack_trace (i,op,val) values (19,'I','M');
insert into stack_trace (i,op) values (20,'O');
insert into stack_trace (i,op,val) values (21,'I','N');
insert into stack_trace (i,op) values (22,'O');
insert into stack_trace (i,op,val) values (23,'I','O');
insert into stack_trace (i,op) values (24,'O');
insert into stack_trace (i,op,val) values (25,'I','P');
insert into stack_trace (i,op) values (26,'O');
insert into stack_trace (i,op) values (27,'O');
insert into stack_trace (i,op,val) values (28,'I','Q');
insert into stack_trace (i,op,val) values (29,'I','R');
insert into stack_trace (i,op) values (30,'O');
insert into stack_trace (i,op) values (31,'O');
insert into stack_trace (i,op) values (32,'O');
insert into stack_trace (i,op) values (33,'O');
insert into stack_trace (i,op) values (34,'O');
insert into stack_trace (i,op) values (35,'O');
insert into stack_trace (i,op,val) values (36,'I','S');
insert into stack_trace (i,op) values (37,'O');
insert into stack_trace (i,op) values (38,'O');
insert into stack_trace (i,op,val) values (39,'I','T');
insert into stack_trace (i,op,val) values (40,'I','U');
insert into stack_trace (i,op) values (41,'O');
insert into stack_trace (i,op,val) values (42,'I','V');
insert into stack_trace (i,op,val) values (43,'I','W');
insert into stack_trace (i,op,val) values (44,'I','X');
insert into stack_trace (i,op) values (45,'O');
insert into stack_trace (i,op) values (46,'O');
insert into stack_trace (i,op,val) values (47,'I','Y');
insert into stack_trace (i,op) values (48,'O');
insert into stack_trace (i,op) values (49,'O');
insert into stack_trace (i,op,val) values (50,'I','Z');
insert into stack_trace (i,op) values (51,'O');
insert into stack_trace (i,op) values (52,'O');


Required results



i top_of_stack_val
-- ----------------
1 A
2 B
3 C
4 D
5 E
6 D
7 C
8 B
9 F
10 B
11 G
12 H
13 G
14 B
15 I
16 J
17 K
18 L
19 M
20 L
21 N
22 L
23 O
24 L
25 P
26 L
27 K
28 Q
29 R
30 Q
31 K
32 J
33 I
34 B
35 A
36 S
37 A
38
39 T
40 U
41 T
42 V
43 W
44 X
45 W
46 V
47 Y
48 V
49 T
50 Z
51 T
52

Answer

Although it does require an additional step -

Generic solution for Hive, Teradata, Oracle, SQL Server and PostgresSQL

select      s.i

           ,min (s.val) over
            (
                partition by    s.depth
                               ,s.depth_val_seq
            )                                   as top_of_stack_val            

from       (select      s.i
                       ,s.val
                       ,s.depth

                       ,count (s.val) over 
                        (
                            partition by    s.depth
                            order by        s.i
                            rows            between unbounded preceding and current row
                        )                                                                   as depth_val_seq

            from       (select      s.i
                                   ,s.val

                                   ,sum (case s.op when 'I' then 1 else -1 end)   over
                                    (
                                        order by        s.i
                                        rows            between unbounded preceding and current row
                                    )                                                                   as depth

                        from        stack_trace s
                        )
                        s
            )
            s

order by    i
;
Comments