Yahoo Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
The Goal is to find the value of n here
private void isS2SubstringOfS3(String s1, String s2){
int n = (int)Math.ceil(((double)s2.length() -1) % s1.length()) + 1;
String s3 = formString(s1, n);
return s3.contains(s2); // use KMP String match here
}
private String formString(String s1, int n){
StringBuilder sb = new StringBuilder();
while(n > 0){
sb.append(s1);
--n;
}
return sb.toString();
}
Solution in JS
function run() {
let s1 = 'aabc';
let s2 = 'bcaab';
let maxCycle = 4;
let matchStarted = false;
for (i = 0; i < s2.length; i++) {
j = 0;
while (j < s1.length) {
if (s1[j] == s2[i]) {
j++; i++;
matchStarted = true;
} else {
if(matchStarted){
i=0;
matchStarted = false;
}
j++;
}
if (i == s2.length) {
console.log('Matching !');
return;
}
if (j == s1.length) {
j = 0;
if (maxCycle < 0) {
console.log('its too much - give up !');
return;
}
maxCycle--;
}
}
}
}
a not wonky solution. O(L1 * L2) in the worst possible case (s1 = "aaaab", s2 = "ab").
static boolean isSub(String s1, String s2) {
if (s2.isEmpty()) return true;
for (int i = 0; i < s1.length(); i++) {
for (int j = 0; j < s2.length(); j++) {
int s1I = (i + j) % s1.length();
if (s1.charAt(s1I) != s2.charAt(j)) {
break;
} else if (j == s2.length() - 1) {
return true;
}
}
}
return false;
}
Looking for interview experience sharing and coaching?
Visit AONECODE.COM for ONE-ON-ONE private lessons by FB, Google and Uber engineers!
SYSTEM DESIGN
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algorithms, Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Get hired from G, U, FB, Amazon, LinkedIn, Yahoo and other top-tier companies after weeks of training.
Email us aonecoding@gmail.com with any questions. Thanks!
SOLUTION:
- aonecoding May 28, 2018