This week's book giveaway is in the OO, Patterns, UML and Refactoring forum. We're giving away four copies of Refactoring for Software Design Smells: Managing Technical Debt and have Girish Suryanarayana, Ganesh Samarthyam & Tushar Sharma on-line! See this thread for details.

As everybody knows Google has started its own Aptitude Test for hiring. (its there on google site).This was one of the problem Consider a function for a given whole number N,returns the number of ones(1s) required when writing out all the numbers between 0 and N. For example f(13) = 6 and f(1) =1 What is the next largest N such that f(N) = N ? (I wrote a program and tried to find an answer.It seems to be correct but we are interested in maths here!)

Its not a joke Jayesh.Google is really carrying out the test.

Jayesh Lalwani
Ranch Hand

Joined: Nov 05, 2004
Posts: 502

posted

0

I wouldnt call a test that asks you to write a haiku or asks you to improve upon emptiness or asks you what you do on weekends as a serious test. It's a spoof on SAT tests. BTW, if you google a litte bit more for the Google aptitude test, you'll find a solution. There's no logical way of solving that puzzle. The only way is brute-force, and the answer comes to 198991 or something like that

Also, I beleive that if Google really wanted to put up an aptitude test, they would have put an online test. They wont ask you to snail-mail your answers.

Let me tell you I don't know if Google really put the test, but I liked the challenge and made the following little program to find out the value:

It really uses brute force, but running on a Superdome it turned out quick the value of 199981.

Best regards.

Luis F Mexico

Arjun Shastry
Ranch Hand

Joined: Mar 13, 2003
Posts: 1888

posted

0

, Thats correct.I also got the same.

Arjun Shastry
Ranch Hand

Joined: Mar 13, 2003
Posts: 1888

posted

0

Originally posted by Jayesh Lalwani: I wouldnt call a test that asks you to write a haiku or asks you to improve upon emptiness or asks you what you do on weekends as a serious test.

But google thinks in a different way.They have given similart problems in the past on bill boards in somewhere in USA.People sent them answers and those with correct solutions had been called for interview.

BTW, if you google a litte bit more for the Google aptitude test, you'll find a solution. There's no logical way of solving that puzzle. The only way is brute-force, and the answer comes to 198991 or something like that

Aim is to solve the problems and not search for solution on google. How do you know there is no logical way of solving the problem?Can you prove it that it can not be solved mathematically?Brute force is the one way by which we got the answer.

It really uses brute force, but running on a Superdome it turned out quick the value of 199981.

A Superdome, for this? You can get 199981 pretty quickly on a much slower computer - but you'll need to modify the algorithm first. The unos() method seems to be repeating a lot of work unnecessarily. Try finding a way to save some results from previous calculations, rather than repeat them.

Actually I'm not sure 199981 is the best answer anyway. Consider the phrasing: "What is the next largest N such that f(N) = N ?" This could mean, what is the smallest value of N greater than 1 for which f(N) = N. Or it could mean, what is the second-largest solution (out of all possible solutions) to the equation f(N) = N. (Yes, there is a maximum possible value of N here.) If the question had asked "what is the largest N such that f(N) == N" then there would be no ambiguity about what they meant; unfortunatly when they say "next largest" it's not so clear. I believe that the second interpretation (next largest == second-largest overall) is correct; moreover, it's a better problem, IMO.

The original source of this problem can be found here. (Page 4, #17.) The wording says "Notice that f(1) = 1. What is the next largest n such that f(n) = n?" Here the fact that they talked about f(1) just before saying "next largest" does suggest that maybe they really did mean next after 1. (Which leads us back to the original, easier version of the problem.) But if that's what they meant, they really should have said "next larger" rather than "next largest", IMO.

"I'm not back." - Bill Harding, Twister

Luis F Garcia
Greenhorn

Joined: Oct 20, 2004
Posts: 6

posted

0

Hi there, Jim.

You are right, the code can always get improvements for speed and it shouldn't take a big machine to run faster. I agree with your opinions about "the next largest N", but honestly I didn't get into the problem that much, only liked the challenge and that code was the first thing I got. Just for fun !

BTW, luckily I had the chance to run it on a Superdome that is not heavily loaded at work.

Cheers !! Luis F

Arjun Shastry
Ranch Hand

Joined: Mar 13, 2003
Posts: 1888

posted

0

{ ..they really should have said "next larger" rather than "next largest } or 'least integer greater than 1 such that f(n) = n

I’ve looked at a lot of different solutions, and in my humble opinion Aspose is the way to go. Here’s the link: http://aspose.com