aspose file tools*
The moose likes Programming Diversions and the fly likes Google Aptitude Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Google Aptitude" Watch "Google Aptitude" New topic
Author

Google Aptitude

Arjun Shastry
Ranch Hand

Joined: Mar 13, 2003
Posts: 1874
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!)


MH
Vedhas Pitkar
Ranch Hand

Joined: Jan 27, 2001
Posts: 445
Did you give the Google aptitude test?Would like to know more info
Arjun Shastry
Ranch Hand

Joined: Mar 13, 2003
Posts: 1874
No.Test is there on the web.Search for Google Aptitude Test in google
Jayesh Lalwani
Ranch Hand

Joined: Nov 05, 2004
Posts: 502
You do know that it's a joke, right?
Arjun Shastry
Ranch Hand

Joined: Mar 13, 2003
Posts: 1874
Its not a joke Jayesh.Google is really carrying out the test.
Jayesh Lalwani
Ranch Hand

Joined: Nov 05, 2004
Posts: 502
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.
Luis F Garcia
Greenhorn

Joined: Oct 20, 2004
Posts: 6
Hi Arjun !!

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: 1874
,
Thats correct.I also got the same.
Arjun Shastry
Ranch Hand

Joined: Mar 13, 2003
Posts: 1874
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.
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
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
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: 1874
{
..they really should have said "next larger" rather than "next largest
}
or 'least integer greater than 1 such that f(n) = n
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Google Aptitude