当前在线人数16263
首页 - 分类讨论区 - 海外生活 - 待字闺中版 -阅读文章
未名交友
[更多]
[更多]
文章阅读:发个google的面试题
[同主题阅读] [版面: 待字闺中] [作者:Michelle85] , 2013年01月10日14:52:46
Michelle85
进入未名形象秀
我的博客
[上篇] [下篇] [同主题上篇] [同主题下篇]

发信人: Michelle85 (Michelle), 信区: JobHunting
标  题: 发个google的面试题
发信站: BBS 未名空间站 (Thu Jan 10 14:52:46 2013, 美东)

刚收到消息,悲剧了,意料之中,不过我也还ok,还有其他公司move on吧,可能今年
准备的还是不够,希望能对其他找工作的人有帮助。

一共三题,有一道是c++的基础题,那个很简单,基本你要是会c++应该就会写。

另外两道题
1 第一道题,是说你知道(n&(n-1))得出什么结果吗?
  这个好答,我当时说这个我见到过,是看一个数是不是2^n,然后他问,除了这个之
外,还可以用在别的地方吗?然后他问了这个之后,我主要是不知道他要问的point在
哪。。。最后兜兜转转地跟他聊了很多,结果最后终于知道,他要的答案是,“n&(n-1
)”改变最后一位不是0的数字。I mean,这个我未必不知道,但是他问我还可以用来做
什么的时候,我确实不知道他想要什么答案,因为这个可能可以用在很多情况下

2 第二道题,以1/(2^n)的概率返回1,其它的时候返回0,题目应该假设有个函数可以
生成1或者0,以1/2的概率
  我当时想了一下,最intuitive的想法是先产生一个数,num = 1<<n,然后 result =
(double)num * rand();
  当时写的时候没有把num转化成double,这是一个bug,并且我觉得这个bug其实是不
应该的,也是个很关键的bug。 然后他不满意,我也知道,我说n很大的时候num会
overflow,这个时候有两种解决方式,一种是用BigInt,还有一种用divide and
conque,举了个例子,如果int是16位的话,那么n大于16的时候,就不断地divide and
conque,直到小于16为止。
  然后我第二天把这个问题想了一想,我现在来讲,比较好的解决方法是:
  int probability(int n){
      std::vector<int> vec_n;

      int i;
      for(i=0; i<n; i++){
          int t = fun_0_1();
          vec_n.push_back(t);
      }

      if( vec_n[0] == 1 )
          for(i=1; i<n; i++){
                if( vec_n[i]==1 )
                    break;
          }

      if( i==n )      
          return 1;
      else
          return 0;
  }

说实话,题目不难,但是第一题,我真是没看出来他想要什么样的答案,并且最后他要
的这个答案的方向,我觉得很奇怪,其实我最后给他的答案跟他这个意思也很相近了,
但是他觉得这不是他想要的,我也没有办法。
第二题,说实在的,我觉得divide and conquer是可行的,并且这个方法的效率也不差
,但是我觉得最后的code写得还是很不完美的,有两个地方我做的不好,一个是不能假
设int为16位,可以用sizeof函数算出来,第二个我divide and conquer的时候没有考
虑到奇数偶数的问题,这个应该是考虑到的,不然没有办法保证产生的概率是1/(2^n)
不过其实我依然觉得,这个题目不难,但是也不像想象中的那么简单,主要是这些并不
是常见的算法和数据结构的题目,没有碰到的时候,你一下子能不能有最好的思路,这
个很难说。
最后希望大家面g家的人好运了,如果能碰到相同的题目,算是对你有点帮助了。
--

※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 67.]

[上篇] [下篇] [同主题上篇] [同主题下篇]
[转寄] [转贴] [回信给作者] [修改文章] [删除文章] [同主题阅读] [从此处展开] [返回版面] [快速返回] [收藏] [举报]
 
回复文章
标题:
内 容:

未名交友
将您的链接放在这儿

友情链接


 

Site Map - Contact Us - Terms and Conditions - Privacy Policy

版权所有,未名空间(mitbbs.com),since 1996