Problem and solutions book

Kidchameleon

Hi all,

Does anybody here know of a good book or website (preferably book) that has a collection of those typical kinds of programming problems that you may encounter in an interview or programming competition. (examples given below) It would be great to have such a book (with solutions) to get better at such tasks.

Thanks,

KidC.

Examples of the kind of problems im on about, taken from "All-Ireland Schools' Programming Contest" website...


Question 1

When apples fall off the tree, they very quickly go bad. Therefore it is important to gather these apples as quickly as possible.

The local orchard has a very busy apple-collecting robot named Alan. Your goal is to write a computer program that helps Alan collect the apples as quickly as possible.

Your program is given a map, with '1's representing the positions of apples that have fallen in the orchard. In one second, Alan can move one square up, down, left or right. Alan starts in the top-left corner of the grid.

Your program must help Alan by telling him the length of the optimal (shortest) route that will pass through every square that contains an apple. Alan may retrace his steps if necessary.

*********************************************

Question 2

Write a computer program to determine *how many ways* to place N rooks on an NxN chess board, in such a way that no rook is attacking another rook.

In Chess, the rook (or castle) is a piece that can attack any piece that is in the same column or row as itself. Normally, a chess board is a square grid with 8 rows and 8 columns, but here we have N rows and N columns.

You may assume N < 13.

HandWS LTD

This sounds like a little college project.

You need to tell us what kind of programming is involved, otherwise we are lost.

A wild guess is that its for C programming.....or maybe even Cobol programming. Never write off the others like c#, java, prolog, lisp, perl and many more.

ronivek

Any book on algorithms is really what you're looking for.

I've never come across one which would be quite as introductory; but something like Introduction to Algorithms would do the job. That particular example is a bit heavyweight and mathematical though.

Pygmalion

Kidchameleon wrote: »

Examples of the kind of problems im on about, taken from "All-Ireland Schools' Programming Contest" website...

The IOI problems (which I assume is what you're looking for because of the site you mentioned) are usually available online (with solutions).
This site seems to have the problems up until 2007 (may be missing some, haven't tried all the links) and some recommended reading.
The latest 2 years competitions have the tasks up here and here, respectively.
And here is an American site providing tons of similar problems for practise.

All of the above assumes that you're wanting to attempt to compete in the IOI (since the site you mentioned is step one in getting to it), but even if not they're great problem sets (meaning to get around to working through them, or at least trying, myself), though can be very difficult even if you know what you're doing.

Also may not be exactly the same type of problems but Project Euler is a good site, lets you register, tons of problems, when you solve a problem you can access a discussion on it in which people post their solutions (usually they range from a haskell one-liner to optimised x86 assembly).
My problem with this is that they can be more like maths problems than programming problems at times.

Kidchameleon

Thanks guys some of those sites are great and are just what im looking for. Actually im not entering any competition, I just want to keep my "brain trained" with these types of problems. I applyed for a job at Microsoft recently and I dident have a clue how to do the questions they sent me!