## Interview Question for SDE-2s

Country: United States

Comment hidden because of low score. Click to expand.
1
of 1 vote

the answer is to use boyer-moore or KMP, which ar eboth O(n) algorithms. I'd probably study boyer-moore since it's easier to implement if some crazy interviewer actually wants you to implement an O(n) substring matching.

Comment hidden because of low score. Click to expand.
0

Here's a KMP implementation:

``````public static boolean isIn(String str1, String str2){
char[] arr1 = str1.getChars();
char[] arr2 = str2.getChars();
//compute table for str2:
int[] t = computeTable(arr2);

int arr1Index = 0, arr2Index = 0;
while(arr1Index + arr2Index < arr1.length){
if(arr1[arr1Index + arr2Index] == arr2[arr2Index]){
arr2Index++;
if(arr2Index == arr2.length){
return true;
}
}
else{
if(t[arr2Index] > -1){
arr1Index += (arr2Index - t[arr2Index]);
arr2Index = t[arr2Index];
}
else{
arr1Index++;
arr2Index = 0;
}
}
}
return false;
}

private static int[] computeTable(char[] arr){
int[] table = new int[arr.length];
int i = 1; m = 0;
table[0] = -1;
while(i < arr.length){
if(arr[i] == arr[m]){
table[i] = m;
m++;
i++;
}
else if (m > 0){
m = t[m];
else {
table[i] = 0;
i++;
}
}
return table;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Objective C solution

``````NSString *stringOne = @"aaaaaabbb";
NSString *stringTwo = @"aaaaaabbbbbbb";
BOOL containsString = NO;
if (stringOne.length>stringTwo.length) {
//NSLog(@"Contains Substring: %d",[stringOne containsString:stringTwo]);
for (int i = 0; i<=(stringOne.length-stringTwo.length); i++) {
NSRange mainRange = NSMakeRange(i, stringTwo.length);
NSString *subString = [stringOne substringWithRange:mainRange];
if ([subString isEqualToString:stringTwo]) {
containsString = YES;
break;
}
}
NSLog(@"%@",containsString?@"Contains String":@"Does not contain String");
}else{
//NSLog(@"Contains Substring: %d",[stringTwo containsString:stringOne]);
for (int i = 0; i<=(stringTwo.length-stringOne.length); i++) {
NSRange mainRange = NSMakeRange(i, stringOne.length);
NSString *subString = [stringTwo substringWithRange:mainRange];
if ([subString isEqualToString:stringOne]) {
containsString = YES;
break;
}
}
NSLog(@"%@",containsString?@"Contains String":@"Does not contain String");
}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

``````def SS(str1, str2):
if(len(str1)>len(str2)):
return False

for i in range(len(str2)-len(str1)+1):
found = True
for j in range(len(str1)):
if(str2[i+j]!=str1[j]):
found = False
break
if (found):
return True
return False

A = 'aaaaaabbb'
B = 'aaaabbb'
print SS(A,B) or SS(B,A)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

not sure if would be ok to use charAt(), if not convert the two string to arrays won't change much in the actual implementation but it would affect time.

``````private static boolean evaluate(String stringOne, String stringTwo) {
for(int i=0; i<stringOne.length(); i++){
int startIndex = i, counter = 0;
for(int j=0;j<stringTwo.length(); j++){
if(stringOne.charAt(startIndex) == stringTwo.charAt(j)){
startIndex++;
counter++;
}
if(counter == 2){
return true;
}
}
}
return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public boolean strstr (String src, String target){
if (src.length() < target.length()) return strstr(target,src);
for (int i = 0 ; src.length() - i >= target.length() ; ++i) {
int j = 0 ;
int k = i ;
while (j < target.length() && src.charAt(k) == target.charAt(j)) {
k++;
j++;
}
if (j == target.length()) return true ;
}
return false;``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def is_sub(txt, txt2):
uno, dos = set(txt), set(txt2)
return uno.issuperset(dos) or dos.issuperset(uno)

print(is_sub('aaaaaabbb', 'aaabbb'))  # True
print(is_sub('asdasdf', 'cxvbxcvb'))  # False``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

class SubstringPresent{
private String largerString = "aaabcdedfd";
private String smallerString = "cdf";

public boolean isSubString(String largerString, String smallerString){
int temp=0;
for(int k = 0; k < largerString.length(); k++){
if(largerString.charAt(k)==smallerString.charAt(temp)){
temp = k;
break;
}
}

int temp_1 = 0;
for(int m = temp; m<largerString.length(); m++){
if(largerString.charAt(m)!=smallerString.charAt(temp_1))
return false;
temp_1++;
if(temp_1 == smallerString.length()){
return true;
}
}

return false;
}

public static void main(String[] args){
SubstringPresent test = new SubstringPresent();
System.out.println(test.isSubString(test.largerString, test.smallerString));
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

class SubstringPresent{
private String largerString = "aaabcdedfd";
private String smallerString = "cdf";

public boolean isSubString(String largerString, String smallerString){
int temp=0;
for(int k = 0; k < largerString.length(); k++){
if(largerString.charAt(k)==smallerString.charAt(temp)){
temp = k;
break;
}
}

int temp_1 = 0;
for(int m = temp; m<largerString.length(); m++){
if(largerString.charAt(m)!=smallerString.charAt(temp_1))
return false;
temp_1++;
if(temp_1 == smallerString.length()){
return true;
}
}

return false;
}

public static void main(String[] args){
SubstringPresent test = new SubstringPresent();
System.out.println(test.isSubString(test.largerString, test.smallerString));
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

class SubstringPresent{
private String largerString = "aaabcdedfd";
private String smallerString = "cdf";

public boolean isSubString(String largerString, String smallerString){
int temp=0;
for(int k = 0; k < largerString.length(); k++){
if(largerString.charAt(k)==smallerString.charAt(temp)){
temp = k;
break;
}
}
int temp_1 = 0;
for(int m = temp; m<largerString.length(); m++){
if(largerString.charAt(m)!=smallerString.charAt(temp_1))
return false;
temp_1++;
if(temp_1 == smallerString.length()){
return true;
}
}
return false;
}
public static void main(String[] args){
SubstringPresent test = new SubstringPresent();
System.out.println(test.isSubString(test.largerString, test.smallerString));
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````class SubstringPresent{
private String largerString = "aaabcdedfd";
private String smallerString = "cdf";
public boolean isSubString(String largerString, String smallerString){
int temp=0;
for(int k = 0; k < largerString.length(); k++){
if(largerString.charAt(k)==smallerString.charAt(temp)){
temp = k;
break;
}
}
int temp_1 = 0;
for(int m = temp; m<largerString.length(); m++){
if(largerString.charAt(m)!=smallerString.charAt(temp_1))
return false;
temp_1++;
if(temp_1 == smallerString.length()){
return true;
}
}
return false;
}
public static void main(String[] args){
SubstringPresent test = new SubstringPresent();
System.out.println(test.isSubString(test.largerString, test.smallerString));
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public boolean strstr (String src, String target){
if (src.length() < target.length()) return strstr(target,src);
for (int i = 0 ; src.length() - i >= target.length() ; ++i) {
int j = 0 ;
while (j < target.length() && src.charAt(i + j) == target.charAt(j)) j++;
if (j == target.length()) return true ;
}
return false;``````

}

Comment hidden because of low score. Click to expand.
-1
of 3 vote

In Java

``````//aaaabbb aaaaaabbb
//Checking if s1 is a substring of s2 (s1 < s2)
// O(n) - letters in the larger string
public boolean isSubstring(String smallerString, String largerString){
for(int i = 0; i < largerString.length(); ++i){
int endIndex = i + smallerString.length();
if(endIndex > largerString.length())
break;
if(largerString.substring(i, endIndex).equals(smallerString))
return true;
}
return false;
}

public boolean checkSubstring(String s1, String s2){
if(s1.length() < s2.length())
return isSubstring(s1, s2);
//s2 >= s1
return isSubstring(s2, s1);
}
}``````

Comment hidden because of low score. Click to expand.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.