ChasePay这个不要脸的偷Alipay的技术 - 未名空间MITBBS历史存档

ChasePay这个不要脸的偷Alipay的技术# Money - 海外理财

c*t2017-06-05 07:06

1 楼

上周电面遇到了一道pattern match的实现，
boolean matchPattern(String s, String q)
其中，
s: "catdogcatdogapplecatdogapple",
p(pattern): "XYXYZXYZ"
要求返回input s是否match输入的pattern p，比如以上例子，可以把X映射成cat，Y映
射成dog，apple对应Z，所以结果返回true，否则返回false。
其他限制条件有:
1) 输入都是alphabetical
2) 每个pattern对应的字符串长度大于1
面的时候完全没有切入点，感觉是得找到每个重复出现的最长prefix，存为candidate
mapping(X->cat, Y->dog, Z->apple)，然后再扫一遍原字符串进行匹配，这个思路对
么？

u*n2017-06-05 07:06

2 楼

尽然用二维码，太不要脸了

d*62017-06-05 07:06

3 楼

你要找最长prefix，第一个字符串中最长的prefix是catdog，pattern就是00101了
第二个字符串也要运行一下最长的prefix才变成00101

z*22017-06-05 07:06

4 楼

慢慢都在用了，exxon mobil加油也能app扫码支付了。

【在 u***n 的大作中提到】

: 尽然用二维码，太不要脸了

c*t2017-06-05 07:06

5 楼

有道理啊，那这道题应该用什么思路入手呢？

【在 d**********6 的大作中提到】

: 你要找最长prefix，第一个字符串中最长的prefix是catdog，pattern就是00101了
: 第二个字符串也要运行一下最长的prefix才变成00101

r*e2017-06-05 07:06

6 楼

location based service, 选个pump number就行，码都不用扫

【在 z****2 的大作中提到】

: 慢慢都在用了，exxon mobil加油也能app扫码支付了。

r*72017-06-05 07:06

7 楼

哪个公司的电面？感觉有点儿难啊
暴力解的话，就类似lc上的正则匹配，不停的backtracking
不知道能不用用后缀树数组解。

【在 c******t 的大作中提到】

: 上周电面遇到了一道pattern match的实现，
: boolean matchPattern(String s, String q)
: 其中，
: s: "catdogcatdogapplecatdogapple",
: p(pattern): "XYXYZXYZ"
: 要求返回input s是否match输入的pattern p，比如以上例子，可以把X映射成cat，Y映
: 射成dog，apple对应Z，所以结果返回true，否则返回false。
: 其他限制条件有:
: 1) 输入都是alphabetical
: 2) 每个pattern对应的字符串长度大于1

b*g2017-06-05 07:06

8 楼

DD用了很久了吧

d*62017-06-05 07:06

9 楼

这个思路不对，因为你用longest prefix压缩的话，信息就丢失可能会判断错误
比如XYXYZXYZ这个pattern可以压缩为00101
但XYXYZXYZY你一压缩的话就是001013了，最后一个y被对待成一个新的pattern
我觉得可以这样，从pattern string，也就是q入手。假设X对应的长度为L1, Y对应长
度为L2，Z为L3如此类推
先从(L1,L2,L3)=(2,2,2)开始，然后判断目标string也就是s是否符合
符合的条件比较简单，比较对应位置的元素是否相等，
比如XYX这个pattern，因为假设L1=2, L2=2，所以s里面就会出现s[0]=s[5],s[1]=s[6]
，不相等就return false
判断函数写好以后，就变成一个空间搜索问题
从(L1,L2,L3)=(2,2,2)
(3,2,2)
(3,3,2)
(3,3,3)
...
...
这个问题就可以用别的算法来优化了

【在 c******t 的大作中提到】

: 有道理啊，那这道题应该用什么思路入手呢？

d*62017-06-05 07:06

10 楼

我的这个思路要写起来比较麻烦，比较琐碎，面试期间40~50分钟不一定能写出来啊。
可能有更简单的办法

h*c2017-06-05 07:06

11 楼

哎呀，你这个题呀！
让我想起来linear diaophantine equations (show the big bulge)
还记得不？
我提醒你am+bn =c
想起来了吧！
"catdogcatdogapplecatdogapple"
XYXYZXYZ has 3X, 3Y, 2Z
Then solve linear system
3X + 3Y + 2Z = "catdogcatdogapplecatdogapple".length()
X,Y,Z is in bigz ( integer+) abelian group.

【在 c******t 的大作中提到】

: 上周电面遇到了一道pattern match的实现，
: boolean matchPattern(String s, String q)
: 其中，
: s: "catdogcatdogapplecatdogapple",
: p(pattern): "XYXYZXYZ"
: 要求返回input s是否match输入的pattern p，比如以上例子，可以把X映射成cat，Y映
: 射成dog，apple对应Z，所以结果返回true，否则返回false。
: 其他限制条件有:
: 1) 输入都是alphabetical
: 2) 每个pattern对应的字符串长度大于1

z*m2017-06-05 07:06

12 楼

这样的解有很多啊
1 1 11
1 3 8
1 5 5
1 7 2
2 2 8
2 4 5
2 6 2
3 1 8
3 3 5
3 5 2
4 2 5
4 4 2
5 1 5
5 3 2
6 2 2
7 1 2
然后一个个的试？

【在 h**********c 的大作中提到】

: 哎呀，你这个题呀！
: 让我想起来linear diaophantine equations (show the big bulge)
: 还记得不？
: 我提醒你am+bn =c
: 想起来了吧！
: "catdogcatdogapplecatdogapple"
: XYXYZXYZ has 3X, 3Y, 2Z
: Then solve linear system
: 3X + 3Y + 2Z = "catdogcatdogapplecatdogapple".length()
: X,Y,Z is in bigz ( integer+) abelian group.

S*w2017-06-05 07:06

13 楼

题目好难
dfs暴力试吧
boolean dfs(String s, String p, Map s_to_p, Map, String> p_to_s) {
if (s.isEmpty() && p.isEmpty()) return true;
if (s.isEmpty() || p.isEmpty()) return false;
for(int i = 2; i <= s.length(); ++i) {
String pre = s.substring(0, i);
if (s_to_p.containsKey(pre)) {
if (s_to_p.get(pre) == p.charAt(0) &&
dfs(s.substring(i), p.substring(1), s_to_p, p_to_s))
return true;
}
else if (p_to_s.containsKey(p.charAt(0))) {
if (p_to_s.get(p.charAt(0)) == pre &&
dfs(s.substring(i), p.substring(1), s_to_p, p_to_s))
return true;
}
else {
s_to_p.put(pre, p.charAt(0));
p_to_s.put(p.charAt(0), pre);
if (dfs(s.substring(i), p.substring(1), s_to_p, p_to_s)) return true;
s_to_p.remove(pre);
p_to_s.remove(p.charAt(0));
}
}
return false;
}
boolean solve(String s, String p) {
return dfs(s, p, new HashMap(), new HashMap, String>());
}

【在 c******t 的大作中提到】

: 上周电面遇到了一道pattern match的实现，
: boolean matchPattern(String s, String q)
: 其中，
: s: "catdogcatdogapplecatdogapple",
: p(pattern): "XYXYZXYZ"
: 要求返回input s是否match输入的pattern p，比如以上例子，可以把X映射成cat，Y映
: 射成dog，apple对应Z，所以结果返回true，否则返回false。
: 其他限制条件有:
: 1) 输入都是alphabetical
: 2) 每个pattern对应的字符串长度大于1

h*c2017-06-05 07:06

14 楼

filter XYXY first
2*X + 2*Y + 3*Z= LENGTH will have only one unkown.
maybe just try optimize it.

【在 z***m 的大作中提到】

: 这样的解有很多啊
: 1 1 11
: 1 3 8
: 1 5 5
: 1 7 2
: 2 2 8
: 2 4 5
: 2 6 2
: 3 1 8
: 3 3 5

U*A2017-06-05 07:06

15 楼

暴力法行吗？
bool matchPatternHelper(string s, int pos1, string q, int pos2, mapstring> &mp){
if(pos1 == s.length() && pos2 == q.length()){
return true;
}
else if((pos1 < s.length() && pos2 == q.length()) || (pos1 == s.
length() && pos2 < q.length())){
return false;
}

for(int i=pos1+1; istring s1 = s.substr(pos1, i-pos1+1);
if(mp.find(q[pos2]) == mp.end()){
mp.insert(make_pair(q[pos2], s1));
if(matchPatternHelper(s, i+1, q, pos2+1, mp)){
return true;
}
mp.erase(q[pos2]);
}
else{
if(mp[q[pos2]] == s1){
if(matchPatternHelper(s, i+1, q, pos2+1, mp)){
return true;
}
}
}
}
return false;
}

bool matchPattern(string s, string q){
int len1= (int)s.length();
if(len1 ==0) return false;
int len2=(int) q.length();
if(len2==0) return false;
map mp;
return matchPatternHelper(s, 0, q, 0, mp);
}

c*t2017-06-05 07:06

16 楼

上周电面遇到了一道pattern match的实现，
boolean matchPattern(String s, String q)
其中，
s: "catdogcatdogapplecatdogapple",
p(pattern): "XYXYZXYZ"
要求返回input s是否match输入的pattern p，比如以上例子，可以把X映射成cat，Y映
射成dog，apple对应Z，所以结果返回true，否则返回false。
其他限制条件有:
1) 输入都是alphabetical
2) 每个pattern对应的字符串长度大于1
面的时候完全没有切入点，感觉是得找到每个重复出现的最长prefix，存为candidate
mapping(X->cat, Y->dog, Z->apple)，然后再扫一遍原字符串进行匹配，这个思路对
么？

d*62017-06-05 07:06

17 楼

你要找最长prefix，第一个字符串中最长的prefix是catdog，pattern就是00101了
第二个字符串也要运行一下最长的prefix才变成00101

c*t2017-06-05 07:06

18 楼

有道理啊，那这道题应该用什么思路入手呢？

【在 d**********6 的大作中提到】

: 你要找最长prefix，第一个字符串中最长的prefix是catdog，pattern就是00101了
: 第二个字符串也要运行一下最长的prefix才变成00101

r*72017-06-05 07:06

19 楼

哪个公司的电面？感觉有点儿难啊
暴力解的话，就类似lc上的正则匹配，不停的backtracking
不知道能不用用后缀树数组解。

【在 c******t 的大作中提到】

: 上周电面遇到了一道pattern match的实现，
: boolean matchPattern(String s, String q)
: 其中，
: s: "catdogcatdogapplecatdogapple",
: p(pattern): "XYXYZXYZ"
: 要求返回input s是否match输入的pattern p，比如以上例子，可以把X映射成cat，Y映
: 射成dog，apple对应Z，所以结果返回true，否则返回false。
: 其他限制条件有:
: 1) 输入都是alphabetical
: 2) 每个pattern对应的字符串长度大于1

d*62017-06-05 07:06

20 楼

这个思路不对，因为你用longest prefix压缩的话，信息就丢失可能会判断错误
比如XYXYZXYZ这个pattern可以压缩为00101
但XYXYZXYZY你一压缩的话就是001013了，最后一个y被对待成一个新的pattern
我觉得可以这样，从pattern string，也就是q入手。假设X对应的长度为L1, Y对应长
度为L2，Z为L3如此类推
先从(L1,L2,L3)=(2,2,2)开始，然后判断目标string也就是s是否符合
符合的条件比较简单，比较对应位置的元素是否相等，
比如XYX这个pattern，因为假设L1=2, L2=2，所以s里面就会出现s[0]=s[5],s[1]=s[6]
，不相等就return false
判断函数写好以后，就变成一个空间搜索问题
从(L1,L2,L3)=(2,2,2)
(3,2,2)
(3,3,2)
(3,3,3)
...
...
这个问题就可以用别的算法来优化了

【在 c******t 的大作中提到】

: 有道理啊，那这道题应该用什么思路入手呢？

d*62017-06-05 07:06

21 楼

我的这个思路要写起来比较麻烦，比较琐碎，面试期间40~50分钟不一定能写出来啊。
可能有更简单的办法

h*c2017-06-05 07:06

22 楼

哎呀，你这个题呀！
让我想起来linear diaophantine equations (show the big bulge)
还记得不？
我提醒你am+bn =c
想起来了吧！
"catdogcatdogapplecatdogapple"
XYXYZXYZ has 3X, 3Y, 2Z
Then solve linear system
3X + 3Y + 2Z = "catdogcatdogapplecatdogapple".length()
X,Y,Z is in bigz ( integer+) abelian group.

【在 c******t 的大作中提到】

: 上周电面遇到了一道pattern match的实现，
: boolean matchPattern(String s, String q)
: 其中，
: s: "catdogcatdogapplecatdogapple",
: p(pattern): "XYXYZXYZ"
: 要求返回input s是否match输入的pattern p，比如以上例子，可以把X映射成cat，Y映
: 射成dog，apple对应Z，所以结果返回true，否则返回false。
: 其他限制条件有:
: 1) 输入都是alphabetical
: 2) 每个pattern对应的字符串长度大于1

z*m2017-06-05 07:06

23 楼

这样的解有很多啊
1 1 11
1 3 8
1 5 5
1 7 2
2 2 8
2 4 5
2 6 2
3 1 8
3 3 5
3 5 2
4 2 5
4 4 2
5 1 5
5 3 2
6 2 2
7 1 2
然后一个个的试？

【在 h**********c 的大作中提到】

: 哎呀，你这个题呀！
: 让我想起来linear diaophantine equations (show the big bulge)
: 还记得不？
: 我提醒你am+bn =c
: 想起来了吧！
: "catdogcatdogapplecatdogapple"
: XYXYZXYZ has 3X, 3Y, 2Z
: Then solve linear system
: 3X + 3Y + 2Z = "catdogcatdogapplecatdogapple".length()
: X,Y,Z is in bigz ( integer+) abelian group.

S*w2017-06-05 07:06

24 楼

题目好难
dfs暴力试吧
boolean dfs(String s, String p, Map s_to_p, Map, String> p_to_s) {
if (s.isEmpty() && p.isEmpty()) return true;
if (s.isEmpty() || p.isEmpty()) return false;
for(int i = 2; i <= s.length(); ++i) {
String pre = s.substring(0, i);
if (s_to_p.containsKey(pre)) {
if (s_to_p.get(pre) == p.charAt(0) &&
dfs(s.substring(i), p.substring(1), s_to_p, p_to_s))
return true;
}
else if (p_to_s.containsKey(p.charAt(0))) {
if (p_to_s.get(p.charAt(0)) == pre &&
dfs(s.substring(i), p.substring(1), s_to_p, p_to_s))
return true;
}
else {
s_to_p.put(pre, p.charAt(0));
p_to_s.put(p.charAt(0), pre);
if (dfs(s.substring(i), p.substring(1), s_to_p, p_to_s)) return true;
s_to_p.remove(pre);
p_to_s.remove(p.charAt(0));
}
}
return false;
}
boolean solve(String s, String p) {
return dfs(s, p, new HashMap(), new HashMap, String>());
}

【在 c******t 的大作中提到】

: 上周电面遇到了一道pattern match的实现，
: boolean matchPattern(String s, String q)
: 其中，
: s: "catdogcatdogapplecatdogapple",
: p(pattern): "XYXYZXYZ"
: 要求返回input s是否match输入的pattern p，比如以上例子，可以把X映射成cat，Y映
: 射成dog，apple对应Z，所以结果返回true，否则返回false。
: 其他限制条件有:
: 1) 输入都是alphabetical
: 2) 每个pattern对应的字符串长度大于1

h*c2017-06-05 07:06

25 楼

filter XYXY first
2*X + 2*Y + 3*Z= LENGTH will have only one unkown.
maybe just try optimize it.

【在 z***m 的大作中提到】

: 这样的解有很多啊
: 1 1 11
: 1 3 8
: 1 5 5
: 1 7 2
: 2 2 8
: 2 4 5
: 2 6 2
: 3 1 8
: 3 3 5

U*A2017-06-05 07:06

26 楼

暴力法行吗？
bool matchPatternHelper(string s, int pos1, string q, int pos2, mapstring> &mp){
if(pos1 == s.length() && pos2 == q.length()){
return true;
}
else if((pos1 < s.length() && pos2 == q.length()) || (pos1 == s.
length() && pos2 < q.length())){
return false;
}

for(int i=pos1+1; istring s1 = s.substr(pos1, i-pos1+1);
if(mp.find(q[pos2]) == mp.end()){
mp.insert(make_pair(q[pos2], s1));
if(matchPatternHelper(s, i+1, q, pos2+1, mp)){
return true;
}
mp.erase(q[pos2]);
}
else{
if(mp[q[pos2]] == s1){
if(matchPatternHelper(s, i+1, q, pos2+1, mp)){
return true;
}
}
}
}
return false;
}

bool matchPattern(string s, string q){
int len1= (int)s.length();
if(len1 ==0) return false;
int len2=(int) q.length();
if(len2==0) return false;
map mp;
return matchPatternHelper(s, 0, q, 0, mp);
}

t*52017-06-05 07:06

27 楼

mark 这个暴力解法，暂时想不到更好的

Character

【在 S***w 的大作中提到】

: 题目好难
: dfs暴力试吧
: boolean dfs(String s, String p, Map s_to_p, Map: , String> p_to_s) {
: if (s.isEmpty() && p.isEmpty()) return true;
: if (s.isEmpty() || p.isEmpty()) return false;
: for(int i = 2; i <= s.length(); ++i) {
: String pre = s.substring(0, i);
: if (s_to_p.containsKey(pre)) {
: if (s_to_p.get(pre) == p.charAt(0) &&

x*92017-06-05 07:06

28 楼

[email protected]
如果pattern少的话，就枚举XYZ的长度，顺序验证一下就好了。。。
我觉得这个最起码是一个60分的答案

x*92017-06-05 07:06

29 楼

想了半天，还是没有好方法。。。
如果是在OJ上的话，pattern < 5, strlen < 500，这题我就敢枚举每个pattern长度来
暴力搞
如果数据规模更大的话，可能会更难

F*n2017-06-05 07:06

30 楼

dfs
First match abb with Len(a)>1 Len(b) > 2
If true check if b = az

【在 c******t 的大作中提到】

: 上周电面遇到了一道pattern match的实现，
: boolean matchPattern(String s, String q)
: 其中，
: s: "catdogcatdogapplecatdogapple",
: p(pattern): "XYXYZXYZ"
: 要求返回input s是否match输入的pattern p，比如以上例子，可以把X映射成cat，Y映
: 射成dog，apple对应Z，所以结果返回true，否则返回false。
: 其他限制条件有:
: 1) 输入都是alphabetical
: 2) 每个pattern对应的字符串长度大于1

s*u2017-06-05 07:06

31 楼

Mark this interesting problem.

w*k2017-06-05 07:06

32 楼

Mark

x*12017-06-05 07:06

33 楼

mark

【在 F****n 的大作中提到】

: dfs
: First match abb with Len(a)>1 Len(b) > 2
: If true check if b = az

j*02017-06-05 07:06

34 楼

https://leetcode.com/problems/word-pattern-ii/

h*n2017-06-05 07:06

35 楼

大爷的这个题用来做电面? 哪个面试官这么变态故意黑你吧

【在 c******t 的大作中提到】

: 上周电面遇到了一道pattern match的实现，
: boolean matchPattern(String s, String q)
: 其中，
: s: "catdogcatdogapplecatdogapple",
: p(pattern): "XYXYZXYZ"
: 要求返回input s是否match输入的pattern p，比如以上例子，可以把X映射成cat，Y映
: 射成dog，apple对应Z，所以结果返回true，否则返回false。
: 其他限制条件有:
: 1) 输入都是alphabetical
: 2) 每个pattern对应的字符串长度大于1