Arjun Shastry

Ranch Hand

Posts: 1903

1

posted 12 years ago

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 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

Posts: 445

Arjun Shastry

Ranch Hand

Posts: 1903

1

Arjun Shastry

Ranch Hand

Posts: 1903

1

Jayesh Lalwani

Ranch Hand

Posts: 502

posted 12 years ago

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.

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

Posts: 6

posted 12 years ago

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

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

Posts: 1903

1

posted 12 years ago

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.

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.

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.

MH

Jim Yingst

Wanderer

Sheriff

Sheriff

Posts: 18671

posted 12 years ago

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

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.

**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

Posts: 6

posted 12 years ago

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

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