Hint for a C# and also an SQL Puzzle

Question

I was browsing SO careers and came across a job that had a pdf with a couple of puzzles they wanted applicants to send in.

Although I'm not interested in the job, I read the questions anyway and had a play in Visual Studio / SMSS. The first question was fairly easy to solve although I couldn't think if any way to optimise it (I solved it in C#). The second puzzle only one obvious solution strikes me and I can't think of any others.

I'm not sure if it's bad to discuss these questions here though, but if anyone can give me some hints or perhaps suggest somewhere where I can ask this without creating any grief it'd be appreciated.

The questions are in here: http://www.debtx.com/doc/DebtX_Programming_Problems.pdf

I could let the first one slide but the second one has me stumped on other ways of solving it than the obvious. Shame there's no PM function on SO...

Boilerplate solution for the first part C#:

public static bool Compare(int[] num, int[] div)
{
    for (int i = 0; i < num.Length; i++)
    {
        for (int j = 0; j < div.Length; j++)
        {
            if (num[i] % div[j] == 0)
                return true;
        }
    }

    return false;
}

My SQL Solutions

select Table1.Key1, Table1.Key2 from Table1 inner join Table2 on Table1.Key1 = Table2.key2 where IsDeleted=0

select * from Table1 where key1 in(select Key2 from Table2 where IsDeleted=0)

It all seems so samey though

Answer 1

couple of examples using pseudo SQL to not give too much away

Not In

   SELECT * FROM TBL1 
   WHERE NOT IN (
            SELECT FROM TBL2  
            WHERE Deleted=0 AND Tbl2.Key1= Tbl1.Key1 AND Tbl2.Key2=Tbl1.Key2
            )

Not Exists

    SELECT * FROM TBL1 
    WHERE NOT EXISTS (
        SELECT FROM TBL2 
        WHERE Deleted =0 AND Tbl2.Key1= Tbl1.Key1 AND Tbl2.Key2=Tbl1.Key2
        ) 

Outter Join Is Null

    SELECT * FROM TBL1 LEFT JOIN TBL2 
    WHERE TBL2.Key1 IS NULL OR Deleted=0

Answer 2

Well which solution have you used already? Immediately I think it can be done using a subquery with IN, using a LEFT OUTER JOIN and filtering on NULL, or using EXISTS.

Answer 3

One optimisation to the C# question is to sort the DIV array. You're more likely to find a match quickly starting with the smaller numbers.

EDIT: Another optimisation to the C# question may be to look at an approach similar to the Prime Number Sieve of Eratosthenes the general theory being that you pre-empt some results without having to perform the checks.

As for the SQL question, the three obvious (common) ways are as others have stated, a JOIN, an IN and an EXISTS.

Answer 4

Spoiler alert!!!!!

SELECT
     T1.key1,
     T1.key2
FROM
    Table1 T1
WHERE
    NOT EXISTS
    (
        SELECT *
        FROM
            Table2 T2
        WHERE
            T2.key1 = T1.key1 AND
            T2.key2 = T1.key2 AND
            COALESCE(T2.IsDeleted, 0) <> 1
    )

---

SELECT
     T1.key1,
     T1.key2
FROM
    Table1 T1
LEFT OUTER JOIN Table2 T2 ON
    T2.key1 = T1.key1 AND
    T2.key2 = T1.key2 AND
    COALESCE(T2.IsDeleted, 0) <> 1
WHERE
    T2.key1 IS NULL

---

SELECT
     T1.key1,
     T1.key2
FROM
    Table1 T1
WHERE
    (
        SELECT COUNT(*)
        FROM
            Table2 T2
        WHERE
            T2.key1 = T1.key1 AND
            T2.key2 = T1.key2 AND
            COALESCE(T2.IsDeleted, 0) <> 1
    ) = 0