cuiyi's blog(崔毅 crazycy)

记录点滴 鉴往事之得失 以资于发展
数据加载中……

google笔试的败笔(大家来仁者见仁哦)

1 超级失败的1:说8点开始,考试时间100分钟 ,怎么算都是9:10交卷;9点一到匆匆交卷了,晚上躺床上才发现错也;

2 超级失败的2:把自个的生日又记错了;

3 怕怕的发现:发现mm还是超级可怕滴,眼睁睁看着一个骗局,哎,也得谨慎些以防上当受骗啊;

题目如下:

T( 0 ) = 1 ; T(1)=1;T(2)=2;T(n)=T(n-1)+T(n-2)+T(n-3);
用最优方式求T(n) ;

int T(int n) {
}

可以用最熟悉的语言写


在考场的第一个做法

 1 public   class  T  {
 2   public   int  t( int  n) {
 3    if  (n  ==   0 {
 4     return   1 ;
 5   }
  else   if  (n  ==   1 {
 6     return   1 ;
 7   }
  else   if  (n  ==   2 {
 8     return   2 ;
 9   }
  else   {
10     return  t(n - 1 +  t(n - 2 +  t(n - 3 );
11   }
 
12  }

13 }

当时发现时间够用,进行了公式推理,但未得出规律的真谛
每个都与T(3)可以直接发生关系,关系是2的幂次方,但最终没有得出公式
遂改进如下:

 1 public   class  T  {
 2   public   int  t( int  n) {
 3    if  (n  ==   0 {
 4     return   1 ;
 5   }
  else   if  (n  ==   1 {
 6     return   1 ;
 7   }
  else   if  (n  ==   2 {
 8     return   2 ;
 9   }
  else   {
10     return   2   *  t(n - 1 -  t(n - 3 );
11   }
 
12  }

13 }

晚上躺床上,怎么可能这样直接呢?
突然想到最起码的一点就是重复数的计算,应该进行保存;
如果正向逐个求然后保存,可行;
如果倒向如何保存,尚未想好
大家来仁者见仁一下哦(有更好的思路的请指点)
public class T {
 Map values = new HashMap();
 
 public int t(int n){
  int result = 0;
  if (n == 0) {
    result = 1;
  } else if (n == 1) {
   result = 1;
  } else if (n == 2) {
   result = 2;
  } else {
   result =  2 * t(n-1) - t(n-3);
  }
  return result;
 }
}

posted on 2006-10-18 11:37 crazycy 阅读(3111) 评论(23)  编辑  收藏 所属分类: JavaSE语言

评论

# re: google笔试的败笔(大家来仁者见仁哦)  回复  更多评论   

应该是:
public class T {
public int t(int n){
if (n == 0) {
return 1;
} else if (n == 1) {
return 1;
} else if (n == 2) {
return 2;
} else if (n == 3) {
return 4;
} else {
return 2 * t(n-1) - t(n-4);
}
}
}
2006-10-18 12:37 | katlao

# re: google笔试的败笔(大家来仁者见仁哦)  回复  更多评论   

增开7群,号码 30440732
8群 30756649
9群 30178567
10群 28694497

我们的qq群:15096318 学习程序的都可以来
2006-10-18 14:16 | 123bingbing

# re: google笔试的败笔(大家来仁者见仁哦)  回复  更多评论   

@katlao

对;呵呵;这个地方是记错了;上交的卷子是这样写的;

觉得还应该能继续推导的;当时在考场上没有推导出来;因为都与t(3)有2的幂方关系

另外,我觉得另外的思路上正向做,并且存储每一个数字;

我现在思考的是倒向是否有办法存储呢?
2006-10-18 16:21 | crazycy

# re: google笔试的败笔(大家来仁者见仁哦)  回复  更多评论   

@123bingbing

我曾经加入了47个群;呵呵,现在只留了4个,拒绝新的群了。
2006-10-18 16:31 | crazycy

# re: google笔试的败笔(大家来仁者见仁哦)  回复  更多评论   

最优的算法是推导出递推公式的,但是那个要用到矩阵,有一些技巧来推,我当时也没有推出来。次优的一个方案是对中间的结果进行缓存,dp阿,O(n)的复杂度,而不是O(3^n)
----------------------------------------------------
int buffer[n+1]

buffer[0] = 1; buffer[1] = 1; buffer[2] = 2;

for(int i = 3; i<=n; i++)
buffer[i] = buffer[i - 1] + buffer[i - 2] + buffer[i - 3];

return buffer[n];
2006-10-18 19:38 | yangfan

# re: google笔试的败笔(大家来仁者见仁哦)  回复  更多评论   

我把楼上的作了一下修改,也不知道是改好了,还是改差了,呵呵
就是把计算的结果存储到数组中值最小的元素当中,因为它对以后的计算已经没有用处了
虽然节省了空间,但是不知道速度会不会明显变慢

public static int t1( int n ){
if( n==0 ){
return 1;
}else if( n== 1 ){
return 1;
}else if( n==2 ){
return 2;
}else{
int[] b= new int[3];
b[0] = 1;
b[1] = 1;
b[2] = 2;
for( int i = 3; i < n+1; i++ ){
b[i%3] = b[i%3] + b[(i+1)%3] + b[(i+2)%3];
}
return b[n%3];
}
2006-10-18 22:38 | 马嘉楠

# 我的  回复  更多评论   

#!/usr/bin/python
x=[1,1,2]
def T(n):
if n > len(x)-1:
x.append(T(n-1)+T(n-2)+T(n-3))
return x[n]

import sys
print T(int(sys.argv[1]))

$ python test.py 100
180396380815100901214157639
2006-10-19 09:22 | oneleaf

# re: google笔试的败笔(大家来仁者见仁哦)  回复  更多评论   

重贴,不到1秒
[code]
#!/usr/bin/python
x=[1,1,2]
def T(n):
if n > len(x)-1:
x.append(T(n-1)+T(n-2)+T(n-3))
return x[n]

import sys
print T(int(sys.argv[1]))
[/code]

$ python test.py 1000
2758842807766486252615892411656158645133100149652696210351601845036392978912293462801016485671033253921841350537004356434253826361707295202024537559785200706502368152965047761644352316799391470273906561574500883480570560512982435681502330814068718832813973880527601
2006-10-19 09:36 | oneleaf

# re: google笔试的败笔(大家来仁者见仁哦)  回复  更多评论   

@马嘉楠
不错!
2006-10-19 12:28 | katlao

# re: google笔试的败笔(大家来仁者见仁哦)  回复  更多评论   

是不是还得考虑溢出的情况?
2006-10-19 14:39 | Gasbarroni

# re: google笔试的败笔(大家来仁者见仁哦)  回复  更多评论   

#!/usr/bin/python

import sys
import datetime

def T(n):
if n == 0:
return 1
elif n == 1:
return 1
elif n == 2:
return 2
else:
i = 3
a = 1
b = 1
c = 2
while i <= n:
d = a + b + c

if i == n:
return d
else:
i = i + 1
a = b
b = c
c = d

t_start = datetime.datetime.today()

print T(int(sys.argv[1]))

t_end = datetime.datetime.today()

print t_end - t_start


当n=100000时执行时间为5.86秒
2006-10-19 17:20 | wes109

# re: google笔试的败笔(大家来仁者见仁哦)  回复  更多评论   

都乱了,大家可以到http://bbs.btant.com/viewthread.php?tid=80&extra=page%3D1

copy代码
2006-10-19 17:22 | wes109

# re: google笔试的败笔(大家来仁者见仁哦)  回复  更多评论   

@Gasbarroni

哦 题目中声明了不需考虑溢出

呵呵
2006-10-19 19:14 | crazycy

# re: google笔试的败笔(大家来仁者见仁哦)  回复  更多评论   


崔崔强啊,到google面试了?

2006-10-19 23:49 | pigo

# re: google笔试的败笔(大家来仁者见仁哦)  回复  更多评论   

“发现mm还是超级可怕滴,眼睁睁看着一个骗局”,恩,建议你闭上眼过日子:)不然一睁眼就是怕怕了~
2006-10-20 00:09 | qqsy

# re: google笔试的败笔(大家来仁者见仁哦)  回复  更多评论   

程序在运行中由于数据值过大,会导致溢出,所以在程序中计算时间的准确性值得怀疑.
2006-10-20 10:07 | joycsharp@hotmail.com

# re: google笔试的败笔(大家来仁者见仁哦)  回复  更多评论   

给出此问题的一种“记忆”解法(java解法)
//n的值到了80应该要超出Long型的范围了
static long[] knownT=new long[100];
public static long t(n)
{ long t;
if (knownT[n]!=0) return knownT[n];
if(n<0) return 0;
else if(n==0) return (knownT[n]=1);
else if(n==1) return (knownT[n]=1);
else if(n==2) return (knownT[n]=2);
else if(n>=3) t=t(n-1)+t(n-2)+t(n-3);
return (knownT[n]=t);

}
数据再大一些,只有使用BigInteger了。



BigInteger
2006-10-23 10:13 | oliver456

# re: google笔试的败笔(大家来仁者见仁哦)  回复  更多评论   

不好意思

long t=0;

要不然,会出现编译错误
2006-10-23 10:17 | oliver456

# re: google笔试的败笔(大家来仁者见仁哦)  回复  更多评论   

@wes109

乱了,乱了
重新来过,哈哈
2006-10-23 22:55 | 马嘉楠

# re: google笔试的败笔(大家来仁者见仁哦)  回复  更多评论   

#!/usr/bin/python
x=[1,1,2]
def T(n):
if n < 3:
return x[n]
else:
for i in xrange(n-2):
x.append(sum(x))
x.pop(0)
return x[-1]

import sys
print T(int(sys.argv[1]))

time t.py 150000

real 0m9.860s
user 0m9.553s
sys 0m0.016s
2006-11-01 20:43 | guyingbo

# re: google笔试的败笔(大家来仁者见仁哦)  回复  更多评论   

int T(int n)
{
int i, temp, a[3] = {1, 1, 2};

for (i = 3; i <= n; ++i)
{
temp = a[0] + a[1] + a[2];
a[0] = a[1];
a[1] = a[2];
a[2] = temp;
}

return a[2];
}
2007-10-01 10:35 | peng

# re: google笔试的败笔(大家来仁者见仁哦)[未登录]  回复  更多评论   

int T(int n){
int a=0,b=2,c=1,d=1;
for(int i=3; i<n; i++){
a = b+c+d;
d=c;c=b;b=a;
}
return a;
}
2008-03-08 16:52 | jimmy

# re: google笔试的败笔(大家来仁者见仁哦)[未登录]  回复  更多评论   

晕 大家难道就没有 发现 递归 运算最大的问题是重复计算嘛?
2008-05-28 22:54 | 季失羽

只有注册用户登录后才能发表评论。


网站导航: