[算法]Google的面试题

wes109 · 发表于 2006-10-26 19:36:43

英文原题是:
  Consider a function which, for a given whole number n, returns the number of ones required when writing out all numbers between 0 and n.

  For example, f(13)=6. Notice that f(1)=1. What is the next largest n such that f(n)=n?

  翻译过来大体是这样：
  有一个整数n,写一个函数f(n),返回0到n之间出现的"1"的个数。比如f(13)=6,现在f(1)=1,问下一个最大的f(n)=n的n是什么？

  为什么f(13)=6, 因为1,2,3,4,5,6,7,8,9,10,11,12,13.数数1的个数，正好是6.

  请大家写出自己的算法，并统计一些在你机器上计算出1111111110的时间。

http://bbs.btant.com/viewthread.php?tid=120&extra=page%3D1

ziwarlee · 发表于 2006-10-27 09:53:26

这些东西真的复杂，要不懂这些怎么学计算机呢？

pointer · 发表于 2006-10-27 16:13:02

考虑一下, 也编程试了试, 看图片上的描述吧

Iambitious · 发表于 2006-11-7 12:07:47

所有1的个数等于个位1的个数加上十位1的个数。。。。
bit表示是哪位，总共1的个数==((n - bit) / 10 * bit ) * bit + n % (10 * bit) >= 2 * bit?bit:

n % (10 * bit) - bit + 1)(从bit=1加到比n大)
所以对于f（13）来说，个位所贡献的1的个数为2,十位所贡献的1的个数为4，所以总数为6。
所以对于n来说此算法的复杂度为lg(n)

xiaoarly · 发表于 2006-11-7 12:36:22

Post by pointer
考虑一下, 也编程试了试, 看图片上的描述吧

牛，这种题目，没几个人能够做得出来

数学系专业的，做这种题目，还好一点，计算机系，不适合做这种题目。

Iambitious · 发表于 2006-11-7 13:04:58

这种题目属于非常简单的acm题目，属于非常经典的计数题目。

xiaoarly · 发表于 2006-11-7 16:43:51

Post by Iambitious
这种题目属于非常简单的acm题目，属于非常经典的计数题目。

强，我想你可能是教授吧。

Iambitious · 发表于 2006-11-7 18:02:06

不是,只是一个学生,而且水平比较烂,其实最近我看了一些大公司的面试的题目,发现很多都是考察算法的题目,其中尤以google,baidu,ms为最，虽然题目对于搞acm竞赛的选手不难，但是对于普通的只是简单的学过数据结构和算法分析的同学来说，在规定的时间内往往给不出正确和高效的算法，个人感觉很有必要去topcoder,pku做做题目，提高一下这方面的水平，否则面试或者笔试的时候比较劣势。

rudder · 发表于 2006-11-8 14:02:32

什么都不知道
不懂

yiqianshi · 发表于 2006-11-17 15:45:39

有人看懂么发邮件给我yiqianshi@hotmail.com谢谢

		自动登录	找回密码
密码			注册

[算法]Google的面试题

本帖子中包含更多资源