A few programming puzzles

If you are up to sharpening your programming skills, here are a few puzzles to keep you busy. The reason I’m posting these is because I’ll try to solve them myself as I feel kinda rusty lately (I think PHP is trying to kill the best of my programming habits, it’s a good thing I am also programming in Java now for my final year project!)
So yeah, here we go!

1. Given N Queens place count the number of different ways they can be placed on an N x N board so that no queen can attack another queen given one move. (tip: use a backtracking algorithm. Also there are many heuristics you can use for this one, optimizing your algorithms even further).
2. For all 6-digit numbers from 100000 to 999999, find the numbers that, if you add the top three digits to the bottom three digits, and square the result, it will equal the original number. For example, for 123456, you’d add 123 and 456, which equals 579. Then, square that sum, which yields 579 * 579 = 335241. 335241 ≠ 123456, so 123456 is not in the set.
3. Given an array of size 45, containing integers from 1..50 with the exception of five integers, find the missing integers.
4. Create a random number generator that takes as input nodes from a double linked list. (tip: to do this you simply need to un-sort the list in a random way, the algorithm is up to you).
5. Given any file containing code, write a program which calculates the computational complexity of the code. Your output should be in big O notation.
6. Write a small simulation engine for social network interconnections. i.e. it should be able to accept a number of people, some of them connected between them, and the simulation should show the minimum spanning tree for all interconnections to occur based on the already existing ones.

Have fun!

Advertisement

---