技术控

    今日:122| 主题:49179
收藏本版 (1)
最新软件应用技术尽在掌握

[其他] Regular expressions to solve programming interview riddles

[复制链接]
大病猫c 发表于 2016-10-1 01:43:15
203 13

立即注册CoLaBug.com会员,免费获得投稿人的专业资料,享用更多功能,玩转个人品牌!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
Acknowledgements

   This article is a rewrite of the work of Mark Engelberg ) in his automata repository - with a tweak:
   All the code snippets of this page are live and interactive powered by the klipse plugin :
  
       
  • Live : The code is executed in your browser   
  • Interactive : You can modify the code and it is evaluated as you type  
  In his repo, Mark shows how to use regular expressions and automatas to solve programming riddles. In this article, we will focus on regular expressions.
   
Regular expressions to solve programming interview riddles-1 (interview,products,purposes,article,browser)

  Prelude

   For the purposes of this code, it is useful to replace Clojure’s max / max-key with versions that return nil when passed no inputs to maximize. Also, we are going to use clojure.combinatorics by Mark Engelberg ) for generating cartesian products of sequences:
  [code](ns my.combinatorics
  (:require [clojure.math.combinatorics :refer [cartesian-product]]))


(defn max ([] nil) ([& s] (apply clojure.core/max s)))
(defn max-key ([k] nil) ([k & s] (apply clojure.core/max-key k s)))[/code]  The classic interview problem - maximum segment sum

   A popular problem is to find an O(n) algorithm for computing the maximum sum achievable by adding up some contiguous subsequence (aka segment) of a sequence of numbers (typical input is a mix of positive and negative integers).
   For example, (maximum-segment-sum [-1 2 3 -4 5 -8 4]) should return 6 because 2+3+-4+5 is 6 .
  If you’ve never seen this problem before, I encourage you to go try to solve it right now. It’s a fun problem.
  The trick is to keep a running sum as you traverse the sequence, never letting the running sum dip below 0. This has the effect of ignoring negative numbers that make things “too negative”. Return the highest sum you saw.
  This strategy can be implemented concisely in Clojure:
  [code](defn maximum-segment-sum
  (apply max (reductions (comp #(max 0 %) +) 0 s)))[/code]   Let’s the results of the reductions with [-1 2 3 -4 5 -8 4] :
  [code](reductions (comp #(max 0 %) +) 0 [-1 2 3 -4 5 -8 4])[/code]   The max is 6 .
  A harder problem - maximum non-segment sum

   But we’re going to do something harder, we’re looking for the maximum sum among subsequences that are not a continguous segment.
   For example, (maximum-non-segment-sum [-1 4 5 -3 -4]) should be 5 because 4+5+-4 = 5 , and those three numbers don’t form a segment.
   We can’t choose just 4 , or just 5 , or 4+5 , because singletons and adjacent pairs are considered a segment. We can’t even choose the “empty” subsequence with a value of 0 , because that is also considered a segment. We could have chosen things like -1+5 or 5+-4 or 4+-3 , but they happen to be not as good.
  Unfortunately, there’s no clever trick for solving this problem. We’re going to have to look for a more principled approach.
  (If you don’t believe me, go spend a while trying to solve it, just so you can appreciate how hard this problem really is.)
  Brute force with Regular expressions

  Our strategy is going to be brute force:
  [code](defn maximum-non-segment-sum
  (->> (all-non-segment-subsequences s)
    (map (partial apply +))
    (apply max)))[/code]   But how to write all-non-segment-subsequences ?
   First key insight is that you can represent a subsequence by applying a bitmask of 0 s and 1 s to the sequence.
  [code](defn apply-bitmask
  "Takes a sequence and a bitmask, and returns the correpsonding subsequence"
    [s bitmask]
      (for [[item bit] (map vector s bitmask) :when (= bit 1)] item))[/code]  Let’s see how it works:
  [code](apply-bitmask [1 2 3 4 5] [0 1 1 0 1])[/code]  We can describe the satisfactory bitmasks with a regex
  [code](def non-segment-regex #"0*1+0+1(0|1)*")[/code]  What this regex says is that a non segment bitmask is a sequence of:
  
       
  • 0 or 0 s   
  • 1 or more 1 s   
  • 1 or more 0 s   
  • a single 1   
  • 0 s or 1 s freely  
  And indeed, this regex recognizes whether a bitmask represents a non-segment
  [code](re-matches non-segment-regex "011010" )[/code]  or not
  [code](re-matches non-segment-regex "011110")[/code]  Now, let’s make a function that receives a identifies non-segment bitmasks:
  [code](defn non-segment-bitmask?
  "Takes a sequence of 0's and 1's and determines whether this represents a subsequence that is not a contiguous segment"
      
         (not (nil? (re-matches non-segment-regex (clojure.string/join s)))))[/code]  It works as expected:
  [code](defn maximum-segment-sum
  (apply max (reductions (comp #(max 0 %) +) 0 s)))0[/code]   Now, we are ready to write our all-non-segment-subsequences : we will generate all the 0 s and 1 s sequences of the desired length and filter with non-segment-bitmask? .
   We will use the cartesian-product from clojure.combinatorics :
  [code](defn maximum-segment-sum
  (apply max (reductions (comp #(max 0 %) +) 0 s)))1[/code]   Let’s take a look at all the non-segment subsequences of [1 2 -3 4 -5] :
  [code](defn maximum-segment-sum
  (apply max (reductions (comp #(max 0 %) +) 0 s)))2[/code]   And now, all the pieces of the puzzle are in place in order to run the maximum-non-segment-sum that we wrote above:
  [code](defn maximum-segment-sum
  (apply max (reductions (comp #(max 0 %) +) 0 s)))3[/code]  [code](defn maximum-segment-sum
  (apply max (reductions (comp #(max 0 %) +) 0 s)))4[/code]  Please don’t try to run it with too long sequences!
  (On my browser it starts to take too much time with 15 elements).
  In our next article, we will show how to make our alorithm much more efficient using automatas.
   If you like this article, you will enjoy a lot Mark Engelberg’s talk on youtube about automatas .
友荐云推荐




上一篇:MechDome is a Developer Tool that Automatically Converts Android Apps into iOS a
下一篇:3D Printering: Trinamic TMC2130 Stepper Motor Drivers
酷辣虫提示酷辣虫禁止发表任何与中华人民共和国法律有抵触的内容!所有内容由用户发布,并不代表酷辣虫的观点,酷辣虫无法对用户发布内容真实性提供任何的保证,请自行验证并承担风险与后果。如您有版权、违规等问题,请通过"联系我们"或"违规举报"告知我们处理。

dds709635 发表于 2016-10-1 03:44:12
你觉得该怎么做呢?
回复 支持 反对

使用道具 举报

俊驰 发表于 2016-10-1 04:56:24
医生叫我进行光合作用,不要熬夜了。
回复 支持 反对

使用道具 举报

lkbhjh..; 发表于 2016-11-3 20:01:40
向楼主学习
回复 支持 反对

使用道具 举报

卉怀 发表于 2016-11-5 08:56:53
我抢,我抢,抢沙发,不加倍,好了,沙发是我的了!
回复 支持 反对

使用道具 举报

奈何情深缘浅 发表于 2016-11-6 10:12:46
想污染一个地方有两种方法:垃圾,或是钞票.
回复 支持 反对

使用道具 举报

nhix6919 发表于 2016-11-6 12:44:45
帮顶个帖,攒人品,说不定我就会升职加薪、当上总经理、出任CEO、迎娶白富美、走上人生巅峰,嘿嘿,想想还有点小激动。
回复 支持 反对

使用道具 举报

凡夏 发表于 2016-11-11 10:51:10
专业抢沙发的!哈哈
回复 支持 反对

使用道具 举报

时间都去哪了 发表于 2016-11-14 16:21:14
经典,收藏了!
回复 支持 反对

使用道具 举报

pdgz5965 发表于 2016-11-15 15:08:33
请你吃包辣条
回复 支持 反对

使用道具 举报

*滑动验证:
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

我要投稿

推荐阅读

扫码访问 @iTTTTT瑞翔 的微博
回页顶回复上一篇下一篇回列表手机版
手机版/CoLaBug.com ( 粤ICP备05003221号 | 文网文[2010]257号 )|网站地图 酷辣虫

© 2001-2016 Comsenz Inc. Design: Dean. DiscuzFans.

返回顶部 返回列表