Friday, July 29, 2011

Project Euler – Problem1

Problem:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.Find the sum of all the multiples of 3 or 5 below 1000.

Here is a straight forward solution to this problem,

SELECT SUM(DECODE(MOD(ROWNUM,3),0,ROWNUM,

DECODE(MOD(ROWNUM,5,0,ROWNUM,0)))

FROM DUAL

CONNECT BY LEVEL <1000;

The logic is simple. The CONNECT BY clause in the above statement simply acts as row generator to generate natural numbers from 1 to 999.

The DECODEs inside the aggregate function check whether the number is divisible either by 3 or 5 if so the number is added.

This is a simple solution to understand but certainly not the best when it comes to performance. With the help of mathematical formula this problem can be solved little easier.

Multiples of 3 are 3, 6,9,12 … 999. Sum of them is

3+6+9+…999 = 3 ( 1+2 + … + [999/3]) ( [999/3] denotes integer part of 999/3 )

= 3 ([999/3]) ([999/3]+1)/2 ( 1 + 2+ … + n = n(n+1)/2)

Sum of multiples of 5 is

5 + 10 +15 +…[999/5] = 5([999/5]) ([999/5]+1)/2

The tricky part is the numbers 15, 30 …990 are included in both the case. This series should be subtracted once from the solution. So the final solution is

select trunc(999/3)* (trunc(999/3)+1) *3/2

+ trunc(999/5)* (trunc(999/5)+1) *5/2

- trunc(999/15)* (trunc(999/15)+1) *15/2 from dual;

Answer: 233168

Wednesday, July 27, 2011

SQL query to get last and second last payments to employees

Joe Celko is an American relational database expert. He has participated on the ANSI X3H2 Database Standards Committee, and helped write the SQL-89 and SQL-92 standards. The above lines would explain his innumerable contributions to RDBMS world. His “SQL Puzzles and Answers” is another golden feather on his cap. If you are an SQL geek and you’ve never been come across this book then please try this. I promise you will never be disappointed. Here is a puzzle from this book.

Assume that there is salary table with three columns hold employee name, salary date and salary. This table holds salary information paid to employees. The requirement is to write a query that should return employee’s current and previous salary status for each employee.

You can use the following statement and the pl/sql block to create and populate sample data to test the solutions.

CREATE TABLE emp ( NAME VARCHAR2(50), sal_date DATE, salary NUMBER(15,2))

BEGIN
FOR i IN 1 .. 10
LOOP
INSERT INTO emp
VALUES ('James', ADD_MONTHS (TO_DATE(‘01-01-2010’,’DD-MM-YYYY’), i), 5000 * i);

INSERT INTO emp
VALUES ('Rajendran', ADD_MONTHS (TO_DATE(‘01-01-2010’,’DD-MM-YYYY’), i), 5100 * i);

INSERT INTO emp
VALUES ('Krishna', ADD_MONTHS (TO_DATE(‘01-01-2010’,’DD-MM-YYYY’), i), 5200 * i);

INSERT INTO emp
VALUES ('Jagdish', ADD_MONTHS (TO_DATE(‘01-01-2010’,’DD-MM-YYYY’), i), 5300 * i);


END LOOP;
END;

Here is my first solution to this problem,

SELECT NAME,
(SELECT SUM (salary)
FROM emp emp_inner1
WHERE emp_inner1.sal_date > emp_outer.second_last
AND emp_inner1.NAME = emp_outer.NAME) last_salary,
(SELECT salary
FROM emp e1
WHERE e1.NAME = emp_outer.NAME
AND e1.sal_date = emp_outer.second_last) second_last_salary
FROM (SELECT NAME, MAX (sal_date) second_last
FROM emp emp1
WHERE sal_date < (SELECT MAX (sal_date)
FROM emp emp2
WHERE emp2.NAME = emp1.NAME)
GROUP BY NAME) emp_outer;

I think this is a little expensive query. The main query fetches the second last salary data for each employee. The sub queries in select clause find the last and second last salary by using second last salary date.

But the above query fails when there is a new employee who has got only one payment. The above query does not report the new employee at all. The following solution which looks better than the above also takes care of employees with only one payment.

SELECT NAME,
(SELECT salary
FROM emp emp_inner1
WHERE emp_inner1.sal_date = emp_outer.latest
AND emp_inner1.NAME = emp_outer.NAME) latest,
(SELECT salary
FROM emp emp_inner2
WHERE emp_inner2.sal_date = emp_outer.second_latest
AND emp_inner2.NAME = emp_outer.NAME) second_latest
FROM (SELECT e1.NAME, MAX (e1.sal_date) latest,
MAX (e2.sal_date) second_latest
FROM emp e1, emp e2
WHERE e1.NAME = e2.NAME(+) AND e1.sal_date > e2.sal_date(+)
GROUP BY e1.NAME) emp_outer;

The main query fetches both last and second last payment date using self-outer join. This outer join makes sure that employees with only one payment are not missed out. I'm hoping that I will be updating this post with an even better query one day


Project Euler - An Ideal place to enhance your analytical skills

Think about this, you are in love with analytical problems and you are a software guy and you always feel comfortable when it comes to mathematics. One day you found a website where you have mathematical analytical puzzles and you are expected to solve them using your favorite software tool. Things cannot be better than this. Is in it? I just had the same feeling the moment I came to know the website “Project Euler” through few “siragu muzhaitha paravaigal” (colleagues who put their papers) having quality time with this website

This site completely swept my attention towards it from the moment I saw it. Being a mathematician by nature and software guy by profession, I could not restrict me from solving the puzzles despite a full packed busy schedule.

The objective is simple. Project Euler is a series of challenging mathematical problems. You need to solve them by using any of your favorite programming language in line with the "one-minute rule". This means, your algorithm implementation will allow a solution to be obtained on a modestly powered computer in less than one minute.

The “Project Euler” also comes with usual ingredients such as country level ranking, discussion forums, tips to build best algorithm (of course it’s hidden until you post your solution) and many more.

I have chosen interesting software which is not even in the list maintained by Euler Admin itself. Neither have I had any other choice as I know only s/w language since I started my career as IT professional. It is an interesting choice though…It is Oracle SQL and PL/SQL.

People who want to know more before kick-start this just check this link.