瞎扯淡 面试归来 分享一下面试题

karmue · 2014年03月22日 · 最后由 chiangdi 回复于 2014年04月10日 · 5732 次阅读

投简历时候没仔细看 后来发现不是招 ruby 的而是新毕业生的 一共四道

  1. 如果你要写一个简单的游戏,你说说会写哪些 class
  2. C++ 中的 linked list,例如 1->2->3->4->5->6->7->8->4 这种中间有循环的 Linked list, 要怎么用最有效的方法来判断他中间是否有循环,每个 element 都是由一个 pointer 指向下一个
  3. mmddyyyy 的格式的日期,10022001 正反顺序都一样,请问之前一个最近的正反一样的日期是哪年哪月哪天
  4. 两个鸡蛋和一座楼,楼有若干层,从一个固定高的楼层扔下去 鸡蛋会碎,低于这个高度则不会,怎么最有效的找出哪层鸡蛋会碎,鸡蛋不会积少成多的摔碎

  5. 是考 oo 概念的,我写的还好

  6. 我脑子崩了,不熟悉 c++,完全不知道怎么做,只知道笨办法,后来他提示我半天才明白

  7. 很简单,估计论坛上的童鞋 5 分钟内都做的出来

  8. 本人太紧张了,刚开始完全没门路,假设了几个楼层高度然后得出了几个答案,说了他都说你能做的更好吗,后来才猛然醒悟他要看的是方法,是一个公式而不是一个结果,公式列出来然后拿微积分求答案...不过感觉这道题做完他已经不耐烦了....

然后就面试结束了...估计没戏了 算了 不去想了 反正我在现在这家公司也不好意思跳槽....

这题好难啊。

我来猜一下,第四题是不是,第一个鸡蛋每 m 层扔一次,求 n/m + (m-1) 的最小值。求导得 -n/(m*m)+1,当导数为 0 时,m = sqrt(n),代回去得到 2*sqrt(n)-1 -> O(n^(1/2))

是否存在 O(log n) 呢?或者能证明 O(n^(1/2)) 是最小了?

2 楼 已删除

第 4 题可不可以这样做

1) 拿一个鸡蛋用机器测量摔碎时受到外力的大小 2) 根据物体的质量以及高度计算出在多少高度的时候会产生与外力相同的力 3) 根据高度计算出楼层的临界值

#2 楼 @billy 。。。这个笨办法也过于笨了吧…………

只要从 2001..1000 往下构造正反一样的字符串……然后验证是否是有效的日期就行了吧。。。

#1 楼 @bhuztez 我得出的方法就是这样的 这道题考察的如何解决问题 而不是具体的数字答案...可惜我有点紧张 浪费了很多时间才得到这个公式...

2 和 4 其实都是网上传很广的那种的面试题。。。

………………感觉没啥实际意义。。。

#2 楼 @billy 不用写程序 直接拿笔算就可以了

#3 楼 @ywjno 同学你是来砸场子的吧...= =''

@Kabie 那样不会有很多不必要的数字么,比如大于 12 的月份等等。愿闻其详。 @karmue 那岂不是数学考试一样。

#10 楼 @leozwa 思路是这个思路啊,但是没有证明 O(n^(1/2)) 是最小的啊

#8 楼 @leozwa 说实话我第一个反应的就是用物理的方式来解决这个问题。。。

#8 楼 @leozwa 他是要一个通用方法吧…… 其实这题只要考虑到只剩一个鸡蛋的时候只能一层一层试……基本就能想出来方法了……

#9 楼 @billy 你的做法需要循环 1000x12x31 次啊……实际最多只要循环 1000 次 懒得开 ruby 解释器……明白意思就好……

def verify(d):
    return '00'<d[0:2]<'13' and '00'<d[2:4]<'32'

for i in range(2001,999,-1):
    s = str(i)
    if verify(s[::-1]+s):
        print(s[::-1]+s)

第三题不是考编程的 因为编程递增 loop 的话太简单了 而你拿笔用逻辑推理是可以推导出答案的

第三题的答案是 12311321 咩(直接通过 mmdd 来得出 year)

12311321 咩

#15 楼 @ywjno #16 楼 @lazy

不对 不仅要知道要从哪一位开始推导 还要有 attention to details

#17 楼 @karmue 很简单嘛,从 dd 来推导, dd 减 1、year 减 100,基本也就是 (01 31 30 29) 这 4 个数中考虑了,29 太大直接无视,反序最大的年的前两位是 13,year 的前两位就是 13xx, 再把最大的 mm 以及它的反序给带入,就得出 12311321

然后发现居然说不对,我。。。

先从日开始,肯定小于 31,所以是 13xy 年,然后是 x,从最大 9 开始,所以应该是 09311390,但是还要注意是不是有效日期,不过这个题到底是要考推导?还是写个通用的程序呢?没有说明吗?

#20 楼 @michael_roshen 9 月没有 31 号 呵呵 所以还有 attention to detail

看来应该是 08311380,一位数月中最大的大月

#21 楼 @karmue 哈哈,细节就是哪个月有 31 就是哪天,7 月吧

#21 楼 @karmue 百度了一下,1 3 5 7 8 10 12 是 31 天的,4 6 9 11 是 30 天的,我只记得 1 月大,2 月小,3 月大...

@ywjno 我的结果和你一样08311380

2 考的常见算法:pointer chasing

4 其实题目有个关键:这个楼是电梯的还是楼梯的... 楼梯的效率计算法和电梯的计算法很不一样... 举个简单例子:楼梯的可以这么扔:先上 m 楼扔,不碎就再往上走 m 楼扔另一只,不碎就下 2m 楼捡起两只鸡蛋再上 3m 楼扔...

#3 楼 @ywjno 还需要一个参数:地面硬度。或者直接用发球机用 n*(2gh)**0.5 (h 是一层的高度,n=1,2,3,...) 的速度照地面打好了

第二题答出来两个指针一个步长一一个步长二就可以了

28 楼 已删除

#28 楼 @llvm 这样应该会被面试者直接赶出去吧

估计是某种外企。前两个编程入门知识,后两个智商为主,算法为辅。

今天我过生日,早上居然收到这个公司的 offer 了 哈哈

#31 楼 @karmue 面试之后公司竟然考虑了半个月?有点奇葩啊

生日快乐!跟我舍友同一天哈

#32 楼 @datty258 之前还有个 2 面,问的都是技术无关的问题 我当时觉着没戏来着

我觉得最后一题的,就是第一层楼摔下去肯定就碎了。就是从桌子上摔下去也碎了啊。

需要 登录 后方可回复, 如果你还没有账号请 注册新账号