## Thursday, August 11, 2016

### Zenefits 一道面试题 | 书脊

Zenefits 一道面试题 | 书脊
A, B两个String
//example
A = XYZ;
A^2 = XXYYZZ;
A^3 = XXXYYYZZZ;

A^2 是B的subsequence, 所以
return k = 2;

A可能有重复的char, B可能有其他字符, 求k.

http://www.mitbbs.com/article_t/JobHunting/33043355.html
Test if A^k is in B takes simple O(n), as follows:

var test = function(A, k, B) {
var i = 0;
var next = A[i];
var quota = k;

for(j = 0; j < B.length; j++) {
if (B[j] == next) {
quota--;
}
if (quota == 0) {
i++;
if (i >= A.length) {
return true;
} else {
next = A[i];
quota = k;
}
}
}
return false;
};

Then apply binary search to find the largest k, as follows:

var searchK = function(A, B) {
var bot = 1;
var top = Math.floor(B.length / A.length);

while (bot < top) {
var mid = (bot + top) / 2;
if (test(A, mid, B)) {
bot = mid;
} else {
top = mid;
}
}

return test(A, top, B);
};

This take O(n*log(k)), overall.

-- don't think this works
public int findK(String a, String b) {
int[] count_a = new int[256];
int[] count_b = new int[256];
for (int i = 0; i < a.length(); i++) {
count_a[a.charAt(i)]++;
}
for (int i = 0; i < b.length(); i++) {
if (count_a[b.charAt(i)] == 0)
count_b[b.charAt(i)] --;
else
count_b[b.charAt(i)] ++;
}
StringBuffer sb_b = new StringBuffer();
for (int i = 0; i < b.length(); i++) {
if (count_b[b.charAt(i)] > 0)
sb_b.append(b.charAt(i));
}
String t_b = encode(sb_b.toString());
int min = Integer.MAX_VALUE;
for (int i = 0; i <t_b.length(); i++) {
if (t_b.charAt(i) <= '9' && t_b.charAt(i) >= '0')
min = Math.min(min, t_b.charAt(i) - '0');
}
return min;
}
public String encode(String s) {
StringBuffer sb = new StringBuffer();
for (int i = 0; i < s.length(); i++) {
int counter = 1;
while (i+1 < s.length() && s.charAt(i) == s.charAt(i+1)) {
counter++;
i++;
}
sb.append(counter);
sb.append(s.charAt(i));
}
return sb.toString();
}
public static void main(String[] args) {
String a = "XYX";
System.out.println(new Zenefits().findK(a,b));
}