无线院2018上半年技术教练认证-专业能力测评

红太狼 2021-11-17 23:44 213阅读 0赞

## 提交代码到：[挑战代码提交地址][Link 1] ##

以8位工号作为代码库名称(**注：2018（上）认证已经完成，题目仅供大家练习、挑战**)

## 初赛题目(线下编码)： ##

实现指定规则的字符串大小比较功能：  
两个字符串（字符串1、字符串2）的大小比较，字符串只可能含有如下字符

1.  字母：a～z|A~Z
2.  数字：0～9
3.  转义符：\\

比较规则如下：

1.  从左到右分离单纯的子字母串（均为字母）和子数字串（均为数字）进行比较；
2.  如果一边已无子串（子字母串或子数字串），另外一方还有子串，则无子串的小；如果双方均无子串，则相等
3.  如果被比较的一边是子数字串，一边是子字母串，则子数字串小；
4.  如果被比较的都是子字母串，则按C库strcmp的规则比较子字母串大小；
5.  如果被比较的都是子数字串，则按数值比较规则比较大小，如果值相等，则子数字串短的一方小；
6.  如果当前子串相等，才需要比较下一个子串；
7.  支持转义符\\，对后面的1至3个（尽可能多的匹配）数字作字母处理，\\当做不存在，比如，abc\\123，作为子字母串abc123;
8.  支持转义符\\，对后面的1个字母，按其ascii码作为数字处理，数字长度算为1，\\当做不存在，比如1\\A\\A，值为`1*100+65*10+65`，长度为3；
9.  转义符\\后只能跟字母或数字；

举例：  
按照上述字符串大小比较规则，对如下字符串组进行递增排序时：B1，B11，B01，B2：输出应该是B1，B01，B2，B11；

附加限制：

1.  不能用递归
2.  使用TDD开发，同步提交表达清晰的用例
3.  开发语言：`c/c++、java、python、scala`，不能使用正则表达式库，不能使用三方库（测试框架例外）
4.  提供源码、用例，另外需提供完整可执行文件包，其中入口可执行文件给定两个字符串s1,s2，输出1,0,-1，分别`s1>s2、s1=s2、s1<s2`，非法字符返回-2

测评用例

基本用例：
    abc,abc,0
    Abc,abc,-1
    abc,aBc,1
    abc,abcd,-1
    abcd,abc,1
    123,123,0
    1234,123,1
    508,123,1
    121,123,-1
    12,012,-1
    00900,0900,1
    0018,0018,0
    ab123,ab,1
    ab,ab10,-1
    ab49,ab49,0
    98ce,98ce,0
    98,98ff,-1
    98fe,98,1
    gc0c,gc0c,0
    gc0f,gc0g,-1
    000h,00h,1
    abc\123,abc\123,0
    abc\123,abc\234,-1
    abc\82,abc\8,1
    abc\28,abc\8,-1
    abc\1234,abc\1235,-1
    ab0\a,ab97,0
    dc9\a\a,dc1967,-1
    123\A\888\B456,1295\888\B456,0
    abcd,a;b,-2
    :ad,f,-2
    \-,x,-2
    \\x,x,-2
    
    进阶用例：
    4294967\A295bb,4294967\A295aa,1

## 复赛题目（线上编码） ##

不使用语言自身提供的正则表达式的库，实现一套基于如下语法定义的正则表达式库，包括代码和测试用例，语言选择各自领域主开发语言

<table> 
 <thead> 
  <tr> 
   <th>语法</th> 
   <th>对应的API</th> 
   <th>语言示例</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>字串字面值</td> 
   <td>lit(x)</td> 
   <td>lit(‘abc’)定义的语言只包含{‘abc’}</td> 
  </tr> 
  <tr> 
   <td>seq</td> 
   <td>seq(x,y)</td> 
   <td>seq(lit(‘a’), lit(‘b’))定义的语言只包含{‘ab’}</td> 
  </tr> 
  <tr> 
   <td>*</td> 
   <td>star(x)</td> 
   <td>star(lit(‘a’))包含{‘’, ‘a’, …}</td> 
  </tr> 
  <tr> 
   <td>+</td> 
   <td>plus(x)</td> 
   <td>plus(lit(‘a’))包含{‘a’,…}</td> 
  </tr> 
  <tr> 
   <td>alt（二选一）</td> 
   <td>alt(x, y)</td> 
   <td>alt(lit(‘a’), lit(‘b’))包含{‘a’, ‘b’}</td> 
  </tr> 
  <tr> 
   <td>eol（end of line）</td> 
   <td>eol</td> 
   <td>eol只能匹配空字符串{‘’}且只能在字符串末尾</td> 
  </tr> 
  <tr> 
   <td>.（any character）</td> 
   <td>dot</td> 
   <td>dot: {任意字符}</td> 
  </tr> 
  <tr> 
   <td>oneof</td> 
   <td>oneof(x)</td> 
   <td>oneof(‘afe’)包含{‘a’, ‘f’, ‘e’}，其中oneof只接受字符串</td> 
  </tr> 
 </tbody> 
</table>

### 需求一： ###

基于上述语法，实现search接口，search接受两个参数，一个是pattern（也就是语法），一个是待测文本。  
返回待测文本中最早匹配语法的结果字串，如果在同一个位置有多种匹配，返回最长的那个匹配（即“贪婪”匹配）。如果没有找到合适的匹配，返回为空

示例（仅表达意思，非接口形态）:

1.  `r = search(lit('def'), 'abcdef')`
2.  `r = 'def'`

### 需求二： ###

实现match接口，接受和search同样的参数，和search的区别在于：match的匹配只能从待测文本的起始开始，贪婪匹配。比如字符串“abcdef”如果用search匹配”def”,则返回”def”，如果用match匹配的话就返回空

示例（仅表达意思，非接口形态）:

1.  `r = match(lit('abc'), 'abcdef')`
2.  `r = 'abc'`

### 需求三： ###

实现findall接口，接受两个参数，一个是pattern（也就是语法），一个是待测文本。返回待测文本中所有匹配语法的结果子串，贪婪匹配  
示例（仅表达意思，非接口形态）:

1.  `r = findall(plus('def'), 'defabdefdef')`
2.  `r[0] = 'def'`
3.  `r[1] = 'defdef'`

### 需求四： ###

实现split接口，接受两个参数，一个是pattern（也就是语法），一个是待测文本。返回待测文本中按pattern分割后的结果字串，贪婪匹配  
示例（仅表达意思，非接口形态）:

1.  `r = split(lit('e'), 'defdef')`
2.  `r[0] = 'd'`
3.  `r[1] = 'fd'`
4.  `r[2] = 'f'`

### 附加题一： ###

实现group语法，能提取匹配的子序列，使用贪婪匹配，0为匹配的全序列，1…N为子序列

<table> 
 <thead> 
  <tr> 
   <th>语法</th> 
   <th>对应的API</th> 
   <th>语言示例</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>group</td> 
   <td>group(x)</td> 
   <td>group(lit(‘abc’)) 能取出匹配的子序列{‘abc’}</td> 
  </tr> 
 </tbody> 
</table>

示例（仅表达意思，非接口形态）:

1.  `r = match(seq(lit('def'), group(lit('abc'))), 'defabc')`
2.  `r[0] = 'defabc'`
3.  `r[1] = 'abc'`

### 附加题二： ###

实现ungreedy语法，使用非贪婪匹配

<table> 
 <thead> 
  <tr> 
   <th>语法</th> 
   <th>对应的API</th> 
   <th>语言示例</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>?</td> 
   <td>ungreedy(x)</td> 
   <td>ungreedy(star(‘abc’)) 能取出匹配的子序列{‘abc’}</td> 
  </tr> 
 </tbody> 
</table>

示例（仅表达意思，非接口形态）:

1.  `r = match(seq(lit('def'), group(ungreedy(plus(lit('a'))))), 'defaaa')`
2.  `r[0] = 'defa'`
3.  `r[1] = 'a'`

[Link 1]: http://gitlab.zte.com.cn/coach-auth/2018-challenge