讨论两个面经题

两个面经题：

1. 描述：给一个目标字符串，从一个段text里面找到，并且返回index。follow up - 目标字符串可以允许通配符*，代表0或者多个任意字符。比如"*A", 从文档“CDFGAGB”，返回0。比如"A**B"，返回4。用递归很好解。

我其实没理解这个题为什么要用递归呢

按照lz的例子是匹配substring即可（比如A*CD 并不一定要text最后是CD，可以是BAXCDY），所以可以按照*把每个部分分割开，比如A*CD*EF
那么就按照strstr在text里先找到A，然后剩下的text里找到第一个CD，剩下的再找第一个EF，是可以greedy做的 吧

2. 描述：给一个target 比如T3, 还有 T1 = 2, T2 = 3, T3 = T4 + T5, T4 = T1 - T2, T5 = T4 + T1, 计算出 T3 = 0, 我的解法是build mappings from T3 -> T4 + T5, T4 -> T1 - T2, T5 = T4 + T1, 然后用recursion计算。

我的理解是 如果说给定的计算式如果和递归的顺序一样，这样是可以做的。但如果变化一下 比如 T4 = T3 - T5，那大家会选择怎么做呢？好像在建graph的时候，需要把这个计算式转换成 T3 = T4 + T5, T5 = T3 - T4， 然后作为edge放进去？有什么更好的方法么，比如适用于任何多元一次方程的，比如 T3 = T4 + T5 - T1 - T2....

itaymaoz 发表于 2021-03-25 16:16:26
KMP就不必了，像KMP，manacher，还有什么高级图论算法， 面试官都不一定会写的，不会考的

robinkarp很简单 没必要kmp

补充内容 (2021-03-26 07:25 +08:00):
具体这个题面试的时候strstr用library就行了

第一题可以用递归也可以用dp，第二题就是建图，也可以用递归做，搞一个memo存T#的value，避免重复计算，如果 T4 = recur(T3) + recur(T2) 之类的

I cam up with the below. Not sure if this covers all the use cases. Rice if this helps

1. public void run() {
   
2.         String text = "CDFGAGB";
   
3.         String pattern = "*A*";
   
4.         System.out.println(patternMatch(text, pattern));
   
5.     }
   
6.    
   
7.     public int patternMatch(String s, String pattern) {
   
8.         String[] patternList = pattern.split("\\*");
   
9.         
   
10.         //for (int i = 0; i < patternList.length; i++) {
    
11.             System.out.println(patternList.length);
    
12.         //}
    
13.         
    
14.         if (patternList.length == 0) return 0;
    
15.         if(patternMatch(s, patternList, 0))
    
16.             return getIndex(s, patternList[0]);
    
17.         else return -1;
    
18.             
    
19.     }
    
20.    
    
21.     public boolean patternMatch(String s, String[] pattern, int index) {
    
22.         while (index < pattern.length && pattern[index] == "") index++;
    
23.         if (index == pattern.length) return true;
    
24.         
    
25.         int patIndex = getIndex(s, pattern[index]);
    
26.         
    
27.         if (patIndex == -1) return false;
    
28.         
    
29.         if (index == pattern.length-1) return true;
    
30.         if (patIndex+pattern[index].length() >= s.length()) return false;
    
31.         
    
32.         return patternMatch(s.substring(patIndex+pattern[index].length()), pattern, index+1);
    
33.     }
    
34.    
    
35.     public int getIndex(String s, String pattern) {
    
36.         int m = s.length();
    
37.         int n = pattern.length();
    
38.         
    
39.         for (int i = 0; i <= m-n; i++) {
    
40.             boolean notMatch = false;
    
41.             for (int j = 0; j < n; j++) {
    
42.                 if (s.charAt(i+j) != pattern.charAt(j)) {
    
43.                     notMatch = true;
    
44.                     break;
    
45.                 }
    
46.             }
    
47.             if (!notMatch) return i;
    
48.         }
    
49.         
    
50.         return -1;
    
51.     }

复制代码

1. Leetcode 44. 一题超过一个解法是很正常的事，另外你说的递归该不会是指 DP 吧？
2. 解线性方程组的经典算法是高斯消元法。

usr_opta 发表于 2021-1-26 10:28
1. Leetcode 44. 一题超过一个解法是很正常的事，另外你说的递归该不会是指 DP 吧？
2. 解线性方程组的经 ...

这题不是44 因为不是match整个string， 递归是因为之前有人说来着。

我只是觉得对方应该不想要高斯消元，我后来通过parse string建graph做了一下 好像也可行

第一个我觉得greedy是更好的解法啊。第二个的话，感觉常规是高斯消元。

第二个问题所给的一组表达式可以理解为某种简单的领域专有语言，然后要求写一个该语言的执行引擎求出结果。

而这组表达式之所以语义上可以有不同的理解（比如楼主提到的能不能对等号左右移项），关键在于等号"="的语义是什么，主要有三种：

(1) "赋值" (assignment)，对应于过程式语言的操作语义。

可以理解为写一个极简版的Python/R/...的解释器来执行

1. T1 = 1
   
2. T2 = 2
   
3. T4 = T2 - T1

复制代码

这样的代码

那么实现方式主要就是维护一个符号表从变量名映射到具体的值，然后对于每个表达式 <var> = <expr>，先从符号表中查找已有的变量值以计算<expr>，再在符号表中更新<var>到结果值的映射。

(2) "定义" (definition)，对应于函数式语言的指称语义。

可以理解为如下的Python代码：

1. def T1():
   
2.     return 1
   
3. 
   
4. def T2():
   
5.     return 2
   
6. 
   
7. def T4():
   
8.     return T2() - T1()
   

复制代码

(2)在执行上与(1)最重要的区别就是惰性求值（lazy evaluation），这使得表达式可以“乱序”，比如在T1和T2还没有定义的情况下就定义T4 = T2 - T1，那么我们此时将T4映射到其计算过程（code as first-class citizen）而不是立即就需要最终结果。

对于(2)，如果要写代码的话，简单一点的处理是将变量名映射到类似于std::variant<int64, string>这样的混合数据结构，如果是int64那么就是已经算了结果，如果是string那么就是还未计算的表达式。

而工程上的经典方法是先将表达式解析（parse + resolve）成一种宿主语言下的中间表示（IR, intermediate representation）—— IR可以是byte code，例如Python；也可以是一种functional的data structure（例如R和各种SQL引擎），如下面的例子所示：

1. class Expression {
   
2.   // 如果需要的话可以写个cachedEval方法做memoization
   
3.   public abstract long eval();
   
4. }
   
5. 
   
6. // 每个表达式实现eval方法以进行具体的计算
   
7. class LiteralExpression {
   
8.   private long value;
   
9.   public LiteralExpression(long value) { this.value = value; }
   
10. 
    
11.   @Override
    
12.   public long eval() { return value; }
    
13. }
    
14. 
    
15. class AddExpression {
    
16.   private Expression left;
    
17.   private Expression right;
    
18.   public AddExpression(Expression left, Expression right) {
    
19.     this.left = left;
    
20.     this.right = right;
    
21.   }
    
22. 
    
23.   @Override
    
24.   public long eval() { return left.eval() + right.eval(); }
    
25. }
    
26. 
    
27. // class SubtractExpression
    
28. // class MultiplyExpression
    
29. // ...

复制代码

然后写一个解析器将"T1 = 1", "T4 = T2 - T1"这样文本代码转化为Expression并且link起来，全部解析完成后调用eval()即可。

(3) 数学意义上的"等于" (equality)，比如说逻辑式语言Prolog及其变体SQL，以及各种数学领域的领域专有语言。

(3)本质上就是解方程组，那么基本上是具体问题具体分析，比如高斯消元法解多元一次方程，relational algebra解SQL方程，再比如Mathematica的DSolve可以解微分方程也是靠内置了各种特殊解法去一个个匹配的。

我猜楼主对于(3)的一个疑问大概是有没有类似于(1)/(2)那样看起来“通用”的方法（而不是“高斯消元”这种一听就非常特殊的专用于某个domain的方法）来处理方程类问题？应该是没有，甚至只要方程涉及的domain稍微复杂一点（也就是不局限于加减乘除）就可能in general变成不可计算问题只能找数值解/部分解..

Smilenceyu 发表于 2021-1-26 11:34
这题不是44 因为不是match整个string， 递归是因为之前有人说来着。

我只是觉得对方应该不想要高斯消 ...

刷题不能死板，我只要把44的pattern前后各加一个星号就变成你的问题了。

usr_opta 发表于 2021-1-26 14:49
刷题不能死板，我只要把44的pattern前后各加一个星号就变成你的问题了。

对啊 但是44 更复杂。你的说法就好像是要求最大值，你把整个sort了 然后取最后一个。但杀鸡用牛刀了。

楼主第二题有思路么？

usr_opta 发表于 2021-1-26 14:49
刷题不能死板，我只要把44的pattern前后各加一个星号就变成你的问题了。

我感觉只有刷穿了才能有这样的高屋建瓴