你好,游客 登录 注册 搜索
背景:
阅读新闻

大数据爬虫实习面试题

[日期:2015-07-20] 来源:CSDN博客  作者:潇洒走一回LW [字体: ]

大数据

  公司就不说了,等下公司面试官看到不太好……

  面试问题(职位:大数据创新中心爬虫方向实习):

  一面:

  1.给一个数组,里面数据比如:2 3 4 1 1 1 1 1,值代表往后最多能跳多少次,问跳到最后一个的最少步数?(贪心)

  答:这题刚开始想的dp,后面想不出方程,然后用了说dfs暴力搞时间复杂度n!,然后再想一下,我觉得是贪心,然后还没说出他就说你想一下贪心,然后想了30秒就想到了,跟他说了下思路,然后他说对了,不用写代码了。然后又问我怎么证明对不对?这个想了好久不知道怎么证明,因为贪心证明感觉是挺难的,然后说不会……

  2.给一个楼梯,从最下面往上走,每次可以走1到n步,求总共有多少种走法?(dp或者公式)

  答:这题我还给校赛出过题,所以记忆特别清晰,一看就知道是dp,而且方法特容易。

  然后他说能不能更快一点的?

  然后我说这好像有公式的吧,我推了一下,推的时间好像超过2分钟了,然后他就提示了一下说用二进制的方法试一下?

  然后发现都是2^(n-1)。

  3.还有什么问题我忘了……

  二面:

  1.给一个字符数组,字符包含a-z、1-9,比如:a b c 4 b 2 a c 1 1 3,求只出现一次的第一个出现的字符?(这题太坑,HashMap+queue)

  答:这题我感觉太容易了,然后说就用一个数组统计一下字符出现的字数,然后再遍历一下这个统计的数组,第一个出现的就是了。

  然后他说你能只遍历一遍,然后O(1)输出这个字符吗?

  然后想了好久,想过set、map、queue、list等,还是没想出来,然后跟他说没想出来。

  然后他说你试试用你刚才的两个数据结构组合试一下,然后我又想啊想,也没想出来。

  然后他说你看看这个LRU Cache,这个里面就是用的HashMap和queue,你再试一下用这两个。

  然后我想,你不是说O(1)的吗,现在这些最少也O(lgn)啊,不是坑我嘛!

  然后我又想,也没想出O(1)的方法。

  然后他说queue统计次数,HashMap存储queue的指针不就行了嘛,然后演示了一下,感觉会了,然后他让我写出代码来……

  然后发现虽然思路会了,但是HashMap怎么存指针不知道,然后还是说没会,然后他感觉我指针不会还是啥地,就让我写一下单链表的结构和查询一个值的函数,然后1分钟就搞定了,他说那还行吧……

  (那时我都想跟他说了,刚才用的HashMap和queue不能达到O(1)的复杂度输出结果,而且空间复杂度还非常大,虽然能降到O(lgn),但是O(n)就只用了一个数组就行了,后面感觉不能顶撞他,所以不敢说……)

  2.有一个html文本字符串,让我取出sflkj这个a标签里面的href的链接地址?

  答:这个刚开始我直接for遍历的,写了十几二十行代码他看不下去了,说有如果有个find函数寻找字符串首地址,重新写一下看看。

  然后我又擦了重新写,又跟他聊了bug,说链接地址里面可能有>什么特殊字符的,然后我又处理,写了几分钟吧,写好了,然后他说还行吧,不过还得优化一下,让代码最少。(因为我定义了4,5个int的变量让他不爽)

  然后他又给我写了一下最优化的代码,只用了一个Int变量就行了,代码也比我的短。

  3.用bfs把一个图改成树?二维数组表示图这个直接队列模拟一遍就行了。

  但是我用的也是二维数组表示的树,然后他说你能不能用一个结构体表示一下树,然后我想了一下只会二叉树的结构体,然后他提示说二叉树不是一个左右结点嘛是吧,如果多叉树的话,你放一个list存子结点不就有多个了嘛,然后才恍然大悟。

  总的来说,比第一次面试其他公司好多了,第一次面试问的基本不会,因为考的不是算法和数据结构方面的,都是问的框架或者别的东西,然后还没复习到,所以这次还行吧。

  但是他说,你写的代码多多少少都有点问题,写一遍还要debug一遍,你之前比赛的时候写代码每次写一遍还要debug吗,不能一次就搞定吗?

  然后我说比较容易的题目一般都是写一遍就行了,难的题目可能要debug一下,然后可能他觉得还行吧。

  然后他又说,我发现你好像不太会举一反三啊,数据结构那些你都还行,但是组合起来就不行了,然后我只能语塞……

  他问我能实习多久,这个之前我觉得实习3-5个月就好了,然后再去别的公司实习这样;就跟他说3,4个月吧。然后他想了一下说,不能再久点了?我说因为明年4,5月要做毕设,所以明年四月之前都可以,然后他算了一下,感觉时间挺多的吧,但是之前说的3,4个月有点少。因为把这个时间告诉学长们的时候,他们说一定要说半年以上,不然公司可能因为这个原因挂掉的!然后我才发现之前跟他说的 3,4个月可能会影响面试结果,无语了,如果他真因为这个原因挂我的话,那只能再去面试别的公司了……

  最后问我有什么问题有问的?我就问了大数据方面的,用的什么语言,他说用的go(一面的面试官挺膜拜他的,说他用go写了一个分页式的爬虫框架,现在公司都在用他的,据学长们说他是行业的典范,出过书,而且从Hulu回来的)……





收藏 推荐 打印 | 录入:Cstor | 阅读:
本文评论   查看全部评论 (4)
表情: 表情 姓名: 字数
点评:
       
评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款