Thu 19 February 2009

Programming skills..

Posted by ankur in Tech (380 words, approximately a 2 minute read)

Im still a noob at programming.. I get these questions from places and try to solve them to improve my skills.. Someday in the near future, I'll be writing apps.. Hopefully :)

Here's one such question that I'm working on..  It's one of a few from Bitwise 2007 :

Note: it was to be programmed in C.

Problem 1: A Dream House for Mary-Jane (100 points)

Santiago was sitting on the steps of a local shop, reading a book and waiting for the merchant to return. “I didn’t know shepherds knew how to read,” said a girl’s voice behind him.

Santiago turned around and was greeted by the warm smile of an Andalusian girl, to whom he started narrating the story he was reading – Spiderman’s search for the best spot for his dream house.

In this model of New York City (Spiderman’s home town), each house is represented by a node, and a link between two nodes indicates that a path of unit length exists between those two nodes. It is also given that all nodes are connected, and there exists a unique path between each pair of nodes.

Spiderman is looking for a new house to enjoy life with Mary-Jane. Since he is always conscious of his duties, he wants to minimize the maximum distance of any house from his house. This would allow him to minimize travel time on his rescue acts and spend more time with the lovely MJ.

Can you help Spiderman select his dream house?

Input: The first line specifies the number of test cases (<10000). Each test case is represented thus: first line specifies the number of nodes in the graph. The next n-1 lines specify undirected edges in source destination format (the nodes are numbered from 0 to n-1). (n<1000)

Output: For each test case, display (on a new line) all the best possible nodes for Spiderman to buy his house.

Sample input file:

0 1
0 2
0 3
0 1
2 1
1 3
3 4
3 5

Sample output file:

1 3

I'm still thinking about it.. If anyone else wants to try it, please do mail your result to me..Most of you are hard-core coders.. So your solution will probably be better than what I code..