求职 面试时候如何用 Ruby 写一个最短二分查找代码

mvj3 · 2014年01月03日 · 最后由 yfractal 回复于 2017年07月12日 · 15480 次阅读
本帖已被设为精华帖!

声明: 以下描述并非抱怨,而只是针对面试中的算法题,希望给别人提供点借鉴,更多地清醒头脑,理清思路,跳出当时的思维局限,和面试官互动解决掉面试题。

本人技术背景: 全栈式 Ruby on Rails 开发四年多,并在大数据分析方面有些经验,详见个人主页 http://mvj3.github.io


今天面试的时候被要求手写二分查找代码。

这让我不由得想起几年前去 yottaa 面试要求手写二分查找代码时失败的窘迫来。于是我和面试官提了说,有人说过 专业程序员里的 90% 都无法正确实现二分查找 ,而且我之前用 二分查找实现过日志二分查找 ,大概原理就是不断依据范围进行折半查找。面试官还是要求现场写一个,于是我只好硬着头皮开始写了,不断回想和思考里面的边界和技巧,脑子里一团乱,在纸上写实在没感觉(因为要运行程序测试嘛,本人的大脑还不是 CPU。。。),就打开自己带的笔记本开始写了。

测试代码是:

puts binary_search((1..15).to_a, 8) == 7
puts binary_search((1..15).to_a, 1) == 0
puts binary_search((1..15).to_a, 14) == 13
puts binary_search([2,3,8,15], 8) == 2

这个没有疑问。然后先写了代码的轮廓,因为之前项目有好多模块都是通过递归实现的,就构造了一下 binary_search array, value, from, to 这样的 API,最终代码是:

def binary_search array, value, from = nil, to = nil
  return nil if array.blank?

  from ||= 0
  to   ||= array.size
  mid_idx = ((from + to) / 2.0).round
  mid_val = array[mid_idx]

  if value == mid_val
    return mid_idx
  elsif value > mid_val
    binary_search array, value, (mid_idx+1), to
  else
    binary_search array, value, from, (mid_idx-1)
  end
end

测试通过。面试官反应用迭代方式实现,他说有性能问题。这里稍微和他有些讨论,迭代就迭代吧,我和他说那就用这第二种方式实现。

这次写的时间比较久,估计在二三十分钟,遇到死循环的问题。途中和面试官抱怨了一句,他回说就是考边界。最终调试无果(当时我严重怀疑是边界出了问题,但是我想不起那个准确的解法),就说和面试官一起看看吧。

def binary_search array, value
  @idx = nil

  loop do
    @from ||= 0
    @to   ||= (array.size - 1)

    return nil if array[@from..@to].blank?

    puts "+ #{@from + @to}"
    @idx = ((@from + @to) / 2.0).round
    puts "[#{@from}, #{@to}] #{@idx}"
    #binding.pry

    mid_val = array[@idx]

    if value == mid_val
      break
    elsif value > mid_val
      @from = @idx.round
      break if value == array[((@from + @to) / 2.0).round]
    else
      @to = @idx.round
      break if value == array[((@from + @to) / 2.0).ceil]
    end
  end

  return @idx
end

上面在跑前二个用例是准确的,但是第三个有点异常了,现在回来一看才发现是实例变量在方法多次调用后混淆的问题。而其中出现 round 和 ceil 之类方法的原因是他和我提到了之前远程面试时做的一个题目里我没有用 String#chars 这样更 Ruby 的写法,而是用了 str.split(//) ,所以我潜意识里可能顺着他的这个原则走了,当然这里的路走错了。

下面的是我现在改好的:

def binary_search array, value
  puts "查找数组 #{array}, 值 #{value}" if ENV["DEBUG"]
  from, to, idx = 0, array.size.pred, nil
  loop do
    return nil if array[from..to].blank?

    idx = (from + to) / 2
    mid_val = array[idx]
    puts "起始 #{from}, 终止 #{to}, 当前索引 #{idx}"  if ENV["DEBUG"]

    if value == mid_val
      break
    elsif value > mid_val
      from = idx + 1
    else
      to = idx - 1
    end
  end

  return idx
end

在和他讨论这个迭代的死循环代码时,他指明写的太冗余了,好的写法应该可以更短。这个就突然提示了我想起以前其实在 yottaa 面试结束后回家就调查了相关资料,然后写过 这两个版本 的,里面还包括插入功能,更深的影响就是加入 eoe 后写了上面提到的 logpos 日志二分查找模块。

然后我打开以前保存的代码,给他看,他反馈说还是可以更短。我说能不能找给我看。他说你回去可以自己找。

现在回来搜了一个迭代版本的, http://gistflow.com/posts/199-binary-search-with-ruby-and-tdd

class Array
  def iterative_bindex element, lower = 0, upper = length - 1
    while upper >= lower
      mid = (upper + lower) / 2
      if self[mid] < element
        lower = mid + 1
      elsif self[mid] > element
        upper = mid - 1
      else
        return mid
      end
    end

    return nil
  end
end

按语义来说,包括关键字和方法, %W[class Array def iterative_bindex element lower = 0 upper = length - 1 while upper >= lower mid = () upper + lower / 2 if self[] mid < element lower = mid + 1 elsif self [] mid > element upper = mid - 1 else return mid end end return nil end end] ,为 55 个词。

而我回来后实现的版本, %W[def binary_search array value from to idx = 0 array size pred nil loop do return nil if array [] from .. to blank? idx = () from + to / 2 mid_val = array [] idx if value == mid_val break elsif value > mid_val from = idx + 1 else to = idx - 1 end end return idx end] 为 62 个词。

我个人觉得两者无甚区别。不知道哪位大牛可以给出更短的 Ruby 版本,标准算 40 个词吧。

最后面试官总结我应用或 Rails 方面的经验比较多,但是算法不太行,他准备和 CEO 再讨论看看。于是我咨询他公司技术部有哪些算法工作,他提了一个数据排重,然后我说如果准确度不太要求的话,可以用 bloomfilter 进行过滤。但是他坚持这一轮面试结束了,于是只能出门和他道别了。

额,只能等后续再沟通了,总之有点冤。。。


本人之前写过 前端工程师的面试也可以如此生动 ,过段时间也总结一篇如何面试 Ruby 工程师的文章吧。

看起来这公司对算法的实际使用要求很高

#1 楼 @goinaction 手写二分查找代码要求还高啊。给个动态规划题目做才是面算法吧。要求高的就给个复杂算法项目了。。

#1 楼 @goinaction 这应该是面实际 coding 能力。二分法大家都清楚的。来一个快排估计会筛掉 95% 的人,ruby 人本来就少筛筛就没有了。。

#1 楼 @goinaction 谁没事自己写二分查找啊,写错了咋办 ...

#4 楼 @bhuztez 二分查找是对于实际编码能力的一个测试。能够在面试时间里面完成的,方便统一考察编码能力的项目,也就简单算法题目了。

#5 楼 @linjunhalida 给出所有边界情况的正确处理方法太容易,不给又太难 ...

招个人,算法完了,还要和 CEO 讨论,感觉不靠谱啊。薪水可不能少要。

8楼 已删除

#1 楼 @goinaction 从单独给这道题和我问的算法业务还真没看出来,就大部分应用层的 Rails 系统而言,真的不需要应用什么算法,当然这也不是说算法就不需要了解和掌握,它对你架构系统有好处。如果写一些底层库,可能需要那么一些算法,但是很多开源都有,而且也只是作为一个模块引入即可,所以应用层的开发人员只需要了解原理即可。

#2 楼 @linjunhalida "手写二分查找代码"难度其实挺高的,在同样了解基本算法原理条件下,除非面试者提前背书,否则写的代码真的有 BUG。二分查找算法"虽然早在 1946 年就有人将二分查找的方法公诸于世,但直到 1962 年才有人写出没有 bug 的二分查找程序。",我觉得我们论坛大部分人都比不过那些大牛吧,何况也没人发明个厉害的基础算法出来,所以面试中的大部分实现我可以说就是和高考一样的性质,背书而已。

本人不是算法大牛,智商也只是够考个三本学校而已,了解的常用算法最高层次也只有二分查找和 B-Tree 等相对直观的概念而已,其他高级的红黑树,优先队列等数据结构我可能就得花一点时间去明白其中过程。

但是这不妨碍我写诸多 Ruby 相关开源软件统计分析引擎框架 statlysis 。就个人直观的理解,常用算法无非就是 CPU 和 IO 互换,或者发现里面某些规律,比如以下几种(数据挖掘和机器学习等排除)

  1. 各种树,无非是针对查找,删除,插入等组合优化。
  2. 各种排序,里面包含各种二分,三分,广度优先,深度优先等思想。
  3. 散列,只要知道映射原理就可以了,如果对 IO 有要求的,可以适当降低精度。
  4. 图论,这个 Web 开发一般还真用不到,我唯一用过的是 依赖排序
  5. 动态规划简单的就是理解为 Rails 里的各种组合和缓存嘛,哈夫曼编码也就是排个序映射一下而已,等等。

以上可能有错误,望算法大牛指点!我分析的关键点是上面的都太数学了,是给 Knuth 等搞数学的人玩的,给那些写数据库,操作系统,网络等的大牛们玩的。

而对于像我这样的类似 DHH 一样容易数学不及格的人直观的理解这些算法即可,也许我们更懂得直观的如何像作一幅油画一样把一个大型程序写好并模块化,依我看 Web 开发大牛 @huacnlee 也是属于这种人。

#4 楼 @bhuztez 在理,算法的话,我们就阅读和使用为主,真的要实现那也是因为符合不了实际业务。

二分真的很不难…… 无理的要求是让你实现 rb tree,avl tree 这种。

举个 Python 的例子,假如我面试某人,出了一个需要使用二分查找的题

知道二分查找的基本原理,但写不出正确程序的给 D 写出正确程序但是性能不是最优的给 C 写出正确的二分查找实现的给 B 用 bisect 标准库的给 A

说我需要搜搜 Google 看看 Python 有没有二分查找的库/实现的也给 A,真的

#10 楼 @rasefon 你之前从来没听说过没写过,突然让你写,而且在有很大压力的情况下,还只准用纸笔,你确定 你一定能 10 分钟给我写出个对的来吗 ...

#12 楼 @bhuztez 二分你从来没听说过…… 我觉得像 kmp 这种即使看过很多次也容易忘的算法确实难了点,但二分就像快排是最基础的。

#13 楼 @rasefon

  第 2466 位会员
ID: rasefon
Name: Raw
城市: 上海市
公司: Autodesk
Email: rasefon@gmail.com
Since: 2012年6月08日
倍受大家喜欢的帖子

Ruby 发个很好的 Ruby VM 的学习资料 13 人喜欢, 9 条回复
数学 傅立叶变化的完美解释。 5 人喜欢, 6 条回复
算法 相似图比较算法。 2 人喜欢, 2 条回复
瞎扯淡 恒大威武!!! 0 人喜欢, 39 条回复
瞎扯淡 关于 C++,关于 gc 的一些东西 0 人喜欢, 24 条回复
瞎扯淡 分享一首非常赞的歌和歌词。 0 人喜欢, 1 条回复
Ruby 无意中找了 ruby 语法的伪 BNF 范式,发出来给大家参考一下。 0 人喜欢, 4 条回复
Ruby 2.0 respond_to?(x,x) 坑死人! 0 人喜欢, 4 条回复
瞎扯淡 最近想到一个关于上传图片的问题。 0 人喜欢, 8 条回复
Gem Ubuntu 下国内的 gem 镜像有问题。

对于这种以关注 VM, 傅里叶,相似图,BNF 范式的人去写二分查找,红黑树,AVL 树等数据结构为兴趣的人,本人表示不需要解释。

#13 楼 @rasefon 听说过啊,经常拿来当考算法的反例的那个么。除此之外真心没见过,也没用过 ...

反正我觉得多看看算法总是非常有用的。

常用排序查找算法都不会写就不要去面试,浪费双方时间

#17 楼 @rasefon 但是我反对面试时过多的考察这种单向编码的笔试,而是应该结合业务来互动为主,当然这个得要求面试官有足够的驾驭能力。

我最讨厌压力编码了,这就是变相的加班,把工程师当码农使。写程序其实是个创造性的过程,只有艺术家自己才能给自己压力,外在的压力只会导致堆砌垃圾冗余问题代码。

#18 楼 @camel 写和理解是两回事(我个人觉得最重要的是结合业务能深入的理解),做学术写的代码和做工程写的代码也是两回事。这种只占软件工程里一小部分的算法,我觉得没必要拿出来太当回事。

请问你写过的软件中有多少是需要你手工实现这种基础算法的,如果简单或有很强的应用,那为何我们写 Ruby 的基本就用不到呢,而是直接放到 Array#binary_search 就可以了呢。编写常用排序算法,也就是对不会实际工程的刚毕业的学生练练得了。

#18 楼 @camel 怪不得我老是被鄙视啊 ...

#19 楼 @mvj3 我也一直思考,为什么算法已经要变成了面试谈价钱的筹码而不是实用的能力。我的理解,这是比较有效的方法。业务逻辑密集型软件,比如各种 ui,金融软件等,大多也是体力密集型劳动。程序员从中学到的多是对现有工具的用法,很难从中区分 a,b 两个应聘者到底哪个更好。可能多数两人都能很好的完成工作,为了选其一,必须有其他测量方式,算法就是最普遍有效的方式。反过来,算法一直需要温故而知新,久而久之对思维有很大帮助。

#21 楼 @rasefon 算法难道不应该是库的任务么?编程活动难道不是一个不断抽象、不断复用已有知识的过程么?重复实现一个已知算法有何意义呢?

如果是给一个问题让面试者思考解决的算法,这是有意义的。而对于已经非常常见的算法,理解其使用条件和优劣比实际实现更有价值。

我唯一能想到考这种知识的场景就是对工作 1 年左右的人进行测试,主要目的是看他的思维速度、逻辑严密性,另外可以顺便观察一下编程习惯。

#21 楼 @rasefon 算法它的确也是实用的能力,但它只是数学模型,而不是工程模型。因为算法只是从工程中提炼,就像你不会因为 MongoDB 用了 B-Tree 而去为它买单,而是为它提供了良好的工程而买单。所以我以为用人单位对待面试者也应该如此。

对于你举例的"业务逻辑密集型软件,比如各种 ui,金融软件等",如果你觉得它们只是单纯的体力劳动,我不赞同,只能说明你的经验太浅了,我以为两者兼备,而且智力投入更重要,这个从国内外网站的质量就可以看出来。国内对开源软件贡献的太少,而国外的开源遍地开花。国内的只会死板的逻辑性分析开源软件,最多打个补丁,而国外更多在于创造解决方案。

所以对于成熟的软件工程师,比如三四年以上,我以为看 TA 如何解构分析 TA 之前做过的项目更为有益,或者就面试公司的实际工程问题,去考察面试者的经验和思路,以及迭代过程。

#22 楼 @fsword 分析的在理。

#19 楼 @mvj3 面试中之所以重视算法,我感觉是因为:

算法是短期内测试一个人抽象思维和学习能力虽不完美,但最高效的方法 个人非常赞成这种做法。

算法与语言,我觉得后者是软实力,前者是硬实力。

如果要招人救火,写一两年 Ruby 后走人,就招相对熟悉 Ruby 的。 如果要招人一直做下去,并给团队带来新东西,那就招学习能力强的,培养新人的时间不需要很多。

我的团队里有个以前搞 Machine Learning 的,算法那是一套一套的,以前没写过 Ruby,但上来翻两本 Ruby 书就写的很溜,

我相信一个算法好的程序员能写好 Ruby,也能写好 Go,JavaScript....

这是一个有个最近很火的美帝前端面试活生生的例子 http://css-tricks.com/interviewing-front-end-engineer-san-francisco/ 前端面试没有问一个 HTML 相关,CSS 和 JS 只问一两个问题。 问的大多都是算法相关的问题。

事实本该如此

#22 楼 @fsword 我的理解,一是看个人到底愿意做什么。如果愿意做使用者,那也没问题,如果觉得厌倦,那学习算法是有用的。二是可替代性问题,比如我现在做的工作,无非就是用别人写的库,加上些很高层的业务逻辑,做些外围的工作,也即可替代性很高,并且我周围同事做的也都是如此的工作。然而,做同一个产品的一个老美,做的是几何建模算法,比如曲面相交求曲线这类事情。这种工作的可替代性太低了,基本上就是无法替代类的。孰轻孰重,自然是一目了然。 用黑客和画家里面的说法就是,技术的门槛。

「黑客搞懂 “计算理论” 的必要性,与画家搞懂颜料化学成分的必要性差不多大,黑客新想法的最佳来源,并非那些名字里有 “计算机” 三个字的理论领域,而是来自于其解决问题的创作领域。」 我想 ruby 程序员更容易引起共鸣。

#25 楼 @rasefon #24 楼 @camel

毫无疑问,算法好的确实逻辑性会强,但是它只是占工程里的一小块。

你们说的算法的好处这点无可厚非,但是请不要犯了和 “大数据” 这种名词一样忽悠的毛病,搞 Machine Learning 的和搞 Web 工程的是两个工种,多想想 github 的开源软件和 infoq 的实战文章被创造出来的最大来源吧:)

#27 楼 @mvj3 我很赞同你说的,核心算法只占整个工程很小一部分。 主要一点就是,你是不是愿意做那些次要的大部分里的工作呢?

#28 楼 @rasefon 本人作为一个工程师一直在做这种工作,请看我的 开源软件 ,我丝毫不觉得它们是次要的,画家对不必要的细节也会细致的刻绘,国外优秀网站都很注重细节。

说到底,会算法(就是像这种面试)和会利用算法解决实际问题(你想想 Google Analysis 背后的技术吧)真的是两种能力。

#25 楼 @rasefon #24 楼 @camel #28 楼 @rasefon 我觉得你们没注意到关键,楼主的面试是测试编程能力,而不是测试算法能力和水平。把一个大家都很熟悉的、常用的算法拿过来实现一遍,这能够达到对算法能力进行评估的价值么? 所以算法是短期内测试一个人抽象思维和学习能力虽不完美,但最高效的方法这句话和楼主的情况一点关系都没有,而用这种方式面试到的人,也不太可能是那个做几何建模算法的老美,反倒更可能是 “做那些次要的大部分工作的人”(在这个行当里,重复工作必然是次要工作)

#26 楼 @shiny 画家还真得对颜料的化学成分有点研究... 有些专业画家为了特殊效果还自己找矿石来研磨或者合成颜料. 水彩, 水粉, 油画, 丙烯, 硝基漆等等颜料的化学特性决定了相应技法的基础, 学习颜料相关的化学也能帮助选购颜料, 和安全正确的使用颜料...

#25 楼 @rasefon 多数情况下掌握很多业务知识的工程师比单纯做算法的可替代性更低,一般人搞得毕竟是软件工程不是计算机科学。

#32 楼 @luikore 定量的技术容易被规则分析,但定性的艺术很难被分析,画家还是靠艺术修养比较多吧。好的艺术家必然是涉足多种领域的,但是对颜料的研究只是其价值体现很少的一部分。

大师难求呀,很多人只好挑容易验证的标准来考核了。。。

搞编程的,最多的是码农,其次是真正的工程师,稀有的就是创作出像 coffee script 这种级别的黑客了。

#9 楼 @mvj3 比较赞同这种观点。太数学化了,至少我的理解中,常规性的 web 开发不是那么回事情,可能我涉及的一些都太弱了。算法差,并不影响你去发明创建,参与开源项目。资料是可以被检索的,学习的态度很重要。 在这个问题上,关键还是在于从什么角度,哪个层次去看问题,没有正确与否之分。

面试如果不考算法,怎么面呢?

#36 楼 @rasefon 详见 为什么我反对纯算法面试题

看过这上面的分析,我相信你明白我为什么反对纯算法面试题了。原因就是纯算法的面试题根本不能反应一个程序的综合素质!

那么,在面试中,我们应该要考量程序员的那些综合素质呢?我以为有下面这些东西:

* 会不会做需求分析?怎么理解问题的?
* 解决问题的思路是什么?想法如何?
* 会不会对基础的算法和数据结构灵活运用?

另外,我们知道,对于软件开发来说,在工程上,难是的下面是这些挑战:

* 软件的维护成本远远大于软件的开发成本。
* 软件的质量变得越来越重要,所以,测试工作也变得越来越重要。
* 软件的需求总是在变的,软件的需求总是一点一点往上加的。
* 程序中大量的代码都是在处理一些错误的或是不正常的流程。

所以,对于编程能力上,我们应该主要考量程序员的如下能力:

* 设计是否满足对需求的理解,并可以应对可能出现的需求变化。
* 程序是否易读,易维护?
* 重构代码的能力如何?
* 会不会测试自己写好的程序?

所以,这段时间,我越来越倾向于问应聘者一些有业务意义的题,而且应增加或更改需求来看程序员的重构代码的能力,写完程序后,让应聘者设计测试案例。

比如:解析加减乘除表达式,字符串转数字,洗牌程序,口令生成器,通过ip地址找地点,英汉词典双向检索……

总之,我反对纯算法面试题!

以上是摘自该文章总结,我以为我在网上可见的 开源项目 都完全体现了上面所有要求,而这些都是来自我实际工程生涯中的长期结果,要算法有算法,要代码风格有代码风格,要需求分析有需求分析,要文档有文档,要重构有重构,就看面试官能否有水平 Hold 住。

好贴!我觉得无所谓对错,招聘方跟求职者处境类似,他想招到合适的人却不一定有发现分辨的能力。求职者即使有能力也不一定能说服招聘方。不能期待每次都遇到合格的面试官,对双方都是筛选的过程。 我个人认为能力有三个层面,我自己一直是这样去修炼。 算法与数据结构是基本功。所以人家要面试算法也无可非议。 二是解决实际问题的能力,主要是 OOA/OOD。有了 Rails/NodeJS 这样的工具,基本上可以想到哪写到哪,写代码不是主要问题,知道写什么才是问题。 三是搜索能力。当分析出问题所在,你可以就自己的知识范围给出解决方案,但更重要的是发现和利用别人的成果。其实是很难会遇到没有人解决过的问题了,github 上开源项目已经超过 100 万了,stackoverflow 上已经问过无数的问题了。如果真有前无古人的问题,那就是你做贡献的时候了。

#32 楼 @luikore 是需要研究,但是没那么重要吧。就像我们是需要学习算法,但是没那么重要。就像梵高随意用了当时的新颜料,结果化学性质并不稳定,到了今天已经慢慢褪色了。但这并不妨碍他成为一个好的画家。 你精通颜料化学性质那是化学家。

#24 楼 @camel 厉害的毕竟是少数 ...

更多的是,数据怎么表示都搞不清楚,就开始来瞎扯算法,协议大概需要有啥都没搞清楚,就开始来大谈架构,某个模型适用于哪些问题都没搞清楚,就在那里乱套 ...

但是很多面试非要考已经实现的算法的具体实现,真是很无奈啊 ...

#24 楼 @camel 这个角度倒是没问题的。但是我没可刻意去看算法就很吃亏,因为确实平时用不到算法,需要花时间看下。

前年远程面小米,除了问些基础性的,还 mail 收到三道网上到处都是的算法题,当时就喷了——这更像是在考验诚信而不是算法,而且显得他们很没诚意。

对我这个算法盲来说,高深啊

return nil if array[from..to].blank?

blank 是 rails 的, ruby 语法没有滴 ^_^

#42 楼 @shooter 哈,被你严谨地发现了,我是故意去掉了 require 'active_support/all' 以方便理解。

其实写成 from <= to 这种形式就 OK 了,都怪我最近被面试题搞的编程思维太 OO 了。

#36 楼 @rasefon

之前公司来一小哥面试,聊了聊,他提到之前有做过导出 CSV,于是产生灵感,拿出之前帮同学解决过的问题: 一个上百页的有规则的 doc 文档,格式大概是

姓名:张三
公司:xxx
电话:11123

有少量数据错乱,比如

姓名:张三
公司:xxx
电话:11123
姓名:李四

公司:ooo

或者中文的冒号、英文的冒号混用

让他把这个文档转成 excel 能打开的表格,我和他结对完成,思路他完全提供,可以用任何手段,代码他有不会的地方我可以帮他写

我的想法是这样的:

  • 了解他的背景,如果和我需要的不符,那开门见山好了
  • 过去工作学习中积累了很多问题,结合面试者的背景和我需要招的岗位的能力,选择一个问题略做一些调整,交给他去完成
  • 我会和他结对完成,可以观察他的思路、编码习惯,也可以在此过程相互分享经验
  • 这样面试时间也不长,一个小时左右,我认为我对面试者有着充分的重视和尊重

这样面试如何?

#44 楼 @jasl 才一个小时!!!我的面试都跨年了!!!好吧,算周期都有一周以上,平均两三周。。。

#24 楼 @camel

我仔细看了 "这是一个有个最近很火的美帝前端面试活生生的例子 http://css-tricks.com/interviewing-front-end-engineer-san-francisco/ 前端面试没有问一个 HTML 相关,CSS 和 JS 只问一两个问题。 问的大多都是算法相关的问题。",我想你理解的有点偏差了。。。这个正是他认为的反面例子。

他说算法是很重要,但是面试时候得结合实际的前端例子来,比如他举了

$("#nav a")
  .addClass("link")
  .attr("data-initialized", true)
  .on("click", doSomething)

这样的例子来让面试者去解释这背后的原理和执行过程,这样才会让真正好的有经验的前端工程师被选中,他的原话是"The problem is they have nothing to do with front-end development. As I said before, most smart developers with a strong computer science background could answer all of these, even if they'd never built a website."

#45 楼 @mvj3 没有正经公司工作的经验,不过我认为不浪费他人时间精力就是对他人的最大尊重

#46 楼 @mvj3 就是像你我这样的卢瑟才在吐槽啊,稳拿还在继续出这种算法题啊

#48 楼 @bhuztez 也不必这样的,向 DHH 学习吧,做出个 Rails 框架把他们羞死。"他知道也许自己没有数学天赋,也许没有能力解决难题,但是他对他的开发实力和理解力很自信,因为他知道他有另外一种能力——他能将简单的事情变得更简化。" 我觉得我也有这种能力,目前已经开发了 statlysis 统计分析框架,哈哈

话说回来,世界本质还是精英论的,所以该学的算法还是得补,但是它需要更多的宽容和维度,开源和互联网是一种强大的力量。

#49 楼 @mvj3 Rails 那是广告做得好 ...

#39 楼 @shiny 是不重要, 但那是最低要求啊. 难道画家个个都是不需要技法不懂颜料一步就能登天的么...

#51 楼 @luikore「是不重要」「最低要求」两者就是矛盾的吧,这个逻辑…… 呃,有什么东西是最低要求但不重要的呢? 我不懂算法还写了那么多年程序真是给程序届丢脸了呀。

#52 楼 @shiny ... 你现在学也不迟

#53 楼 @luikore 哈哈哈,请教下怎么样的学习路线好?创业团队更多可能会思考产品怎么做,已经后续的架构和扩展问题,算法细节涉及得很少,所以也不是很重视,请多多指教。

#53 楼 @luikore 怎么学啊 ... 求入门宝典什么的

@shiny 干活太忙了没时间充电学习可以理解... 可以向 @bhuztez 请教.

#56 楼 @luikore 真心不会啊,面试从来都是被虐的 ...

其实我感觉问个二分查找没必要出现这么多话。代码写完一放那,直接进入下一话题。而不是写不明白讨论这个问题有没有必要。

#54 楼 @shiny 我觉得这是设置技术门槛的问题,如果都是很容易复制的产品,竞争力就会变低。

#59 楼 @rasefon 算法强对一个成功的起步产品来说实在是很小的因素(除了某些领域),要是真的需要,研究几天搞个协同过滤算法什么的也没问题(当然可能不够好,但够用)。 设计,体验,运营,资金什么的还是最关心的方面。 另外,有钱后再招几个算法强的人也未必不可啊,生存下来了,什么都好说。 😄 于是就有了这样的帖子……

貌似二分查找的应用场合不多,都排好序了,查找就没太多问题了,怎么查都快。考考 quicksort 才对。 不过那时候学的还有记忆,中间变量用的是 k,练下手

def binary_search(ary, num)
  return -1 if num < ary.first or num > ary.last
  k = ary.size / 2
  i = 0
  j = ary.size
  while(i<=j)
    if num > ary[k]
     i = k+1
    elsif num < ary[k]
     j = k-1
    else
     return k
    end
    k = i + (j-i)/2;
  end 
  -1
end

#59 楼 @rasefon 有一种叫数学竞赛,有一种叫数学创造,两种成分每个人都有,当然后者少多了,话语权只能被代表了。

但是当你去应聘一些相对高或者好的大公司的职位时,人家还是拿这种竞赛式的方式来搞,或者拿学历来卡人,而完全忽视了其过往项目经验在该专业能力上体现出来的创造力。 遗憾的是有些人就是适应不了条件反射式的竞赛,TA 们更喜欢通过自省来创造,这方面工程实践可以看 Rails 项目 重构,我在阳光书屋的三个月 ,我对架构和 Model 的重构都是通过内在关系来自省解决的:)

#62 楼 @mvj3 #60 楼 @shiny 我也说不清楚,因为我从来不去做面试官,所以不清楚到底怎么做才最适合。如果我要面试一个人,基础的算法还是希望应聘者能掌握的,不要求细枝末节的方方面面,但是对一个问题,怎样去解决还是需要的。比如二分法,对一些边界条件写的不是很精确这没问题,但是至少要知道它是怎么工作的,伪代码即可。 我一直相信一个对各种算法都了然于心的人,应该是很聪明的,聪明的人就算学新东西,也会快,大概这就是为什么大多数公司喜欢用算法来考人吧。 另外一个人聪明不聪明其实并不是固定的,用的越多越聪明。

#63 楼 @rasefon 我是面试官的话,我会更看重人文涵养,和企业气质是否符合,能否和团队愉快合作,解决实际问题的能力,是否对代码真正热爱,对开源的贡献。 我相信这方面优秀的人,一定能打造一款优质的产品。

当然阿里的「闻味官」也太过份了 😄

#30 楼 @fsword

把一个大家都很熟悉的、常用的算法拿过来实现一遍,这能够达到对算法能力进行评估的价值么?

我没有说只要会写常用算法就能通过面试,这种类似唐诗 300 首的算法是最初级的算法面试。 高级点做法应该是用算法解决问题。像:如何确定链表是否存在环,判断回文,你可以用任何语言实现。

#46 楼 @mvj3

他那个例子是自己 YY 的,在面试中不存在,所以没必要讨论。 他的想法肯定很多大牛想过,但最终大公司还是继续问算法(非语言框架),他们不是傻子。

不管你信不信,低级外包公司最不喜欢问算法问题,最喜欢问框架细节方面的东西。 刚毕业那会搞 Java,面试时都是问 Struts, Hibernate, Spring,如 Hibernate 某个配置项是什么意思。 还好我听到这些问题直接回去了。

低级码农拼的是记忆力,攻城狮拼的是想法,我还差的远。

#65 楼 @camel 怎么判断链表是否存在环啊?真心不会,求教

#65 楼 @camel 。。。” 配置项 “,这帖子里我的全部回复都指明了一点,那就是理解整个框架的运作原理比单单背熟一个算法实现要有用的多。

#66 楼 @bhuztez 两个指针,一个一次进 2 格,一个一次进 1 格,前面那个如果能追上后面那个,就有环,就像两个人绕圈跑步一样。

#66 楼 @bhuztez B 大就别装嫩了☺ 我知道的一种是用龟兔赛跑法http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare

#68 楼 @rasefon 你是怎么知道有这么个算法的,有什么办法可以推导出来么?

#69 楼 @camel 真不会啊,有一次被虐惨了 ...

#70 楼 @bhuztez 初中物理题。。。

#68 楼 @rasefon 完美的龟兔赛跑法解释

#72 楼 @rasefon 这也有关联?

#74 楼 @bhuztez 反正我觉得和以前那种绕圈跑相关的数学物理智力题很像。

#75 楼 @rasefon 那不是想得到就想得到,想不到就想不到。只有多看答案才行么 ...

#76 楼 @bhuztez 没办法啊,其实所有学科都是熟能生巧的。我记得费曼还是谁以前说过,让你脑子里时刻保持 6 个问题,每次有一个想法,试试看能不能解决你脑子那 6 个问题,久而久之你就成了人们口中的天才了。

#77 楼 @rasefon 我现在真心觉得方法不对全是瞎搞,花了时间也没效果的 ...

80楼 已删除

数据结构才学完查找与排序,不过我们是 JAVA 版的,还没用 ruby 来实现过。看到你的面试,个人觉得这方面知识现在应该学牢才行,尝试用不同的方法解决一个问题。

#65 楼 @camel 同意观点。。貌似我去面试基本没有问啥配置。基本都是算法,OS,数据库。。

我面试的时候,算法问题可以通过思路考察,不一定要求写出完善的代码;但是肯定有写代码的考查题,也要考察思路、基本功、代码风格、习惯等等,其中最关健的还是找一些实际场景或者问题问一下候选人的思路,看看他会如何解决相关问题,并且是否能分析出该解决方案的优缺点和改进方向,顺便了解下沟通能力、表达能力、耐心等等,如果有不错的还会考察更多,比如团队合作、职业规划、文化适应性等,甚至有时候还是需要看看情商等,工程师也是需要有情商的。。。

#68 楼 @rasefon 我被问到时也是想到这个方法,但感觉还是不够好。。不知道有没有更好的做法。。。

看来你的 about 让我很惊讶, 为什么你只上了 2 年大学!!

#85 楼 @OneMagicAnt 。。。不用怀疑,就是大学肄业了。

面试应该经验什么的更重要些吧,算法出点差子如果一棒子打倒未免太牵强了

#87 楼 @dddd1919 该公司是文艺型创业公司,CEO 对于我的提问也是置于不理,所以我明白我已被默拒。算了,不去这种不尊重人才和没有大格局的公司了。

def binary_search(ary, num)
  ary.bsearch {|x| x >= num}
end

不知道还能怎么短了……

  1. blank? 是 rails 带来的方法吧?
  2. 没有 from 和 to 的边界判断,puts binary_search((1..15).to_a, 16) == nil

#88 楼 @mvj3 没什么的,每个公司都有自己的风格,有缘有份的干着才舒服

面试 Ruby 还用考算法? 表示那些基本算法只用 C 实现过。。

最短的代码有什么意义?

哈哈,看 lz 的开源东西,是蛮牛的,可惜二分没写好。 我上次面试也写二分,还在纸上用笔写。。。写的时候那个紧张,那个#¥%#%¥%》。。。唉。。。呵呵,共勉。

#93 楼 @blackanger 到目前为止还没有人给出本质上更短的 Ruby 版本( 参与此贴的算法大牛 @luikore 好像也没有看法),所以看来是那位面试官技术涵养有问题,他意思是你要背熟一个最短解法(二分算法解法在细节上还是可以是有很多不同的,我不相信谁在这么短时间里就这种原理性算法可以创造性地发明一个新解法,否则中国的计算机事业赶超美国就不用担心了),否则他看不明白,个人觉得他的水平只停留在王国维的第二层次。

#94 楼 @mahone3297 本人之前更有说服力的二分查找项目 logpos 被他忽视。。。一定得现场背出来一个。

要难倒一个人是很容易的,难的是如何去发掘别人的优点。

迭代版从递归略改下就可以了... 递归改循环的机械方法好像是算法有讲过的? 而且这里是单递归, 改成一个尾调用就很清楚了, 都不用手动加栈.

def binary_search a, e, from=0, to=(a.size-1)
  while to > from           # if to > from
    mid = (from + to) / 2   #   mid = (from + to) / 2
    case a[mid] <=> e       #   case a[mid] <=> e
    when -1; from = mid     #   when -1; from = mid
    when  1; to = mid       #   when  1; to = mid
    else return mid         #   else return mid
    end                     #   end
  end                       #   binary_search a, e, from, to
                            # else
  from                      #   from
                            # end
end

持续关注中

#96 楼 @luikore 没看到区别。。。虽然很工整漂亮。

数了下,大概在 48 个字符。

%W[def binary_search a e from = 0 to = () a size - 1 while to > from %mid = () from + to / 2 case a[] mid <=> e when -1 from = mid when %1 to = mid else return mid end end %from end].size # => 48

#98 楼 @mvj3 要词数少就直接调 Array#bsearch 了, 或者奇葩点:

def binary_search a, e, from=0, to=(a.size-1)
  while to > from
    mid = (from + to) / 2
    eval %w'from= return to='[(a[mid] <=> e) + 1] + ' mid'
  end
  from
end

#95 楼 @mvj3 估计是故意刁难你吧。

#99 楼 @luikore #100 楼 @blackanger

国外都怎么面试比较高级的程序员呢,比如 CoffeeScript 作者,或者人家压根就不需要被面试?就是面试失败了,能就这样完全否定人家在这领域的价值吗?还是离职位要求或公司文化还有 1% 的距离?

个人觉得从过往项目,特别是开源的,再加上博客等这些被时间洗礼的网上公开信息,只要面试官洞察力和资历够深,比如 @luikore 这样的,还需要出题面试吗?我觉得详细地探讨下期待的将来能为公司作到哪些成绩或者贡献多大价值就可以了。

#101 楼 @mvj3 基础技能是一个,但对算法要求这么高,多半是和业务相关的,他们的业务需要对算法很精通吗? 面试的时候基础技能是一个方面,主要是看你是否愿意和他一起工作,是否容易沟通,思维方式是否很另类,综合考虑吧。

#96 楼 @luikore 嗯,用尾递归版本证明方便,直接搞循环不变式反而不如递归

#102 楼 @blackanger 这个"综合考虑 “确实可以灭掉很多人。不过我确实没看出了算法要求有多高,我以为好的算法面试应该是举实际例子,并在里面应用多个算法,而且过程中还是以原理性探讨为佳。编码习惯看面试者的开源项目就可以了。

#95 楼 @mvj3 看大家还说可能这个公司对算法要求比较高。。。我上次去面试写二分,然后我问公司 “公司是对算法有要求吗?” 然后老大讲,要如何如何效率高,然后讲亚马逊如何计算什么货物送达时间,要计算很多因素,然后在多少秒内返回给你。。。听起来好像很厉害的样子。。。最后进来,还不是这样。。。大家都懂的。。。

#101 楼 @mvj3 需要啊,需要出各种难题难死他 ...

#101 楼 @mvj3 #106 楼 @bhuztez "这个家伙很有名我认识, 为什么来我们公司? 是不是脑震荡傻掉了? 考考他!" 于是掏出一本数论中未解决的问题 ...

#107 楼 @luikore 。。。,果断加入想读列表

那大牛要不介绍一下一般你怎么被别人面试的?还有你怎么面试别人的?是否会根据对方特点进行决策树的面试法?

#108 楼 @mvj3 被面试我就找人透题. 没面试过别人... 曾经面着别人变成被人面试很尴尬...

#110 楼 @bhuztez 没想过怎么找的, 总是碰巧被透露会考什么就是了...

把算法导论通刷一遍,包括习题,基本上你就是去鄙视面试官的节奏。

好的 Web 开发人员是基础跟经验均衡,各方面水平平均,学习能力强的人。 尤其是 Full Stack 的开发人员。 水桶最短板理论最适合 Web 开发人员。

花大量的时间在调查一根木板是不是合格,其他木板花不花时间问呢。。 这种人才选拔制度值得怀疑。。

就好像买车。。 只看发动机。。 是不行的,

好的发动机还需要好的变速箱,真正吧发动机的力量传输到地面的还是轮胎跟轮圈。

动力好,开的舒不舒服,还要看好多其他的东西。。。

所有都一流的名车,说到最后还要看你买得起么。。

即便是名车也有法拉利,宾利,陆虎只分。。

这些名车也不是只用发动机来横向对比的。。

115楼 已删除
116楼 已删除

每个公司都有自己的风格,有缘有份的干着才舒服. 快速傅立叶变换,有需要的无偿奉送.

def fft(a)
  n = a.size
  return a if n == 1
  w = Complex.polar(1, -2 * Math::PI / n)
  a1 = fft((0 .. n / 2 - 1).map {|i| a[i] + a[i + n / 2] })
  a2 = fft((0 .. n / 2 - 1).map {|i| (a[i] - a[i + n / 2]) * (w ** i) })
  a1.zip(a2).flatten
end

输入 [2,4,2,8,9,2,6]) 输出 -9.117449009293669+3.9091574123401482i -3+0i -2.8825509907063323-3.9091574123401482i

#108 楼 @mvj3 工作定了吗?去哪家公司了? 我的扣扣:291179688。方便的话加一下,便于联系。

#118 楼 @diguage 在一家公司用 Python 做数据分析呢,微信联系吧~

考验思维啊

觉得楼主第一个递归算法有点问题。二分查找应该有两个出口,一个是查找成功,这个出口再楼主代码中已经出现了。第二个出口是没有查找的数据,这个出口楼主没有。因为楼主代码中另一个出口是通过 array.blank?条件判断的。问题是递归过程中 array 没有变化啊。变化的只有 from 和 to。所以楼主要实现第二个出口,应该要判断 from 和 to 的关系。 楼主试试 array 中没有的数据测试试试。应该有 bug

搜索搜到这个帖子,没啥事,就试着写了下,跑通那几个用例,一共用了不到 30 分钟。

感觉挺好写的。这个算法我知道怎么回事。翻译成代码就 ok 了,ruby 又这么好写。二分法的递归也是属于比较容易的递归。写个骨架,然后再加最简单的测试用例(下面的前 4 个),之后对着用例开始微调,无外乎就是加减 1 的问题,试几次就 ok 了。再之后,就看看给的测试用例有没用问题。

递归转遍历,只要理解递归的原理,把递归维护的状态,手动维护下,就 ok 了。反正测试用例有了,测试一直跑的,开始微调。

倒是觉得测试用例挺重要的。要是让我直接用面试官给的用例,我估计就要懵逼了。

递归是基本功。可以很好的锻炼抽象和分解问题的能力。递归学东西,一大片算法可以随便撸了。

递归可以这么考,先递归实现,之后用尾递归实现,再之后用遍历实现。再问问为啥尾递归可以被优化之类的。哈哈哈哈,我承认我挺无聊的。。。

代码如下,算法相关的,就没注意命名之类的问题。

## recursive version
def binary_search_helper(arr, ele, start, end_)
  return false if start > end_
  middle = (start + end_) / 2

  middle_ele = arr[middle]

  if ele > middle_ele
    binary_search_helper(arr, ele, middle + 1, end_)
  elsif ele < middle_ele
    binary_search_helper(arr, ele, start, middle - 1)
  else
    middle
  end
end

def binary_search(arr, ele)
  end_ = arr.length

  binary_search_helper(arr, ele, 0, end_ - 1)
end

def expect(r, expected)
  unless r == expected
    puts expected
  else
    puts "Success"
  end
end

## iterative version
def binary_search_helper(arr, ele, left, right)
  return false if left > right

  while left <= right
    middle = (left + right) / 2

    middle_ele = arr[middle]

    if ele > middle_ele
      left, right = middle + 1, right
    elsif ele < middle_ele
      left, right = left, middle - 1
    else
      return middle
    end
  end
  false
end

def binary_search(arr, ele)
  length = arr.length

  binary_search_helper(arr, ele, 0, length - 1)
end

expect binary_search([0], 0), 0
expect binary_search([0], 1), false
expect binary_search([0], -1), false
expect binary_search([], 0), false

expect binary_search((1..15).to_a, 8), 7
expect binary_search((1..15).to_a, 1), 0
expect binary_search((1..15).to_a, 14), 13
expect binary_search([2,3,8,15], 8), 2
mvj3 Homebrew 作者被 Google 鄙视了… 中提及了此贴 03月28日 16:02
需要 登录 后方可回复, 如果你还没有账号请点击这里 注册