Oct 3, 2007 posted by TechMonk

TopCoder has made an announcement about the 2008 TopCoder Open to be held once again in *Las Vegas* (Yes! Las Vegas and programming :P!!)

What more, the finalist pool has been increased to 120 competitors. (Looks like I will get the chance to go Vegas this time )

The 50% growth promises the toughest onsite competition in TopCoder history!

There’s going to be a TopCoder Masters Invitational also, which will have all of the previous onsite TCO finalists competing head-to-head. WOW! Thats going to be really exciting to watch..

These competitions are going to be bundled with top notch selection of educational sessions. The TopCoder Software Symposium will feature a lineup of the most talented engineers in the business who will share their expertise with TopCoder members in attendance.

Mark your calendars and start planning and practicing now!

Check out the website for more details: http://www.topcoder.com/tco08

See ya at Vegas

-Fr0z3n

Aug 2, 2007 posted by TechMonk

A classic puzzle involves being given 2 ropes and a lighter. The burning of one rope from end to end takes 1 hour, however the ropes do not burn in a uniform manner (ie: if you light it at one end, the first half of the rope could burn through in one minute while the second half may take 59 minutes to burn). Your goal is to measure out 15 minutes using the two ropes and the lighter.

You can assume that lighting a rope takes zero time.

Hint: You can break the rope with your bare hands..

Best Solution by Dark

using a single rope

it takes 1hr to burn the whole rope

rope is not burning evenly

break the rope in 2 parts (sizes don’t matter), part A and B

burn both the parts A and B from both sides.

as the ropes burn unevenly, let say A is burnt, and B has still unburnt part.

At the moment A is finished start a new fire somewhere in mid of B, thus making 2 new parts of ropes, lets say A’ and B’

if you continue this and the rope has 4 burnings ends always.. you can measure 15 mins using a single rope (assuming burning takes 0 time)

About the 2nd rope.. just burn it or timepass

Jul 6, 2007 posted by Navin

This one is simple…

You have eight balls and a balancing pan (the one on which you have two pans and can compare weights), one of the eight balls is either heavier or lighter than the rest. The remaining 7 have the same weight. How many least no of weight comparisons will it take to find out the defective ball and also weather it is heavier or lighter.

Also tell how you achieved at the number… mail your detailed reply’s to **gurus [dot] comments [at] gmail [dot] com **and put up the least number you required here as a comment

Solution (by ross):

put 2 balls on each side**(1st weigh)**, if they balance put them to one side and mark as OK if they don’t balance then mark the other 4 as OK.

take 3 of the 4 NOT OK balls, put 2 on one side and 1 on the other with 1 of the balanced balls **(2nd weigh)**. if they balance the only ball that hasn’t yet been on the scales is DEFECTIVE, weight it against one of the OK balls**(3rd weigh)** to see if it’s heavier or lighter…

if the balls don’t balance on the second weigh then take the known OK ball and the one that you put with it (let’s call it ball A) off then weigh **(3rd weigh)** the other 2 balls (call them B & C). If B & C balance then A is the defective ball. We now know that B & C are OK balls so if A & OK were heavier on the 2nd weigh then A is HEAVY DEFECTIVE, if A & OK were lighter on the 2nd weigh then A is LIGHT DEFECTIVE…

If B & C don’t balance on the **(3rd weigh)** then we know one of them is DEFECTIVE so we know A is OK. If B & C were heavier than A & OK **(on the 2nd weigh)** then we know the defective ball must be HEAVY so which ever is heavier out of B & C is the HEAVY DEFECTIVE ball. If B & C were lighter than A & OK **(on the 2nd weigh)** then we know the defective ball must be LIGHT so which ever is lighter out of B & C is the LIGHT DEFECTIVE ball.

Jun 28, 2007 posted by TechMonk

I have decided to come up with series of challenges n problems which are algorithmic in nature and are asked in interviews of reputed companies like Microsoft, Google.

This one was asked in a Google interview recently. Try to answer it in your comments. I will post the solutions if no one comes up with the right answer (let’s hope not).

“You have an unordered array X of N integers. Find the array M containing N elements where M_i is the product of all integers in X except for X_i. You may not use division. You can use extra memory.

What is the best way of doing this?”

Example:

N=4

X = {2, 5, 3, 7}

M_0 = 5*3*7 = 105

M_1 = 2*3*7 = 42

M_2 = 2*5*7 = 70

M_3 = 2*5*3 = 30

M = {105, 42, 70, 30}

(hint: There are solutions faster than O(N^2))

**NOTE: while posting solution put your code (if any) inside <code></code> tags. **

**SOLUTION:**

Thanks for your efforts. The solution presented here runs in O(N) time. Yes O(N), and thats what an interviewer would expect you to come up with, in less than an hour.
Form two arrays P and Q such that

P[1] = 1

P[i] = X[1] * X[2] * … * X[i-1] for 1 < i <= N

and

Q[i] = X[i+1]*X[i+2]*… * X[N] for 1 <= i < N

Q[N] = 1

Set M[i] = P[i]*Q[i]

Both P and Q (i.e. M) can be found in O(N) time.

Once can access corresponding code snippet here.