`
simohayha
  • 浏览: 1389917 次
  • 性别: Icon_minigender_1
  • 来自: 火星
社区版块
存档分类
最新评论

google的一道面试题。

Google面试F#算法编程 
阅读更多
这个题目的英文原题是:
引用

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.
分享到：
评论
23 楼 阳光晒晒 2007-04-14  
有。。。
用分治法+贪心算法
命中一个区域
之后用双循环会快。。。
Ｏ(log2n）
22 楼 mjy304122 2007-04-13  
哈哈，首先我是来分析题目的。
我看到楼上的众多讨论其实都没有从根本上降低速度。
首先，在寻找“1”的个数上就没有数学方法吗？
其次，在遍历1至MAX里就没有一下就提高位数的思想了吗？
先引出讨论，再给出我的思路！！！
21 楼 cherami 2007-04-08  
都没有我的快：
http://www.jiehoo.com/google%e9%9d%a2%e8%af%95%e9%a2%98%e8%a7%a3%e8%af%b4%e6%80%a7%e8%83%bd%e4%b9%8b%e4%ba%94%ef%bc%9a%e4%ba%ba%e6%af%94%e7%94%b5%e8%84%91%e8%81%aa%e6%98%8e.htm

Find 535199989, 7031ms
Find 535199990, 7031ms
Find 535200000, 7031ms
Find 535200001, 7031ms
Find 1111111110, 14250ms
20 楼 imcaptor 2007-03-29  
我把我的算法也贴出来
package untitled3;

import java.util.Date;

public class Untitled1 {
    public Untitled1() {
    }

    public static void main(String[] args) {
        Untitled1 untitled1 = new Untitled1();
        //System.out.println(countOneNumberUnderN(199981));
        findN();
    }
    public static void findN(){
        long start = System.currentTimeMillis();
        int count = 0;
        for ( int i = 1; i < Integer.MAX_VALUE; i++ ){
            count += countOneNumber(i);
            if ( count == i ){
                System.out.println("find "+i+","+(System.currentTimeMillis()-start)+"ms used!");
            }            
        }
    }   
    public static int countOneNumber(int n){
        int count = 0;
        while ( n > 0 ){
            //模除10
            int mod = n%10;
            if ( mod == 1 )
                count++;
            n = n/10;
        }
        return count;
    }
}


下面是运行结果
find 1,0ms used!
find 199981,32ms used!
find 199982,32ms used!
find 199983,32ms used!
find 199984,32ms used!
find 199985,32ms used!
find 199986,32ms used!
find 199987,32ms used!
find 199988,32ms used!
find 199989,32ms used!
find 199990,32ms used!
find 200000,32ms used!
find 200001,32ms used!
find 1599981,329ms used!
find 1599982,329ms used!
find 1599983,329ms used!
find 1599984,329ms used!
find 1599985,329ms used!
find 1599986,329ms used!
find 1599987,329ms used!
find 1599988,329ms used!
find 1599989,329ms used!
find 1599990,329ms used!
find 2600000,532ms used!
find 2600001,532ms used!
find 13199998,3047ms used!
find 35000000,8829ms used!
find 35000001,8829ms used!
find 35199981,8875ms used!
find 35199982,8875ms used!
find 35199983,8875ms used!
find 35199984,8875ms used!
find 35199985,8875ms used!
find 35199986,8875ms used!
find 35199987,8875ms used!
find 35199988,8875ms used!
find 35199989,8875ms used!
find 35199990,8875ms used!
find 35200000,8875ms used!
find 35200001,8875ms used!
find 117463825,32282ms used!
19 楼 jasongreen 2007-03-28  
我们将数x表示成 head*10(n)+tail;
如：x=1234 , 则表示为 1* 10(3) + 234;
f(1234) = 1 * f(99) + 235 + f(234);
不用我解释吧
234 = 2 * 10(2) + 34;
f(234) = 2 * f(99) + 100 + f(34);
从1到234，有两次 f(99) ,从 100 到 199 共有100个1， 从 200到234 的 1的总和  = f(34)

可以得出：
对于数x，
如果x<10
f(x) = x>=1 ? 1 : 0;
如果head = 1
f(x) = head * f(10(n) - 1) + f(tail) + tail+1
如果head > 1
f(x) = head * f(10(n) - 1) + f(tail) + 10(n);

根据这个公式我们可以迅速的求出f(x），而如果用getCountOfOne（long number)，只能得到某数中1的个数，对于从1到n的值，必须使用循环相加的方法，如果计算，123456789的值的话，就需要循环 123456789次，即便剪枝，也不能减少多少循环次数， 而用这个公式，写个递归方法，可以很快的算出答案。

但仍然有个问题：
如何证明满足f(n)=n的n是最大的n？
18 楼 shenhai 2007-03-26  
public static void main(String[] args) {
// TODO Auto-generated method stub
TestMain test=new TestMain();

Calendar startCalendar = Calendar.getInstance();
long start = startCalendar.getTimeInMillis();
// start count time
long nums=1;
for(long n=2;n<=400000000;n++) {
//int nums=0;
nums+=test.getNumbersOfOne(String.valueOf(n));

if(nums==n) {
System.out.println(nums);
break;
}

}
System.out.println("run end...");
Calendar endCalendar = Calendar.getInstance();
long end = endCalendar.getTimeInMillis();
System.out.println(end-start);

}

//
public long getNumbersOfOne(String strNum) {
int nums=0;
for(int i=0,len=strNum.length();i<len;i++) {
char a=strNum.charAt(i);
if(a=='1') nums++;
}
return nums;
}

}
计算到199981，用了63ms
其实我的getNumbersOfOne（）方法还可以在改进。。。。
我的思路很简单，当计算f(n)=f(n-1)+getNumbersOfOne(n)
其中getNumbersOfOne用来计算n中包含1的个数；
因为我不懂剪枝算法，我只能这种简单的思想了。。。。
17 楼 simohayha 2007-03-24  
f(13)=6 那么下一个 f(n)=n 的最大的n是多少？
呵呵，有点拗口。
不过很同意大法师所说的，这个算法的关键是剪枝.
16 楼 coolwangyu 2005-11-28  
package test.thinkinjava;

import java.util.Calendar;

/**
* @author NEUSOFT.wangyu
*/
public class TestGoogle{

int xx = 0;
int result = 1;

public static void main(String[] args){
TestGoogle instance = new TestGoogle();
instance.run2();
}

public void run2(){
Calendar c = Calendar.getInstance();
long aa = c.getTimeInMillis();
for(int i = 2;i&lt;Integer.MAX_VALUE;i++){
int num = i;
while(num &gt; 0){
xx = num;
num = num / 10 ;
if((xx - num*10) == 1){
result++;
}
}
//System.out.println("i= "+i+"result = "+result);
if(result == i){
System.out.println("result num ="+i);
break;
}
if(i == (Integer.MAX_VALUE -10)){
System.out.println("out of range !");
}
}

Calendar b = Calendar.getInstance();
long bb = b.getTimeInMillis();
System.out.println(bb-aa);

}

}
15 楼 simohayha 2005-10-19  
设g(k)是数ｋ中１的个数
f(n) = sum(0&lt;=k&lt;=n) g(k)
= sum(0&lt;=k&lt;n+1) g(k)

f(10n+9) = sum(0&lt;=k&lt;10(n+1)) g(k)
= sum(0&lt;=k&lt;n+1) (g(10k)+g(10k+1)+...+g(10k+9))
= sum(0&lt;=k&lt;n+1) (10g(k)+1)
= sum(0&lt;=k&lt;n+1) 10g(k) + sum(0&lt;=k&lt;n+1) 1
= 10 f(n) + n+1
14 楼 xiaoyu 2005-10-19  
Elminster 写道
这题的关键其实不是计算 f(n) ，这个是简单的。真正在降低计算时间上作用巨大的是剪枝，也就是说如果把那么多数字看作一棵搜索树上的节点的话，如何知道哪些分支子树是不用去检查判断的，否则无论怎么做也快不起来。


这是我后来想说的。讲得十分对。但在这里上面详细的计算方法，是起到很关键的作用的。
13 楼 Elminster 2005-10-19  
这题的关键其实不是计算 f(n) ，这个是简单的。真正在降低计算时间上作用巨大的是剪枝，也就是说如果把那么多数字看作一棵搜索树上的节点的话，如何知道哪些分支子树是不用去检查判断的，否则无论怎么做也快不起来。
12 楼 jkit 2005-10-19  
如果要求从0到n每个数字的f(n)都算出来，不妨试试下面的
fs(n) = 数字n本身含有1的个数
f(0) = 0
f(n+1) = f(n) + fs(n+1)
单算某一个数n效率很低，但是从0算到n时间的话速度就快了，主要取决于fs(n)计算数字n本身含有1的个数的时间。再加上跳跃，还能更快。
11 楼 xiaoyu 2005-10-19  
ajoo 写道

也许可以直接推导出常量级别复杂度的公式来？


嗯，就是，就是，其实都有很大的关系（后一个位与前一位的关系,例如：0到999与0到99有很大的关系），可以以10的次方跳跃。所以能省N多的时间和处理。
10 楼 xiaoyu 2005-10-19  
simohayha 写道
它不止是得到199981,它把4000000000内的所有都遍历出来了。而且速度还只是几十毫秒，或者更快


当然，我知道，如果只是计算到199981的话，就没有意思了。
9 楼 ajoo 2005-10-19   
  int cal(int num);{
    if(num <1); return 0;
    int i = num%10;
    int n = 0;
    int power = 1;
    for(int k=num/10; k>0; k/=10, n++, power*=10);{
      i = k % 10;
    }
    if(n==0); return 1;
    int remainder = num - i*power;
    if(i==1);{
      return n*(power/10);+1+remainder+cal(remainder);;
    }
    else{
      return power+i*(n*power/10);+cal(remainder);;
    }
  }

对数级的复杂度．也许可以直接推导出常量级别复杂度的公式来？

不过，这只是计算f(n)而已．

什么叫＂下一个最大的＂？
8 楼 simohayha 2005-10-18  
它不止是得到199981,它把4000000000内的所有都遍历出来了。而且速度还只是几十毫秒，或者更快
7 楼 xiaoyu 2005-10-18  
你真没有意思，这么快就公布答案了（我的新思路已经出来）。

不过我应该能算得比它快。
6 楼 simohayha 2005-10-18  
我把c的代码贴出来!

他计算到4000000000,用的是剪枝。 

#include "stdafx.h"

#include <windows.h>
#include <stdlib.h>

int f(int n);
int count1(int n);
int cal(unsigned int number,int nwei,int count1,unsigned int ncount);

int gTable[10];
const unsigned int gMAX = 4000000000L;

int main(int argc, char* argv[])
{
  int i;
  unsigned int n=1;
  unsigned int ncount = 0;
  int nwei = 0;
  int ncount1;

  /*if(argc>1)
  {
    n = atoi(argv[1]);
    ncount = f(n);
    printf("f(%d) = %d\n",n,ncount);
  }*/

  int beginTime=GetTickCount();
  //init gTable
  for(i=0;i<10;++i)
  {
    n *= 10;
    gTable[i] = f(n-1);
  }

  n=0;
  nwei = 0;
  ncount1 = 0;
  while(n<gMAX)
  {
    unsigned int temp;
    
    temp = 1;
   
    ncount =cal(n,nwei,ncount1,ncount);
    for(i=0;i<nwei;++i)
      temp *= 10;
    n += temp;
    if( (n/temp)/10 == 1)
      ++nwei;
    ncount1 = count1(n);
  }

  int endTime=GetTickCount();
  endTime-=beginTime;

  printf("time: %d ms\n",endTime);
return 0;
}


int f(int n)
{
  int ret = 0;
  int ntemp=n;
  int ntemp2=1;
  int i=1;
  while(ntemp)
  {
    ret += (((ntemp-1)/10)+1) * i;
    if( (ntemp%10) == 1 )
    {
      ret -= i;
      ret += ntemp2;
    }
    ntemp = ntemp/10;
    i*=10;
    ntemp2 = n%i+1;
  }
  return ret;
}

int count1(int n)
{
  int count = 0;
  while(n)
  {
    if( (n%10) == 1)
      ++count;
    n /= 10;
  }
  return count;
}

int cal(unsigned int number,int nwei,int count1,unsigned int ncount)
{
  int i,n=1;
  unsigned int maxcount;
  if(nwei==0)
  {
    ncount += count1;
    if(number == ncount)
    {
      printf("f(%d) = %d \n",number,number);
    }
    return ncount;
  }
  for(i=0;i<nwei;++i)
    n *= 10;
  maxcount = ncount + gTable[nwei-1];
  maxcount += count1*n;
  if(ncount > (number +  (n-1)) )
  {
   return maxcount;
  }
  if(maxcount < number)
  {
    return maxcount;
  }
  n /= 10;
  for(i=0;i<10;++i)
  {
    if(i==1)
       ncount = cal(number+i*n,nwei-1,count1+1,ncount);
    else
       ncount = cal(number+i*n,nwei-1,count1,ncount);
  }
    return ncount;
}
5 楼 xiaoyu 2005-10-18   
    int getCountOfNumber(int number);{
		int count=0;
		int length=("" + number);.length();;
		
		for(int i=0;i<=length;i++);{
			int num=number%10;
			number=(number-num);/10;
			
			if(num*num==1); count++;
		}
		
		return count;
	}


能提升不少性能.

计算到：199981
只用：203
4 楼 xiaoyu 2005-10-18  
我的计算199981,
要用1453
不活了。
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    程序员面试题精选100题

    分析：这是去年google 的一道面试题。 我看到这道题目时，第一反应就是每次push 一个新元素时，将栈里所有逆序元素排序。这样栈顶元素将 是最小元素。但由于不能保证最后push 进栈的元素最先出栈，这种思路设计的...

    程序员面试金典-第五版

    第8～9 章从数据结构、概念与算法、知识类问题和附加面试题4 个方面，为读者呈现了出自微软、苹果、谷歌等多家知名公司的150 道编程面试题，并针对每一道面试题目，分别给出了详细的解决方案。 本书适合程序开发和...

    google百度北电华为腾讯试题及面试

    中兴面试题 1&gt;某人在某个市场某个商家买了某台电脑,请用你熟悉的计算机语言表达出里面的关系. 其中有商家类，买家类，商品类。还要有买方法，卖方法。 2&gt;一个完整的单例模式 3&gt;曹操南下攻打刘备，刘备派关羽守...

    程序员面试金典 第五版 带书签目录

    第8～9 章从数据结构、概念与算法、知识类问题和附加面试题4 个方面，为读者呈现了出自微软、苹果、谷歌等多家知名公司的150 道编程面试题，并针对每一道面试题目，分别给出了详细的解决方案。 本书适合程序开发和...

    程序员面试金典 第5版

    本书是原谷歌资深面试...第8～9 章从数据结构、概念与算法、知识类问题和附加面试题4 个方面，为读者呈现了出自微软、苹果、谷歌等多家知名公司的150 道编程面试题，并针对每一道面试题目，分别给出了详细的解决方案。

    程序员面试金典-5版

    第8～9 章从数据结构、概念与算法、知识类问题和附加面试题4 个方面，为读者呈现了出自微软、苹果、谷歌等多家知名公司的150 道编程面试题，并针对每一道面试题目，分别给出了详细的解决方案。 本书适合程序开发和...

    程序员面试金典（第5版）.rar

    本书是原谷歌资深面试...第8～9 章从数据结构、概念与算法、知识类问题和附加面试题4 个方面，为读者呈现了出自微软、苹果、谷歌等多家知名公司的150 道编程面试题，并针对每一道面试题目，分别给出了详细的解决方案。

    程序员面试金典-卷一

    第8～9 章从数据结构、概念与算法、知识类问题和附加面试题4 个方面，为读者呈现了出自微软、苹果、谷歌等多家知名公司的150 道编程面试题，并针对每一道面试题目，分别给出了详细的解决方案。 本书适合程序开发和...

    程序员面试金典-卷二

    第8～9 章从数据结构、概念与算法、知识类问题和附加面试题4 个方面，为读者呈现了出自微软、苹果、谷歌等多家知名公司的150 道编程面试题，并针对每一道面试题目，分别给出了详细的解决方案。 本书适合程序开发和...

    Cracking the Coding Interview 6th Edition

    亚马逊超级畅销书，...第8～9 章从数据结构、概念与算法、知识类问题和附加面试题4 个方面，为读者呈现了出自微软、苹果、谷歌等多家知名公司的150 道编程面试题，并针对每一道面试题目，分别给出了详细的解决方案。

    程序员面试金典(第五版)-高清扫描PDF

    本书是原谷歌资深面试官的经验之作，全面而详尽地介绍了程序员应当如何...为读者呈现了出自微软、苹果、谷歌等多家知名公司的150 道编程面试题，并针对每一道面试题目，分别给出了详细的解决方案。是刷题面试的好资料。

    front-end-interview:前端面试问题汇总

    （html&&CSS）基础面试题（一般大公司很少问到） JS 算法与数据结构 HuangCongQing/JS-AlgorithmsAndDataStructure hyccpq/js-Data-Structures-and-Algorithms zouyang1230/JS-algorithms matthew-sun/data-...

    100层楼2个鸡蛋C程序递归实现

    来自一道google面试题，本资源以VC编译器下的C递归实现，楼层数和鸡蛋数作为可变输入参数，输出（测试出保证鸡蛋不破的最高安全层的）最小次数。比如100层楼2个鸡蛋输出结果14：表示2个鸡蛋测试100层楼以获得最高...

    软件水平考试《程序员》习题及答案.docx

    这是一道广为流传的google面试题，考察了应聘者的算法设计和编程能力。 知识点11：数据结构 在解决问题时，需要了解数据结构的概念，如数组、链表、树等，以便更好地设计算法和编写程序。 知识点12：问题分析 在...

    leetcode知乎-lc_books:从Leetcode、CodingInterviews等中精心挑选的算法问题的解决方案，由Java解决

    之前做题，几乎只能去参考Leetcode里面Discussion的解法和Google别人的解法，一道题当时做完觉得没什么貌似是理解了，但是等一段时间再次碰到，又不知道如何下手，这就是典型的没有理解和掌握透。所以在这里，我们...

    leetcode中国-leetcode:一起学习算法

    leetcode中国 home comment heroImage footer true false /favicon.png ...算法是很重要的基础素质，而且也能保持你的思维状态。可能你在工作中，很多业务，很难用得上算法。...每一道题，你不看题解完全独立做

Magicbox
Global site tag (gtag.js) - Google Analytics