SELECT SomeColumn where SUM(SomeOtherColumn) of any N rows or less is a certain value

Question

I got totally stumped by this skill assessment question. The skill assessment is done. I am too old to use SO to cheat my way through... Just curious how to solve this.

You have a table with the following columns:

Sender | Recipient | Date | Amount

How would you select all Recipients that each have a sum of ANY 3 or fewer amounts that is greater than or equal to X?

For example:

Sender  | Recipient |    Date    | Amount
--------+-----------+------------+-------
William | Jane      | 2016-05-27 |  $1243
Sarah   | Josh      | 2016-05-12 |   $500
Rohit   | Tammy     | 2016-05-24 |   $200
Jacob   | Josh      | 2016-05-17 |   $500
Abraham | Josh      | 2016-05-15 |    $10
Marie   | Vivian    | 2016-05-16 |  $1243    
Alex    | Josh      | 2016-05-07 |   $150

If X = $1024, you should get Jane, Vivian and Josh. Josh, because $500 + $500 + $150 > $1024.

SOLUTION All the three solutions worked. Thanks so much guys. Really appreciate it.

Chose @Tim Biegeleisen's answer for the simplicity factor.

http://stackoverflow.com/questions/2617661/whats-the-execute-order-of-the-different-parts-of-a-sql-select-statement look at the clauses of a sql query, there is a specific one for yor need — Paul Maxwell, May 29 '16 at 05:57
Yes, this will be a pain in mysql. It doesnt support limits in correlated subqueries. — Giorgi Nakeuri, May 29 '16 at 06:04
it could also be vivian josh and tammy. Your question is vague. — Drew, May 29 '16 at 06:19
@drew I dont think the order of the names matter that much. but it could be based off of highest to lowest on single amounts — John Ruddell, May 29 '16 at 06:26
It is just not defined what the output must be. As described, I could find what I said. I could also find a row that merely outputs Vivian. Also Vivian and Josh. etc — Drew, May 29 '16 at 06:28
Please let us know if there might be duplicates and if so how can one record be distinguished from another. — Tim Biegeleisen, May 29 '16 at 08:15

Tim Biegeleisen · Accepted Answer · 2016-05-30T14:29:57.740

3

One trick which will work is to generate a row number for each Amount, for each recipient. Then we can simply restrict to the greatest three amounts for each group using a simple WHERE condition.

SELECT Recipient, SUM(Amount)
FROM test t
WHERE (SELECT 1 + COUNT(*)
     FROM test
     WHERE Amount >= t.Amount AND Recipient = t.Recipient AND
           date < t.date) <= 3
GROUP BY Recipient
HAVING SUM(Amount) >= 1024

This solution uses the transaction date to break ties (e.g. in the case of Josh receiving $500 in two different records). This solution is not robust to the use case of a recipient having two transactions for the same amount on the same day. One nice thing about this solution is that it does not require the use of any user defined variables.

SQLFiddle

edited May 30 '16 at 14:29

answered May 29 '16 at 06:28

Tim Biegeleisen

502,043
27
286
360

Sorry, this doesn't work. It gives me Jane and Vivian only. Tried to create a SQL fiddle but it hangs. – KalC May 30 '16 at 14:13
Yes, that's the challenge :( ... but at least it gives me a close enough solution. – KalC May 30 '16 at 14:24
1

@KalC I updated my answer to use the transaction date to break a tie, and it works, at least for the sample data you showed us. Really, if you expect to have two records which are completely identical then you should consider at least adding an id column of some sort. – Tim Biegeleisen May 30 '16 at 14:30
This solution worked. This is a bad table design. This was part of a skill assessment process. – KalC May 30 '16 at 14:38
1

Assessment: Many SO users have a lot of database skill (especially [this guy](http://stackoverflow.com/users/1144035/gordon-linoff)). – Tim Biegeleisen May 30 '16 at 14:40

trincot · Answer 2 · 2016-05-30T13:56:16.417

You could use variables to number records per receiver in order of descending amount, and then filter for those records that have received a number not more than 3:

select   receiver,
         sum(amount)
from    (select   @num := if(@rec = receiver, @num + 1, 1) as rn,
                  @rec := receiver as receiver,
                  amount
         from     transaction
         order by receiver,
                  amount desc) as numbered
where    rn <= 3
group by receiver
having   sum(amount) >= 1024

SQL fiddle

The nice thing about this solution is that it uses variables to avoid the base table being queried twice, which on large data sets can have a huge performance impact.

Also, it guarantees that at most 3 records will be returned per receiver, even if in the third place there would be a tie: you'll never get 4.

score 1 · Answer 3 · answered May 29 '16 at 06:19

What you can do is grab the top 3 of every recipient. and if their sum is greater than the set limit then you can return their names

SET @x = 1024;
SELECT t.Recipient
FROM (
    SELECT 
      Sender, 
      Recipient, 
      Amount, 
      SUM(Amount) as total_amount,
      @count := if(@rec = Recipient, @count + 1, 1) as counter,
      @rec := Recipient
  FROM test
  CROSS JOIN (SELECT @count := 1, @rec := '') t
  GROUP BY Recipient
  HAVING counter <= 3
  ORDER BY Recipient, Amount desc
) t
WHERE t.total_amount >= @x;

FIDDLE

This worked perfectly. Thanks a lot. This is very elegant. Lot to learn from. — KalC, May 30 '16 at 15:02

score -2 · Answer 4 · answered Feb 09 '17 at 10:37

;
WITH cte
AS (SELECT
  t.amount,
  t.recipient,
  1 AS cnt
FROM transfers t
UNION ALL
SELECT
  t1.amount + t2.amount,
  t2.recipient,
  cnt + 1
FROM cte t2
INNER JOIN transfers t1
  ON t1.recipient = t2.recipient
  AND t1.amount + t2.amount <= 1024
WHERE cnt <= 2)
SELECT
  *
FROM cte
WHERE amount >= 1024

SELECT SomeColumn where SUM(SomeOtherColumn) of any N rows or less is a certain value

4 Answers4

SQLFiddle