You are hereProgramming Problems / 2009 Programming Problems

2009 Programming Problems


By gconway - Posted on 17 April 2012

Fibonacci

The Fibonacci numbers are a sequence of numbers with lots in interesting properties, and have been used in many disciplines, including art, architecture, literature and music. It is also related to the Golden Ratio, a proportion used in Renaissance works by many artists and architects who believed this proportion to be aesthetically pleasing.

The first number of the sequence is 0, the second number is 1, and each subsequent number is equal to the sum of the previous two numbers in the sequence.
The sequence begins: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Write a computer program to compute the sum of the first N Fibonacci numbers (1 <= N <= 40)

(hint: to check your answer, you can use an interesting property of the sequence. If F(k) is the kth Fibonacci number, then F(k+2)-1 is equal to the sum of the first k Fibonacci numbers)

 

Blocks

Trevor's table has finally collapsed! He had been piling books, boxes and computer hardware onto it for years, and just yesterday, the left leg of the table splintered, causing a big mess.

He now wants to replace the leg with something tougher, so goes to the local quarry to get some stone blocks. Unfortunately, Trevor can only afford two blocks, and must find two such blocks so that the sum of their sizes adds up to exactly one metre (1000mm), since the other table leg is this height.

The quarry has a long list of all the sizes of the stone blocks they currently have on sale. Write a computer program to help Trevor find two blocks whos sizes sum to 1000. If there are multiple solutions, choose the solution where the size of largest stone is minimised:
E.g. 100 & 900 is a solution, and 400 & 600 is also a solution, but 400&600 is better because 600<900.

Example input:
How many stones are in the quarry? 10
What are the sizes of the 10 stones? 200 250 401 708 358 100 150 330 999 850

Example output:
Trevor should buy a size 150 and a size 850

 

 

Randomness

Given a sequence of 1,000,000 non-negative whole numbers (integers), with each number smaller than 256, how would you determine how random the sequence is?

(This is a discussion task, and as such there is no perfect answer to this question. Just write how you would approach the problem)

 

Treasure

(a variant of this task was asked at Microsoft interviews to select candidates with exceptional logical deduction)

The pirate crew of the Jolly Roger ship have found a hoard of treasure and decide to divide it among themselves. Each pirate has a unique rank and the highest rank pirate gets to suggest how the gold should be divided. The pirates then vote on his plan. His plan is accepted if at least half the crew vote in favour of it. Otherwise, there is a mutiny and that pirate is made walk the plank. The next highest ranked pirate then takes over and the proposal/voting procedure is repeated.

All pirates always act logically, and try to avoid walking the plank while maximising their own share of the gold.

Given that there are G gold coins in the treasure chest and P pirates in the crew, how would you suggest dividing the gold if you were the top ranked pirate?

Write a computer program to input two integers, G and P, and to output P integers, indictating the division of gold that you would suggest for the P pirates (The pirates are ordered highest to lowest, so as the highest ranked pirate, the number of
gold coins you get should be the first integer)

Examples:

(1) G=5 P=2
Answer = 5 0
You should suggest that you get all the gold. Since you would vote for your own plan, that counts as "at least half the crew", therefore it will be accepted.

(2) G=10 P=3
Answer = 9 0 1
You should suggest that you get 9 gold coins and the bottom ranked pirate gets 1. Let's number the pirates 1 to 3, 1=highest ranked, 3=lowest ranked. If your plan fails, then pirate 2 will take all the gold, so it is in the interest of pirate 3 to vote for your plan, since he gets 1 coin (otherwise he would get nothing).

You can assume the input will be two positive integers within these ranges:

P <= 1,000

G <= 1,000,000

G > (0.5 x P)

 

 

Choc-O-Chess

Fatty Malone loves chocolate. Your task is to beat him in a game of choc-o-chess and to prevent him from eating too much of his beloved snack food. Here's how the game works:

You start with a rectangle of chocolate of MxN squares. You then break it into two rectangular pieces, any way you like. For example, starting with a 10x11 piece, you could split it in a 3x11 and a 7x11 piece. You then put the bigger piece in a bowl and continue the game with the SMALLER piece. You pass this piece to your opponent and they do the same thing (break it in two, put the larger piece in the bowl and pass back the small piece). If you are given a 1x1 piece, then you can't split it in two, and you lose. The winner gets all the chocolate in the bowl.

Part I
You must write a computer program that will play choc-o-chess using the optimal strategy. You are given the MxN rectangle of chocolate first. You can assume there is always a way to win from the starting position.

Example: (Player 1 starts and is given a 7x3 block of chocolate)

1 gets 7x3
2 gets 3x3
1 gets 1x3
2 gets 1x1

Player 1 wins

Part II
How should the strategy change if the rules of choc-o-chess are changed, so that instead of putting the larger piece into the bowl, you put the smaller piece in the bowl and continue the game with the larger piece?

Write a computer program to play with the new strategy.