[算法]Google的面试题

lsosa · 发表于 2006-11-20 19:14:51

数学的东西忘的差不多了，不过随便写了个程序，代码如下：
/***************************/
/*
* lsosa.BIT
*/

#include <iostream>

using namespace std;

int countOnes(int n){
// get the numbers of ones of the n number;
unsigned int ones = 0;
unsigned int remainder;

while( n >= 10){
remainder = n % 10;
if ( remainder == 1 ){
ones ++;
}
n = n / 10;
}
if ( n > 0 && n < 10 ){
if ( n == 1){
ones ++;
}
}
return ones;
}

int main(int argc, char ** argv){
//
unsigned int sum = 0; // 前n个数的包含1个数的和；
unsigned int n = 1;
unsigned int i = 0;
unsigned int step; // 每个n包含的1的个数；
int counts = 10000; // 查找的符合要求的数字的个数；

while(true){
//得到n包含1的个数；
step = countOnes(n);
// 累加到sum上
sum += step;
if ( sum == n ){
cout << "the " << i + 1 << " number is " << n <<endl;
if ( i++ == counts ){
// find 5 ;
break;
}
}
n ++;
}

}

/************************************/

运行效率不敢恭维，写个程序，抛砖引玉吧；

运行效果：

/************************************/

the 1 number is 1
the 2 number is 199981
the 3 number is 199982
the 4 number is 199983
the 5 number is 199984
the 6 number is 199985
the 7 number is 199986
the 8 number is 199987
the 9 number is 199988
the 10 number is 199989
the 11 number is 199990
the 12 number is 200000
the 13 number is 200001
the 14 number is 1599981
the 15 number is 1599982
the 16 number is 1599983
the 17 number is 1599984
the 18 number is 1599985
the 19 number is 1599986
the 20 number is 1599987
the 21 number is 1599988
the 22 number is 1599989
the 23 number is 1599990
the 24 number is 2600000
the 25 number is 2600001
the 26 number is 13199998
the 27 number is 35000000
the 28 number is 35000001
the 29 number is 35199981
the 30 number is 35199982
the 31 number is 35199983
the 32 number is 35199984
the 33 number is 35199985
the 34 number is 35199986
the 35 number is 35199987
the 36 number is 35199988
the 37 number is 35199989
the 38 number is 35199990
the 39 number is 35200000
the 40 number is 35200001
the 41 number is 117463825
the 42 number is 500000000
the 43 number is 500000001
the 44 number is 500199981
the 45 number is 500199982
the 46 number is 500199983
the 47 number is 500199984
the 48 number is 500199985
the 49 number is 500199986
the 50 number is 500199987
the 51 number is 500199988
the 52 number is 500199989
the 53 number is 500199990
the 54 number is 500200000
the 55 number is 500200001
the 56 number is 501599981
the 57 number is 501599982
the 58 number is 501599983
the 59 number is 501599984
the 60 number is 501599985
the 61 number is 501599986
the 62 number is 501599987
the 63 number is 501599988
the 64 number is 501599989
the 65 number is 501599990
the 66 number is 502600000
the 67 number is 502600001
the 68 number is 513199998
the 69 number is 535000000
the 70 number is 535000001
the 71 number is 535199981
the 72 number is 535199982
the 73 number is 535199983
the 74 number is 535199984
the 75 number is 535199985
the 76 number is 535199986
the 77 number is 535199987
the 78 number is 535199988
the 79 number is 535199989
the 80 number is 535199990
the 81 number is 535200000
the 82 number is 535200001
the 83 number is 1111111110
the 84 number is 2971027783

[1]+  Stopped                ./main

real 38m2.302s
user 0m0.000s
sys    0m0.000s

/*************************************/

cat /proc/cpuinfo

model name    : AMD Athlon(tm) 64 Processor 3000+

slashseed · 发表于 2006-11-20 19:59:58

简单的组合数学问题，鉴定完毕

搭车问你们一个问题：
大家用过diff，也用过win下的comp吧，有没有人发现，对于同一个比较，diff返回的不同处总是不多于win的呢，比如对于如下两个文件A,B
A:    B:
1    4
2    1
3    2
      3
diff返回B文件第一行多一个4,而comp返回每行都不一样，
请问diff是用什么方法来比较的呢

lsosa · 发表于 2006-11-20 20:13:41

这个问题我前两天也注意到了，不过还没有想到什么好办法能够实现diff的这一点；

slashseed · 发表于 2006-11-20 20:21:42

那再仔细想想

linuxreborn · 发表于 2006-11-20 23:56:46

这个程序还蛮有意思的,写了段代码,效率还不是很好,大家看看有什么改进的地方

#include <iostream>
using namespace std;

int main()
{
int input;
cin>>input;
int *ff=new int[input+1];//用空间保存之前的结果
                           //ff保存的就是数值为i的结果
int i=1;
while(i<=input)
{
   if(i<=9)
   {
      ff=1;
      }
      else
      {
         int temn=i;
         int m=10;
         int id=0;
         while(m<=temn)
            {
            if(temn%m==1)//个位数为1
                  {
                  id++;
                  temn=temn-1;
                  }
               else
                  {
                  if(temn/m==1)//十位,百位,千位...为1
                        {
                           id++;
                        }
                  m=m*10;
                  }
            }
         ff=ff[i-1]+id;
   }
   i++;
   }
   int result=ff[input];
   cout<<result<<endl;
}

pointer · 发表于 2006-11-22 17:46:45

#include<stdio.h>
#define __USE_ISOC99
#include<stdlib.h>
#include<string.h>
#define MAXNL 11
long long tenpower[MAXNL]= {1,10, 0};// 10^i
long long ftenpower[MAXNL]= { 0,1,0};// nnumone(10^i -1)
long long stepnum[MAXNL]={0};
int tens[MAXNL]={0};
long long nnumone(int len)
{
int i;
long long rt=0;
for(i=len-1;i>=0;--i)
{
if(tens[i]>1) rt+=tenpower[i]+tens[i]*ftenpower[i];
else if(tens[i]==1)
rt+=ftenpower[i]+stepnum[i]+1;
}
return rt;
}
int settens(long long n)
{
int i, j;
lldiv_t qr;
i=0;
qr.quot=n;
while(qr.quot)
{
qr=lldiv(qr.quot, 10L);
tens[i++]=qr.rem;
}
for(j=1;j<i;++j)
{
stepnum[j]=stepnum[j-1]+tens[j-1]*tenpower[j-1];
}
return i;
}
int main(int argc, char * argv[])
{
int i,len=0;
long long rt, n=1, c;
for(i=1;i<MAXNL;++i)
{
tenpower[i]=tenpower[i-1]*10;
ftenpower[i]=tenpower[i-1]*i;
}
do
{
len=settens(n);
rt=nnumone(len);
c=n-rt;
if(c>len)
{
n+=c/len+1;
}
else if(c<0)
{
n+=(-c);
}
else{
if(c==0)
printf("%lld\n",n);
++n;
}
}while(len<MAXNL);
return 0;
}

复制代码

this is the result

time ./a.out
1
199981
199982
199983
199984
199985
199986
199987
199988
199989
199990
200000
200001
1599981
1599982
1599983
1599984
1599985
1599986
1599987
1599988
1599989
1599990
2600000
2600001
13199998
35000000
35000001
35199981
35199982
35199983
35199984
35199985
35199986
35199987
35199988
35199989
35199990
35200000
35200001
117463825
500000000
500000001
500199981
500199982
500199983
500199984
500199985
500199986
500199987
500199988
500199989
500199990
500200000
500200001
501599981
501599982
501599983
501599984
501599985
501599986
501599987
501599988
501599989
501599990
502600000
502600001
513199998
535000000
535000001
535199981
535199982
535199983
535199984
535199985
535199986
535199987
535199988
535199989
535199990
535200000
535200001
1111111110
real 0m0.006s
user 0m0.008s
sys 0m0.000s

复制代码

iveney · 发表于 2006-11-30 16:25:18

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

同意，个人感觉这些公司招人都是针对算法的，因此ACM不牛，数学不牛的朋友不要轻易去受鄙视

ihappy · 发表于 2006-12-5 13:38:24

题目非常简单，关键是要优化速度

dabasir · 发表于 2006-12-28 09:09:15

谁有ACM的题目，传一份给我看看，练习一下
lynux (a) 126.com

arxor · 发表于 2006-12-28 12:58:20

Post by dabasir
谁有ACM的题目，传一份给我看看，练习一下
lynux (a) 126.com

acm.pku.edu.cn

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